最新要闻
- 每日热文:八方点赞!姆巴佩、莫德里奇等多人点赞C罗社媒动态
- 世界快报:零下50℃室外玩电脑 显卡都冻傻了:核心温度167万摄氏度
- 【速看料】能用沐浴露洗头吗?可以是可以 但最好别
- 天天动态:国内首个类ChatGPT模型:复旦大学团队称MOSS将于三月底开源
- 观速讯丨国产八核CPU!诺基亚发布G22:小白都能自己修
- 方敏仪
- 享年86岁 电影美术大师杨占家去世 手绘媲美CAD制图
- 世界快资讯:《流浪地球》地下城成真?我国地下基础设施监测技术实现新突破
- 【环球时快讯】易烊千玺 我们还会在一起吗?_对于易烊千玺 我们还会在一起吗?简单介绍
- 世界观察:卡罗拉车主试驾完比亚迪唐DM-i之后 丰田信仰瞬间崩塌
- 80后夫妻攒300万“提前退休” 不生孩子这些钱够了?网友吵翻
- 一加Buds Pro 2新配色“云峰白”亮相:打磨难度拉满
- 天天通讯!推特进一步削减开支:马斯克挥刀裁掉50名员工
- 快播:上映10天:《中国乒乓》票房终于破9000万大关
- 不是“空中楼阁”:努比亚Pad 3D搭载全球最大Leia 3D内容生态
- 【报资讯】男子车停路边去吃烧烤 回来瞬间崩溃:路边已装上护栏
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
Codeforces Global Round 15 CF1552 A~G 题解
点我看题
(资料图片)
对两三年前的cf进行考古的时候偶然做到这场,像这种全是构造题和思维题的比赛还是比较少见的。题目本身很有意思,但是对于现场打比赛想上分的人来说体验就比较差了。
A. Subsequence Permutation
先把原串s排序,令排完序的串为t。注意到s和t不相等的那些位置是必须被修改的;而直接把这些位置拿出来排个序,发现就已经能把s变成t了。所以直接统计s和t有多少个位置不同即可。
时间复杂度\(O(n)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i>t; rep(tn,t) { cin>>n>>s; string ss=s; sort(ss.begin(),ss.end()); int ans=0; rep(i,n) if(s[i]!=ss[i]) ++ans; cout<
B. Running for Gold
题目渐渐变得思维起来了
我们从前到后遍历所有的选手,把它们一个个放进当前参赛选手的集合。同时维护一个集合中"最可能拿到金牌"的选手编号。维护方法如下:加入一个选手i时,令当前最可能拿到金牌的选手编号为opt,如果i有至少三场比赛比opt强,就令opt=i,否则opt不变。实际上,任何时刻opt都是集合中唯一可能拿到金牌的选手。证明可以归纳,假设opt是当前集合中唯一可能拿到金牌的选手,当加入一个选手i时,如果它有至少三场比opt强,那opt就不可能拿到金牌;否则,i就不可能拿到金牌。
最后再检查一下opt与所有选手想必是否都能有至少三场更强就行了,如果不是那就是无解。时间复杂度\(O(n)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i=3;}int main(){ fileio(); cin>>t; rep(tn,t) { cin>>n; rep(i,n) rep(j,5) scanf("%d",&r[i][j]); int good=0; repn(i,n-1) if(isBetter(i,good)) good=i; bool bad=false; rep(i,n) if(i!=good&& !isBetter(good,i)) bad=true; if(bad) puts("-1"); else cout<
C. Maximize the Intersections
首先要知道(a,b)和(c,d)两条线段相交,当且仅当[a,b]和[c,d]两个区间相交(\(a
已经存在的线段之间的交点数是已经确定的,单独统计一下就行。令\(lft=n-k\)。对每一条已经存在的线段(a,b)(a
但其实这两个最大值可以同时达到,把所有没匹配的点按照顺时针顺序拿出来,从0开始编号,把第i个与第\((i+lft)mod\ 2lft\)个匹配即可。
点击查看代码
#include #define rep(i,n) for(int i=0;i>t; rep(tn,t) { cin>>n>>k; rep(i,n+n+3) mark[i]=0; rep(i,k) { cin>>x[i]>>y[i];--x[i];--y[i]; mark[x[i]]=mark[y[i]]=1; if(x[i]>y[i]) swap(x[i],y[i]); } int ans=(n-k)*(n-k-1)/2; rep(i,k) for(int j=i+1;j
D. Array Differentiation
首先当a中有0的时候一定是有解的。然后把a中的负数全都取绝对值,因为这里正数和负数是一样的。
我们可以把数组b看成一张图,第i个点的权值为\(b_i\)。在两个点i和j之间可以连一条权值为\(|b_i-b_j|\)的边。我们要求权值为\(a_1\cdots a_n\)的边都在这个图里出现,问存不存在这样的图。
既然点和边都是n个,那如果存在合法的图,其中一定存在环,存在环也就一定有解。所以有解的充要条件就是:能从a中取出一些边使他们构成一个环。也就是a中存在两个不相交的集合,满足两个集合的权值和相等。这个枚举一下mask就行了。
时间复杂度\(O(3^n)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i>t; rep(tn,t) { cin>>n; rep(i,n) cin>>a[i]; if(n==1) { cout<<(a[0]==0 ? "YES":"NO")<0;msk2=(msk2-1)&full) if(sum[msk]==sum[msk2]) { //cout<
E. Colors and Intervals
脑筋急转弯题
首先令\(pos_{i,j}\)表示数值i在数组中的第j次出现的位置。注意到每个数值一定是选相邻的两次出现作为a和b最优。假设现在已经求出了答案,按照每个数值i在最后选取的区间\([a_i,b_i]\),我们可以把数值分类:选第一次和第二次出现的,选第二次和第三次的,\(\cdots\) ,选第\(k-1\)次和第\(k\)次的。令\(B=\lceil \frac n{k-1} \rceil\),现在我们以B个为一组,给每个组分配对应的数值。从左到右依次遍历每个组(12,23,...,k-1和k 这个顺序),遍历到第i组时,每次取出还没有分配组别的数值,把他们按照\(pos_{val,i+1}\)从小到大排序,并选最小的B个作为这组的成员,如果不足B个就全选。发现这样构造,不同的两组之间的区间绝对不会相交,每个组内部的位置也最多被覆盖B次,所以是符合题目要求的。
时间复杂度\(O(n^2logn)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define pb push_back#define mpr make_pairusing namespace std;void fileio(){ #ifdef LGS freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif}void termin(){ #ifdef LGS std::cout<<"\n\nEXECUTION TERMINATED"; #endif exit(0);}int n,k,c[10010],mark[110];pii ans[110];vector pos[110];int main(){ fileio(); cin>>n>>k; rep(i,n*k) { cin>>c[i];--c[i]; pos[c[i]].pb(i); } int b=(n+k-2)/(k-1); rep(i,k-1) { vector cand; rep(j,n) if(!mark[j]) cand.pb(mpr(pos[j][i+1],j)); sort(cand.begin(),cand.end()); rep(j,min((int)cand.size(),b)) { mark[cand[j].se]=1; ans[cand[j].se]=mpr(pos[cand[j].se][i],pos[cand[j].se][i+1]); } } rep(i,n) cout<
F. Telepanting
虽然难度不高,但是题目的想法很有创造性
从前往后做似乎是不太好做的,因为蚂蚁的路线一直在循环往复,找不出规律。我们试试从后往前做。
对于每个传送门,我们观察它的起点(\(x_i\))会被经过多少次。对于最后一个传送门n,如果\(s_n=0\)则只会经过1次,就是从前往后正常走的那次;否则会经过两次,第一次正常经过的时候会被传送回去,第二次经过的时候门已经关了,所以正常通过。在\(s_n=1\)的情况中,蚂蚁被往回传送了1次,所以它会给在\((y_n,x_n)\)范围内的所有传送门的终点都增加1次"正常经过"的次数。观察发现,一个传送门i的终点被"正常经过"的次数是1+后面的传送门把蚂蚁传送到它前面的次数。而这个传送门把蚂蚁往前传送的次数是 正常经过次数+\(s_i\)-1。这样通过一个前缀和或者其他数据结构就能求出每个传送门把蚂蚁往前传送的次数,也就能求出答案了。
时间复杂度\(O(n)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i>n; rep(i,n) scanf("%lld%lld%lld",&x[i],&y[i],&s[i]); ans=(x[n-1]+1)%MOD; LL cur=1; for(int i=n-1;i>=0;--i) { (cur+=add[i])%=MOD; LL bk=(s[i]==1 ? cur:(cur+MOD-1)%MOD); (ans+=bk*(x[i]-y[i]))%=MOD; (cur+=bk)%=MOD; LL p=lower_bound(x,x+n,y[i])-x-1; if(p>=0) (add[p]+=MOD-bk)%=MOD; } cout<
G. A Serious Referee
令"第i步的操作集合"表示\(\{j_{i,1},j_{i,2}\cdots j_{i,q_i}\}\)。
首先1-n的每个位置都必须被至少一个操作集合覆盖,否则肯定能构造出一个无法排序的序列。
接下来进行两步转化。我们要判断输入的这组操作是否能排序任意序列,其实也就是判断是否能排序任何 元素两两不同 的序列,这是显然的,因为如果有两个元素相同,你可以给它们任意定一个大小关系。进一步转化,能排序任何元素两两不同的序列 的充要条件其实是:能排序任何只由0和1组成的序列。必要性是显然的,来证明一下充分性:对于任意一个两两不同的序列,以及任意\(1\le i 定义一个进行完i步的"合法状态"为一个bitmask(长度为n),满足存在一个初始01序列使得进行前i步操作后得到这个bitmask。令\(T_i\)表示所有进行完i步的合法状态的集合。发现答案为ACCEPTED当且仅当\(T_n\)中的所有元素都形如\(\{0,0,0\cdots 1,1,1\}\)(所有0在前,所有1在后)。 进一步观察发现每个\(T_i\)的大小都不会特别大。令\(cur_i\)表示前i步操作覆盖到的所有位置的集合(\(cur_n=\{1,2,3\cdots n\}\)),\(radd_i\)表示\(cur_{i+1}\)比\(cur_i\)多出的部分(写成位运算也就是\(cur_i \bigoplus cur_{i+1}\))。注意到\(T_i\)中的每个状态只能转移到\(|radd_i|+1\)个\(T_{i+1}\)中的状态,转移到什么状态取决于\(radd_i\)中的位置上有多少个0多少个1。因此\(|T_{i+1}|\le |T_i|\cdot (|radd_i|+1)\)。\(|T_n|\)最大的情况肯定是\(radd\)的大小分布得尽量均匀的情况,因此\(|T_n|\le (\frac{n+k}k)^k\),是不大的。 所以按照上面的做法直接模拟,算出\(T_n\)中的所有元素就行了。几个时间优化:转移的时候不要去重,去重复杂度很高,重复了是没关系的;用bitmask和位运算处理集合操作。点击查看代码
#include
Codeforces Global Round 15 CF1552 A~G 题解
每日热文:八方点赞!姆巴佩、莫德里奇等多人点赞C罗社媒动态
世界快报:零下50℃室外玩电脑 显卡都冻傻了:核心温度167万摄氏度
【速看料】能用沐浴露洗头吗?可以是可以 但最好别
天天动态:国内首个类ChatGPT模型:复旦大学团队称MOSS将于三月底开源
观速讯丨国产八核CPU!诺基亚发布G22:小白都能自己修
全球快看:解决IDEA无法识别SpringBoot项目
方敏仪
享年86岁 电影美术大师杨占家去世 手绘媲美CAD制图
世界快资讯:《流浪地球》地下城成真?我国地下基础设施监测技术实现新突破
【环球时快讯】易烊千玺 我们还会在一起吗?_对于易烊千玺 我们还会在一起吗?简单介绍
世界观察:卡罗拉车主试驾完比亚迪唐DM-i之后 丰田信仰瞬间崩塌
80后夫妻攒300万“提前退休” 不生孩子这些钱够了?网友吵翻
一加Buds Pro 2新配色“云峰白”亮相:打磨难度拉满
头条:Linux极简入门系列(二):Linux的目录结构和常用操作
【速看料】Linux vim
当前动态:Vue2 里如何优雅的清除一个定时器
天天通讯!推特进一步削减开支:马斯克挥刀裁掉50名员工
快播:上映10天:《中国乒乓》票房终于破9000万大关
关于数据分析中的绘图分析的学习报告
LWIP学习记录---ARP协议(2)ARP数据包发送过程
go A*寻路记录
59.类的自动转换和强制类型转换
不是“空中楼阁”:努比亚Pad 3D搭载全球最大Leia 3D内容生态
【报资讯】男子车停路边去吃烧烤 回来瞬间崩溃:路边已装上护栏
【独家焦点】作文游西湖300字(精选40篇)
千里托运奔驰GLC被淋满牛粪 女子崩溃:花1900元洗了5遍
【世界速看料】情侣打车3小时后跑单拉黑司机 司机:246元车费没了
世界资讯:微软承认向无法升级的设备推荐Win11:已进行修复
环球即时:压水堆
当前滚动:这些“领导”短信收到没?专门针对iPhone用户诈骗:全国多地预警
环球精选!王一博、梁朝伟《无名》北美院线扩映!豆瓣降至6.7分
当前简讯:大爷怒斥夜市挂日本元素油纸伞:主办方回应令人不解
环球头条:导演新海诚:中国动画电影迟早会超过日本
天天最资讯丨pat乙级链表问题
LWIP学习记录------ARP协议(1)
天天热文:开办以来首位!跨性别演员柏林电影节获奖
微速讯:长城放出王炸?长城水平对置八缸发动机摩托曝光 真猛兽
环球热头条丨可以两天一充的骁龙8 Gen2手机:出现了
每日热讯!马里肯涅巴地区发生武装抢劫 中使馆提醒关注当地安全情况
威马汽车再发内部信:部分员工复工 其余人员无薪休假
【全球热闻】视觉四边等宽!魅族20系列边框仅1.57mm:比iPhone 14 Pro都窄
全球热点!Go编程实战:博客备份
Markdown简明教程
《使命召唤》前景动荡
世界新资讯:上海一高校推出高启强同款猪脚面:师生直呼“舌尖上的《狂飙》”
乌苏啤酒大促:立减64元 折合3元/瓶到手
信息:女子考研期间生娃初试395分 回应外界好奇:多亏家人替自己分担很多
每日焦点!高德、百度地图红绿灯读秒很神奇 接入交管平台?真相并非如此
【天天新要闻】《我们的日子》里,不要忽视这些法律问题
天天资讯:俄州“毒火车”引发环境灾难后 美国又一货运列车脱轨
中兴通
全球热讯:读Java性能权威指南(第2版)笔记02_ Java SE API技巧上
世界动态:你昨晚关注的那个福利姬 可能是假的
世界即时看!国产新能源疯狂内卷!哈弗H6 PHEV官降1.5万 配置全系顶配
【世界报资讯】iPhone 15 Pro Max渲染图出炉:对比14 Pro Max边框更窄、机身更厚
对接水仙后台(支持AndLua+、FA、FA2、AIDE lua、Simple Lua等)
【全球报资讯】Golang基于Mysql分布式锁实现集群主备
世界观热点:薪资4K-5K!公司招聘财务要求做饭被吐槽像保姆
天天百事通!男子长期高血糖导致视网膜病变:不可逆
热头条丨不愧是万元机皇!酷安网友给三星Galaxy S23 Ultra打最高分
当前聚焦:《蚁人3》上映9天中国内地票房破2亿 网友:回到小众也挺好
世界微资讯!如何给公众号投稿赚钱_怎样给公众号投稿赚钱
双亲委派机制
天天微动态丨中国教师队伍建设研究/京师教师教育论丛
当前视讯!即将让核污水倒入大海!日本港口大量有毒海胆聚集 或出现爆发式增长
三星降低QD-OLED面板成本!让电视更具竞争力
世界关注:努比亚Z50新版下周首销:骁龙8 Gen2旗舰焊门员 性价比无敌
最新:python实现客户端和服务端的UDP相互通信
【报资讯】hbuilderx打正式包所需的私钥证书的创建方法
全球新动态:2.【go-kit教程】go-kit启动http服务
室内单目深度估计-4
最新:kaggle中训练得到的output太大该怎么下载?
世界热消息:2消息,中超新贵签约32岁国脚,5中超外援上诉国际足联
环球新动态:超市宣称1元纸币将退出历史引热议 网友直呼太突然:官方回应不属实
视点!女子患异食癖3年吃上百块粉饼:体检身体无异常
天天热点!刷题疑问
环球速读:史上最好的真全面屏手机!努比亚Z50 Ultra上架接受预约
天天精选!禁止自带食材 关停300家店 海底捞从巨亏41亿到盈利13亿
天天讯息:day04-原生的API&注解方式
【环球新要闻】Git使用
美食博主三亚买3888元海鲜被好心人提醒多花1700:当事人心累
热消息:秋裤先别着急脱!“春捂”到底该“捂”哪儿?
前沿资讯!2023年安卓之光!小米13 Ultra手机壳曝光:背部造型抢眼
餐馆接到网吧10个外卖订单 结果被刷9个差评 店主:下次亲自送餐
天天微速讯:门店2299元 GXG男士羊毛大衣0.8折清仓大促:实付199元!
世界热资讯!乐堡苏打气泡酒12罐到手19.9元:低糖0脂无负担
威马员工在线讨薪:被恶心到了、恶心的事还有更多
广州塞车登“热搜”?“甜蜜的烦恼”重回一线城市,中国经济活力加快恢复
【Tire树】高效统计字符串
80、90后泪目 国产暗黑《赵云传重制版》试玩
1岁男童误食降糖药成植物人:愿康复顺利
环球速看:中央人民广播电台民族节目中心
Ubuntu安装Zabbix6.0
秒睡令人羡慕?医生提醒:可能是种睡眠障碍
《流浪地球2》科幻成真?武汉国博用特效“加建”太空电梯
今头条!【element UI】在 el-select 与 el-tree 结合组件
环球热文:python教程:模块的搜索路径
Python中模块的四种方式
《原子之心》种族主义漫画引争议:涉嫌歧视黑人!官方道歉