Codeforces Round #782 (Div. 2)
2022/4/18 23:16:38
本文主要是介绍Codeforces Round #782 (Div. 2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
两个 E,两个印度人。
\(\texttt{Rating Change:}\color{grey}{683}\color{black}\to \color{green}{1205}\)
\(\Delta={\color{green}{\texttt{522}}}\qquad \texttt{rank:285}\)
A
由于题目保证了红色一定大于蓝色,所以直接算在 \(b+1\) 个空隙中把红色均匀插入就可以了。然后模拟一遍输出。
My Code
void solve(){ int n,r,b;cin>>n>>r>>b; int num=r/(b+1); int rem=r%(b+1); if(0<rem){ rep(j,1,num+1) cout<<"R"; }else{ rep(j,1,num) cout<<"R"; } rep(i,1,b){ cout<<"B"; if(i<rem){ rep(j,1,num+1) cout<<"R"; }else{ rep(j,1,num) cout<<"R"; } }cout<<'\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T;for(cin>>T;T--;) solve(); return 0; }
B
首先讨论 \(k\) 的奇偶性。如果是奇数,我们可以考虑把序列 01 翻转来把 \(k\) 变成偶数,这是合法的。接下来,每次对一个数操作相当于在最后的时候是翻转了它的二进制位的,所以从高到低翻转 \(0\) 就可以了。最后的时候如果 \(k\) 还有多,那就疯狂翻最低位一定是最优的。
My Code
const int MAXN=2e5+10; int cnt[MAXN]; void solve(){ int n,k;cin>>n>>k; rep(i,1,n) cnt[i]=0; string b;cin>>b; if(k&1) rep(i,0,n-1) b[i]=(b[i]=='1'?'0':'1'); rep(i,0,n-2) if(b[i]=='0'&&k) k--,b[i]='1',cnt[i+1]++; cnt[n]=k;if(k&1) b[n-1]=(b[n-1]=='1'?'0':'1'); cout<<b<<'\n'; rep(i,1,n) cout<<cnt[i]<<' ';cout<<'\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T;for(cin>>T;T--;) solve(); return 0; }
C
给你一个数轴上若干个点,你的起点初始为 \(0\),每个点初始是白色的,然后你需要把每个点染黑,代价是 \(b\times |s-t|\)。或者你可以改变你的起点到任意一个黑色的点,代价是 \(a\times |s-t|\)。求最终每个点都染黑的最小代价。
最直观的感受一定是你先染第一个点,然后把这个点定为你的起点。考虑什么情况会比这样子做更优。就是我们一定是到某一个位置就不改起点了,那么后面的点就全部要通过重新跑一遍来染色。预处理一下就可以啦。
My Code
const int MAXN=2e5+10; int x[MAXN],sum[MAXN],cur[MAXN]; void solve(){ int n,a,b;cin>>n>>a>>b; rep(i,1,n) cin>>x[i],sum[i]=cur[i]=x[i]-x[i-1],sum[i]=sum[i]*(a+b); rep(i,2,n) sum[i]+=sum[i-1];int now=0,ans=INF; per(i,n,1) now+=cur[i]*(n-i+1)*b,ans=min(ans,now+sum[i-1]); cout<<ans<<'\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T;for(cin>>T;T--;) solve(); return 0; }
D
首先容易想到,\(a\) 的和除以 \(n\) 就是 \(b\) 中 \(1\) 的个数对吧。如果我们确定当前位,那么我们就能知道前缀中 \(1\) 的数量是怎么变的。接下来,我们在后缀的 \(k\) 个中减去 \(1\),表示最后一次排序给序列带来的结果。然后我们每次考察一个位置是否等于 \(0\) 就能知道当前位是 \(0\) 还是 \(1\) 了。一个后缀中减去可以转化成前缀加然后判断是否和 \(a\) 相等,树状数组即可。
My Code
const int MAXN=2e5+10; struct BIT{ int tr[MAXN],n; void init(int len){rep(i,0,len) tr[i]=0;n=len;} int lbt(int x){return x&(-x);} void upd(int x,int v){for(;x<=n;x+=lbt(x))tr[x]+=v;} int ask(int x){int ret=0;for(;x;x-=lbt(x))ret+=tr[x];return ret;} }Tr; int a[MAXN],ans[MAXN]; void solve(){ int n,sum=0;cin>>n; rep(i,1,n) cin>>a[i],sum+=a[i]; Tr.init(n);sum/=n;Tr.upd(n-sum+1,1); per(i,n,2){ int cur=Tr.ask(i); if(cur^a[i]) ans[i]=1,sum--; else ans[i]=0; if(i^sum) Tr.upd(i-sum,1); }ans[1]=sum; rep(i,1,n) cout<<ans[i]<<' ';cout<<'\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T;for(cin>>T;T--;) solve(); return 0; }
E
神奇的简单题/qd。容易发现答案只能是 \(0\) 或者 \(1\) 或者 \(2\)。然后考虑 \(0\) 的情况,你对每个二进制位维护一个并查集然后查连通性就可以了。考虑 \(1\),既然不是 \(0\),那我们就只要判断中间会不会出现 \(1\)。也很好做,你考虑路径一定是这样的:先是一段与和为奇数的非 \(1\),然后是一段与和为偶数的,由于 \(mex\) 不是 \(0\),所以这样一定会出现 \(0\) 而不出现 \(1\)。所以我们需要维护联通块是边权为奇数的并且 \(i\) 位都是 \(1\) 的,并查集即可。
My Code
const int MAXN=1e5+10; int ok[MAXN]; struct dsu{ int f[MAXN]; int find(int x){while(x^f[x])x=f[x]=f[f[x]];return x;} void merge(int x,int y){if(find(x)^find(y))f[find(x)]=find(y);} }D[35],C[35]; int sok[35][MAXN]; int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n,m;cin>>n>>m; rep(i,1,n) rep(b,0,30) D[b].f[i]=i,C[b].f[i]=i; rep(i,1,m){ int u,v,w;cin>>u>>v>>w; rep(b,0,30) if(w&(1<<b)) D[b].merge(u,v); if(w%2==0) ok[u]=ok[v]=1; else rep(b,1,30) if(w&(1<<b)) C[b].merge(u,v); } rep(i,1,n) if(ok[i]) rep(b,1,30) sok[b][C[b].find(i)]=1; int Q,u,v;cin>>Q; while(Q--){ cin>>u>>v; int ans=2; rep(b,0,30) if(D[b].find(u)==D[b].find(v)) {ans=0;break;} if(ans==2){ rep(b,1,30) if(sok[b][C[b].find(u)]) {ans=1;break;} } cout<<ans<<'\n'; } return 0; }
F
牛逼博弈,不会。
这篇关于Codeforces Round #782 (Div. 2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23增量更新怎么做?-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些?-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码?-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗?-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行?-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处?-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用?-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表?-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享