比赛链接
*注意：在本文中，题目大意没有还原题目背景，也没有细节说明，如果您没有看过题目，还请前往Codeforces官网看
A题
题目大意
给定长度为$n$且只包含$1$和$m$之间的正整数数列$a_1,a_2,\cdots,a_n$，有一个长度为$m$的字符串$s$，初始时串$s$只包含字符B
接下来进行如下$n$次操作：
- 在第$i$次操作时$(1\le i \le n)$，你可以选择将$s$串的第$a_i$个字符或者第$(m+1-a_i)$个字符改成
A。（注意，你可以对同一个位置进行若干次操作）
找到$n$次操作后，你能得到的字典序最小的串$s$
*本题有多组数据$(t\le2000)$，对于每组数据$1\le n,m \le50$
解析
签到题。显然数列${a_n}$的顺序与答案没有关系，因此可以考虑贪心，每次操作都优先将靠前的位置换成A，如果靠前的位置已经被更换了，就换另一个，如果两个都被更换过当然这次操作无论如何都没有意义了。
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define debug(x) cerr << #x << " = " << (x) << endl
const int maxn = 55;
int n, m;
int cnt[maxn];
char str[maxn];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
memset(cnt, 0, sizeof cnt);
memset(str, 'B', sizeof str);
scanf("%d%d", &n, &m);
str[m] = 0;
for(int i = 0; i < n; i++)
{
int v; scanf("%d", &v);
v = min(v, m - v + 1); // v和m-v+1的操作选择是一样的，所以就取小的存下来
cnt[v]++; // 这里我用的桶存ai
}
for(int i = 1; i <= m; i++) // 实际上当i>m/2时cnt[i]就恒为0了
{
if(cnt[i]) str[i-1] = 'A'; // 优先把靠前的换为A
if(cnt[i] > 1) str[m - i] = 'A'; // 如果不止1次更换机会，就把靠后的也换掉
}
puts(str);
}
return 0;
}B题
题目大意
有一个长度为$n$的数列数列${c_i}$，其值为不超过$n$的正整数。
现在对每个$c_i$依次进行如下操作：
- 对$c_1$，你将它放在$(0,0)$点
- 对$c_i(2\le i\le n)$，记$c_{i-1}$放在了$(x,y)$点，则你可以将$c_i$放在$(x+1,y)$或$(x-1,y)$或$(x,y+1)$（但是不能放在$(x,y-1)$）当然前提是这些地方之前没有放置过其他的$c_i$
若对于某个$(x,y)$和某个$s$，若$(x,y),(x,y+1),\cdots,(x,y+s-1)$被放置了值相同的$c_i$，则定义这些点组成了一个“塔”。定义“塔”的高是$s$，“塔”被放置在了$(x,y)$处，“塔”的颜色为这些相同的$c_i$的值。
对于每一个不超过$n$的正整数$r$，独立的解决如下问题：
- 找到你能按规则构造出的，颜色为$r$的，高度最高的“塔”。
*本题有多组数据$(t \le 10^4)$，每组数据满足$n \le 10^5$，对于全部数据$\sum n \le 2 \cdot 10^5$
解析
注意到题目要求我们独立的处理每一个$r$而且只需要找出最高的“塔”，所以我们可以考虑对于固定的$r$，贪心的希望每个$r$都能刚好搭在上一个$r$上。抽象化的，记$c_i=c_j=r(i < j)$，什么情况下$c_i$和$c_j$可以组成一个“塔”呢？
进过简单的推理可以证明，当且仅当$(j-i)$为奇数时，$c_i$和$c_j$能构成一个“塔”。
必要性证明过程大致如下：
若$c_i$被放置在$(x,y)$处，则记$Q(c_i)=x+y$
则根据题意有$Q(c_{i+1})=x+y\pm1$，即$Q(c_{i+1}) \equiv Q(c_i) + 1 \ (mod\ 2)$
所以$Q(c_j) \equiv Q(c_i) + j - i \ (mod \ 2)$
因为$c_j$和$c_i$构成“塔”，所以$Q(c_j)-Q(c_i)=1$
于是有$j-i \equiv 1 \ (mod \ 2)$，即$(j-i)$是奇数
充分性证明略，因为只需要给出一个简单的构造，这里就留给读者吧~
那么当$(j-i)$是偶数的时候会发生什么情况呢？由于$c_i$下面可能已经成塔了，但是$c_j$并没有，所以当出现$c_k=r$而且$(k-i)$是奇数时（此时显然$(k-j)$也是奇数）将$c_k$放在$c_i$的上面为“塔”填一层楼是更优的。
因此本题只需要记录第一个$c_i=r$的$i$值，然后之后一旦碰见$c_j=c_i$而且$(j-i)$是奇数时就ans++即可。
最后可以看出，对于不同的$r$，我们可以同时进行计算，至此本题解决。
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define debug(x) cerr << #x << " = " << (x) << endl
const int maxn = 1e5 + 5;
int n, c[maxn], cnt[maxn], lst[maxn];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
lst[i] = -1;
cnt[i] = 0;
}
for(int i = 0; i < n; i++) scanf("%d", &c[i]);
for(int i = 0; i < n; i++)
{
if((i - lst[c[i]]) % 2 == 1 || lst[c[i]] == -1)
cnt[c[i]]++;
lst[c[i]] = i;
}
for(int i = 1; i <= n; i++)
{
printf("%d ", cnt[i]);
}
puts("");
}
return 0;
}C题
题目大意
给定长度为$n$的正整数列${h_i}$，你可以花费代价增大其中的值，每花费$1$点代价可以将一个$h_i$增大$1$。
描述$h_i$是“好看的”，当且仅当$i\neq 1$且$i\neq n$且$h_i > h_{i-1}$且$h_i > h_{i+1}$。
要求在保证整个数列“好看的”$h_i$最多的情况下花费的最小代价。
*本题有多组数据$(t \le 10^4)$，对于每组数据$3 \le n \le 10^5$，$h_i \le 10^9$，对于全部数据$\sum n \le 2 \cdot 10^5$
解析
首先肯定要考虑如何让“好看的”$h_i$最多。根据题意，“好看的”$h_i$无法连续出现，也不能出现在收尾，所以必然可以使得而且最多只能使得$\lfloor\frac{n-1}{2}\rfloor$个$h_i$成为“好看的”。而且当$n$是奇数时很容易解决，因为必然得是所有的$h_{2i}$都是“好看的”。所以接下来重点讨论当$n$是偶数的情况。
可以注意到，$n$是偶数时，必然存在一个$k$，使得$i<k$时，当$i$是偶数时$h_i$是“好看的”，当$i>k$时，当$i$是奇数时$h_i$是“好看的”。于是，我们可以考虑进行dp。
设dp[i]使得$h_i$是好看的前提下，保证前$i$个$h_i$中的“看好的”数最多，需要的最少花费，那么最终答案就是min(dp[n-2],dp[n-1])。下面考虑如何转移。进过我们之前的讨论，可以知道，当$i$是偶数时，前面一个好看的数必然是偶数，当$i$是奇数时则既可能是奇数有可能是偶数，于是转移方程如下：
int w = max(h[i-1], h[i+1]) - h[i] + 1; // w就是变成“好看的”的代价
if(w < 0) w = 0;
if(i & 1) dp[i] = min(dp[i-2], dp[i-3]) + w;
else dp[i] = dp[i-2] + w;最后需要注意一点，本题需要开long long
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define debug(x) cerr << #x << " = " << (x) << endl
const int maxn = 1e5 + 5;
int n, h[maxn];
long long ans, dp[maxn];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &h[i]);
if(n & 1)
{
for(int i = 2; i < n; i+=2)
{
int w = max(h[i-1], h[i+1]) - h[i] + 1;
if(w > 0) ans += w;
}
printf("%lld\n", ans);
continue;
}
dp[0] = dp[1] = 0;
for(int i = 2; i < n; i++)
{
int w = max(h[i-1], h[i+1]) - h[i] + 1;
if(w < 0) w = 0;
if(i & 1) dp[i] = min(dp[i-2], dp[i-3]) + w;
else dp[i] = dp[i-2] + w;
}
printf("%lld\n", min(dp[n-1], dp[n-2]));
}
return 0;
}D题
题目大意
给定长度为$n$的正整数列${a_n}$以及正整数$k$，寻找一个长度为$n$，值不超过$k$的正整数列${p_n}$，使得下面这个式子的值最小
$$
\max_{1 \le i \le n}(\lfloor\frac{a_i}{p_i}\rfloor)-\min_{1 \le i \le n}(\lfloor\frac{a_i}{p_i}\rfloor)
$$
最后题目只要求输出上面这个式子可能的最小值，不需要输出对应${p_n}$
*本题分为D1和D2，仅仅是数据范围不同
*D1范围：有多组数据$(t \le 100)$，对于每组数据$n,k,a_n \le 3000$，且保证${a_n}$单调不减，且对于全部数据$\sum n \le 3000$
*D2范围：有多组数据$(t \le 100)$，对于每组数据$n,k,a_n \le 10^5$，且保证${a_n}$单调不减，且对于全部数据$\sum n \le 10^5$
解析 1
先考虑D1怎么做，这里根据范围可以猜想存在$O(n^2)$的做法可以通过D1。显然遍历所有的${p_n}$是非常不现实的，因为复杂度将达到$O(k^n)$，十分恐怖。
观察要求的式子，如果我们令$M=\max_{1 \le i \le n}(\lfloor\frac{a_i}{p_i}\rfloor)$以及$m=\min_{1 \le i \le n}(\lfloor\frac{a_i}{p_i}\rfloor)$，则我们可以考虑遍历$M$（从$a_n$遍历到$\lfloor\frac{a_n}{k}\rfloor$），然后对于每个$M$尽可能的选取较大的$m$即可。具体做法如下：
对于固定$M$和每一个$a_i$，为了使得$m$最大，则必须让每个$\lfloor\frac{a_i}{p_i}\rfloor$尽量大，即$p_i$尽量小，即有$\lfloor\frac{a_i}{p_i}\rfloor \le M$但是$\lfloor\frac{a_i}{p_i-1}\rfloor > M$，如果记$a_i = kM + r(0\le r < M)$可以解出$p_i = k (0 \le r < k)$或者$p_i = k + 1 (k \le r < M)$。借此我们就可以以$O(n^2)$的复杂度过D1。
代码1
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define debug(x) cerr << #x << " = " << (x) << endl
const int maxn = 3e3 + 5;
const int inf = 1e9 + 7;
int n, k, a[maxn];
int ans;
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
if(a[n] / k == 0)
{
puts("0");
continue;
}
ans = inf;
for(int max_val = 3000; max_val >= 1; max_val--)
{
int min_val = inf;
for(int i = 1; i <= n; i++)
{
int p = a[i] / max_val;
if(p == 0 || a[i] / p > max_val) p++;
if(p > k) p = k;
if(a[i] / p > max_val) { min_val = inf; break; }
min_val = min(min_val, a[i] / p);
}
if(min_val <= max_val) ans = min(ans, max_val - min_val);
}
printf("%d\n", ans);
}
return 0;
}解析2
沿用D1的思路，但是我们希望可以在$O(log n)$的复杂度内找出给定$M$情况下的最大$m$。
要做到这一点，我们要先回过头来看看式子，$\lfloor\frac{a_i}{p_i}\rfloor \le M$但是$\lfloor\frac{a_i}{p_i-1}\rfloor > M$，但是这次我们不解出$p_i$而是反而解出$a_i$，于是有$(M+1)(p_i-1)\le a_i < (M+1)p_i$。由于对于相同的$p_i$当然是$a_i$越小才能影响到$m$的值，所以对于每一个$M$，遍历$p$（从1开始直到$(p+1)\cdot(M+1)>a_n$为止），然后对于每一个$p$，可以用二分的方式（因为$a_n$有序）找到第一个不小于$(M+1)(p_i-1)$的$a_i$，用$\lfloor\frac{a_i}{p}\rfloor$更新$m$（取min）。
于是复杂度来到了$O(\sum\frac{n}{i}log n)$，可以证明$O(\sum\frac{n}{i})=O(nlogn)$所以总的复杂度是$O(nlog^2n)$。但是这个复杂度并不是最优的（虽然对于1e5的数据已经足够了）。我们可以考虑预处理而非每次都二分来寻找$a_i$，这使得复杂度降到$O(nlogn)$。
代码2
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define debug(x) cerr << #x << " = " << (x) << endl
const int maxn = 1e5 + 5;
const int inf = 1e9 + 7;
int n, k, a[maxn];
int ans, max_val, min_val;
int great_min[maxn];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
if(a[n-1] / k == 0)
{
puts("0");
continue;
}
n = unique(a, a + n) - a; // 去重，显然重复的ai对本题无影响，当然这个语句本来也不是必须的
for(int i = 0, *p = a; i <= a[n-1]; i++)
{
if(*p < i) p++;
great_min[i] = *p; // 预处理，即great_min[x]表示不小于x的最小的ai
}
max_val = a[n-1], min_val = a[0];
ans = max_val - min_val;
while(max_val >= a[n-1] / k)
{
for(int i = 0; i * (max_val+1) <= a[n-1]; i++) // 这里i其实是遍历的(p-1)
{
min_val = min(min_val, great_min[i*(max_val+1)] / (i+1));
}
ans = min(ans, max_val - min_val);
max_val--;
}
printf("%d\n", ans);
}
return 0;
}E题
题目大意
给定一个$n$个点$m$条边的无向无权连通图，点编号从1到n，边编号从1到m。
给出$q$次询问，每次询问包括两个正整数$l$和$r$。你需要找到你一个最小的满足下列要求的$k$：
- 对任何满足$l \le a \le b \le r$的点对$(a,b)$，点$a$和点$b$可以只使用前$k$条边（即编号从1到k的边）的情况下连通
*本题有多组数据$(t \le 1000)$，对每个数据$n\le10^5$，$m,q\le2\cdot10^5$，对全部数据$\sum n\le10^5$，$\sum m,\sum q\le2\cdot10^5$
解析
本题第一眼看的时候有一种二分答案+可持续化并查集的感觉。然而可惜的是，每次询问不是检查两个点是否连通，而是检查一个区间是否连通。那么提到区间，就可以想到一种做法是倍增。而且我们惊人的发现两个区间的合并是如此的简单，只要有公共点，两个区间合并就是对$k$取max。于是问题转化为如何求得每两个相邻点的$k$。
转化到这个地步了，当然可以直接二份答案+可持续化并查集，可是复杂度将来到3个log，而且写起来还很麻烦，根本用不着。于是考虑只使用普通的并查集，而且不用路径压缩，而是改为启发式合并的并查集，这样做的好处就是每加一条边的时候，都只检查小集合里面的所有点有没有和相邻的点相连。复杂度是$O(nlogn)$。
于是本题总复杂度为$O(nlogn+nlogn+qlogn)$即$O((n+q)logn)$
代码
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define debug(x) cerr << #x << " = " << (x) << endl
const int maxn = 1e5 + 5;
const int c_pow2[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072 };
int n, m, q;
int fa[maxn];
int ans[maxn][20];
vector<int> forest[maxn];
inline int c_log2(int x)
{
return upper_bound(c_pow2, c_pow2 + 18, x) - c_pow2 - 1;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i++)
{
fa[i] = i;
ans[i][0] = -1;
vector<int>({i}).swap(forest[i]);
}
for(int i = 1; i <= m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
if(fa[v] == fa[u]) continue;
if(forest[fa[v]].size() > forest[fa[u]].size()) swap(u, v);
int fa_v = fa[v];
for(int x : forest[fa_v])
{
fa[x] = fa[u];
forest[fa[u]].push_back(x);
}
for(int x : forest[fa_v])
{
if(x != 1 && ans[x-1][0] == -1 && fa[x-1] == fa[x]) ans[x-1][0] = i;
if(x != n && ans[x][0] == -1 && fa[x+1] == fa[x]) ans[x][0] = i;
}
vector<int>().swap(forest[fa_v]);
}
vector<int>().swap(forest[fa[1]]);
for(int pk = 1; c_pow2[pk] < n; pk++)
{
for(int i = 1; i <= n; i++)
{
if(c_pow2[pk] + i > n) break;
ans[i][pk] = max(ans[i][pk-1], ans[i+c_pow2[pk-1]][pk-1]);
}
}
while(q--)
{
int l, r;
scanf("%d%d", &l, &r);
int pk = c_log2(r - l);
printf("%d ", max(ans[l][pk], ans[r-c_pow2[pk]][pk]));
}
puts("");
}
return 0;
}
