题面在代码里A. 换座位    简单模拟换完新座位是什么样子，跟原来的座位对比一下，难度在于读题。#include<bits/stdc++.h>#define debug(x) std::cerr << "debug: " << x << '\n';#define all(x) x.begin(), x.end()using pii = std::pair<int, int>;using i64 = long long;using vi = std::vector<int>;using vp = std::vector<pii>;using vl = std::vector<i64>;std::string s[205][205], change[205][205];void solve(int cas) {  int n, m, a;  std::cin >> n >> m >> a;  for (int i = 0; i < n; i++) {    for (int j = 0; j < m; j++) {      std::cin >> s[i][j];    }  }  for (int i = 0; i < n; i++) {    for (int j = 0; j < m; j++) {      int r = (i - 1 + n) % n, c = (j - 1 + m) % m;      change[i][j] = s[r][c];      std::cerr << change[i][j];    }    std::cerr << '\n';  }  int ans = 0;  for (int i = 0; i < n; i++) {    for (int j = 0; j < m; j++) {      for (int k = 0; k < a; k++) {        if (s[i][j][k] ^ change[i][j][k]) {          ++ans;        }      }    }  }  std::cout << ans << '\n';} int main() {  int T = 1;  //std::cin >> T;  while (T--) {    solve(T);  }  return 0;}/*小团班级的座位排成了 n 行（行从 1 到 n 编号），共有 m 个大列（大列从 1 到 m 编号），每个大列中有 a 个小列（小列从 1 到 a 编号），大列与大列之间有一个过道。小团的班级每周会换一次座位，首先所有同学都换到后一行，最后一行的同学换到第一行，然后所有同学都移动到自己右边的那个大列的相同小列上，在最右大列的同学移动到最左大列。换句话说，对于坐在第 i<n 行的同学，新位置在第 i+1 行，如果 i=n，那么新位置在第一行；对于坐在第 j<m 大列的同学，新位置在第 j+1 大列，如果 j=m，那么新位置在第一大列；对于坐在第 k 小列的同学，新位置仍然在第 k 小列。小团的学校最近换了一批学生桌椅。这批学生桌椅的优点在于可以调节桌子的高度，一些同学调整了桌子高度，但是另一些没有。这样换座就变得麻烦了起来，如果一位调整了桌子高度的同学换到了未调整桌子高度同学的位置，他就会调整新位置的桌子到他想要的高度，而一位没有调整桌子高度的同学换到了调整过桌子高度同学的位置，他也会调整新位置的桌子高度，使其恢复原高度。现在小团的班级要进行换座位了，给出换座位前班级所有桌子的情况，小团想知道，换一次位置后，有多少同学需要重新调整桌子高度。输入描述输入第一行包含三个数 n, m, a，意义如题目所示。接下来 n 行，每行 m 个长度为 a 的 01 字符串，表示目前小团班上的桌子情况。其中 0 表示这个位置未调节桌子高度，1 表示已调节桌子高度。对于全部数据，1 ≤ n, m ≤ 200, n × m ≥ 2, 1 ≤ a ≤ 5。输出描述输出一行一个整数，表示换座位后有多少同学需要重新调整桌子高度。样例输入3 3 201 10 0010 00 1101 00 00样例输出8*/B. 最长路径    在树上，要切掉一条边，那么原图被划分成两颗子树，以u, v为根在两个子树里找距离最远的点。#include<bits/stdc++.h>#define debug(x) std::cerr << "debug: " << x << '\n';#define all(x) x.begin(), x.end()using pii = std::pair<int, int>;using i64 = long long;using vi = std::vector<int>;using vp = std::vector<pii>;using vl = std::vector<i64>;vi G[100005];int dist[100005], res = 0;void dfs(int u, int par) {  res = std::max(res, dist[u]);  for (auto v : G[u]) {    if (v == par) {      continue;    }    dist[v] = dist[u] + 1;    dfs(v, u);  }}void solve(int cas) {  int n;  std::cin >> n;  for (int i = 2; i <= n; i++) {    int fa;    std::cin >> fa;    G[fa].emplace_back(i);    G[i].emplace_back(fa);  }  int from, to;  int ans = 1;  std::cin >> from >> to;  dfs(from, to);  ans += res;  res = 0;  dfs(to, from);  ans += res;  std::cout << ans << '\n';} int main() {  int T = 1;  //std::cin >> T;  while (T--) {    solve(T);  }  return 0;}/*题目描述：有一棵 n 个节点的树，有一条边被选定。小美想知道对于所有经过这条选定边的所有树上简单路径，最长的那条有多长。一条简单的路径的长度指这条简单路径上的边的个数。输入描述第一行一个整数 n，表示树的节点个数。第二行 n-1 个整数，第 i 个整数 pi 表示节点 i+1 和 pi 之间有一条边相连。第三行两个整数 x, y，表示这条选定的边。保证这条边一定是树上的一条边。对于全部数据，2 ≤ n ≤ 1e5, 1 ≤ pi ≤ n, 1 ≤ x, y ≤ n, x ≠ y。保证输入数据正确描述一棵树，并且 (x, y) 是树上的一条边。输出描述输出一行，一个整数，表示所有经过选定边的树上简单路径中，最长的那条的长度。样例输入71 2 3 4 5 33 7样例输出4*/C. 水果分配    简单dp，假设当前考虑到第 i 个水果，那么上一个行程果篮的位置为 j，只需要求出区间[j + 1, i] 的最大值和最小值即可，转移式为 dp[i] = min(dp[i], dp[j] +cal(j + 1, i).    做这道题的时候有个小插曲，一开始看到的时间限制是3s，后面好像后台偷偷把时间改成1s了。因为我不会背 st 表怎么写，所以写了个线段树时间复杂度O(nmlogn) 超时了，用两个 cache 去存查询过的点记忆化也不行，最后直接暴力求以 i 为起点，j 为终点的最大值，最小值。正确写法应该是开 1e4 个 vector，每个 vector 的大小都是 m，但是我开了1e8的数组，好像编译器帮我优化了那些没用到的空间..#include<bits/stdc++.h>#define debug(x) std::cerr << "debug: " << x << '\n';#define all(x) x.begin(), x.end()using pii = std::pair<int, int>;using i64 = long long;using vi = std::vector<int>;using vp = std::vector<pii>;using vl = std::vector<i64>;int A[10005];i64 dp[10005];int cache_max[10005][10005], cache_min[10005][10005];//std::unordered_map<int, int> cache_min[10005];// class SegTree {//   private://   struct Node {//     int l, r, Max, Min;//   };//   std::vector<Node> t;//   public://   SegTree(int n) {//     t.resize(4 * n + 1);//   }//   void push_up(int rt) {//     t[rt].Max = std::max(t[rt << 1].Max, t[rt << 1 | 1].Max);//     t[rt].Min = std::min(t[rt << 1].Min, t[rt << 1 | 1].Min);//   }//   void build(int rt, int l, int r) {//     t[rt].l = l, t[rt].r = r;//     if (l == r) {//       t[rt].Max = t[rt].Min = A[l];//       return ;//     }//     int mid = (t[rt].l + t[rt].r) >> 1;//     build(rt << 1, l, mid);//     build(rt << 1 | 1, mid + 1, r);//     push_up(rt);//   }//   int query_max(int rt, int ql, int qr) {//     if (cache_max[ql].count(qr)) {//       return cache_max[ql][qr];//     }//     if (ql <= t[rt].l and qr >= t[rt].r) {//       return t[rt].Max;//     }//     int mid = (t[rt].l + t[rt].r) >> 1;//     if (ql > mid) {//       return query_max(rt << 1 | 1, ql, qr);//     }//     if (qr <= mid) {//       return query_max(rt << 1, ql, qr);//     }//     return std::max(query_max(rt << 1, ql, qr), query_max(rt << 1 | 1, ql, qr));//   }//   int query_min(int rt, int ql, int qr) {//     if (cache_min[ql].count(qr)) {//       return cache_min[ql][qr];//     }//     if (ql <= t[rt].l and qr >= t[rt].r) {//       return t[rt].Min;//     }//     int mid = (t[rt].l + t[rt].r) >> 1;//     if (ql > mid) {//       return query_min(rt << 1 | 1, ql, qr);//     }//     if (qr <= mid) {//       return query_min(rt << 1, ql, qr);//     }//     return std::min(query_min(rt << 1, ql, qr), query_min(rt << 1 | 1, ql, qr));//   }// };void solve(int cas) {  int n, m, s;  std::cin >> n >> m >> s;  for (int i = 1; i <= n; i++) {    std::cin >> A[i];    dp[i] = 1e18;  }  for (int i = 1; i <= n; i++) {    int max_obj = 0, min_obj = 1e9;    for (int j = i; j <= n; j++) {      max_obj = std::max(max_obj, A[j]);      min_obj = std::min(min_obj, A[j]);      cache_max[i][j] = max_obj;      cache_min[i][j] = min_obj;    }  }  // SegTree T(n);  dp[0] = 0;  // T.build(1, 1, n);  auto cal = [&](int l, int r) {    // auto Max = T.query_max(1, l, r), Min = T.query_min(1, l, r);    // cache_max[l][r] = Max;    // cache_min[l][r] = Min;    auto Max = cache_max[l][r], Min = cache_min[l][r];    int k = r - l + 1;    return 1LL * k * ((Max + Min) / 2) + s;  };  for (int i = 1; i <= n; i++) {    for (int last = std::max(i - m, 0); last <= i - 1; last++) {      dp[i] = std::min(dp[i], dp[last] + cal(last + 1, i));    }  }  std::cout << dp[n] << '\n';} int main() {  int T = 1;  //std::cin >> T;  while (T--) {    solve(T);  }  return 0;}/*小美不干外卖配送了，转行开了一家水果店。一天她接到了一个大单，客户订购了 n 个水果，并且要求打包成多个果篮，一个果篮最多装 m 个水果。为了包装方便，水果按从 1 到 n 编号，同一个果篮里装的水果编号必须是连续的。果篮的成本与容积成线性关系。为了估计容积，小美简单地用样本中点估计了一下。具体来说，假设一个果篮中装的最大的水果体积是 u，最小的是 v，那么这个果篮的成本就是 k × floor((u+v)/2) + s，其中 k 是果篮中装入水果的个数，s 是一个常数，floor(x) 是下取整函数，比如 floor(3.8)=3, floor(2)=2。客户并没有规定果篮的数量，但是希望果篮的成本越小越好，毕竟买水果就很贵了。请求出小美打包这 n 个水果所用的最小花费。输入描述第一行三个正整数 n, m, s。意义如题面所示。第二行 n 个正整数 a1, a2, ..., an，表示每个水果的体积。对于全部数据，1 ≤ n ≤ 1e4,   1 ≤ m ≤ 1e3,   m ≤ n,   1 ≤ ai, s ≤ 1e4。输出描述输出一个整数，表示打包这 n 个水果果篮的最小成本。样例输入6 4 31 4 5 1 4 1样例输出21*/D. 地雷考虑先对每个点求离他最近的地雷的距离，然后类似于 Dijkstra 的做法跑个 dp 就行了。#include<bits/stdc++.h>#define debug(x) std::cerr << "debug: " << x << '\n';#define all(x) x.begin(), x.end()using pii = std::pair<int, int>;using i64 = long long;using vi = std::vector<int>;using vp = std::vector<pii>;using vl = std::vector<i64>;int X[405], Y[405];int dist[505][505], dp[505][505];bool vis[505][505];int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};void solve(int cas) {  int n, m, k;  std::cin >> n >> m >> k;  memset(dist, 0x3f, sizeof(dist));  for (int i = 1; i <= k; i++) {    std::cin >> X[i] >> Y[i];  }  for (int i = 1; i <= n; i++) {    for (int j = 1; j <= m; j++) {      for (int u = 1; u <= k; u++) {        int distance = std::abs(i - X[u]) + std::abs(j - Y[u]);        dist[i][j] = std::min(dist[i][j], distance);      }    }  }  int _x1, _y1, _x2, _y2;  std::cin >> _x1 >> _y1 >> _x2 >> _y2;  std::priority_queue<std::tuple<int, int, int> > que;  que.emplace(dist[_x1][_y1], _x1, _y1);  dp[_x1][_y1] = dist[_x1][_y1];  while (!que.empty()) {    auto [cost, x, y] = que.top();    que.pop();    if (vis[x][y]) {      continue;    }    vis[x][y] = true;    for (int i = 0; i < 4; i++) {      int nx = x + dir[i][0], ny = y + dir[i][1];      if (nx <= 0 or ny <= 0 or nx > n or ny > m) {        continue;      }      if (!vis[nx][ny] and dp[nx][ny] < std::min(dist[nx][ny], dp[x][y])) {        dp[nx][ny] = std::min(dist[nx][ny], dp[x][y]);        que.emplace(dp[nx][ny], nx, ny);      }    }  }  std::cout << dp[_x2][_y2] << '\n';} int main() {  int T = 1;  //std::cin >> T;  while (T--) {    solve(T);  }  return 0;}/*题目描述：有一片 n × m 大小的网格，共 n 行 m 列，其中行和列都用从 1 开始的整数编号，网格中有 k 个格子中埋有地雷。我们记第 a 行第 b 列的格子为 (a, b)。小美现在位于 (x1, y1)，她想要移动到 (x2, y2) 处。小美每次移动可以移动到与她所处格子的相邻的一格中，形式化地说，如果小美位于 (x, y)，则小美可以移动到 (x-1, y), (x+1, y), (x, y-1), (x, y+1) 的格子之一，但小美不能移动到网格之外。小美想要在移动过程中，离这些地雷越远越好，而不是走最短路径。这里定义两个格子之间的距离为曼哈顿距离，即格子 (a, b) 和 (c, d) 之间的距离是 |a-c|+|b-d|。小美想知道，移动中与地雷之间距离的最小值最大可能是多少。请注意，如果无论小美如何移动，都会进入一个有地雷的格子的话，这个最大可能值为 0。输入描述第一行三个整数 n, m, k，分别表示网格的行数，列数和地雷个数。接下来 k 行，每行两个整数 p, q，表示一个地雷放置在格子 (p, q) 中。任意两地雷的放置位置不同。接下来一行四个整数 x1, y1, x2, y2，表示小美的出发位置和目的位置。保证小美的出发位置和目的位置上没有地雷。对于全部数据，1 ≤ n, m ≤ 500, n × m ≥ 3, 1 ≤ k ≤ min{n × m-2, 400}, 1 ≤ p, x1, x2 ≤ n, 1 ≤ q, y1, y2 ≤ m, (x1, y1) ≠ (x2, y2)，保证 (x1, y1) 和 (x2, y2) 中没有地雷，并且一个格子中最多放置一个地雷。输出描述输出一行一个整数，表示移动过程中与地雷之间距离的最小值的可能最大值。样例输入5 6 22 12 31 1 5 1样例输出13 3 91 12 23 34 45 56 67 78 89 91 1 3 3*/E. 划分彩色树感觉跟 B 题差不多，因为求的是有多少条边能满足条件，不妨枚举边，先预处理子树下RGB三种颜色的个数就可以了。#include<bits/stdc++.h>#define debug(x) std::cerr << "debug: " << x << '\n';#define all(x) x.begin(), x.end()using pii = std::pair<int, int>;using i64 = long long;using vi = std::vector<int>;using vp = std::vector<pii>;using vl = std::vector<i64>;int tot;vi G[100005];char color[100005];struct Edge {  int u, v;} edge[100005];int szR[100005], szG[100005], szB[100005];void dfs(int u, int par) {  szR[u] = color[u] == 'R';  szG[u] = color[u] == 'G';  szB[u] = color[u] == 'B';  for (auto v : G[u]) {    if (v == par) {      continue;    }    dfs(v, u);    szR[u] += szR[v];    szG[u] += szG[v];    szB[u] += szB[v];  }}void solve(int cas) {  int n;  std::cin >> n;  for (int i = 2; i <= n; i++) {    int fa;    std::cin >> fa;    ++tot;    edge[tot].u = i, edge[tot].v = fa;    G[i].emplace_back(fa);    G[fa].emplace_back(i);  }  std::string s;  std::cin >> s;  s = ' ' + s;  int R = 0, G = 0, B = 0;  for (int i = 1; i <= n; i++) {    color[i] = s[i];    R += color[i] == 'R';    G += color[i] == 'G';    B += color[i] == 'B';  }  dfs(1, 0);  int ans = 0;  for (int i = 1; i <= tot; i++) {    int u = edge[i].u, v = edge[i].v;    if (szR[u] and szG[u] and szB[u]) {      if (R - szR[u] > 0 and G - szG[u] > 0 and B - szB[u] > 0) {        ++ans;      }    }  }  std::cout << ans << '\n';} int main() {  int T = 1;  //std::cin >> T;  while (T--) {    solve(T);  }  return 0;}/*题目描述：有一棵 n 个节点的树，树上每个点都有红绿蓝三种颜色中的一种。定义一棵树是多彩的，当且仅当这棵树同时存在一个红色节点，一个蓝色节点和一个绿色节点。保证最初这棵树是多彩的，现在要砍掉这棵树的某一条边，请问有多少种砍法，使得砍完之后形成的两棵树都是多彩的。输入描述第一行一个整数 n，表示节点个数。第二行 n-1 个整数 p2, p3, ..., pn，pi 表示树上 i 和 pi 两点之间有一条边。保证给出的一定是一棵树。第三行一个长度为 n 的字符串，第 i 个字符表示第 i 个节点的初始颜色。其中 R 表示红色，G 表示绿色，B 表示蓝色。保证字符串只由这三种大写字母构成。对于全部数据，3≤n≤1e5。输出描述输出一行，一个正整数，表示答案。样例输入71 2 3 1 5 5GBGRRBB样例输出1*/