T1 是无意义题，就不说了。这次周赛出得最差的题目就是 T1。
T2: ABC282E
题目描述
有 \(n\) 个数 \(a_i\)，你每次可以选出两个数 \(a_i\) 和 \(a_j\)，获得 \((a_i^{a_j}+a_j^{a_i}) \bmod M\) 分，并选择这两个数中的一个数删掉，求最大得分。
\(1\le n\le 500\)。
题目思路
我们把选出的两个数看成一条边，\((a_i^{a_j}+a_j^{a_i}) \bmod M\) 就是边权。先对两两个数建边，可以得到一个图。可以知道，通过操作得到的一个图不存在环。即选出的子图是一颗树。
也就是说：对原图求最大生成树，就是答案。
T3: CF1954E
题目描述
给定一个长度为 \(n\) 的序列 \(a\)，你还有一个属性 \(k\)，定义一次操作为：
-
选择 \(a\) 中一段极长的区间 \([l, r]\)，满足 \(\min \limits_{i = l} ^ r a_i > 0\)。
在这里，极长的区间定义为 \([l, r]\) 满足条件但 \([l - 1, r]\) 与 \([l, r + 1]\) 不满足条件。
-
\(\forall i \in [l, r] \cap \mathbb{N}\)，执行 \(a_i \gets a_i - k\)。
定义 \(f(k_0)\) 为当 \(k = k_0\) 时，为使 \(\max \limits_{i = 1} ^ n a_i \le 0\) 的最小操作数。
你需要分别求出 \(f(1), f(2), f(3), \dots, f(\max \limits_{i = 1} ^ n a_i)\) 的值。
保证 \(1 \le n \le 10 ^ 5\)，\(1 \le a_i \le 10 ^ 5\)。
题目思路
这次周赛出得最好的题目之一就是 T3。
为了简单起见，我们从 \(k = 1\) 开始。
第一道闪电可以向任何怪物发射，因为它总是会扩散到所有怪物身上。我们将继续发射闪电，直到有怪物死亡。当一个或多个怪物死亡时，问题就会分解成几个独立的子问题，因为没有闪电会穿过死亡的怪物。而且我们不管选择什么怪物来发射闪电，分成的子问题都是相同的。这意味着不存在 "最少秒数 "的概念——答案并不取决于发射闪电的怪物的选择。这个结论真的是妙！
那么我们该如何计算这个答案呢？攻击第一个怪物，直到它死亡。这需要 \(a_1\) 秒。然后我们继续攻击第二个怪物。如果它的生命值比第一个怪物高，我们就需要额外发射 \(a_2 - a_1\) 枚闪电来杀死它。否则，它已经死亡。在这两种情况下，第三个怪物会受到多少伤害？假设它的生命值很高。在第一种情况下，它会受到 \(a_2\) 伤害，因为所有的闪电都会击中它。但在第二种情况下，它也会受到 \(a_2\) 次伤害。以此类推。这就意味着 \(i\) 个怪物需要被 \(\max(0, a_i - a_{i - 1})\) 个闪电击中。
那么 \(k = 1\) 的答案就等于 \(a_1 + \sum\limits_{i = 2}^{n} \max(0, a_i - a_{i - 1})\) 。
如何计算任意 \(k\) 的答案呢？事实上，两者的差别并不大。只需将每个怪物的健康值从 \(a_i\) 改为 \(\lceil \frac{a_i}{k} \rceil\) 即可，而前面所述的整个过程将保持不变。因此，任何 \(k\) 的答案都等于 \(\lceil \frac{a_1}{k} \rceil + \sum\limits_{i = 2}^{n} \max(0, \lceil \frac{a_i}{k} \rceil - \lceil \frac{a_{i - 1}}{k} \rceil)\) 。
这个结论也真的是妙！对于我来说，很难获得 30 分 \(n\leq 5000\) 算法。
继续优化。把 max 拆开，看每一个 \(\lceil \frac{a_i}{k} \rceil\) 的系数，取决于两个条件：
- 如果是 \(i = 1\) 或 \(a_i \ge a_{i - 1}\) ，则系数增加 \(1\) ；
- 如果是 \(i = n\) 和 \(a_i < a_{i + 1}\) ，则系数减少 \(1\) 。
我们把 \(i\) 怪兽的这个系数称为 \(c_i\) 。因此，我们需要计算 \(\sum\limits_{i = 1}^n c_i \cdot \lceil \frac{a_i}{k} \rceil\) 。注意，\(c_i\) 是固定的。
这是什么？数论分块，只不过是向上取整的数论分块，但是我们知道 \(\lceil \frac{n}{l} \rceil=\lfloor \frac{n-1}{l} \rfloor+1\)，所以依然可以转化为下取整。
我们可以考虑每个 \(a_i\) 对答案的贡献，比如当前极长 \([l,r]\) 使得 \(\lceil\frac{a_i}{l}\rceil=\lceil\frac{a_i}{r}\rceil\)，那么答案区间 \([l,r]\) 整体就加上 \(c_i\times \lceil\frac{a_i}{l}\rceil\)。这个也 tm 很妙！
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define _pfor(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long
const int N = 3e5 + 5;
int n, a[N], maxn, ans[N];
signed main() {
cin >> n;
_for(i, 1, n) cin >> a[i], maxn = max(maxn, a[i]);
_for(i, 1, n) {
int cnt = 0;
if (i == 1 || a[i] > a[i - 1]) cnt++;
if (i < n && a[i + 1] > a[i]) cnt--;
int l = 1, r;
while (l <= a[i]) {
int t = (a[i] - 1) / l;
if (t) r = (a[i] - 1) / t;
else r = a[i];
ans[l] += cnt * (t + 1);
ans[r + 1] -= cnt * (t + 1);
l = r + 1;
}
ans[a[i] + 1] += cnt; // warning!
}
_for(i, 1, maxn) ans[i] += ans[i - 1];
_for(i, 1, maxn) cout << ans[i] << ' ';
}
T4: ARC100E
题目描述
给你一个长度为 \(2^n\) 的序列 \(a\)，每个 \(1\le K\le 2^n-1\)，找出最大的 \(a_i+a_j\)（\(i \mathbin{\mathrm{or}} j \le K\)，\(0 \le i < j < 2^n\)）并输出。
\(\mathbin{\mathrm{or}}\) 表示按位或运算。\(n\leq 18\)。
题目思路
求出 \(i\mathbin{\mathrm{or}} j\leq K\) 的最大值，等于说是求出等于 \(1\)，等于 \(2\)，一直到 \(k\) 的最大值。但是小于 \(k\) 的在之前的询问中求过，所以我们只需要把 res 放在外面就求出 \(\leq K\) 的最大值。比如：
int res = 0;
for (int i = 1; i < ((1 << n) - 1); i++) {
res = max(res, or=i的答案);
cout << res << endl;
}
两个数或起来等于 \(K\)，那么这两个数肯定是 \(K\) 二进制表示的子集。定义 \(mx_k\) 表示 \(k\) 二进制子集中 \(a\) 数组的最大值，\(mn_k\) 表示 \(k\) 二进制子集中 \(a\) 数组的次大值。那么答案就是 \(mx_K+mn_K\)。
预处理 mx 数组和 mn 数组，首先外层循环枚举 \(k\)，再枚举 \(k\) 的子集，花费 \(O(3^n)\) 的时间，足以通过本题，440ms。
signed main() {
cin >> n;
_for(i, 0, (1 << n) - 1) a[i] = read();
_for(i, 0, (1 << n) - 1) {
for (int j = i; j; j = (j - 1) & i) {
if (a[j] > tt[i]) tt2[i] = tt[i], tt[i] = a[j];
else if (a[j] > tt2[i]) tt2[i] = a[j];
}
if (a[0] > tt[i]) tt2[i] = tt[i], tt[i] = a[0];
else if (a[0] > tt2[i]) tt2[i] = a[0];
}
int res = 0;
_for(i, 1, (1 << n) - 1) {
res = max(res, tt[i] + tt2[i]);
wr(res); putchar('\n');
}
}
但是我们可以用一个更高效的方式，类似于 dp（被叫做高维前缀和）。就是 \(mx_i\) 可以由 \(mx_j\) 转移过来，其中 \(j\) 是 \(i\) 的子集。当然，快多了，32 ms。
signed main() {
cin >> n;
_for(i, 0, (1 << n) - 1) a[i] = read(), tt[i] = a[i];
_for(j, 0, n - 1) {
_for(i, 0, (1 << n) - 1) {
if (i >> j & 1) {
// mx[i]由子集mx[i^(1<<j)]转移过来
if (tt[i ^ (1 << j)] > tt[i]) tt2[i] = tt[i], tt[i] = tt[i ^ (1 << j)];
else if (tt[i ^ (1 << j)] > tt2[i]) tt2[i] = tt[i ^ (1 << j)];
}
}
}
int res = 0;
_for(i, 1, (1 << n) - 1) {
res = max(res, tt[i] + tt2[i]);
wr(res); putchar('\n');
}
}