最新要闻
- 男子花32万买比亚迪海豹 内心崩溃:汽配城都没这么难看
- 焦点要闻:节能版酷睿i9-13900T现身:35W战平12900K
- 观天下!腾讯开出48人惩治名单 马化腾曾称内部贪腐“触目惊心”
- 【环球热闻】110度高烧不退!AMD RX 7900 XTX退换货率高达11%
- 为啥北方二十三过小年 南方却是二十四?和康熙乾隆有关
- 观察:无广告一年免费用!通信UOS家庭版22.0开始推送
- 男子买898元零食P图付款 被抓现行:实际支付了1分钱
- 天天通讯!基于传奇车型AE86!丰田推出两款新能源概念改装车
- 女子骑电动车载两人闯红灯被撞 被判全责 网友:这才是公正
- 苹果回应iPhone车祸监测误报频发:正收集相关反馈
- 《新·福音战士剧场版:终》国内海报抄袭!竹也文化官方布道歉声明
- 环球今热点:几十年数学难题被谷歌研究员意外突破 当年差点被导师赶出门
- B站2022百大UP主出炉:手工耿入选 走向世界的手工匠人
- 天天亮点!稳居春节档票房前三:《流浪地球2》官方揭秘太空电梯创作思路
- 世界讯息:12月新能源销量排名出炉:比亚迪吉利长安强攻 特斯拉扛不住了?
- 观速讯丨长征第462发!我国成功发射一箭14星:“共享”火箭了解下
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
当前快讯:Atcoder Regular Contest ARC 153 A B C D 题解
点我看题
A - AABCDDEFE
一个beautiful number是形如这样的:\(S1S1S3S4S5S5S7S8S7\)。如果选定了\(S1\),后面的数有100000种选法,所以先求出答案的\(S1\)。假设现在我们要求出以\(S1\)开头的第\(n\)小的beautiful number。发现这个条件其实等价于\(S3S4S5S7S8\)这个五位数等于\(n-1\),所以直接求即可。
点击查看代码
#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,ans[20];int main(){ fileio(); cin>>n; int s1=1; while(n>100000) { ++s1; n-=100000; } --n; ans[1]=ans[2]=s1; ans[8]=n%10;n/=10; ans[7]=ans[9]=n%10;n/=10; ans[5]=ans[6]=n%10;n/=10; ans[4]=n%10;n/=10; ans[3]=n%10; repn(i,9) cout<
B - Grid Rotations
发现行和列实际上是独立的,每次操作\(a,b\)实际上我们相当于依次做了这四步:把第\(1\cdots a\)行翻转(注意是行与行之间的顺序reverse,不是把每行的内容reverse,后面的"翻转"同理);把第\(a+1\cdots n\)行翻转;把第\(1\cdots b\)列翻转;把第\(b+1\cdots m\)列翻转。如果我们能求出两个数组\(r,c\),\(r_i\)表示所有操作做完后,原来的第\(i\)行被移到了第\(r_i\)行,第\(j\)列被移到了第\(c_j\)列,那么原来的\(a_{i,j}\)就被移动到了\((r_i,c_j)\)。用两个平衡树维护两维的翻转情况即可。
(资料图片仅供参考)
时间复杂度单log。
其实也可以线性,因为行列坐标的变换也可以看成是加一个数再取模。但平衡树的优势是不要动脑子。
点击查看代码
#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 to[2][500010];mt19937 rndtr(114514);struct node{int val,key,ls,rs,sz,tag;};struct tr{int len;node a[1000000];int newNode(int x){a[++len].val=x;a[len].key=rndtr();a[len].ls=a[len].rs=a[len].tag=0;a[len].sz=1;return len;} void addTag(int x) { if(x==0) return; swap(a[x].ls,a[x].rs);a[x].tag^=1; } void pushDown(int x) { if(x==0||a[x].tag==0) return; addTag(a[x].ls);addTag(a[x].rs); a[x].tag=0; }void calc(int x){if(x==0) return;a[x].sz=a[a[x].ls].sz+1+a[a[x].rs].sz;}int merge(int x,int y){if(x==0||y==0) return max(x,y); pushDown(x);pushDown(y);int ret;if(a[x].key<=a[y].key){ret=x;a[ret].rs=merge(a[ret].rs,y);}else{ret=y;a[ret].ls=merge(x,a[ret].ls);}calc(ret);return ret;}pii splitSz(int x,int y)//左边y个{if(x==0) return mpr(0,0);if(y==0) return mpr(0,x);if(y==a[x].sz) return mpr(x,0); pushDown(x);int ret1,ret2;if(a[a[x].ls].sz>=y){pii p=splitSz(a[x].ls,y);ret1=p.fi;ret2=x;a[ret2].ls=p.se;}else{pii p=splitSz(a[x].rs,y-1-a[a[x].ls].sz);ret1=x;a[ret1].rs=p.fi;ret2=p.se;}calc(ret1);calc(ret2);return mpr(ret1,ret2);} void build(int x,int frt,int w) { if(x==0) return; to[w][a[x].val]=frt+a[a[x].ls].sz; pushDown(x); build(a[x].ls,frt,w);build(a[x].rs,frt+a[a[x].ls].sz+1,w); }}row,col;int n,m;string a[500010],ans[500010];char c[500010];int main(){ fileio(); cin>>n>>m; rep(i,n) { scanf("%s",c); a[i]=ans[i]=c; } row.len=0;col.len=0; int rootr=0,rootc=0; rep(i,n) rootr=row.merge(rootr,row.newNode(i)); rep(i,m) rootc=col.merge(rootc,col.newNode(i)); int q;cin>>q; rep(qn,q) { int x,y; scanf("%d%d",&x,&y); pii p=row.splitSz(rootr,x); row.addTag(p.fi);row.addTag(p.se); rootr=row.merge(p.fi,p.se); p=col.splitSz(rootc,y); col.addTag(p.fi);col.addTag(p.se); rootc=col.merge(p.fi,p.se); } row.build(rootr,0,0); col.build(rootc,0,1); rep(i,n) rep(j,m) ans[to[0][i]][to[1][j]]=a[i][j]; rep(i,n) printf("%s\n",ans[i].c_str()); termin();}
C - ± Increasing Sequence
(A数组的下标从0开始)
令\(suf_i=\sum_{j=i}^{n-1}a_i\)。我们其实是要找出一个序列\(b_0\cdots b_{n-1}\),满足\(b_1\cdots b_{n-1}\)都是正整数,且\(\sum b_isuf_i=0\)。其实b就是题目中x的差分数组。
由于b中除了第一个数都要取正数,那就先把\(b_1\cdots b_{n-1}\)都取1,\(b_0\)取0,后面如果需要可以再加。如果此时\(\sum b_isuf_i\)已经为0,那就直接输出解。否则,如果\(suf_1\cdots suf_{n-1}\)中有正有负,那肯定有解,因为\(suf_{n-1}\)是1或-1,如果是1的话就随便找一个\(<0\)的\(suf_i\),不断给\(b_i\)加1直到\(\sum b_isuf_i\le 0\),然后再用\(suf_{n-1}\)加回来即可。\(suf_{n-1}=-1\)同理。
剩下的情况,如果\(suf_0=0\)肯定无解,这是显然的。否则也肯定有解,比如\(suf_{n-1}=1\)时,可以像上面一样,先用\(suf_0\)把\(\sum b_isuf_i\)压到非正数,在用\(suf_{n-1}\)加回来。
点击查看代码
#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 n,a[200010],ans[200010],sufsum[200010];void print(){ puts("Yes"); rep(i,n) { printf("%d ",ans[i]); ans[i+1]+=ans[i]; } puts(""); termin();}void fuck(){puts("No");termin();}int main(){ fileio(); cin>>n; rep(i,n) scanf("%lld",&a[i]); LL sum=0,cur=0,posi=-1,nega=-1; for(int i=n-1;i>0;--i) { sum+=a[i];sufsum[i]=sum; ans[i]=1;cur+=sum; if(sum>0) posi=i;else if(sum<0) nega=i; } if(cur==0) print(); //if(a[n-1]==1) posi=n-1;else nega=n-1; if(posi>-1&&nega>-1) { if(a[n-1]==1) { LL usenega=(max(0LL,cur)-sufsum[nega]-1)/(-sufsum[nega]); ans[nega]+=usenega;cur+=usenega*sufsum[nega]; ans[n-1]-=cur; } else { LL useposi=(-min(0LL,cur)+sufsum[posi]-1)/sufsum[posi]; ans[posi]+=useposi;cur+=useposi*sufsum[posi]; ans[n-1]+=cur; } print(); } if(sum+a[0]==0) fuck(); sum+=a[0]; if(a[n-1]==1) { LL targ=(cur+llabs(sum)-1)/llabs(sum)*llabs(sum); ans[n-1]+=targ-cur; ans[0]=-(targ/sum); } else { LL targ=(-cur+llabs(sum)-1)/llabs(sum)*llabs(sum);targ=-targ; ans[n-1]+=llabs(targ-cur); ans[0]=-(targ/sum); } print(); termin();}
D - Sum of Sum of Digits
看起来像数位dp,其实也确实是dp。
令原数组所有数的数位和为\(S\),x的数位和为X。那么最终的数位和为\(S+nX-所有数加x的总进位次数\cdot 9\),这个模拟一下加法的过程就能发现。我们把进位次数\(\cdot 9-nX\)称为"收益",我们想让收益最大。
我们从低往高确定x的每一位。关键观察:当确定了x的最低的i位时,\(a\)数组中那些会从第i位到第i+1位进一位的数,肯定是\(a\)中前i位按照数值比较最大的一些数。所以就可以dp了:\(dp_{i,j}\)表示计算到第i位,前\(i-1\)位最大的j个数被第\(i-1\)位到第\(i\)位进位了一次的情况下的最大收益。转移时枚举x的当前这一位选什么,计算第i位到第i+1位的进位数只要用前缀和预处理一下就行了。
时间复杂度\(O(10^2n)\)。
点击查看代码
#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;void chmax(LL &x,LL y){if(x=k的个数LL dp[15][200010];//dp[i][j]: 第i层,前缀最大的j个被进位的最大收益int main(){ fileio(); pw10[0]=1;repn(i,12) pw10[i]=pw10[i-1]*10; cin>>n; rep(i,n) scanf("%lld",&a[i]); rep(i,10) { rep(j,n) clue[j]=a[j]%pw10[i],lft[j]=a[j]/pw10[i]%10,ord[i][j]=j; sort(ord[i],ord[i]+n,[](LL x,LL y){return clue[x]>clue[y];}); rep(j,n) { rep(k,12) pref[i][j+1][k]=pref[i][j][k]; for(int k=0;k<=lft[ord[i][j]];++k) ++pref[i][j+1][k]; } } rep(i,14) rep(j,n+3) dp[i][j]=-1e18; dp[0][0]=0; rep(i,10) rep(j,n+1) if(dp[i][j]>-1e18) { rep(nxt,10) { LL gain=(LL)(-nxt)*n,add=pref[i][j][10-nxt-1]+pref[i][n][10-nxt]-pref[i][j][10-nxt]; gain+=add*9; chmax(dp[i+1][add],dp[i][j]+gain); } } LL ans=-1e18; rep(j,n+1) ans=max(ans,dp[10][j]); LL ori=0; rep(i,n) { while(a[i]>0) { ori+=a[i]%10; a[i]/=10; } } ans=ori-ans; cout<
-
当前快讯:Atcoder Regular Contest ARC 153 A B C D 题解
点我看题A-AABCDDEFE一个beautifulnumber是形如这样的:$S1S1S3S4S5S5S7S8S7$。如果选定了$S1$,后面的...
来源: 当前快讯:Atcoder Regular Contest ARC 153 A B C D 题解
焦点关注:PhotoEnhancer人工智能一键修复老照片,老照片修复,图像去噪
男子花32万买比亚迪海豹 内心崩溃:汽配城都没这么难看
焦点要闻:节能版酷睿i9-13900T现身:35W战平12900K
观天下!腾讯开出48人惩治名单 马化腾曾称内部贪腐“触目惊心”
Phi的反函数
【环球热闻】110度高烧不退!AMD RX 7900 XTX退换货率高达11%
为啥北方二十三过小年 南方却是二十四?和康熙乾隆有关
观察:无广告一年免费用!通信UOS家庭版22.0开始推送
111111
男子买898元零食P图付款 被抓现行:实际支付了1分钱
天天通讯!基于传奇车型AE86!丰田推出两款新能源概念改装车
CF构造题1600-1800(2)
女子骑电动车载两人闯红灯被撞 被判全责 网友:这才是公正
苹果回应iPhone车祸监测误报频发:正收集相关反馈
《新·福音战士剧场版:终》国内海报抄袭!竹也文化官方布道歉声明
Python开发的常用组件
每日观察!推荐一本正在看的书
环球今热点:几十年数学难题被谷歌研究员意外突破 当年差点被导师赶出门
B站2022百大UP主出炉:手工耿入选 走向世界的手工匠人
天天亮点!稳居春节档票房前三:《流浪地球2》官方揭秘太空电梯创作思路
世界讯息:12月新能源销量排名出炉:比亚迪吉利长安强攻 特斯拉扛不住了?
【全球独家】读编程与类型系统笔记08_面向对象变成的元素
观速讯丨长征第462发!我国成功发射一箭14星:“共享”火箭了解下
国内《新·福音战士剧场版:终》限定海报被指抄袭 官方正在联系画师确认
无法恢复!微软杀软Defender误删开始菜单/任务栏捷方式
天天观点:排量830cc 马自达转子发动机正式回归!首车发布
天天亮点!雨雪降温重心转移至南方 大范围雨雪天气明日结束
天天短讯!一步一步实现若依框架--2.3防止重复提交 repeat_submit
焦点快播:2022一年 特斯拉车主为地球节省20亿美元油费
每日消息!全球首现!四川一地发现新物种:长得特别好看
每日动态!《三体》剧版今日CCTV8、腾讯视频全网首播:会员提前看三集
天天观点:使用ActiveMQ Artemis进行重连
环球热议:千万别在有WiFi的房间里摆这种姿势
焦点观察:微软收购动视暴雪更难了!NVIDIA出手阻挠
环球观焦点:联名中国第一科幻IP!荣耀80 Pro《三体》动画定制版来了:限量卖
【全球独家】淘汰所有老款!新一代PS5主机年内到来:不向下兼容
环球热门:无磷配方 低泡易漂 绿伞洗衣液6斤17.9元
每日焦点!碰撞测试能拿一星 创维是造了什么“神仙”车
全球播报:中国科幻顶级IP首登荧屏!《三体》电视剧今晚央视、腾讯视频首播
中国制造多牛?世界最先进工厂:我们占了近一半
今日热文:堪比抢iPhone 泰国车主凌晨排队买!比亚迪泰国发运破万台
世界快报:微信全新拜年红包上线!支持语音祝福录制 动画效果太萌了
当前头条:Python树与树算法
B站大会员促销:12个月年卡到手价98元
天天动态:污染环境?代表建议允许春节分区分时燃放烟花 留住年味
每日消息!吓哭孩子!《中国奇谭》导演回应家长炮轰被网友赞:要走出国门征服老外
吃惊!杭州湿度达到100% 墙壁、窗台“挤”出水:网友吐槽难受到爆
当前聚焦:Linux中查看日志的常用命令
环球聚焦:算法学习笔记(8.2): 上下界网络流
当前最新:直播:央视网络春晚 最美女主播王冰冰亮相:王心凌等也来了
动态焦点:屏幕最小的第二代骁龙8旗舰!曝三星Galaxy S23卖6500元
老款iPhone激活原生灵动岛!DynamicCow教程来了
python批量发邮箱
有了这份Java面试中的葵花宝典,让你面试起飞!!!
每日时讯!还买什么Zen3/Zen4 6核酷睿i5-12490F到手1139元(首发1499)
焦点速讯:公司年终奖老员工人手1个30克金牌 感谢忠诚引热议:网友问还招人吗?
世界微资讯!Codeforces Round #843 (Div. 2) A1A2BCE(D待补)
储量超100万吨 瑞典发现欧洲最大稀土矿床:有望结束进口依赖
环球即时:首发4999元 Bose家庭娱乐扬声器550发布:支持TrueSpace增强原音
苹果iOS 17新特性和新功能抢先看!今年6月登场
有家长炮轰《中国奇谭》 导演回应:审美提高了就理解了
世界速看:Codeforces 1630 E Making It Bipartite 题解 (Dilworth定理)
世界播报:使用 Elasticsearch 搭建自己的搜索系统,这个厉害了。。
理解宏定义
2023春节新片预售票房破3000万:黑马杀出 《流浪地球2》仅排第三
数字化“乡村小道”跑得不舒服,试试低代码“高速公路”
当前看点!一位民办二本学生的年终总结
今日看点:荣耀首款小折叠屏来了:5千档真香
世界信息:今晚8点播出 王冰冰、撒贝宁等人组团剧透央视网络春晚
3999元解决安卓四大不可能 一加11成酷安最热机型:领先第二名一倍
认识Java语言
读编程与类型系统笔记07_子类型
张朝阳称年轻人不要只追求赚钱和快乐:想法不对 你会很痛苦 本人风趣回应
当前热讯:网易开始解散暴雪游戏相关团队!分手已成定局
世界微头条丨特斯拉海外大降价 美国新车主:恶心、不愿再看一眼爱车
全球快消息!门票值了!大熊猫看到游客后展示“才艺”:抱着竹子连续翻跟头
省钱还是抠门?马斯克不交房租:员工在工作日被房东赶出
当前视点!Netty-核心模块组件-4
环球视点!微信将处理假冒仿冒官方组织公众号:严重违规直接删号
全体起立!马自达MX-30 R-EV官图发布:转子发动机回归
全球要闻:雷军晒奖杯:《小米创业思考》获2022豆瓣年度大奖 揭秘小米创业经历
和女神视频聊天再也不害羞了!NVIDIA新技术让你“暗送秋波”:画面以假乱真
今日热讯:新娘刚下婚车遭痱子粉迎面砸脸引网友热议:婚闹是素质缺乏没教养?
当前讯息:“爱妻”来了!理想L7“皇后座”到底有多爽?1米2的腿部空间感受下
万元LV误标1599元被秒拍 得物回应:多次确认无异 无权干预
ruoyi打包jar分离配置部署
环球热消息:今晚8点见!2023央视网络春晚节目单发布:王心凌、董宇辉首次加盟
数论笔记-同余
“背菜女孩”家人回应1年赚20万 不穷:虚构捏造博眼球视频获流量应被整治
每日简讯:国铁西安局回应火车内设麻将桌:系主题定制列车 还有KTV、影院
【焦点热闻】苹果1200万像素为何胜过安卓1亿像素?历代iPhone相机揭秘:果然是神优化
记好这24个ES6方法,用于解决实际开发的JS问题
C#、TS和Dart对比3:编译时常量和运行时常量
2023性能战神!卢伟冰:Redmi K60 Pro是用户追求性能的不二之选
环球要闻:卡梅隆发文diss漫威电影:超级英雄演的像大学生
【天天报资讯】集体涨价!Intel 13代酷睿8款新U开卖:65W 24核高达4889元
为什么人类很难准确预测未来?
全球快看点丨《和平精英》开枪时的振动:居然可以造福盲人
当前消息!模板-线段树