最新要闻
- 阿根廷vs法国今晚开打:梅西即将独享世界杯出场纪录
- 【全球新要闻】《阿凡达2》坐骑仿生扑翼鸟开售:可遥控飞行 359元
- 卡梅隆透露《阿凡达3》已拍完 《阿凡达5》也写好了
- 天天日报丨魅族未来产品规划曝光:3年打造“全家桶”、不止手机和汽车
- 天天快消息!路边轿车挡道 SUV司机故意撞开 网友:很爽但应先联系114
- 微信iOS版拍照“大升级”:终于支持微距拍摄
- 当前快看:支付宝新增“极速模式”:自动收起首页推荐 更清爽了
- 当前关注:连花清瘟可致肝损伤肝衰竭?药企回应:严重误导
- 腾讯:2022年游戏盗号量上涨300% DDoS攻击全行业最高
- 花费13亿、飞了540万公里:韩国探测器终于进入月球轨道
- 天天观察:6GHz就这?!Intel i9-13900KS跑分勉强提升5%
- 微速讯:油管上最爆火的恐怖游戏:被托马斯小火车追杀
- 电池供电不插线:世界首款真无线电视将在CES亮相
- 快看:3D领域大神约翰·卡马克宣布彻底离开Meta:称其效率低到无法忍受
- 男子按导航开车到冰冻江面 一头栽入松花江
- 天天讯息:索尼要爆发了!明年有望推出新款PS5:独占大作护航
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
微动态丨Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解
A. Add Plus Minus Sign
如果有偶数个1,显然可以通过加减各一半的方式达到和为0;否则可以达到和为1。需要注意如果序列的第一个数是1,则它的前面只能填加号。
时间复杂度\(O(n)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid 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);}using namespace std;int t;string s;int main(){ fileio(); cin>>t; rep(tn,t) { int n; cin>>n>>s; int cnt=(s[0]=="1" ? 1:0); repn(i,s.size()-1) { if(s[i]=="0") printf("+"); else { if(cnt==1) printf("-"),cnt=0; else printf("+"),cnt=1; } } puts(""); } termin();}
B. Coloring
是一道挺难的题,我是做完了A~F1才回去做这题的。现在cf比赛的前面几道题越来越偏向于猜结论了,可是场上又有多少人来得及去证明这些结论呢?我认为这是个不好的现象。
(相关资料图)
所以还是来猜个结论吧:令\(x=\lceil\frac nk \rceil\)。如果\(a_{max}>x\)显然无解。其余情况,当\(k|n\)时,\(a_{max}\)的数量不应超过k;否则,\(a_{max}\)的数量不应超过\(n\ mod\ k\)。这个条件的必要性显然,充分性不知道,看着是对的。反正是猜结论题嘛。
可能有80%的人都只判了前面一个条件,几乎全被hack掉了,pretest还贼弱。这事儿直接把这场比赛提高到了它不该有的高度,可以竞争cf史上最烂比赛了。
时间复杂度\(O(m)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid 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);}using namespace std;LL t,n,m,k,a[100010];int main(){ fileio(); cin>>t; rep(tn,t) { scanf("%lld%lld%lld",&n,&m,&k); rep(i,m) scanf("%lld",&a[i]); LL most=(n+k-1)/k,num=n%k; if(num==0) num=k; LL cnt=0,bad=0; rep(i,m) { if(a[i]>most) bad=1; else if(a[i]==most) ++cnt; } if(bad||cnt>num) puts("NO"); else puts("YES"); } termin();}
C. Ice and Fire
仍然是猜结论题。如果我们总是把现在场上还剩余的人按照编号从小到大排序,那么一个0可以淘汰掉任意一个不是最左侧(最小)的人;1可以淘汰掉任意一个不是最右侧的人。假设现在用输入的01序列的前i项进行比赛,第i项为0,从第i项往前有k个连续的0。这个情况下,能成为冠军的位置在比赛开始前,它右边至少要有k个人。因为如果右边不到k个人,在比赛还剩k轮的时候,它左边必定还有没消掉的。由于剩下的全是0,它左边的东西不可能全消掉。第i项为1同理。所以i的答案就是i+2-k。充分性照常不证明
时间复杂度\(O(n)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid 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);}using namespace std;int t,n;string s;int main(){ fileio(); cin>>t; rep(tn,t) { cin>>n>>s;--n; int con=0; rep(i,n) { if(i==0||s[i]!=s[i-1]) con=1; else ++con; printf("%d ",i+1-con+1); } puts(""); } termin();}
D. Same Count One
如果1的总数不是n的倍数,显然无解。否则一定有解。令\(ave=\frac {tot_1}n\),也就是最终每行应该有的1的个数。令初始1的个数超过ave的行,它们比ave多出的1的个数总和为sum,显然至少需要sum步才能达成目标,因为我们最好的情况就是每次把一个1从平均线之上的行搬运到平均线之下的行。只操作sum不其实是可以达到的。我们一列一列地看,每次把这一列中能做的这种操作都做完。把这一列所有的在平均线上且对应位置为1的行都拿出来,把所有在平均线下且对应位置为0的行也都拿出来。把这两类行尽量配对。容易发现,依次对每一行把能配对的都配了,也就达成目标了。
时间复杂度\(O(nm)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid 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);}using namespace std;int t,n,m,cur[100010];vector a[100010];int main(){ fileio(); cin>>t; rep(tn,t) { scanf("%d%d",&n,&m); rep(i,n+3) a[i].clear(); int tot=0; rep(i,n) { vector tmp;int x; cur[i]=0; rep(j,m){scanf("%d",&x);tmp.pb(x);tot+=x;cur[i]+=x;} a[i]=tmp; } if(tot%n!=0) { puts("-1"); continue; } int ave=tot/n; vector > ans; rep(col,m) { vector abo,und; rep(i,n) { if(cur[i]>ave&&a[i][col]==1) abo.pb(i); if(cur[i]
E. Two Chess Pieces
其实某种程度上也是靠猜。既然要求两个棋子距离不超过d,那如果两个人要去同一个目的地,不如一起行动。具体来说,两个人都是一个子树一个子树地访问,如果某一个子树内同时有这两个人需要访问的点,那就两个人一起去;否则如果只有第一个人需要访问的,那第二个人去了就是浪费,不如第二个人直接留在当前点,让第一个人去。但是如果当前点到子树内最深的第一个人需要访问的点的距离>d,那第二个人还是需要去一下的,他只需要去子树内所有满足"下方所有第一个人需要到达的点的深度最大值-当前点深度>=d"的点就行了,多一个都是浪费。如果只有第二个人需要访问的,同理。所以这题其实只要dfs就能解决。
时间复杂度\(O(n)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid 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);}using namespace std;int n,d,b1[200010],b2[200010],sum1[200010],sum2[200010],ans=0,dep[200010],opt1[200010],opt2[200010];vector g[200010];void dfsPre(int pos,int par){ sum1[pos]=b1[pos];sum2[pos]=b2[pos]; if(b1[pos]) opt1[pos]=dep[pos]; if(b2[pos]) opt2[pos]=dep[pos]; rep(i,g[pos].size()) if(g[pos][i]!=par) { dep[g[pos][i]]=dep[pos]+1; dfsPre(g[pos][i],pos); sum1[pos]+=sum1[g[pos][i]];sum2[pos]+=sum2[g[pos][i]]; opt1[pos]=max(opt1[pos],opt1[g[pos][i]]); opt2[pos]=max(opt2[pos],opt2[g[pos][i]]); }}void dfs1(int pos,int par){ ++ans; if(opt1[pos]-dep[pos]>=d) ++ans; rep(i,g[pos].size()) if(g[pos][i]!=par&&sum1[g[pos][i]]) dfs1(g[pos][i],pos);}void dfs2(int pos,int par){ ++ans; if(opt2[pos]-dep[pos]>=d) ++ans; rep(i,g[pos].size()) if(g[pos][i]!=par&&sum2[g[pos][i]]) dfs2(g[pos][i],pos);}void dfs(int pos,int par){ rep(i,g[pos].size()) if(g[pos][i]!=par) { if(sum1[g[pos][i]]&&sum2[g[pos][i]]) { ans+=2; dfs(g[pos][i],pos); } else if(sum1[g[pos][i]]) dfs1(g[pos][i],pos); else if(sum2[g[pos][i]]) dfs2(g[pos][i],pos); }}int main(){ fileio(); cin>>n>>d; int x,y; rep(i,n-1) { scanf("%d%d",&x,&y); g[x].pb(y);g[y].pb(x); } int mm; cin>>mm;rep(i,mm){scanf("%d",&x);b1[x]=1;} cin>>mm;rep(i,mm){scanf("%d",&x);b2[x]=1;} dfsPre(1,0); dfs(1,0); cout<
F2. Magician and Pigs (Hard Version)
其实F1和F2是差不多的,所以F2只配了800分。
考虑能不能维护一个set,依次遍历所有询问的同时,用set维护一些数对{a,b},表示生命值为a的猪现在有b只。1操作的时候直接往set中插入,2操作就把set中a最小的一些删掉,并把其他的数一并减去一个值。令\(totsub\)表示到当前为止,2操作一共减少了多少生命值(如果一个2操作被3操作重复了多次,也要计算多次)。则一次3操作对这个set的影响是:把set中原有的所有数拿出来,\(>totsub\)的,减去\(totsub\)之后加入set,其余的则不再次加入。这是因为把1~i-1中所有的操作重新做一遍相当于把之前集合中的每头猪都复制了一遍,并且把原有的猪的生命值都减去了\(totsub\)。最后,3操作还会令\(totsub*=2\)。发现在第一次2操作之后,每次3操作都会至少令totsub*2。当\(totsub\ge 1e9\)的时候3操作就完全没用了。所以有效的3操作最多只有\(log_2(1e9)\)次。直接用set维护的复杂度是\((n+X)log^2n\),可以通过F1。F2需要更好的方法。
观察上面维护set的过程,可以想到对每一个1操作求出由它产生的所有猪里面最终活下来的有几只。假设现在正在遍历第i次1操作,从第i次操作往后的每一次3操作j其实都给了从第i次1操作产生的猪两种选择:把生命值减去\(totsub_j\),或是不减去。我们可以把一种选择序列看成一条"路径"。把\(totsub_j=0\)的和\(totsub_j>1e9\)的特殊处理,剩下的3操作最多\(log(1e9)\)种。如果把这些有用的3操作按在题目输入中出现的顺序从前往后排好(令其下标组成的序列为\(c_1,c_2\cdots c_m\)),发现对于其中的第k次3操作,\(totsub_{c_k}>\sum_{p 时间复杂度\(O(nlog(1e9))\)。 F1代码: F2代码: A AddPlusMinusSign如果有偶数个1,显然可以通过加减各一半的方式达到和为0;否则可以达到和为1。需要...点击查看代码
#include
fi+shft<=que[i].se) cur.erase(cur.begin()); //if(i==8) cout<
点击查看代码
#include
微动态丨Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解
微动态丨Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解
阿根廷vs法国今晚开打:梅西即将独享世界杯出场纪录
【全球新要闻】《阿凡达2》坐骑仿生扑翼鸟开售:可遥控飞行 359元
卡梅隆透露《阿凡达3》已拍完 《阿凡达5》也写好了
当前讯息:Blazor和Vue对比学习(进阶.请求WebAPI):通讯协议和HTTP协议
环球播报:windows10 netsh wlan命令连接新wifi
重学c#系列——什么是性能[外篇性能篇一]
天天日报丨魅族未来产品规划曝光:3年打造“全家桶”、不止手机和汽车
天天快消息!路边轿车挡道 SUV司机故意撞开 网友:很爽但应先联系114
焦点热议:核心面试题:MVCC、间隙锁、Undo Log链、表级锁、行级锁、页级锁、共享锁、排它锁、记录锁等等
微信iOS版拍照“大升级”:终于支持微距拍摄
当前快看:支付宝新增“极速模式”:自动收起首页推荐 更清爽了
当前关注:连花清瘟可致肝损伤肝衰竭?药企回应:严重误导
腾讯:2022年游戏盗号量上涨300% DDoS攻击全行业最高
花费13亿、飞了540万公里:韩国探测器终于进入月球轨道
北航计算机网络实验复习——设计性实验汇总
天天观察:6GHz就这?!Intel i9-13900KS跑分勉强提升5%
微速讯:油管上最爆火的恐怖游戏:被托马斯小火车追杀
电池供电不插线:世界首款真无线电视将在CES亮相
快看:3D领域大神约翰·卡马克宣布彻底离开Meta:称其效率低到无法忍受
男子按导航开车到冰冻江面 一头栽入松花江
当前最新:概念、场景技术方案选择的理解
hive配置Tez引擎,并安装Tez-ui
天天要闻:超级好看的 Edge 浏览器新标签页插件:好用、好看、免费浏览器必备
【世界热闻】matplotlib绘图详解
当前观察:下标模意义下的多项式乘法及其应用
【世界聚看点】go-micro v3 rpc服务一次改造经历
天天讯息:索尼要爆发了!明年有望推出新款PS5:独占大作护航
MyBatis核心配置文件详解
每日播报!疯狂裁员后 曝马斯克正为推特寻找新买家
环球最资讯丨“三连跌” 明晚油价迎年内“最后一调”:92号汽油或回归7元时代
世界头条:豆瓣8.3分!《阿凡达:水之道》票房破3亿:会是救市之作吗
全球热推荐:低温蓝色预警!这些地方最低温较历史同期低7℃以上:南方网友瑟瑟发抖
克罗地亚2-1战胜摩洛哥夺世界杯季军 37岁莫德里奇告别世界杯赛场
焦点关注:[PingCTF2022] guess what - S1gMa
环球滚动:女子开特斯拉被查酒驾 罚2000元记12分:本人称吃醉蟹 交警回应
销售开特斯拉撞了顾客的特斯拉 拒赔5万元:直言刹车了停不住
智慧树视频课件课程下载工具,如何在电脑端下载智慧树视频课件PDF,PPT到本地
史上口碑最好的小米旗舰!小米13京东好评率接近100%
VUE组件
【世界时快讯】安全多方计算:(2)隐私信息检索方案汇总分析
全球快资讯:基于海拉克斯打造 丰田推出首款纯电皮卡原型车 网友:丑到我眼睛了
天天快资讯丨卡神离开Meta 批老东家效率低下:GPU利用率5%简直是侮辱
全球热点评!小米MIX Fold 2新配色下周首销:5.4mm厚度已是行业极限 8999元
今热点:同价位无敌手!小米万兆路由器更新
全球观热点:第八天 循环的花里胡哨的用法
重学c#系列——linq(4) [三十]
【速看料】400行的象棋程序
AMD、NVIDIA齐发新品 显卡厂商的好日子来了:加速去库存
世界快报:男子1199元买长江存储2TB SSD吐槽是翻新 手指划痕:网友看完笑死
世界快消息!用户真实评价小米13:太惊艳了 这就是小米13带给我的感觉
精彩看点:北欧品质 口感清爽:OATLY燕麦奶4.1元/斤新低(商超29.8元)
【天天新视野】男子称买到过期3月沐浴露获赔5元:看不起谁呢
焦点信息:java基础面试题
【报资讯】Docker的资源控制管理
全球热资讯!BBA的禁脔 垂涎者不止蔚来
当前通讯!Docker网络模式
环球热点评!冬天空调取暖不热 可能是这些问题
环球观速讯丨小米13成了!线下门店卖断货 供不应求
热点!web项目的开发---第二天
世界今头条!SpringCloud-Ribbon学习笔记
世界速看:挑战行业多项不可能 一加11即将发布:最强性能旗舰
世界动态:python语法笔记
令人气愤!女子曝无良汽修店为赚钱高速路上撒钉子专扎车胎
天天视讯!刘作虎:OPPO一加正式开启双品牌战略 100亿投资扶植一加
环球观速讯丨义乌开始生产阿根廷夺冠球衣 还是三颗星 阿根廷辟谣:假的 侵权
世界快播:“顶级大众” 宾利Batur公布工艺细节:210克黄金3D打印
老人手指被卡:消防员用开塞露救了差点被剪的蓝宝石戒指
全球快资讯:一文了解 Dubbo 的代码架构
今日报丨关于整数二分的详解
滚动:预编译#error的使用
全球要闻:YoloV7 标签匹配机 loss 计算详解
安全多方计算(1):不经意传输协议
每日快讯!元旦假期首日火车票今开抢!迎出行小高峰:五大热门目的地出炉
观天下!Find N2系列发布背后:OPPO再次展示对产品精益求精态度
天天要闻:全国冻哭预警地图来了:周末20余省份或被冻哭 冷到破纪录
热议:售价超300万!乔布斯亲手编号Apple-1电脑落锤成交:46年后 开机画面眼前一亮
世界最大独立圆柱体水族馆爆裂:1500多条鱼全军覆没
世界杯决战前夕 法国又有两大主力倒下!5人感染神秘流感
【环球热闻】被加价千元:AMD喊话正加大RX 7900系生产!NV 4080笑而不语
世界简讯:VUE数据双向绑定
第一百一十四篇: JS数组Array(三)数组常用方法
世界上最大的鱼缸今日突然破裂:100万升水泄露 1500条鱼死亡
放假3天不调休!2023年元旦假期首日火车票开售 除夕票这一天就能买
天天报道:学谁不好学特斯拉!几十万的宝马车 容不下一个收音机
观天下!骗子诈骗1250万 买彩票中1450万:已退还给39名聋哑人
全球热讯:XSX性能比PS5强 但为何游戏性能总是输?
天天速看:Python函数/动态参数/关键字参数
天天热点!女子发烧敷20分钟面膜揭下变3D立体面具 医生提醒:影响退热 当心面瘫
方便面消费第一大国是我们:超6成人每周吃三次
世界速读:注解在Android中的使用场景
热推荐:锂金属电池爱长枝晶?韩国科学家找到破解之法
【当前独家】确认了!《阿凡达2:水之道》没有片尾彩蛋
天天观速讯丨1152分区+4K 144Hz 联合创新32寸miniLED显示器首发5399元
终于修好了!Win11新补丁解决22H2大文件复制缓慢Bug
首款第二代骁龙8游戏旗舰!红魔8 Pro来了
今日最新!王思聪投资百万成立新公司 经营范围包括动漫游戏开发
全球最资讯丨全自动门锁比半自动更人性化!但半自动更受青睐 真相终于揭开
世界简讯:Hessian2序列化支持这一点,让重构dubbo接口更容易了
【热闻】-真正的国产亲民MPV 新款传祺M6 PRO上市:11.98万起