\(A. Two Vessels\)
一开始我以为那个 \(c\) 桶只能装满，看了好久。
范围内的任意容量都可以取的话，那么只要看需要转移多少量，然后看需要多少次。
void solve(){
int n=read(),m=read(),k=read();
double nd=abs(n-m)*1.0/2;
int ans=ceil(nd/k);
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(B. The Corridor or There and Back Again\)
计算每个房间走过之后能最多向后走几个房间，向后遍历的时候取最小值。
void solve(){
int n=read();
vector<int>a(10000,inf);
for(int i=1;i<=n;i++){
int x=read(),y=read();
a[x]=min((y-1)/2,a[x]);
}
int now=inf;
for(int i=1;i<=10000&&i<=now;i++){
now=min(a[i]+i,now);
}
cout<<now<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(C. Non-coprime Split\)
如果一个数能被整除，就可以被分成这么多份，那么只要每份的个数大于 \(1\) 就可以做到题目要求的 \(gcd\ne1\) 。
void solve(){
int l=read(),r=read();
for(int i=l;i<=r;i++){
int x=i;
for(int j=2;j*j<=x;j++){
if(x%j==0){
cout<<x/j<<" "<<x-x/j<<'\n';
return ;
}
}
}
cout<<-1<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(D. Plus Minus Permutation\)
肯定把最大值放在加的地方，最小值放在减的地方，不知道知道的只有放多少个。
显然能起作用的加数是 \(n/x-n/lcm(x,y)\) ，减数同理。
知道个数之后只需要求和即可。
int get_sum(int x,int y){
return (x+y)*(y-x+1)/2;
}
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
void solve(){
int n=read(),a=read(),b=read();
int g=a*b/(gcd(a,b));
b=n/b-n/g;
a=n/a-n/g;
int ans=get_sum(n-a+1,n);
ans-=get_sum(1,b);
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(E. Data Structures Fan\)
每次修改都是直接异或上区间和就行了，那么修改和查询的复杂度都是 \(O(1)\) 。
int sum[N],a[N];
void solve(){
int n=read(),ans0=0,ans1=0;
for(int i=1;i<=n;i++){
a[i]=read();
}
string s;
cin>>s;
s=' '+s;
for(int i=1;i<=n;i++){
if(s[i]=='0')ans0^=a[i];
else ans1^=a[i];
}
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]^a[i];
}
int q=read();
while(q--){
int op=read();
if(op==1){
int x=read(),y=read();
int chg=sum[y]^sum[x-1];
ans1^=chg;
ans0^=chg;
}else{
int x=read();
if(x==0)cout<<ans0<<' ';
else cout<<ans1<<' ';
}
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(F. Selling a Menagerie\)
如果把入度为 \(0\) 的点不断删掉，那么将会变成一个基环图，而且先删掉这样的点肯定是最优的。
对于一个环，可以有一个点被计算一次，其他点计算两次，显然选择最小的点计算一次，用优先队列跑一下。
void solve(){
int n=read();
vector<int>a(n+1),r(n+1),o(n+1),fa(n+1),vis(n+1);
vector<int>res;
for(int i=1;i<=n;i++){
int x=read();
fa[i]=x;
r[x]++;
o[i]++;
}
for(int i=1;i<=n;i++)a[i]=read();
int ans=0;
for(int i=1;i<=n;i++){
if(r[i]==0&&vis[i]==0){
r[fa[i]]--,ans+=a[i],vis[i]=1,res.push_back(i);
int nex=fa[i];
while(r[nex]==0){
r[fa[nex]]--,ans+=a[nex],vis[nex]=1,res.push_back(nex);
nex=fa[nex];
}
}else pq.push(make_pair(a[i],i));
}
while(pq.size()){
int x=pq.top().first,y=pq.top().second;
pq.pop();
if(vis[y]){
continue;
}
ans+=x;
int nex=fa[y];
while(vis[nex]==0){
ans+=a[nex]*2;
res.push_back(nex);
vis[nex]=1;
nex=fa[nex];
}
} for(auto x:res){
cout<<x<<" ";
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}