冒个泡。
B
注意到要求 \ge x 的数字出现次数 \ge x，所以答案至多为 100(1\le N\le 100)，二分或枚举均可。
int main(){
read(n);
for(int i = 1;i <= n;i ++) read(a[i]);
sort(a + 1,a + n + 1);
for(int i = 1;i <= 200;i ++){
if(n - (lower_bound(a + 1,a + n + 1,i) - a - 1) >= i) ans = i;
}
printf("%d\n",ans);
return 0;
}
C
能形成等边三角形的三个点 x,y,z，肯定有 y=x+L/3,z=y+L/3。判掉 L 不是 3 的倍数（这样形不成等边），做个桶即可。
int main(){
read(n),read(l);
if(l % 3){
printf("0\n");
return 0;
}
cnt[now = 1] = 1;
for(int i = 1;i < n;i ++){
read(d[i]);
now = (now + d[i] - 1 + l) % l + 1;
cnt[now] ++;//统计每个位置的点的个数
}
for(int i = 1;i <= l / 3 + 1;i ++){//枚举编号最小的那个点
ans += 1ll * cnt[i] * cnt[i + l / 3] * cnt[i + 2 * l / 3];
}
printf("%lld\n",ans);
return 0;
}
D
贪心。
我们要操作使得字典序变小，那么选择的 l 一定满足 s_l>s_{l+1}，这样右移之后字典序会变小。由于字典序先取决于靠左的位置，所以选择的 l 是满足上式的最小的 l。
使得字典序变小，那 s_l 要向右跨过一串比它小的字符，然后停留在一个比它大的字符的左边。
判掉一些边界（$l$ 不存在，以及把 s_l 移到最右边）即可。时间复杂度 O(\sum N)。
int main(){
read(T);
while(T --){
read(n),l = 0;
scanf("%s",s + 1);
for(int i = 1;i < n;i ++){if(s[i] > s[i + 1]){l = i;break;}}//贪心选择 l
if(l){
r = n;//有把 s[l] 移到最右边的情况
for(int i = l;i <= n;i ++){if(s[i] > s[l]){r = i - 1;break;}}//贪心选择 r
for(int i = 1;i < l;i ++) printf("%c",s[i]);
for(int i = l + 1;i <= r;i ++) printf("%c",s[i]);
printf("%c",s[l]);
for(int i = r + 1;i <= n;i ++) printf("%c",s[i]);
}
else for(int i = 1;i <= n;i ++) printf("%c",s[i]);//特判不操作
printf("\n");
}
return 0;
}
E
贪心。
策略：随便选一个根，令 s 为 x 的子树和，那么除去根结点外每个点 u 向父亲转移 \vert s_u\vert 大小的电荷。
这样做显然能消掉所有电荷，最优性也显而易见，(u,\text{father}_u) 这条路上最少就要传输 \vert s_u\vert 的电荷，不然怎么把 u 子树内的电荷消掉呢。时间复杂度 O(N)。
vector<pair<int,int>>e[N];
void sch(int u,int fa){
s[u] = x[u];
for(auto [v,w] : e[u]) if(v != fa) sch(v,u),s[u] += s[v],ans += abs(1ll * w * s[v]);
}
int main(){
read(n);
for(int i = 1;i <= n;i ++) read(x[i]);
for(int i = 1;i < n;i ++){
read(u),read(v),read(w);
e[u].eb(v,w),e[v].eb(u,w);
}
sch(1,0);
printf("%lld\n",ans);
return 0;
}
F
看到合并和查询是否同集先敲个并查集上去。
每次操作要合并掉距离最近的一些点对，点对之间的距离又是不变的，所以考虑用一个优先队列去存储点对，排序关键字是点对距离，每次加点把它和所有已有的点构成点对丢入，操作 2 就从队头取出一批距离相同的点（注意要忽略已经在同一个并查集中的点对）。时间复杂度 O((N+Q)^2\log N)。
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>>q;
int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
int main(){
read(n),read(m);
for(int i = 1;i < N;i ++) f[i] = i;
for(int i = 1;i <= n;i ++) read(x[i]),read(y[i]);
for(int i = 1;i < n;i ++) for(int j = i + 1;j <= n;j ++) q.ep(abs(x[i] - x[j]) + abs(y[i] - y[j]),i,j);
for(int i = 1;i <= m;i ++){
read(op);
if(op == 1){
read(u),read(v),n ++;
x[n] = u,y[n] = v;
for(int i = 1;i < n;i ++) q.ep(abs(x[i] - u) + abs(y[i] - v),i,n);
else if(op == 2){
ans = -1;
while(q.size()){
auto [a,b,c] = q.top();
if(~ans && (ans ^ a)) break;
q.pop();
if(find(b) ^ find(c)) f[find(b)] = find(c),ans = a;
}
printf("%d\n",ans);
}
else{
read(u),read(v);
if(find(u) == find(v)) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
还是个招笑卡常题，一开始用 map+vector T 了两发。