Atcoder Beginner Contest 426 A-D 题解

A

CODE

#include<bits/stdc++.h>
#define usetime() (double)clock () / CLOCKS_PER_SEC * 1000.0
using namespace std;
typedef long long LL;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=(x<<3)+(x<<1)+c-48;x=(f ? -x : x);
}
string x,y;
int a,b;
int main(){cin>>x>>y;if(x=="Ocelot") a=1;else if(x=="Serval") a=2;else a=3;if(y=="Ocelot") b=1;else if(y=="Serval") b=2;else b=3;if(a>=b) printf("Yes");else printf("No");return 0;
}
//^o^

B

CODE

#include<bits/stdc++.h>
#define usetime() (double)clock () / CLOCKS_PER_SEC * 1000.0
using namespace std;
typedef long long LL;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=(x<<3)+(x<<1)+c-48;x=(f ? -x : x);
}
string s;
map<char,int> mp;
int main(){cin>>s;for(int i=0;i<(int)s.size();i++) ++mp[s[i]];for(auto i=mp.begin();i!=mp.end();i++){if(i->second==1){cout<<i->first;return 0;}}return 0;
}
//^o^

C

考虑某个级别以下的电脑全部升级后，这个以下就没有电脑了

所以可以尝试维护一个下界，表示最低级别电脑的级别

那么我们可以用桶来实现，以 \(t_i\) 表示级别为 \(i\) 的电脑有多少台

每次操作区间查询级别在 \([1,x]\) 的电脑数量，将其加到就级别为 \(y\) 的桶当中

因为维护了一个下界，下界中的级别都没有电脑，所以只需要每次更新下界，不需要进行区间归零操作

至此，我们需要一个支持区间求和，单点修改的数据结构，树状数组是写起来最快，最简单的

CODE

#include<bits/stdc++.h>
#define usetime() (double)clock () / CLOCKS_PER_SEC * 1000.0
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=(x<<3)+(x<<1)+c-48;x=(f ? -x : x);
}
int n,q;
int lowbit(int x){return x&(-x);
}
int f[maxn],lim=0;
void add(int x,int p){for(int i=x;i<=n;i+=lowbit(i)){f[i]+=p;}
}
int query(int x){int ans=0;for(int i=x;i>=1;i-=lowbit(i)){ans+=f[i];}return ans;
}
int t[maxn];
int main(){read(n),read(q);for(int i=1;i<=n;i++) add(i,1);int x,y;while(q--){read(x),read(y);if(x<=lim){printf("0\n");continue;}printf("%d\n",query(x)-query(lim));add(y,query(x)-query(lim));lim=x;//for(int i=1;i<=n;i++) cout<<query(i)-query(i-1)<<' ';//cout<<endl;}return 0;
}
//^o^

D

设转换的目标颜色为 \(x\)

则可以把不同与 \(x\) 的转换为 \(x\) 后集中到一起

此时集中到连续 \(x\) 最多的地方一定最优

其余相同与 \(x\) 的且不在集中地的则需要被连续转换两次，以放到正确位置

分别计算 \(x=0\) 和 \(x=1\) 时的值，取最小值即可

CODE

#include<bits/stdc++.h>
#define usetime() (double)clock () / CLOCKS_PER_SEC * 1000.0
using namespace std;
typedef long long LL;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=(x<<3)+(x<<1)+c-48;x=(f ? -x : x);
}
int t,n;
string s;
int main(){read(t);while(t--){read(n);cin>>s;s.push_back('^');int cnt0=0,cnt1=0,mx0=0,mx1=0;int p0=0,p1=0;for(int i=0;i<(int)s.size()-1;i++){cnt0+=(s[i]=='0'),cnt1+=(s[i]=='1');p0+=(s[i]=='0'),p1+=(s[i]=='1');if(s[i]!=s[i+1]){mx0=max(mx0,p0),mx1=max(mx1,p1);p0=p1=0;}}printf("%d\n",min((cnt0-mx0)*2+cnt1,(cnt1-mx1)*2+cnt0));}return 0;
}
//^o^