比赛链接
本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18822660
开题 + 补题情况
今天打完蓝桥杯，还是 ACM 赛制好玩啊~~
这场题相对而言比较简单，也是汲取了上次的教训，做题节奏放慢了，稍微细心了点，打出了历史最佳战绩，虽然还是不小心 WA 了两发。
1001 - 烤羊
签到题，枚举调料的使用，可以使用二进制枚举，注意选取的不能超过目的值。
点击查看代码（赛时代码写得依托）
void solve()
{
i64 k, a, b, c;std::cin >> k >> a >> b >> c;
if(a == k || b == k || c == k) {
std::cout << 0 xss=removed xss=removed xss=removed xss=removed xss=removed> i64 {
if(x > k)return inf64;
return k - x;
};
i64 ans = inf64;
if(a + b + c > k) {
ans = std::min(ans, get(a));
ans = std::min(ans, get(b));
ans = std::min(ans, get(c));
ans = std::min(ans, get(a + b));
ans = std::min(ans, get(a + c));
ans = std::min(ans, get(b + c));
ans = std::min(ans, get(a + b + c));
if(ans == inf64)ans = k;
std::cout << ans>1003 - 抹茶
连续区间贪心选取，很明显的双指针题。
点击查看代码
void solve()
{
int n;std::cin >> n;
std::vector a(n + 1), b(n + 1);
for(int i = 1;i <= n;i ++) {
std::cin >> a[i];
}
for(int i = 1;i <= n;i ++) {
std::cin >> b[i];
}
i64 ans = 0;
for(int i = 1, j = 0;i <= n;i = j + 1) {
while(j + 1 <= n && a[j + 1] + b[j + 1] == a[i] + b[i]) {
j ++;
}
i64 tmp = 0;
for(int k = i;k <= j;k ++) {
tmp += a[k] * (j - i + 1);
}
ans = std::max(ans, tmp);
}
std::cout << ans> 1007 - 双相
要想最大，肯定是优先选最大的，将两种颜色的分数分别放入两个优先队列，然后模拟选取，直到选不了一人无法移动为止。
点击查看代码
void solve()
{
int n;std::cin >> n;
std::vector a(n + 1);
std::string s;
for(int i = 1;i <= n;i ++)std::cin >> a[i];
std::cin >> s;
s = ' ' + s;
std::priority_queue r, b;
for(int i = 1;i <= n;i ++) {
if(s[i] == 'R') {
r.push(a[i]);
} else {
b.push(a[i]);
}
}
i64 ans = 0;
int sum = 0;
while(true) {
sum ++;
if(sum & 1) {
if(!r.size()) {
break;
}
ans += r.top();
r.pop();
} else {
if(!b.size()) {
break;
}
ans += b.top();
b.pop();
}
}
std::cout << ans> 1008 - 天使
对于此题，我们可以先将范围缩小，假设只有三个使徒，考虑他们的结合顺序，不难发现：
因此，不管怎么结合，最后的答案都不会变化，结合后的又可以和其他的进行结合，那么，把这个结论推广到 \(n\) 个使徒同样成立。
因此不管怎么结合，最后的答案都一样。
所以，我们只需要从左到右结合算出答案，然后用 \(\sum_{i = 2}^n C_i^2\) 算出种类数即可。
点击查看代码（省略了取模类）
Z C(Z n) {
return n * (n - 1) / 2;
}
void solve()
{
int n;std::cin >> n;
std::vector a(n + 1);
for(int i = 1;i <= n;i ++)std::cin >> a[i];
Z ans = 0;
Z now = a[1];
for(int i = 2;i <= n;i ++) {
ans += now * a[i];
now += a[i];
}
Z sum = 1;
for(int i = n;i >= 2;i --) {
sum *= C(i);
}
std::cout << ans> 1002 - 英逃
首先需要观察出答案是具有单调性的。
为什么？
假设修改区间 \([l, r]\) 是可以达到题目要求的，那么对于 \([l - 1, r]\)，可以分析以下两种情况（区间 \([l, r + 1]\) 同理）：
- \(a_{l - 1} \geq \max_{i = l}^ra_i\)（如下图，黑色为修改前，红色为修改后，下同）：
对于区间 \([l, r]\)，它们对代价的贡献无变化，仍为 \(0\)，但对于左边这个新增的 \(a_{l - 1}\)，由于相邻两个数的差值变为了 \(0\)，因此对代价的贡献变小了，那么如果修改区间 \([l, r]\) 能达到题目目的，修改区间 \([l - 1, r]\) 同样能达到题目目的。 - \(a_{l - 1} < \max_{i = l}^ra_i\)，此时继续分两种情况讨论：
- \(a_{l - 2} \leq a_{l - 1}\)（如下图）：
对于这种情况，我们可以发现，\(a_{l - 1}\) 和 \(\max_{i = l}^ra_i\) 的差值缩小了 \(\max_{i = l}^ra_i - a_{l - 1}\)，\(a_{l - 1}\) 和 \(a_{l - 2}\) 的差值增大了 \(\max_{i = l}^ra_i - a_{l - 1}\)，因此对代价的贡献无变化，那么如果修改区间 \([l, r]\) 能达到题目目的，修改区间 \([l - 1, r]\) 同样能达到题目目的。 - \(a_{l - 2} > a_{l - 1}\)（如下图）：
对于这种情况，我们可以发现，\(a_{l - 1}\) 和 \(\max_{i = l}^ra_i\) 的差值缩小了 \(\max_{i = l}^ra_i - a_{l - 1}\)，\(a_{l - 1}\) 和 \(a_{l - 2}\) 的差值缩小了 \(\max_{i = l}^ra_i - a_{l - 1}\)，因此对代价的贡献缩小了 \(2 \times (\max_{i = l}^ra_i - a_{l - 1})\)，那么如果修改区间 \([l, r]\) 能达到题目目的，修改区间 \([l - 1, r]\) 同样能达到题目目的。
- \(a_{l - 2} \leq a_{l - 1}\)（如下图）：
因此，答案具有单调性，可以二分。
我们首先记录一下差分的绝对值以及差分的绝对值的前缀和，使用 ST 表来维护区间最值，然后进行二分答案，对每个二分到的区间长度，遍历所有可能的修改区间，更改修改后的代价总和，判断是否可能达到题目要求，在所有可能的答案中取最小即可。
点击查看代码
void solve()
{
int n;
i64 x;
std::cin >> n >> x;
std::vector a(n + 1);
for(int i = 1;i <= n;i ++)std::cin >> a[i];
std::vector d(n + 1);
for(int i = 2;i <= n;i ++) {
d[i] = abs(a[i] - a[i - 1]);
}
std::vector pre(n + 1);
for(int i = 2;i <= n;i ++) {
pre[i] = pre[i - 1] + d[i];
}
if(pre[n] <= x) {
std::cout << 0>> st(n + 1);
for(int i = 1;i <= n;i ++) {
st[i][0] = a[i];
}
int mx = std::__lg(n);
for(int k = 1;k <= mx;k ++) {
for(int i = 1;i + (1 << (k - 1)) <= n;i ++) {
st[i][k] = std::max(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
}
}
auto getmx = [&](int l, int r) -> i64 {
int s = std::__lg(r - l + 1);
return std::max(st[l][s], st[r - (1 << s xss=removed> bool {
i64 tmp = pre[n];
for(int i = 1;i <= n - m + 1;i ++) {
tmp = pre[n];
tmp -= pre[i + m - 1] - pre[i];
if(i != 1)tmp -= abs(a[i] - a[i - 1]);
if(i + m - 1 != n)tmp -= abs(a[i + m] - a[i + m - 1]);
i64 mx = getmx(i, i + m - 1);
if(i != 1)tmp += abs(mx - a[i - 1]);
if(i + m - 1 != n)tmp += abs(a[i + m] - mx);
if(tmp <= x)return true;
}
return false;
};
int l = 0, r = n + 1;
while(l + 1 < r xss=removed>> 1;
if(check(mid))r = mid;
else l = mid;
}
std::cout << r> 1010 - 章鱼
这题是很明显的换根 DP。
首先我们考虑一下，当一个点是一对点的 \(LCA\) 时，什么样的点对的 \(LCA\) 是它。
- 自己和自己的 \(LCA\) 都是自己。
- 对于这个点，它的子树（不包含父节点那个子树）中任选两个子树，两个子树中各自任选一个点，\(LCA\) 是它自己。
- 对于这个点，从它的子树（不包含父节点那个子树）中任选一个点，和这个点的 \(LCA\) 是它自己。
那么，思路也就出来了，对于每个结点为 \(LCA\) 时，逐个计算，当一个结点作为根时，除了根所在的这棵子树，对其他的子树按上述规则进行计数，对于每一棵子树，无论这棵子树哪个结点作为根，计算得到的答案都是相同的，因为都相当于是把这棵子树变成了父子树，这棵子树的结点都不可能和任何结点的 \(LCA\) 是当前结点。
当然，还要考虑自己为根的时候，此时和任何其他结点的 \(LCA\) 都是它自己。
换根 DP 足以解决这个问题。
点击查看代码
void solve()
{
int n;std::cin >> n;
std::vector> g(n + 1);
for(int i = 1;i < n>> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
std::vector sz(n + 1);
auto dfs = [&](auto &&self, int st, int pre) -> void {
sz[st] = 1;
for(auto &i : g[st]) {
if(i == pre)continue;
self(self, i, st);
sz[st] += sz[i];
}
};
dfs(dfs, 1, 0);
std::vector ans(n + 1);
auto C = [](i64 n) -> i64 {
return n * (n - 1) / 2;
};
auto dfs1 = [&](auto &&self, int st, int pre) -> void {
int n = g[st].size();
std::vector szpre(n + 1), Cpre(n + 1);
for(int i = 1;i <= n;i ++) {
if(g[st][i - 1] == pre)szpre[i] = szpre[i - 1] + sz[1] - sz[st];
else szpre[i] = szpre[i - 1] + sz[g[st][i - 1]];
if(g[st][i - 1] == pre)Cpre[i] = Cpre[i - 1] + C(sz[1] - sz[st]);
else Cpre[i] = Cpre[i - 1] + C(sz[g[st][i - 1]]);
}
for(int i = 1;i <= n;i ++) {
ans[st] += (szpre[i] - szpre[i - 1]) * (C(szpre[i - 1] + szpre[n] - szpre[i]) - (Cpre[i - 1] + Cpre[n] - Cpre[i]));
ans[st] += (szpre[i] - szpre[i - 1]) * (szpre[i - 1] + szpre[n] - szpre[i]);
}
ans[st] += sz[1] - 1;
ans[st] += C(szpre[n]) - Cpre[n];
for(auto &i : g[st]) {
if(i == pre)continue;
self(self, i, st);
}
};
dfs1(dfs1, 1, 0);
for(int i = 1;i <= n;i ++) {
ans[i] += sz[1];
std::cout << ans xss=removed> 1009 - 键帽（补题）
赛时最后一小时硬控我的一个题，身为 DP 低手对于 DP 的理解还是过于弱了。
首先对于这题，可以设置一个比较暴力的状态：\(dp_{i, j}\) 表示长度为 \(i\) 的字符串，后 \(j\) 个字符全是元音。
那么转移方程也很好想：$$dp_{i, j} = dp_{i - 1, j - 1} \times 5, j > 0$$
推广下去可以得到：$$dp_{i, len} = dp_{i - len, 0} * 5 ^ {len}$$
但是，由于需要枚举 \(len\)，这样转移的复杂度依然是 \(O(n^2)\)，并且由于 \(k\) 和 \(n\) 的数量级都是 \(10^6\)，二维数组也开不下哇。
因此不管是在时间上，还是空间上，都需要进行优化。
我们上面的复杂度之所以是 \(O(n^2)\)，是因为我们在维护串长这个维度的同时，还维护了连续元音长度这个维度，但是，根据题目要求，只要连续元音长度不大于 \(k\) 就是好串，因此我们对于连续元音长度的关注点不应该在长度为多少，而是和 \(k\) 的大小关系，也就是说，我们不需要具体维护每一个连续元音长度的信息，把这一维度优化掉，并在转移过程中保证存储的状态都满足连续元音长度不大于 \(k\) 即可。
那么我们新定义状态：
- \(dp_{i, 0}\) 表示长度为 \(i\) 的字符串，以辅音字母结尾。
- \(dp_{i, 1}\) 表示长度为 \(i\) 的字符串，以元音字母结尾。
那么新的转移方程也就出来了：
细看 \(dp_{i, 1}\) 的转移方程，似乎还是 \(O(n ^ 2)\) 的复杂度，但是注意到 \(5 ^ {i - j} = 5 ^ {n - j} / 5 ^ {n - i}\)，因此，我们可以对 \(dp_{i, 0} \times 5 ^ {n - i}\) 维护一个前缀和，查询时用前缀和快速查询出区间的和，并除上 \(5 ^ {n - i}\) 即可。
最后答案就是 \(\sum_{i = n - k}^{n} dp_{i, 0} \times 5 ^ {n - i}\)。
为什么我们不需要去管当已填充的合法字符串出现在中间的情况，而只需要考虑把它放在前缀？
因为若出现在中间，要满足答案，则除了没填的后缀之外，其他没填的位置，一定不能出现连续 \(k\) 个元音字母的情况，那么，也就转化为了更大的 \(i\) 的情况，在更大的 \(i\) 那里会把这种情况计算进去。
时间复杂度 \(O(n)\) 或 \(O(n\log n)\)。
点击查看代码（省略了取模类）
const int N = 1e6 + 9;
std::vector pow5;
void solve()
{
int n, k;std::cin >> n >> k;
std::vector> dp(n + 1, std::array{0});
std::vector pre(n + 1);
dp[0][0] = 1;
dp[0][1] = 0;
pre[0] = pow5[n];
Z ans = 0;
for(int i = 1;i <= n;i ++) {
int l = std::max(0, i - k);
int r = i - 1;
Z now;
if(l == 0)now = pre[r];
else now = pre[r] - pre[l - 1];
dp[i][1] = now / pow5[n - i];
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) * 21;
pre[i] = pre[i - 1] + dp[i][0] * pow5[n - i];
}
for(int i = 0;i <= k;i ++) {
ans += dp[n - i][0] * pow5[i];
}
std::cout << ans xss=removed xss=removed xss=removed xss=removed>> t;
while(t --)solve();
return 0;
}
1004 - 剪切（补题）
一个树形 DP 题。
关于树形 DP 一个很好的思路就是，存储每一棵子树的状态，自底向上进行转移，把每一棵子树的状态汇聚到一个父节点上，形成这个父节点代表的子树的状态。
这个题，要求把一棵树通过删一部分结点的方式分成 \(m\) 个连通块，保证每个连通块里面有且仅有一个喜欢的结点。
首先一个很明显的点就是，如果有两个喜欢的结点相邻，那么一定无解，因为这两个结点不可能通过删除不喜欢的结点的方式来分离。
然后再来考虑其他情况，这里我们定义 DP 状态为 \(dp_{i, j, k},j \in [0, 1], k \in [0, 1]\)，表示对于结点 \(i\)，删除（\(j = 1\)）或不删除（\(j = 0\)）结点 \(i\) 的情况下，结点 \(i\) 的子树中有 \(k\) 个喜欢的结点的到结点 \(i\) 为止的最大价值。
这里要注意一件事，为什么子树中只有可能有 \(0 / 1\) 个喜欢的结点？
因为这里所说的子树，已经是在题目要求下的意义的子树了，题目要求每个连通块中不能出现多个喜欢的结点，那么，如果一个结点的子树中有多个喜欢的结点的话，在这些喜欢的结点之间应该已经进行了分离操作，对于已经分离的，我们就无需继续考虑了，因此子树 \(i\) 中连向当前结点 \(i\) 的喜欢的结点最多只会有 \(1\) 个。
再说简单点的话，这里所说的子树，是已经在子树 \(i\) 中进行了合法性分离的结点 \(i\) 所属的连通块。
把状态明确后，下一个事情就是转移方程了（为了便于转移和描述，下面使用 \(inf\) 表示正无穷，至于正无穷的取值，可以自行根据题目数据范围取一个合适值），对于结点 \(i\)：
首先无论结点 \(i\) 是否喜欢，\(dp_{i, 1, 1}\) 都是不合法的状态，因为按照我们上面对于状态的定义，每一个状态都是对于结点 \(i\) 所属的连通块而言的，但是如果结点 \(i\) 被删除，结点 \(i\) 不应该属于任何一个保留下来的连通块，也就是说属于一个空的连通块，那么这里面没有结点，也就不会有喜欢的结点。
记 \(sum = \sum_{j \in g_i} \max(dp_{j, 1, 0}, dp_{j, 0, 0})\)，\(g_i\) 是结点 \(i\) 的子结点（不包含父节点）集合。
- 如果结点 \(i\) 是喜欢的结点：
- \(dp_{i, 0, 0} = -inf\)
因为这个结点是喜欢的结点，那么这个结点保留下来后，结点 \(i\) 所属的连通块里面一定会包含这个结点，那么这个状态就是一个不合法的状态。 - \(dp_{i, 0, 1} = sum + a_i\)
这个很好理解，当前结点是喜欢的结点，那么它所归属的连通块不能有其他的喜欢的结点，因此状态转移过程中选取的子结点的前置状态应该都是不包含喜欢的结点的状态。 - \(dp_{i, 1, 0} = -inf\)
喜欢的结点必须保留，因此删除喜欢的结点的状态也不合法。
- \(dp_{i, 0, 0} = -inf\)
- 如果结点 \(i\) 不是喜欢的结点：
- \(dp_{i, 0, 0} = sum + a_i\)
这个很好理解，当前结点不是喜欢的结点，那么要让它连接得到的连通块也没有喜欢的结点，因此状态转移过程中选取的子结点的前置状态应该都是不包含喜欢的结点的状态。如果有一个子树不包含喜欢的结点是不合法的（也就是某个子结点是喜欢的结点），那么它的 \(\max(dp_{j, 0, 0}, dp_{j, 1, 0})\) 也一定是 \(-inf\)，只要 \(inf\) 的数量级比 \(dp\) 数组中正常的值的数量级要大得多，那么转移得到的依然会是 \(-inf\) 的数量级，那么此状态依然是不合法的，转移不会出现问题。 - \(dp_{i, 0, 1} = sum + a_i + \max_{j \in g_i}(dp_{j, 0, 1} - \max(dp_{j, 1, 0}, dp_{j, 0, 0}))\)
这个看题解的时候理解了很久，确实很妙，对于一个不喜欢的结点，要让它在保留的情况下，连接得到的连通块中包含一个喜欢的结点，那其实就是对于它所有的子结点，只保留一个子结点所属的连通块含有的喜欢的结点，其他的都在子树中进行切割，也就是对每一个子结点 \(j\)，保留 \(j\) 所属的连通块含有的喜欢的结点的答案是 \(sum + a_i + dp_{j, 0, 1} - \max(dp_{j, 1, 0}, dp_{j, 0, 0})\)，这里面的变量只有 \(dp_{j, 0, 1} - \max(dp_{j, 1, 0}, dp_{j, 0, 0})\)，因此对这部分取最大值。这种情况依然是有不合法的情况的，也就是对于整个子树 \(i\)，一个喜欢的结点也没有，可以特判，也可以按照上一个情况对于不合法的情况的分析来分析，得到的仍然是 \(-inf\) 级别。 - \(dp_{i, 1, 0} = \sum_{j \in g_i} \max(dp_{j, 1, 0}, dp_{j, 0, 1})\)
把当前结点 \(i\) 剪掉，那么对于它的子树，也就都被分开了，每一棵子树都应该合法，对于每一棵子树而言，\(dp_{j, 1, 0}\) 和 \(dp_{j, 0, 1}\) 至少有一个是合法的状态（若不合法也会是 \(-inf\)），取最大就行，\(dp_{j, 0, 0}\) 此时不合法是因为当前这个子结点如果不删且它所属的连通块不包含喜欢的结点，那么结点 \(i\) 被删除后，结点 \(j\) 所属的连通块就是一个独立的连通块，没有任何喜欢的结点，因此不合法。（这一个转移是我觉得最能体现出 DP 的神奇之处的）
- \(dp_{i, 0, 0} = sum + a_i\)
最后的答案也就是 \(\max(dp_{root, 0, 1}, dp_{root, 1, 0})\)，\(dp_{root, 0, 0}\) 不合法的原因同上。
点击查看代码
#include
#define inf32 1e9
#define inf64 2e16
#define ls o << 1 xss=removed xss=removed xss=removed xss=removed>> n >> m;
std::vector a(n + 1);
for(int i = 1;i <= n;i ++) {
std::cin >> a[i];
}
std::vector> g(n + 1);
for(int i = 1;i < n>> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
std::vector vis(n + 1);
for(int i = 1;i <= m;i ++) {
int x;std::cin >> x;
vis[x] = true;
}
g[1].push_back(0);
for(int i = 1;i <= n;i ++) {
for(auto &j : g[i]) {
if(vis[i] == vis[j] && vis[i] == 1) {
std::cout << -1 << '\n';
return;
}
}
}
std::vector, 2>> dp(n + 1);
for(int i = 1;i <= n;i ++) {
for(int j = 0;j <= 1;j ++) {
for(int k = 0;k <= 1;k ++) {
dp[i][j][k] = -inf64;
}
}
}
auto dfs = [&](auto &&self, int st, int pre) -> void {
i64 sum = 0;
for(auto &i : g[st]) {
if(i == pre)continue;
self(self, i, st);
sum += std::max(dp[i][1][0], dp[i][0][0]);
}
if(vis[st]) {
dp[st][1][0] = -inf64;
dp[st][0][1] = sum + a[st];
dp[st][0][0] = -inf64;
} else {
dp[st][1][0] = 0;
for(auto &i : g[st]) {
if(i == pre)continue;
dp[st][1][0] += std::max(dp[i][1][0], dp[i][0][1]);
}
i64 mx = -inf64;
for(auto &i : g[st]) {
if(i == pre)continue;
mx = std::max(mx, dp[i][0][1] - std::max(dp[i][1][0], dp[i][0][0]));
}
dp[st][0][1] = mx + sum + a[st];
dp[st][0][0] = sum + a[st];
}
};
dfs(dfs, 1, 0);
std::cout << std> 
