Codeforces Round 871 (Div. 4)
string t="codeforces"; void solve(){ string s; cin>>s; int ans=0; for(int i=0;i<10;i++){ if(s[i]!=t[i])ans++; } cout<<ans<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
void solve(){ int n=read(),ans=0,res=0; for(int i=1;i<=n;i++){ int x=read(); if(x==0){ res++; }else { ans=max(ans,res); res=0; } } ans=max(ans,res); cout<<ans<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
void solve(){ int n=read(),fla=0,flb=0,minna=inf,minnb=inf,both=0,minnboth=inf; for(int i=1;i<=n;i++){ int x=read(); int y=read(); if(y==1){ fla=1; minna=min(minna,x); } if(y==10){ flb=1; minnb=min(minnb,x); } if(y==11){ fla=1; flb=1; minnboth=min(minnboth,x); } } if(both||(fla&&flb)){ minnboth=min(minna+minnb,minnboth); cout<<minnboth<<'\n'; }else cout<<-1<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
void solve(){ int n=read(),m=read(),ans=0; priority_queue<int>pq; pq.push(n); while(pq.top()>=m&&pq.size()){ int x=pq.top(); // cout<<x<<'\n'; pq.pop(); if(x==m){ ans=1; break; } if(x%3==0&&x!=0){ int y=x/3; if(y>=m)pq.push(y); if(2*y>=m)pq.push(y*2); } } puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
int a[N][N],ans=0,vis[N][N],n,m,temp=0; bool check(int x,int y){ if(x<=n&&x>=1&&y<=m&&y>=1&&a[x][y]!=0&&vis[x][y]==0){ return true; }else return false; } void bfs(int x,int y){ queue<PII>q; q.push({x,y}); while(q.size()){ int xx=q.front().first,yy=q.front().second; temp+=a[xx][yy]; q.pop(); if(check(xx+1,yy))q.push({xx+1,yy}),vis[xx+1][yy]=1; if(check(xx-1,yy))q.push({xx-1,yy}),vis[xx-1][yy]=1; if(check(xx,yy+1))q.push({xx,yy+1}),vis[xx][yy+1]=1; if(check(xx,yy-1))q.push({xx,yy-1}),vis[xx][yy-1]=1; } // cout<<x<<" "<<y<<'\n'; // cout<<temp<<'\n'; } void solve(){ n=read(),m=read(); ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ a[i][j]=read(); vis[i][j]=0; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]!=0&&vis[i][j]==0){ vis[i][j]=1; temp=0; bfs(i,j); ans=max(ans,temp); } } } cout<<ans<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
int d[N]; map<int,int>mp; void solve(){ int n=read(),m=read(); mp.clear(); for(int i=1;i<=n;i++)d[i]=0; for(int i=1;i<=m;i++){ int x =read(),y=read(); d[x]++;d[y]++; } int x=-1,y=-1; for(int i=1;i<=n;i++){ if(d[i]>1){ mp[d[i]]++; if(mp[d[i]]>1){ y=d[i]-1; } } } for(int i=1;i<=n;i++){ if(d[i]>1&&d[i]!=y+1){ x=d[i]; } } if(x==-1)x=y+1; cout<<x<<" "<<y<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
G. Hits Different
题外记：vp的时候没想到怎么做 急着去吃午饭 结果刚下楼没几步就会了 最离谱的是回来一看vp还有6分钟结束 花三分钟写完过了这题
#define int long long int p[N],ans[N]; map<int,int>mp; void yuchuli(){ int cnt=1,now=0; for(int i=1;i<N;i++){ p[i]=cnt; now++; if(now==cnt){ cnt++; now=0; } } for(int i=1;i<N;i++){ int x=i-p[i]; if(p[x]==p[i]-1&&p[x+1]==p[i]-1){ ans[i]+=ans[x]+ans[x+1]-ans[x+1-p[x+1]]+i*i; } else if(p[x]==p[i]-1)ans[i]+=ans[x]+i*i; else if(p[x+1]==p[i]-1)ans[i]+=ans[x+1]+i*i; } } void solve(){ int n=read(); cout<<ans[n]<<'\n'; }
H. Don't Blame Me
数字最大只有63，主打一个穷举()
显然：上一个数字的状态可以原封不动的转移过来 因为我可以不选当前这个数
再显然：上一个数字的各个状态可以转移到当前的&a[i]状态 因为我在上一个状态可以&a[i]
#define int long long int a[N],dp[N][70]; void solve(){ int n=read(),k=read(),ans=0; for(int i=0;i<=n;i++){ for(int j=0;j<=64;j++){ dp[i][j]=0; } } for(int i=1;i<=n;i++){ a[i]=read(); dp[i][a[i]]++; for(int j=0;j<=64;j++){ (dp[i][j]+=dp[i-1][j])%=mod; (dp[i][j&a[i]]+=dp[i-1][j])%=mod; } } for(int i=0;i<=64;i++){ int temp=i,cnt=0; while(temp){ if(temp%2==1)cnt++; temp/=2; } if(cnt==k)(ans+=dp[n][i])%=mod; } cout<<ans<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }