Educational Codeforces Round 116 (CF1606)
2021/10/31 6:10:33
本文主要是介绍Educational Codeforces Round 116 (CF1606),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A
2s
Problem
给一个'a','b'组成的字符串 \(s\) ,每次修改可以把某个'a'改成'b'或把'b'改成'a',要求修改尽量少的次数使得 \(s\) 中 "ab"和"ba"子串的出现次数相等。输出修改后的 \(s\)。
Solution
\(s\) 可以看作由若干"aa...a"和"bb...b"拼接而成,若首尾都是'a'或都是'b'则"ab"和"ba"出现次数一定相同,否则需要把首位改成和末位相同的字母。
Code
cin>>s; s[0]=s[s.size()-1]; cout<<s;
B
2s
Problem
有 \(n\) 台电脑,开始时只有第一台电脑上有文件。
每秒钟可以使用数据线把两台电脑连起来(每台电脑只能插一条线),然后就可以把文件从一台电脑拷到另一台。但是只有 \(k\) 根线,也就是说至多同时拷 \(k\) 个文件。
给定 \(n,k\) 问最少需要多少秒可以全拷上文件。
Solution
当有文件的电脑数量不超过 \(k\) 时,每秒钟乘 \(2\)。
当有文件的电脑数量超过 \(k\) 时,每秒钟加 \(k\)。
所以直接 \(O(\log k)\) 模拟第一步,剩余的除以 \(k\) 上取整即可。
C
2s
Problem
有n种纸币,第i种的面额是 \(10^{a_i}\) (保证\(a_1=0\))
f(s)表示 支付s元至少需要多少纸币(如有1元,10元,100元时,f(59)=14,因为最少5张10元 9张1元)
给定\(n,a_1~a_n,k\),求最小的s使得\(f(s)>k\)
(\(0=a_1<a_2<⋯<a_n\leq 9,1\leq n\leq 10,1\leq k\leq 10^9\))
Code
#define int long long inline int maxx(int x){ int r=1; for(int i=1;i<=x;++i) r*=10; return r-1; } signed main(){ int T=read(); while(T--){ n=read();k=read();res=k+1; for(int i=1;i<=n;++i) a[i]=read(); for(int i=1;i<n;++i) a[i]=a[i+1]-a[i]; for(int i=1;i<n;++i){ if(maxx(a[i])>=res){ ans[i]=res; for(int j=i;j>=1;--j) printf("%lld",ans[j]); printf("\n"); goto nxt; } else{ ans[i]=maxx(a[i]); res-=ans[i]; } } printf("%lld",res); for(int j=1;j<n;++j) printf("%lld",ans[j]); printf("\n"); nxt:; } }
D
4s
Problem
一个n*m的矩阵
你需要把每行涂上红/蓝(不能全红/全蓝)
然后竖着从某两列间把矩阵切成左矩阵和右矩阵
使得:左矩阵中 红数字比所有蓝数字大,右矩阵中 蓝数字比所有红数字大。
如果存在 输出每行染色方式和切割方式,否则输出No
\(2\leq n,m \leq 5\times 10^5,nm\leq 10^6,1\leq a_{i,j}\leq 10^6\)
Solution
每行按字典序排序。可以证明,染色时必然是前若干行蓝色,后若干行红色。
维护一下前后缀最大最小值,然后枚举红蓝交界线和左右矩阵交界线的交点即可
E
3s
Problem
有n个英雄,初始血量\(a_1~a_n\)。每轮游戏中,每个人对其他所有人造成一点伤害,该轮结束后 血量小于等于0的英雄死亡。若最后仅剩一人则此人胜出。
如3个人:3 2 5,第一轮变成1,0,3,第二轮变成0,0,2,所以第三个人胜出。
如4个人:2,2,2,2,第一轮变成-1,-1,-1,-1,无人胜出
给定n,x,已知每个人初始血量都是1~x的整数,求使得无人胜出的方案数%998244353
Solution
我们猜测: 无人胜出当且仅当存在两人血量相同。
F
这篇关于Educational Codeforces Round 116 (CF1606)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享