A. Monsters (easy version)
题意：有 \(n\) 个怪物，每个有 \(a_i\) 滴血，每次可以选择一个怪物减一滴血，也可以“让所有怪物减一滴血，且如果杀死怪物则重复操作”。其中，第二种攻击只能使用一次。问杀死所有怪物，使用第一种攻击的最小次数。
显然要让第二种攻击发挥最大效果，就要让所有怪物的血量连续，一次杀掉所有怪物。可以从小到大排序后依次考虑每个怪物，如果扫到一个怪物的血量比目前连续的最大血量高，则攻击到最大血量\(+1\)。
By Mr_Eight
int n,a[200002];
int main() {
F(adsf,1,read()){
cin>>n;
F(i,1,n)read(a[i]);
sort(a+1,a+n+1);
int now=0;
ll ans=0;
F(i,1,n){
++now;
now=min(now,a[i]);
ans+=a[i]-now;
}
write(ans,'\n');
}
return 0;
}
B. Letter Exchange
题意：有 \(n\) 个人和 \(3\) 种卡片，每种各 \(n\) 张。每人初始有 \(3\) 张卡片，每次操作可以让两人各处一张卡片互换。问让每人都集齐 \(3\) 种卡片的最小操作数，输出方案。
可以将每个人拥有卡片的情况存到 \(vector\) 里，其中 \(v[i][j]\) 存所有多了 \(i\) 且少了 \(j\) 的人的编号。对于 \(000\) 类型的人，在 \(v[0][1]\) 和 \(v[0][2]\) 中各出现一次即可。
显然应该尽可能多地让 \(v[i][j]\) 和 \(v[j][i]\) 的人互换，且所有互换相互独立，直接处理即可。剩下的人一定不存在长度为 \(2\) 的交换环，所以考虑长度为 \(3\) 的，即 \(v[i][j],v[j][k],v[k][i]\)。这里只需要两次交换即可归位，且与外界独立。将两个方向的交换环分别处理即可。由于一共只有三种卡片且每种 \(n\) 张，经过这两步一定可以归位。
By maroonrk
const string win="win";
void slv(){
int n;cin>>n;
vi g[3][3];
rep(i,n){
string s;cin>>s;
int cnt[3]{};
for(auto c:s){
cnt[win.find(c)]++;
}
vi u,v;
rep(j,3)if(cnt[j]==0){
v.pb(j);
}else{
rep(_,cnt[j]-1)u.pb(j);
}
assert(si(u)==si(v));
rep(j,si(u)){
g[u[j]][v[j]].pb(i);
}
}
vc<tuple<int,int,int,int>> ans;
rep(i,3)rep(j,i){
while(si(g[i][j])&&si(g[j][i])){
auto x=g[i][j].back();g[i][j].pop_back();
auto y=g[j][i].back();g[j][i].pop_back();
ans.eb(x,y,i,j);
}
}
auto work=[&](int i,int j,int k){
assert(si(g[i][j])==si(g[j][k]));
assert(si(g[i][j])==si(g[k][i]));
while(si(g[i][j])){
auto x=g[i][j].back();g[i][j].pop_back();
auto y=g[j][k].back();g[j][k].pop_back();
auto z=g[k][i].back();g[k][i].pop_back();
ans.eb(x,y,i,j);
ans.eb(y,z,i,k);
}
};
work(0,1,2);
work(0,2,1);
print(si(ans));
for(auto [x,y,i,j]:ans){
cout<<x+1<<" "<<win[i]<<" "<<y+1<<" "<<win[j]<<"\n";
}
}
C. Monsters (hard version)
题意：杀敌的方式与 A 题相同，区别在于对于每个 \(k\)，要求出假设只有前 \(k\) 个怪物时的最小次数。
做法一
可以倒序考虑。首先像第一题一样处理出所有 \(n\) 个怪物的方案，并把“没有发挥作用的”扔到 multiset 里。
从后往前依次删除怪物，维护当前“连续”到多少（假设为 \(x\)），以及所有“发挥作用”的怪物血量之和（\(sum\)）。答案即为 \(sum-\frac{x(x+1)}{2}\)。
当删除一个怪物时，如果存在“没有发挥作用的”血量值相同的怪物，则直接从 multiset 里删除一个即可，答案不会改变。否则，这个怪物是发挥作用的怪物。将其删掉后 \(sum\) 减去该血量。\(x\) 是否要减去 \(1\) 呢？如果该血量之后存在一个最近的没有发挥作用的怪物，则其会变为发挥作用（从 multiset 中删掉），从而导致连续的长度不变。如果该血量之后所有怪物都已经发挥作用，则连续的长度会减小（\(x\) 减去 \(1\)）。
By fireskydd
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k,a[200004];ll b[200004];
multiset<int>s;ll ans;
void sol(){
scanf("%d",&n),s.clear(),ans=0,k=0;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),s.insert(a[i]);
for(;;){
k++;auto it=s.lower_bound(k);
if(it==s.end()){k--;break;}
ans+=*it,s.erase(it);
}
for(int i=n;i;i--){
b[i]=ans-(ll)k*(k+1)/2;
auto it=s.lower_bound(a[i]);
if(it!=s.end()&&*it==a[i])s.erase(it);
else{
ans-=a[i];
if(it==s.end())k--;
else ans+=(*it),s.erase(it);
}
}
for(int i=1;i<=n;i++)printf("%lld ",b[i]);puts("");
}
int main(){
int tc;scanf("%d",&tc);
while(tc--)sol();
}