AtCoder Beginner Contest 220 A - F 题解

A - Find Multiple

就 for 循环遍历就好了

void solve(){
  int a, b, c;
  cin >> a >> b >> c;
  for (int i = a; i <= b; ++i) {
    if (i % c == 0) {
      cout << i;
      return;
    }
  }
  cout << -1;
}

B - Base K

简单的进制转换

void solve(){
  int k;
  string a, b;
  cin >> k >> a >> b;
  auto tod = [&] (string & s) {
    int res = 0;
    for (auto & ch : s) {
      res *= k;
      res += ch - ‘0‘;
    }
    return res;
  };
  cout << 1ll * tod(a) * tod(b);
}

C - Long Sequence

整个数组可能被遍历 k 次，k - 1 次显然可以直接 O(1) 算出来，最后一次可以 for 循环遍历

ll a[N];
 
void solve(){
  int n;
  cin >> n;
  ll sum = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    sum += a[i];
  }
  ll x;
  cin >> x;
  ll ans = x / sum;
  x %= sum;
  ans *= n;
  ll res = 0;
  for (int i = 0; i < n && res <= x; res += a[i], ++ans, ++i);
  cout << ans;
}

D - FG operation

可以观察发现每次就两种操作，那么第 i 次操作得来的数不是 F 就是 G 所以只需要考虑 F 或 G 操作具体会产生什么数就好了

发现每次 DP 只用到上次 DP 的结果所以空间还可以优化

int a[N], f[N][10];
 
void solve(){
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  f[1][a[1]] = 1;
  for (int i = 2; i <= n; ++i) {
    for (int j = 0; j < 10; ++j) {
      int p = j * a[i] % 10, q = (j + a[i]) % 10;
      f[i][p] = (f[i][p] + f[i - 1][j]) % mod;
      f[i][q] = (f[i][q] + f[i - 1][j]) % mod;
    }
  }
  for (int i = 0; i < 10; ++i) {
    cout << f[n][i] << ‘\n‘;
  }
}

E - Distance on Large Perfect Binary Tree

这个式子没推出来，看别人题解才明白怎么做

对于这个问题考虑枚举出所有不同的节点 i, j保证 len(i, j) = m

对于 (i, j) 先考虑他们的 k = lca(i, j)

k 下面的深度需要保证深度至少为 depk = max(l, r), l 为 i 的深度，r 为 j 的深度

所以 k 的取法是深度为 1 到 n - depk 的上层子树的所有节点所以有 $ 2^depk - 1 $ 种取法

当 k 固定后显然 i 和 j 就好取了，i 是 k 的左儿子为跟节点开始直到深度为 r - 1 所在的子树的所有叶节点，j 也同理

可能说的不是很清楚，画下图可能会更清晰点

ll pw2[N], ans, n, m;
 
void solve(){
  cin >> n >> m;
  pw2[0] = 1;
  for (int i = 1; i <= n; ++i) {
    pw2[i] = pw2[i - 1] * 2 % mod;
  }
  for (int l = 0; l <= m; ++l) {
    int r = m - l;
    if (l >= n || r >= n) continue;
    int depk = max(l, r);
    ll cntk = pw2[n - depk] - 1;
    (ans += (cntk * pw2[max(l - 1, 0)] % mod * pw2[max(r - 1, 0)] % mod)) %= mod;
  }
  cout << ans * 2 % mod;
}

F - Distance Sums 2

换根 dp , 这是换根 dp 专题

换根 dp 看上去虽然是个名词但其实就是树形 dp

之所以需要换根是因为根不同 dp 结果也会有所不同，当然不可能每个节点都作为根去 dp 遍历整棵树

只需要以某个节点为根进行一次 dp

然后再遍历整棵树，对于不同的节点只需要考虑从父节点走到当前节点会对答案造成什么影响即可

这样只需遍历两次就可以找到答案

回到这道题，第一次 dp 要做的是以 1 为根节点求出根节点到所以子节点的距离，以及每个节点的节点个数为后面的一次 dp 做准备

第二次 dp 则是以父节点的答案来求出子节点的答案

第一次 dp

int head[N], ne[N], to[N], tot, n, sz[N];

ll f[N], dep[N];

void add(int u, int v) {
  to[++tot] = v;
  ne[tot] = head[u];
  head[u] = tot;
}

void solve(){
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    add(u, v), add(v, u);
  }
  function dfs1 = [&](int u, int par, int dep) {
    f[1] += dep;
    for (int i = head[u]; i; i = ne[i]) {
      if (to[i] != par) {
        dfs1(to[i], u, dep + 1);
        sz[u] += sz[to[i]];
      }
    }
    sz[u]++;
  };
  dfs1(1, 0, 0);
  function dfs2 = [&](int u, int par) {
    for (int i = head[u]; i; i = ne[i]) {
      if (to[i] != par) {
        f[to[i]] = f[u] + n - 2 * sz[to[i]];
        dfs2(to[i], u);
      }
    }
  };
  dfs2(1, 0);
  for (int i = 1; i <= n; ++i) cout << f[i] << ‘\n‘;
}

原文：https://www.cnblogs.com/empathy/p/15354854.html