CF1079div2
https://codeforces.com/contest/2224/problem/AA贪心因为算是a_ia_ia_i1,所以就是从右侧开始每一个求可以得到的最大值最后看有多少个大于0就是最终的结果。也就是但是注意不要忘记加上最后一个数的结果#includebits/stdc.husingnamespacestd;constintN2e55;#definelllonglongll t;ll n;ll a[N];intmain(){ios::sync_with_stdio(0);cin.tie(0);cint;while(t--){cinn;for(inti1;in;i){cina[i];}intcnt0;for(intin-1;i1;i--){a[i]max(a[i]a[i1],a[i]);if(a[i]0)cnt;}if(a[n]0)cnt;coutcnt\n;}return0;}B数学贪心首先分析要求mex与max的求和的最大值。分析可知max求和要最大时那么最好就是把最大值放在第一个即可对于mex求和最大那么就是尽量从0开始排列连续的数mex的值应该时从0开始逐渐增长的。所以可以发现这里max增大对最终结果的影响最大只需要最大值放在第一个位置后面所有的Max就都是这个最大值了。对应的mex每次只能增加一个1。因此这里的序列取的是第一个数为最大值随后按照尽量从0开始排列例如对于0122234应该排列为4,0,1,2,3,2,2。注意相同的数前面应该放1个就可以。然后就是计算时的问题了max已经是固定的为a[n]最大值*n。只需要关注mex就可以。为了简化计算那么就最开按照把所有数从0开始排列求出最长连续的初始序列可以通过简单的数学计算求出当前的mex值—从1开始的等差数列和剩下的值。随后把最大值放到第一个位置—因为要求的序列相当于是初始序列最大值放到第一位后的结果。由于放到第一个位置导致其中的mex值出现变化那么需要减去这个变化多加的mex。这里分为两种情况1把数组最大值认为mx。如果这个mex值在初始序列的连续部分中例如初始序列为012321对应mex序列为1,2,3,444。变换后的mex序列012444也就是多加了一个mx大小为3。2如果mex不再最开始序列中例如初始序列为012353对应的mex值为123444那么多加的值也就是mex的最大值为4需要减去一个4对应代码也就是ans-min(need,mx);#includebits/stdc.husingnamespacestd;intconstN2e55;#definelllonglongll n;ll a[N];ll t;intmain(){ios::sync_with_stdio(0);cin.tie(0);cint;while(t--){cinn;for(inti1;in;i){cina[i];}sort(a1,an1);ll ans0;ll mxa[n];ll need0;for(inti1;in;i){if(a[i]need){need;}}if(need0){ansansneed*(1need)/2need*(n-need);}ans-min(need,mx);ansansmx*n;coutans\n;}return0;}C规律前缀和首先分析题目可以发现对于一个合法序列应该是任何一个 的左侧都有一个 对应并且在任何一个位置左侧 数量一定大于等于 的数量。因为左侧 多的序列只需在右侧加入 就可以把当前序列变为有效序列。但是如果左侧有多余的那么就无法通过添加变为有效序列。所以有思路了代码中就可以把 当作1当作-1这个序列是合法序列当且仅当 最后一个位置的前缀和为0。同时因为这里的有两个序列交换其实可以看做从两个括号中分别选择添加到两个已有序列后面目标就是把这两个序列最后前缀和为0。#includebits/stdc.husingnamespacestd;#definelllonglongintN2e55;intt;intmain(){ios::sync_with_stdio(0);cin.tie(0);cint;while(t--){intn;string a,b;intca0;intcb0;intf1;cinnab;for(inti0;in;i){if(a[i]b[i]){if(a[i](){ca1;cb1;}else{ca-1;cb-1;}}else{if(cacb){ca-1;cb1;}else{ca1;cb-1;}}if(ca0||cb0){f0;break;}}if(fca0cb0){coutYES\n;}else{coutNO\n;}}return0;}

相关新闻

ID-based RAG FastAPI多模型支持:OpenAI、Azure、Hugging Face等7种嵌入模型配置指南

ID-based RAG FastAPI多模型支持:OpenAI、Azure、Hugging Face等7种嵌入模型配置指南

ID-based RAG FastAPI多模型支持:OpenAI、Azure、Hugging Face等7种嵌入模型配置指南 【免费下载链接】rag_api ID-based RAG FastAPI: Integration with Langchain and PostgreSQL/pgvector 项目地址: https://gitcode.com/gh_mirrors/ra/rag_api ID-based …

2026/11/20 8:14:51 阅读更多 →
数据库关系模型基础:从域、关系到关系代数的完整解析

数据库关系模型基础:从域、关系到关系代数的完整解析

一.与关系相关的名词1.域:具有相同类型值的集合例:整数,实数,介于某一个取值范围的整数,指定长度的字符串集合等。2.笛卡尔积(1)元组:笛卡尔积中每一个元素的(d1&#xf…

2026/11/20 8:14:51 阅读更多 →
VSCode git/gerrit解冲突

VSCode git/gerrit解冲突

文章目录一、git解冲突的步骤二、文章学习一、git解冲突的步骤 1.发现在gerrit上面是 Merge Conflict状态 2.拉代码变基到本地 git stash #保存本地代码 git pull --rebase #变基拉仓库代码到本地3.Auto-merging时,报某些文件Merge conflict&#xff0c…

2026/11/9 1:27:05 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/19 21:38:27 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/19 21:38:49 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/19 21:39:09 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/19 21:36:50 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/19 21:37:45 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/19 21:36:20 阅读更多 →

日新闻

周新闻

月新闻