基础练习（1）
1.Problem - 1728D - Codeforces
首先很好想到得是Bob是不可能赢的，这很好考虑。因为alice总是能把下一步更优的结果留给自己，这时候就可以考虑什么情况下是平局了。
平局的情况肯定是无论alice怎样选接下来的局面都是平局。那只有头尾一样的或者接下来必选的两个字符是连在一起的。所以直接考虑去掉头尾相等的再去掉连在一起的两个。这样最后如果可以保证最后可以把政哥字符串去掉即可
void slove(){
cin>>s;
int i=0,j=s.length()-1;
while(i<j){
if(s[i]==s[j]){
i++;
j--;
}
else break;
}
while(i<j){
if(s[i]==s[i+1]) i+=2;
else if(s[j]==s[j-1]) j-=2;
else break;
}
if(i<j){
cout<<"Alice"<<endl;
}
else cout<<"Draw"<<endl;
}
2.Problem - 5C - Codeforces
远古老题目。一开始想这不区间dp裸题。但是数据范围太大。然后考虑对可以匹配的点都标记一下。这时再考虑是不是只要是一段连续的1即可。一个左括号和一个右括号相匹配，如果中间的括号都不匹配这是不可能的因为你中间总会存在左右括号。而这样的括号应该是会被匹配掉的。所以只要找连续的1即可。
void slove(){
cin>>s;
stack<int>st;
int len=s.length();
for(int i=0;i<len;i++){
if(s[i]=='(') st.push(i);
else {
if(!st.empty()){
vis[st.top()]=1;
vis[i]=1;
st.pop();
}
}
}
s+=" ";
int w=0,ans=0,tot=0;
for(int i=0;i<=len;i++){
if(vis[i]) w++;
else{
ans=max(ans,w);
w=0;
}
}
for(int i=0;i<=len;i++){
if(vis[i]) w++;
else{
if(w==ans) tot++;
w=0;
}
}
if(ans){
cout<<ans<<" "<<tot<<endl;
}
else cout<<0<<" "<<1<<endl;
}
3.Problem - C - Codeforces
考虑每个贪心，每个数肯定是尽量去用最小约数去除掉。所以从小往大遍历i,如果碰到不能除掉的数就break。
void slove(){
cin>>n;
cin>>s;
s=" "+s;
int ans=0;
for(int i=1;i<=n;i++) vis[i]=0;
for(int i=1;i<=n;i++){
if(s[i]=='0'){
for(int j=i;j<=n;j+=i){
if(s[j]=='0'&&vis[j]==0){
//cout<<ans<<endl;
ans+=i;
vis[j]=1;
}
else{
if(s[j]=='1') break;
}
}
}
}
cout<<ans<<endl;
}
4.Problem - D - Codeforces
严格鸽的思路。
考虑为了出去，肯定是要尽量多往一个方向走。考虑往一个方向狂走，如果走不动了，那我在考虑从往这个方向走到的最大值往另外一个方向走，这样往另外一个方向肯定也是会走更远的。最后如果走出来即可。
void slove(){
cin>>n>>k;
fel(i,1,n) cin>>a[i];
int suml,mxl,sumr,mxr;
suml=mxl=sumr=mxr=0;
int l=k-1,r=k+1;
while(l>=1&&r<=n){
int flag=1;
while(l>=1&&a[k]+mxr+suml+a[l]>=0){
flag=0;
suml+=a[l--];
mxl=max(mxl,suml);
}
while(r<=n&&a[k]+mxl+sumr+a[r]>=0){
flag=0;
sumr+=a[r++];
mxr=max(mxr,sumr);
}
if(flag) break;
}
if(l<1||r>n) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
5.Problem - 1680C - Codeforces
两种写法都值得写一些。
1.二分
可以考虑二分答案，然后枚举每个l可以对应的最右边的r。看是否可以在区间内0的个数满足条件，区间外1的个数也满足条件。
bool check(int x){
for(int l=1,r=0;l<=len;l++){
while(sum1[r]-sum1[l-1]<=x&&r<=len) r++;
r--;
if(sum2[l-1]+sum2[len]-sum2[r]<=x) return 1;
}
return 0;
}
void slove(){
cin>>s;
len=s.length();
s=" "+s;
for(int i=1;i<=len;i++){
sum1[i]=sum1[i-1]+(s[i]=='0');
sum2[i]=sum2[i-1]+(s[i]=='1');
}
int l=0,r=len,ans=0;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<endl;
}
2.滑动窗口
这个就稍微推了一个性质
就是最佳结果肯定是删除的1=剩下的0 剩下的数=剩0+剩1 =删1+剩1=tot(1) 所以就直接维护一个大小为tot(1)的窗口
void slove(){
cin>>s;
int n=s.size();
int cnt1=0;
for(auto i:s) cnt1+=(i=='1');
//cout<<cnt1<<endl;
int out1=cnt1,in0=0;
for(int i=0;i<cnt1;i++){
if(s[i]=='0') in0++;
else out1--;
}
int ans=max(in0,out1);
for(int i=cnt1;i<n;i++){
//前端
if(s[i]=='0') in0++;
else out1--;
if(s[i-cnt1]=='0') in0--;
else out1++;
ans=min(ans,max(in0,out1));
}
cout<<ans<<endl;
}
6.Problem - B - Codeforces
二分时间看是否向左走的最大位置是否与向右走的最小位置重合。
考虑只可能出现在0.5的位置所以直接*2然后最后是奇数输出即可。
bool check(int p){
int L=0,R=2e10;
for(int i=1;i<=n;i++){
if(p>t[i]){
L=max(a[i]-(p-t[i]),L);
R=min(a[i]+(p-t[i]),R);
}
else {
L=max(a[i],L);
R=min(a[i],R);
}
}
return R>=L;
}
void slove(){
n=read();
fel(i,1,n) a[i]=read(),a[i]=a[i]*2;
fel(i,1,n) t[i]=read(),t[i]=t[i]*2;
int l=-1,r=2e9;
while(r-l>1)
{
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid;
}
int p=r,L=0,R=2e9;
for(int i=1;i<=n;i++){
if(p>t[i]){
L=max(a[i]-(p-t[i]),L);
R=min(a[i]+(p-t[i]),R);
}
else {
L=max(a[i],L);
R=min(a[i],R);
}
}
cout<<L/2;
if(L%2!=0){
cout<<".5";
}
cout<<endl;
}
7.Problem - C - Codeforces
首先考虑取最大的肯定win，然后如果最大的在对面手里，次大的在自己手里。这个时候就相当于换了一个先手顺序。所以直接考虑2*n-2的情况，考虑后手赢得情况递归解决。
void slove(){
int n;
cin>>n;
n/=2;
cout<<f[n]<<" "<<(c[2*n][n]-f[n]-1+mod)%mod<<" "<<1<<endl;
}
signed main(){
for(int i=0;i<=60;i++){
for(int j=0;j<=i;j++){
if(!j) c[i][j]=1;
else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
f[1]=1;
for(int i=2;i<=30;i++){
f[i]=(c[2*i-1][i-1]+(c[2*i-2][i-1]-f[i-1]-1+mod)%mod)%mod;
}
IOS
int t;
cin>>t;
while(t--){
slove();
}
return 0;
}
8.Problem - D - Codeforces
是个二分.
考虑二分最小的深度。那如何判断这个深度是否可行呢？考虑用dp, dp[u]代表需要的理想深度。然后递归去求子树的理想深度。最后可以得到这个点需要的最小深度。自然把这点接到1上面是最优的。所以考虑只把dp[u]=1的点移动走。这样他的子树也是全部满足条件的。
void dfs(int x,int fa){
dp[x]=mx;
for(auto i:b[x]){
dfs(i,x);
dp[x]=min(dp[x],dp[i]-1);
}
if(dp[x]==1&&x!=1&&fa!=1){
cnt++;
dp[x]=mx+1;//更新一下这个点修改过就不会影响他的父节点了
}
}
bool check(int mid){
mx=mid,cnt=0;
dfs(1,0);
return cnt<=k;
}
void slove(){
cin>>n>>k;
for(int i=1;i<=n;i++) b[i].clear();
for(int i=2;i<=n;i++){
int t;
cin>>t;
b[t].pb(i);
}
int l=1,r=n,ans=inf;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) ans=min(ans,mid),r=mid-1;
else l=mid+1;
}
cout<<ans<<endl;
}
9.Problem - 1720C - Codeforces
题目其实很蠢。
很容易想到第一次才是有可能消耗更多个1。直接考虑四个格子如何消耗更少的1即可。
void slove(){
cin>>n>>m;
fel(i,0,n+1){
fel(j,0,m+1){
mp[i][j]=' ';
}
}
int cnt1=0;
fel(i,1,n) {
fel(j,1,m) {
cin>>mp[i][j];
cnt1+=(mp[i][j]-'0');
}
}
//cout<<cnt1<<endl;
int mi=inf;
fel(i,2,n){
fel(j,2,m){
int sum=mp[i][j]-'0'+mp[i-1][j-1]-'0'+mp[i-1][j]-'0'+mp[i][j-1]-'0';
if(sum==0) continue;
if(sum==1) mi=min(mi,1ll);
if(sum==2) mi=min(mi,1ll);
if(sum==3) mi=min(mi,2ll);
if(sum==4) mi=min(mi,3ll);
}
}
if(cnt1==0){
cout<<0<<endl;
}
else{
cout<<cnt1-mi+1<<endl;
}
}
10.Problem - C - Codeforces
经验：cf这输出yes，no的一般都是判断无解条件。
a[i] > b[i]肯定无解，如果a[i] = b[i]肯定可行
让后考虑小的情况，如果a[i] < b[i]
$$最大的a[i]=a[i+1]+1=b[i+1]+1>=b[i]所以b[i+1]+1<b[i]肯定无解
$$
那b[i+1] + 1 >= b[i]就一定有解吗？
是肯定的。首先考虑有一个a[i] = b[i]了，b[i] + 1 >= b[i-1]得到a[i] + 1>=b[i-1]那a[i-1] 肯定是可以变成b[i-1]了
但是怎样确定又一定有一个a[i] = b[i]呢？考虑选一个最大值a[i]，你是可以从这个最大值一路往上加的，所以每一个点都是可以变成无限大的。这样肯定是可以产生一个相等的项。
void slove(){
cin>>n;
fel(i,1,n) cin>>a[i];
fel(i,1,n) cin>>b[i];
b[n+1]=b[1];
fel(i,1,n){
if(a[i]>b[i]){
cout<<"NO"<<endl;
return;
}
if(a[i]!=b[i]&&b[i+1]+1<b[i]){
cout<<"NO"<<endl;
return;
}
}
cout<<"YES"<<endl;
}
标签：cout,int,mid,练习,基础,cin,else,ans
From： https://www.cnblogs.com/silky----player/p/16774184.html