ucu8xON2nHBY
url:ProblemCCodeforces 题意: 给n个数字和一个m 给一个操作:每次使得其中一个下标的数字=-1 要求最后在所有前缀和中前m个数字是最小的 思路: 在所有前缀和中分为三类,一类是在m前面的前缀和,一类是在m后面的前缀和,一类就是m本身 先考虑在m前面的前缀和 如何让在m前面的前缀和全部都>=m前缀和? 直接反过来考虑,从m开始向前面累加,如果累加的值>0了,代表需要操作一次了 因为如果累加值>0了,前面的一个前缀和直接不加这后面的一坨即可<m前缀和 关于这个思路怎么来的 我借鉴了一下ygg的思路 k为其他前缀和的下标 a[1,k]>=a[1,...
比赛链接:牛客小白月赛65_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ(nowcoder.com) A:牛牛去购物 题意: 给n元钱,有两种商品,价格为a和b,问最少能花到剩多少钱? 思路: 一开始就猜了发结论:min({n%a,n%b,n%a%b,n%b%a}) 感觉自己对麻了 然后喜提WA 但是实际上要花到最少并不一定是先把其中一个花到不能再花才考虑另外一个 比...
url:4366.上课睡觉AcWing题库 题意: 给n个石堆,相邻石堆可以合并 现在要求每个石堆都相等,问最少合并多少次 思路: 由于不管咋个合并,石子数是不会变的 那么就可以枚举一下合并成多少个石堆 然后再用石子总数/目标石堆数,就为每堆石堆的石子数 这时候就会发现,有的石堆数是无法合并成的 因为石堆数必须为石子总数的质因子 不然石堆数每堆的石子数!=石子总数了 然后就是如何去判断合成x堆石堆是否合法 这里我就没想到咋个去判断 其实不用管咋个去合并,换一种思路即可 将n堆石堆划分成x堆,并且每堆的数量为$sum/x$ 这样就好理解多了 直接一个循环就判断完了 由于只能合相邻的石堆 那么就一...
url:4645.选数异或AcWing题库 题意: 给n个数,再给m次查询,给一个数x 每次询问给一个区间l,r,问是否能从$[l,r]$中选出两个下标不同的数 使得它们的异或值等于x 思路: 这题有个异或性质我没想到( 找两个数使得$a[l]⊕a[r]=x$ 根据异或的交换性来说 式子可以变成:$a[r]⊕x=a[l]$ 那么我们直接用$a[r]⊕x$即可得到$a[l]$ 这时候问题就变成了去找离r最近的$a[r]⊕x$即可 暴力思路就是先枚举后端点,往前枚举前端点,记录每个点的满足条件的最右边的值 当然这是O2的,肯定不行 用个map即可很好地解决这个问题 每次map都记录一下a[i]的值...
题意: 给一个长度为n的只包含'G'和'H'字符串 要求统计所有长度>=3且只有一个不一样的字符的子串个数 思路: 最开始的思路就是 找到一个满足的三个字符 然后向两边扩展 然后就寄了 先不论时间复杂度 每添加一个字符并不是贡献+1 然后就换了一种思路 每次碰到那个特殊字符在中间就向两边扩展看看两边的数字是多少 然后贡献等于xy 然鹅发现贡献并不是这么多 比如GGHGG的贡献是6 通过这种方法算出来只有4 看了题解 原来还要考虑那个特殊字符在两边的情况 上面那种情况算漏的情况就是GGH和HGG 分别代表特殊字符在最左边和特殊字符在最右边 贡献分别为max(0,y1)和max(0,x1) ...
url:DashboardCodeforcesRound843(Div.2)Codeforces A1&&A2.GardenerandtheCapybaras 题意: 给你一个只由$a$和$b$两个字符组成的字符串 现在要你把这个字符串分成$s1,s2,s3$三部分,要求满足下面的两个条件之一 $s2>s1ands2>s3$ $s2<s1ands2<s3$ 思路: 一开始就想暴力的,但是看了看后面还有a2,所以这题一定有简单的方法 由于只有$a$和$b$两个字符,所以只要$s2$第一个字符是$b$的话,两边就很难大过$s2$ 所以我们只要分为:开头的一个...
A.LinearKeyboard 题意: 给26个字母代表你的键盘(没错你的键盘键位是一行) 再给你一个字符串,问你打出这个字符串需要消耗多少距离 思路: 前面几个数据键位没乱当然不用管,主要是如何处理乱序键位 就用个map来映射就完事了,把乱序的字母映射到26个正序字母上即可 后面套上map后的处理就跟没乱序一样了 代码: voidsolve() { map<char,char>mp; intans=0; strings1,s2; cin>>s1; cin>>s2; charx='a'; for(inti=0;i<26;i) { ...
A.TrickySum 题意: 给一个n,求1到n的运算,如果不是2的次方就加,否则减 思路: 由于n有1e9,直接暴力扫过去肯定要寄 所以先$n(n+1)/2$来算出1到n的和 再减去2倍的2的次方之和 代码: voidsolve() { cin>>n; intres=n(n+1)/2; intop=0; for(inti=1;i<=n;i=2)op+=i; cout<<res2op<<endl; } 总结: 水题不用总结( B.QueriesonaString 题意: 给一个字符串,再给n个操作 每次取l到r然后操作k次 每次将一个字符从...
url:DashboardCodeforcesRound847(Div.3)Codeforces A.PolycarpandtheDayofPi 题意: 判断给的字符串前多少位跟PI一样 思路: 打个表,然后遍历一下即可,遇到不是的就退出 代码: stringop="314159265358979323846264338327950288419716939937510"; voidsolve() { strings1; cin>>s1; for(inti=0;i<s1.size();i) { if(s1[i]!=op[i]) { cout<<...