2022 暑假水题选做

20220627

P3914 染色计数

思路：考虑树形 dp。设 \(f_{u,i}\) 为考虑以 \(u\) 为根的子树且 \(u\) 染上 \(i\) 时的答案，则：

\[f_{u,i}=\prod_{v\in\operatorname{son}(u)}\sum_{j\ne i}f_{v,j} \]

后面的 \(\sum\) 可以通过维护 \(\sum_{i=1}^m f_{u,i}\) 来优化掉。

算法：dp。

技巧：通过处理某些东西优化复杂度。

想到了的：都想到了。

没想到的：无。

代码 
#include 
#include 
using namespace std;

const int N = 5000, P = 1e9 + 7;

struct Edge {
  int to, nxt;
} e[N * 2 + 10];
int head[N + 10], tote;
void addEdge(int u, int v) {
  e[++tote] = {v, head[u]};
  head[u] = tote;
}

int n, m, f[N + 10][N + 10], sum[N + 10];

void dfs(int u, int _fa) {
  for (int _ = head[u]; _; _ = e[_].nxt) {
    int v = e[_].to;
    if (v == _fa) continue;
    dfs(v, u);
    for (int i = 1; i <= m; i++)
      f[u][i] = 1LL * f[u][i] * ((sum[v] - f[v][i]) % P) % P;
  }
  for (int i = 1; i <= m; i++)
    (sum[u] += f[u][i]) %= P;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int x; scanf("%d", &x);
    while (x--) {
      int y; scanf("%d", &y);
      f[i][y] = 1;
    }
  }
  for (int i = 1; i < n; i++) {
    int u, v; scanf("%d%d", &u, &v);
    addEdge(u, v), addEdge(v, u);
  }
  dfs(1, 0);
  printf("%d\n", (sum[1] % P + P) % P);
  return 0;
}

CF1677C Tokitsukaze and Two Colorful Tapes

思路：先拆置换，对于每个置换，填法一定是 \(\max,\min,\max,\min,\cdots\)。对于一个长度为 \(m\) 的置换，“山峰”有 \(\left\lfloor\frac m2\right\rfloor\) 个，“山谷”有 \(m-\left\lfloor\frac m2\right\rfloor\) 个，而每个山峰 \(x\) 对答案的贡献为 \(2x\)，每个山谷 \(x\) 对答案的贡献为 \(-2x\)。那么当我们让最大的数做山峰时答案有最大值 \(2\sum\left\lfloor\frac m2\right\rfloor(n-\sum\left\lfloor\frac m2\right\rfloor)\)。

算法：贪心。

技巧：拆置换、分别考虑每个数对答案的贡献。

想到了的：拆置换、贪心。

没想到的：考虑贡献。

代码 
#include 
#include 
using namespace std;

const int N = 1e5;

int n, a[N + 10], b[N + 10], pos[N + 10];
bool vis[N + 10];

void mian() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%d", a + i);
  for (int i = 1; i <= n; i++)
    scanf("%d", b + i), pos[b[i]] = i;
  int peak = 0;
  for (int i = 1; i <= n; i++) {
    int x = i, cnt = 0;
    while (1) {
      if (vis[x]) break;
      vis[x] = 1;
      cnt++;
      x = pos[a[x]];
    }
    peak += cnt / 2;
  }
  printf("%lld\n", 2LL * peak * (n - peak));
}

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    for (int i = 1; i <= n; i++)
      a[i] = b[i] = pos[i] = vis[i] = 0;
    mian();
  }
  return 0;
}
水题选做

相关

标签