Codeforces Round 958 (Div. 2)

Luckyblock / 2024-07-16 / 原文

写在前面
A
B
C
D
E
写在最后

写在前面

比赛地址：https://codeforces.com/contest/1988

感觉这场要掉一百分妈的纯傻逼我是

A

签到

显然一种最优的策略是每次操作分出 $k - 1$ 个 1，然后考虑最后是否会剩下一个单独的 1。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    int n, k; std::cin >> n >> k;
    std::cout << ceil(1.0 * (n - 1) / (k - 1)) << "\n";
  }
  return 0;
}

B

结论

发现 1 的个数在操作后是单调递减的。

则一种显然的策略是首先对全 0 连续段进行操作使它们均变为一个 0，先尽可能减少 0 的个数，然后判断是否有 $c_1 > c_0$ 即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    int n; std::cin >> n;
    std::string s; std::cin >> s;

    int c1 = 0, c0 = 0;
    for (int i = 0; i < n; ++ i) {
      if (s[i] == '1') ++ c1;
      if (s[i] == '0' && (i == 0 || s[i - 1] != '0')) ++ c0;
    }
    std::cout << (c1 > c0 ? "YES\n" : "NO\n");
  }
  return 0;
}

C

二进制

显然数列中最大的数为 $n$，考虑反向构造，根据 $a_{i + 1}$ 构造 $a_i$。

为了保证数列递增，则 $a_{i}$ 与 $a_{i + 1}$ 从高向低位中第一个不同的位置，一定 $a_{i}$ 该位为 0，$a_{i+1}$该位为 1。为了保证 $a_i | a_{i +1} = n$，发现上述的不同的位一定在 $n$ 中该位为 1，且各位不能重复产生贡献，则除 $n$ 之外，可构造出的数列元素个数即为 $n$ 中 1 的个数。

记 $n$ 中从高到低各二进制位为 $2^{k_0}, 2^{k_1}, \cdots(k_0 > k_1 > \cdots)$，则一种显然的构造是：

\[n - 2^{k_0}, n - 2^{k_1}, \cdots, n \]

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&(-x))
//=============================================================
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    LL n; std::cin >> n;
    std::vector<LL> ans;
    ans.push_back(n);

    LL last = n, temp = n;
    while (temp) {
      LL b = lowbit(temp);
      temp -= b;
      ans.push_back(n - b);
    }
    std::cout << ans.size() << "\n";
    std::reverse(ans.begin(), ans.end());
    for (auto x: ans) std::cout << x << " ";
    std::cout << "\n";
  }
  return 0;
}

D

树形 DP。

设最多进行 $L$ 轮后可以干掉所有怪物，则题目等价于为每个节点 $u$ 分配 $1\sim L$ 中的一个权值 $k_u$ 作为系数，满足相邻两个节点系数不同，最小化：

\[\sum_{1\le u\le n} k_u\times a_u \]

然后就变成了这个题。这东西显然可以直接大力 $O(nL^2)$ 地树形 DP。设 $f_{u, i}$ 表示令节点 $u$ 系数为 $i$ 时，以 $u$ 为根的子树价值之和的最小值，初始化 $f_{u, i} = 0$，则有转移：

\[f_{u, i} = i\times a_{u} + \sum_{v\in \operatorname{son}(u)} \min_{j\not= i} f_{v, j} \]

答案即为：

\[\min_{1\le i\le L} f_{1, i} \]

转移的时候前后缀最值优化一下可以变成 $O(nL)$。

然后猜一下 $L$ 的数量级，随手写个 20 左右就能过了呃呃，然而赛时以为 3 就行 WA 成狗了。可以证明：$L \le \left\lfloor\log_2 n\right\rfloor + 1$，证明详见官方题解：https://codeforces.com/blog/entry/131567。

则总时间复杂度 $O(n\log^2 n)$ 级别或 $O(n\log n)$ 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL __int128
const int kN = 3e5 + 10;
const int kM = kN << 1;
//=============================================================
int n;
long long a[kN];
int edgenum, head[kN], v[kM], ne[kM];
LL f[kN][21];
//=============================================================
void addedge(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void dfs(int u_, int fa_) {
  for (int i = 1; i <= 20; ++ i) {
    f[u_][i] = 1ll * i * a[u_];
  }

  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    dfs(v_, u_);
    for (int j = 1; j <= 20; ++ j) {
      LL minf = (j == 1 ? f[v_][2] : f[v_][1]);
      for (int k = 1; k <= 20; ++ k) {
        if (j == k) continue;
        minf = std::min(minf, f[v_][k]);
      }
      f[u_][j] += minf;
    }
  }
}
inline void print(LL n) {
  if(n > 9) print(n / 10);
  putchar(n % 10 + '0');
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n;
    for (int i = 1; i <= n; ++ i) std::cin >> a[i];

    edgenum = 0;
    for (int i = 1; i <= n; ++ i) head[i] = 0;
    for (int i = 1; i < n; ++ i) {
      int u_, v_; std::cin >> u_ >> v_;
      addedge(u_, v_), addedge(v_, u_);
    }
    dfs(1, 0);

    LL ans = f[1][1];
    for (int i = 1; i <= 20; ++ i) {
      ans = std::min(ans, f[1][i]);
    }
    // std::cout << ans << "\n";
    print(ans);
    // std::cout << "\n";
    printf("\n");
  }
  return 0;
}