CF2254E Chronostasislz对这种题是完全没有抵抗力啊写一道错一道。这题核心是找到b数组与a数组的关系。aiai-1bj这里的i-1指的是前一个数又因为ai是大于等于1的所以就得到了ai-1与bj的关系bj大于等于1-ai-1这里bj是已知的也就是说只要用lower_bound找出来就行然后ai-1就是ai的钱一个位置最小就是a1然后一次次增大知道an所以这题可解。那么a1的选择呢因为大于0所以要找数组里upper_bound(0)的数如果没有就-1。所以这个初始数组我们可以用multiset来存。因为如果要判断找不找得到可以直接跟end()比较。然后就解决了。CF2120C Divine Tree把这题看成树然后用树的思维去解题是不对的怪不得我没有思路。这道题其实就是要满足条件的构造。首先明确条件要使得总神性等于m很明显的构造。神性的概念是从根到这个编号的所有编号最小值例如3-2就是23-2-1就是1。那么现在的思考方向应该是如何让问题变得简单。分析1为根的情况有些时候特殊情况可以带来灵感那么总神性恒为n不管节点怎么排。那如果要向m靠拢这样不变肯定是不行的要不然就拿出一个数来当根看看放在1上面根为r这个时候我们发现总神性不会再变小r固定的情况下值为rn-1最小值都有了那写出最大值岂不是就能判断了当m在这个区间内说明r成立最大值为r (r1)/2r(n-r)这个最大值是从将以1为根的数移到以r为根所构成的因为在1下面神性值只能是1嘛。然后我们遍历1~n就可已找到那个合理的根root。找到根之后呢在上段写最大值的时候有个发现将1的节点移到r下面可以增大神性值那么我们就可以从最小值开始移动每个值并且更新所需要增加的值。不过其实从最大值开始减可能更好理解需要减去最大值-m每次移动都可以减去min(r,i)-1i就是r下面节点的编号1的话就是 移到1下面之后的神性值然后更新操作同上。代码的话root1要特殊判断然后就只用分为两种情况需要移动和不需要移动需要移动就先输出1在输出i不需移动就先输出root在输出i。别忘记换行就行。CF2110C Racing一直到中间部分lz都想到了当d[i]等于0的时候相当于区间不变当它等于1的时候相当于区间网上移了一格当等于-1的时候相当于上边界向上涨一格。这竟然是正向dp但是lz发现前面的选择会影响到后面比方说前面某个位置选了0当时高度确实合适当时后面可能会因为这1个高度导致不行这样我便卡住了。我的考虑是正确的前面的选择会影响到后面的值那该怎么办可以反向dp也就是通过从后往前判断0或者1是否能够满足前面一个的区间限制那要是一开始就无法满足怎么办那只要一开始判断就可以可以用区间的交集如果没有交集直接输出-1。那么该如果0或1都满足该怎么办优先选择0lz的理解是这样高度不用减1也就不容易出错。然后就可以敲代码了。输入之后先用正向dp来找到每个位置的区间顺便找找有没有交集为空的位置有的话直接退出循环利用旗帜判断就行。然后从后往前dp让最后的高度等于第n个的下边界然后用d去改变h的状态h为高度1、0的时候不用改d1的时候h--0的时候h不变当等于-1的时候要跟前一个区间先判断如果h此时已经满足前一个区间那么直接让d这个位置等与0反之等于1。最后输出即可。CF2084C You Soared Afar With Grace这题lz刚开始有个思路是对的就是必须两两对应当n为奇数个的时候可以有一个两两相等的两两指的是a与b中的4个数例如12和21当n为偶数的时候就必须两两对应。我是代码写了一半才发现这个结论的我的-1判断写的是ab相等的个数显然不正确再加之我不知道改怎么去找到答案和存储答案。看完题解我才知道有一部分代码可以当作模板来使用两个排列同时交换位置变成某种对应关系出现这种情况的时候就可以用这个模板。从最开始说起如果要研究两两的关系需要给他们一个位置方便研究这里使用map的pairmappairint,int,intmp这样ab对应位置的两数的位置就被存下来了。然后要遍历这个mp并且维护这个位置值idx然后取出p中的两个值p表示的是ab中某位置的值然后用find找道mp中ab数倒过来的位置假如没有的话就令旗帜okfalse为0然后退出循环。在找之前其实还要判断p中的两个数相不相等如果相等说明有可能是奇数的中间值n为偶数的话就是-1了。然后就是将这个两个位置放在一个数组pos的对应两处pos就是目标位置这两个位置可以用两个同步移动的指针来确定lr--。然后就是模板部分定义两个数组cur、at两个数组正好相反cur表示正向什么位置该是什么元素与pos对应。而at与cur相反表示的是什么元素在什么位置cur[i]i at[cur[i]]i 他们的初始值都是i然后就是遍历pos判断cur是否与pos吻合假如不就找到要要交换的位置进行交换jat[pos[i]]j为等待交换的位置swap(cur[i],cur[j] at[cur[i]]i,at[cur[j]]j然后将ij存入答案输出的时候各1即可因为位置是从1开始的CF2055C The Trail这题有点像填数独每行每列和相等这题关键是找到每行每列的和等于什么因为有条路从11到nm这上面的数都是未知的也就是说没有一行或者一列的和是已知的那么就要lz自行找到某个值X。这里就难到我了因为我无法证明让所有等于0是对的故陷入了迷茫。其实就是让X0。此时假设X0成立不过还有些细节可以节约步骤并不一定要从最后一个往前寻找因为知道了DR……也就是这个路径的运行方向那么就可以在第一个为D的时候让第一行的相反数赋值给第一个位置因为D这个时候表示下面一个数是未知的又因为路径不会往上或者往左走所以第一行绝对是已知的后面也可以以此类推。这是我觉得精妙和值得学习的点。代码部分有一点需要说在主函数里函数auto X [](int x,int y)X为函数名xy都为函数读入的值我觉得很高级可以在不想在主函数外面定义变量的时候用。最后来证明为什么X0成立lz的理解方法是用样例中最后一个测试理解我一开始做的时候发现除去最后一行和最后一列未知行的和等于列的和也就是说完全可以让每行每列等于零只要让左下角等于这个和的相反数即可。CF2260C Maximize XOR, Minimize Operations一开始我不知道结论想着暴力枚举后来我知道了结论想的依旧是暴力枚举感觉自己没救了。这道题的关键结论x ^yxy为什么要往上想因为可以观察题目发现xy的值保持不变不管经过几次操作。然后为了使xor和最大开始操作到了x-k和yk这个时候令x-ka为了让次数最少a尽可能地大所以运用二进制贪心就是从高位开始尝试因为a是s中的一部分a^(s-a)s所以可以用s作为模板尝试如果第i位s是1那么就尝试让a的s位也是1再加个限制条件就是a要小于等于x很好理解。CF2239B Decidophobia经过学长的讲解lz发现这道题可谓精妙先听听我一开始的思路来进行一个先抑后扬。lz一开始觉得我改变了这个位置的状态体现在题目里就是给ai礼物应该会影响到周围一些人状态因为如果这个人视野内有人获得了礼物那么这个人的幸福度是会改变的。所以我想这题应该是贪心或者动态规划吧。没想到都不是连我的结论每个人的贡献值是一定的就是我改变ai的状态并不会影响其他人先在让lz简单证明一下深入证明我不会这里先给结论------贡献值value为2dai-sum这个sum是从i的左边d个和右边d个a的和。首先这个2dai我这里借用学长的思路真的好BF_AC错题补题解3(1300-1500随机题)-CSDN博客可以说是给他礼物他固定会增加这么多假设这个2d范围内有一个非ai的人有礼物那么他的初始值就是-ai假如此时给ai礼物那么就变成了2d-1ai增加了2dai也就是说和其他人是没有关系的这了省略了2d范围内其他情况。然后这个sum因为视野内有人有了礼物那这个看到的人幸福度肯定是要减少的所以改变了这个人所带来的影响整合到了sum里所以这个人的贡献值就固定为增加的-减少的每个人互不干扰所以就可以遍历每个人然后只加上贡献值大于0的就是最终答案。代码里还是有值得品味的比如说怎么体现环就是n-111chagpt给我的版本里是这么个思路整合三个一样的数组然后遍历中间那一个完整的叫做圆的展开。精妙的思路。CF2034C Trapped in the Witchs Labyrinth竟然想让我困住英雄罗塔姆lz一开始确实想到了用dfs和bfs就是代码忘了怎么写我是这样想的先找到所有能出去的点用bfs就是先在队列里存哪些一定会出去的点比如说第一行的向上、最后一行的向下、等等然后反向bfs找到所有的可出去的点并标记然后就是处理和没被标记的点lz觉得没被标记的点就是困住英雄罗塔姆的路线的一部分然后可以增加这路线的长度但是这样好像不太对再加上我卡在了后面怎么将加到路径上。这道题的核心是找到哪些能被安排的点就是通过来最大化困住罗塔姆的路径这点确实是想到了的CF1974D Ingenuity-2这道题还是挺简单的就是说一下代码里面有些很巧妙的地方。让lz先来简述一下题目的思路为了让两个东西到达同一个地方应该对应分配也就是一个方向在两个行动轨迹中出现的次数要一致然后允许是奇数因为两个方向之间可以抵消比如N和S。所以只要将特殊情况排除即可具体有哪些特殊情况首先只有两两抵消方向虽然终点一致但是另一个会被冷落要排除接着就是如果两个反向的个数的奇偶性不一致最后就是每个方向各一个的情况如果直接按照后面的输出会输出4个H也要特殊处理。代码里用乐一个很巧妙的方式来存储各个方向的个数就是他们的asc码值然后就是普通情况的输出先对个数/2然后再不等于零的情况下输出R否则H因为int会自动抹零也就是说就算是奇数也会被存入H可谓妙哉。CF2237D Fullmetal Bitchemist这题吓到lz了pos想用模拟了不行我要克制结果就是除了模拟啥也不会。ai给的思路后面还行关于mod3理论感觉太过牵强我用洛谷上神犇的思路来解释一下。假设p为数组中1的个数-0的个数。当进行00-1的操作的时候p变为p311-0时p变为p-3所以pmod3肯定固定但是我发现这其实与ai的思路又不太一样因为ai后面要用到前缀和也就是直接用数组的数来判断这个子串是否美丽就是令0-1当00变为1的时候就是-1-1变为1-2mod3111变为-1的也是。这么分析ai的思路其实与洛谷大佬的差不多但是更简单但是也是更难想到的。然后为了找到有多少个漂亮子串但是我们并没有直接的方法证明这个子串是漂亮的不过我们有直接的结论证明最终的mod一定不为0要是等于0就是不漂亮数组因为0mod3我们看作-1mod321mod31。而10是漂亮数组最终的结果所以判断前缀和mod是否等于0就能找到不漂亮数组不过有一种情况无法排除就是偶数个的完全交替数组例如1010。可以发现前缀和等于0但是它并不是漂亮数组并且我们还要让ans为它减去2因为10、1010都需要排除。如果可以找到这段长度4然后/2是不是就行了2其实就是这样接着就是交给acm魔法了现在来简述首先一个完全交替的子串和一定是0所以需要排除的子串长度一定是偶数。i-lst/2只要ans减去它即可简直神奇lst是第一次破坏完全交替的位置比如说1010那么就是2因为没有出现前后一样的情况就是4-0/2等于2正好减去10和1010神奇。