把会的题放一起吧，不然字数太少了。

A. 论如何出一道水题

Description

给定 n，求一对整数 (i,j)，在满足 1 ≤ i ≤ j ≤ n 且 \gcd(i,j)=1gcd(i,j)=1 的前提下，要求最大化 i+j 的值

Solution

打表，然后找到规律

Code

#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

const int mod = 100000000;
const int N = 5e5 + 5;
typedef long long ll;
const double pi = acos(-1.0);
const double EPS=1e-8;


int main() {
  ll n;
  while(cin >> n) {
    if(n == 1) {
      cout << 2 << "\n";
    } else {
      cout << 2 * n - 1 << "\n";
    }
    // ll ans = -1;
    // for(int i = 1; i <= n; i++) {
    //   for(int j = 1; j <= n; j++) {
    //     if(__gcd(i, j) == 1) {
    //       ans = max(ans, 1LL * (i + j));
    //     }
    //   }
    // }
    // cout << ans << "\n";
  }
  return 0;
}

B. 暴力出奇迹

Description

给定一个序列，寻找一对l,r，满足1 ≤ l ≤ r ≤ n

Solution

一开始看错题，以为是要最大化区间与的值, 不过照着这个思路，对于每一个二进制位，我们以当前点为右端点，找连续的该位为1的段的最左端点，按左端点排序，从左到右取贡献。

Code

#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

const int mod = 100000000;
const int N = 1e5 + 5;
typedef long long ll;
const double pi = acos(-1.0);
const double EPS=1e-8;

ll dp[N][32], sum[N], a[N];
struct node {
  int l, val;
  node(int _l = 0, int _val = 0): l(_l), val(_val){}
  bool operator < (const node &s) const {
    return l < s.l;
  }
};
int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j < 32; j++) {
      dp[i][j] = 0;
      if(a[i] & (1LL << j)) {
        dp[i][j] = dp[i - 1][j] + 1;
      }
    }
  }
  ll ans = 0;
  for(int i = 1; i <= n; i++) {
    vector<node> v(50);
    for(int j = 0; j < 32; j++) {
      ll p = (1LL << j);
      v[j] = node(i - dp[i][j], p);
    }
    sort(v.begin(), v.end());
    ll now = 0;
    for(int j = 0; j < 32; j++) {
      now ^= v[j].val;
      ans = max(ans, 1LL * now * (sum[i] - sum[v[j].l]));
    }
  }
  cout << ans << "\n";
  return 0;
}

E. 跳石头

Description

一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。

Description

看了一堆人过，就知道是水题，求最大最小值，简单思路就是二分，二分答案，发现相邻距离比答案小，就要去掉石头。

Code

#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

const int mod = 100000000;
const int N = 1e5 + 5;
typedef long long ll;
const double pi = acos(-1.0);
const double EPS=1e-8;

int a[N];
int l, n, m;
bool check(int x) {
  int res = 0;
  int now = 0;
  for(int i = 1; i <= n; i++) {
    if(a[i] - now < x) {
      res++;
    } else {
      now = a[i];
    }
  }
  return res <= m;
}
int main() {
  cin >> l >> n >> m;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int left = 1, right = l;
  a[n + 1] = l;
  n++;
  int ans = -1;
  while(left <= right) {
    int mid = left + right >> 1;
    if(check(mid)) {
      left = mid + 1;
      ans = mid;
    } else {
      right = mid - 1;
    }
  }
  cout << ans << "\n";
  return 0;
}

F. 树上求和

Description

有一棵包含n个节点和n-1条边的树，规定树链(u,v)为树上从u到v的简单路径。
树的每条边上都有一个正整数，这个正整数被称作这条边的颜色，规定一条树链的权值w(u,v)为这条树链上所有边的颜色的代数和。
而整棵树的权值为所有不同的树链的权值的代数和。
已知所有边的颜色集合恰好为1到n-1这n-1个不同的正整数，请你为每条边安排一种颜色，使得这棵树的权值尽量小，你不需要给出具体方案，只需要求出这个最小的权值即可。

Solution

一开始想的是先从叶子染色(类似拓扑排序的思想) 然后贴个树上任意两点距离和的板子(只能过60%样例
正确做法:树形dp处理出每条路径要走的次数, 排序后赋值即可
那么如何处理出要走的次数呢？
考虑sum[i] 是以i为根的子树拥有的节点数
那么假设把这个点作为树上的划分点，左边有sum[i]个点，右边有n - sum[i]个点
显然经过这个点的次数是左边的点去往右边的点的路径数量,即sum[i] * (n - sum[i])

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
struct Edge{
    int v, nextz;
    ll w;
}E[N << 1];
int head[N], tot;
void init(){
    memset(head, -1, sizeof(head));
    tot = 0;
}
int n;
ll sum[N];
void add(int u, int v, ll w){
    E[tot].v = v;
    E[tot].w = w;
    E[tot].nextz = head[u];
    head[u] = tot++;
}
ll dp[N], sz[N], val[N];
ll ans = 0;
void dfs(int u, int fa) {
    sum[u] = 1;
    for (int i = head[u]; ~i; i = E[i].nextz) {
        int v = E[i].v;
        if (v == fa)
            continue;
        dfs(v, u);
        sum[u] += sum[v];
    }
}
ll cal[N];
void solve(int u, int fa) {
    for (int i = head[u]; ~i; i = E[i].nextz) {
        int v = E[i].v;
        ll w = E[i].w;
        if (v == fa)
            continue;
        cal[w] += sum[v] * (n - sum[v]);
        solve(v, u);
    }
}
bool vis[N];
int se[N];
int main(){
  init();
  cin >> n;
  for(int i = 1; i <= n - 1; i++){
    int u, v;
    cin >> u >> v;
    add(u, v, i);
    add(v, u, i);
  }
  dfs(1, -1);
  solve(1, -1);
  ll ans = 0;
  for(int i = 1; i <= n - 1; i++){
    se[i] = i;
  }
  sort(se + 1, se + n, [](int x, int y){return cal[x] < cal[y];});
  ll color = n - 1;
  for(int i = 1; i <= n - 1; i++){
    ans += color * cal[se[i]];
    color--;
  }
  cout << ans << "\n";
  return 0;
}