CF1929C Sasha and the Casino本来楼主认为只要前x1次都投一块然后一次能拿出比之前多1快就行 就是x1x2/k-1a但是我发现我的理解有问题我们每次投入的都要以赚的前提去投先设两个变量sum和betbet表示本次投入的本次需要投入的硬币枚数因为每次都要当作回本来投入所以betk-1-sum要大于等于1也就是betsum/k-11。需要注意的是x在这里指的不是保底机制输x1次后一定能赢而是赌了x次后就不能再赌了。然后代码里有一个需要注意的点就是循环从0开始因为输第零次也是输。CF1927E Klever Permutation感觉不难可是我又没想到我想我应该是卡在了没又重点分析s上因为有个核心就是围绕s的。这题我总结出了两点核心首先就是用s之间的关系找到奇数位上和偶数位上的构造方法第二个核心就是构造的方法上不难但是控了lz好久。先来讲讲这个ss的是一个数组与题目中的s一致我们要知道一个现象s中两个相邻两个数不可能相等因为相邻两个数之间的区别就是ai、aik然后因为a中没有两个相等的数所以导致了a为我们要构造的数组。又因为是s相邻两个数之差不能超过1也就是说s11s2s2s31……然后用我们上面分析出的s1与s2之间的差异为a1、ak1所以a1 1ak1a2ak2 1。所以得出偶数与奇数的构造方法。然后就是另一个核心这也是代码里值得讨论的首先i从1到k代表的是链的个数然后j每个j之间隔着k。打个比方n10k4只需要4个链1-5-9 ; 2-6-10 ; 3-7 ; 4-8;完事四条链。真是太巧妙了。B. Fashionable Array(div2)这道题我的构造思路是对的循环构造从最大值到最小值每个值在一个循环里面只构造一遍如果用完就跳过。可惜代码部分我败了所以本文着重讨论代码部分是如何实现上述思路的。首先我们要压缩数组吧我一开始想到的是set但是当时不知道set如何从大到小排而且循环部分写的也不太好我们不妨先排序然后用一个循环和一个数组来进行压缩就是如果这个数在新数组中存在那么就不存如果不存在就存所以循环之前要先将压缩前的数组中的第一个数存入新数组不然会re。在这之前我们在读入数据的时候就可以用到mapunordered_map来存每个数的在原数组的中的个数。最后我们循环存n次每次按照新数组从前到后就行。C. GCD Treasurydiv2这种gcd的题目我老是抓不中本质lz初看这道题目我只能想到每个等于x的是我们期望的因为这样可以全部拿走或者是gcdxai等于ai的这也可以全部拿走但是其他的我就想不出来。这题核心朝着x的质因数想每堆金币能被这个质因数整除就能被全部拿走然后比较每个质因数取最大的那一个。这里应该问我自己为什么结论成立怎么想到这个结论的首先为什么成立举个例子金币2344x66的质因数为2、3那么所有能被2整除的2、4、4结果为103的结果就是3答案就是10。模拟一下就是6先找到4gcd64为2取24变为2x变为2金币堆变成了2324继续找4发现最后全变成了2x此时也是2那么全都可以取也就是能被质因数整出的数全部可偷。然后是怎么想出来的g是x和ai的最大公约数也就是g小于ai并且是ai的因数又因为x要变成g再加上ai-g还是g的倍数所以还能选这个ai直到ai等于0并且最后这个g一定是x的质因数所以就想到了。我们要怎么找质因数用质数的模板然后x除掉这个质因数如果能除然后边界此时也发生变化最后循环完之后还有一个需要注意的地方此时x除完可能大于1也就是说剩下的也可能是x的质因数。最后找答案的时候别忘记取最大值就行。CF2226C Mental Monumental (Easy Version)这道题真没想到可以用二分去做。lz一开始想到的是直接求mex最大值但是怎么想都想不到有什么好的方法。先说说为什么能二分二分的前提条件是单调性写完这题我觉得单调性比较难理解可以这么说线性结构里面这个位置被证明可行那么在这之前的位置都一定可行如果这个位置不可行那么后米一定不可行。这道题体现在如果这个值可以作为mex那么小于这个值的值一定也行如果这个值不能作为mex那么大于这个值的值就一定不能作为这个数组的mex。上述是一个核心另一个核心当然是如何判断这个值能否作为mex。开始之前我们应该先搞清楚一个现象8可以变成什么0、1、2、3也就是说我们要构造出x需要的值要大于等于2*x1这个现象有什么用。也就是说我们可以用二分出的这个值k当作mex然后去构造这个0~k可以发现可能有些数是数组里面有的这个时候有两种选择将它变为跟小的或者不变这么看来只能是不变更加的划算因为就算这个值在数组里面没有我们也可以通过比这个值大2倍1的值构造如果没有那也只能说这个k不对。这也就是我们的判断思路。代码怎么去实现思路首先二分不要忘记rmid--就好然后这个检查可以写成函数函数里有几个关键怎么找到0~k剩什么我们维护一个数组来存储每个值的个数然后遍历0~k如果有这个数就-1然后跳过如果没有可以存入一个missing数组然后为了方便判断我们可以数组中存完的数存入一个数组b然后遍历数组missing每个值都在b中找不符合条件的就跳过如果没有就说明这个k不对返回false。CF1923C Find B我想的是偶数个数的时候就可以直接倒转数组来构造bi也就是好数组然后奇数情况我考虑了考虑的很多但是偶数情况的判断就错了我就不说了。应该是我没有考虑到这个数组两个数相等的时候倒转就行不通了。正确的思路应该是从和出发和又从每个值出发所以研究每个aibi我们可以发现ai大于1的时候bi可以是1但是ai等于1的时候bi至少为2也就是说这个b的和最小的情况就是m长度为m当ai都大于1并且先不看a与b的和相等我们要得出这个子串是否可行按照题目的意思应该是从这个S也就是字串的和出发和什么比较呢也可以说我们该怎么限制它首先这个m是可以算上的然后通过ai1的时候bi必定大于1也就是说还要加上1的个数。CF1909C Heavy Intervals这题给我的感觉就是贪心但是我弄错了一个很重要的点。先说我的思路我的思路是直接排序l和r然后反着排c然后对应加起来。这样虽然有点贪心思路在里面但是我只排序l和r相当于只在l与r的内部进行比较而正确的贪心应该是找到与r最接近且小于r的l。代码里有一点我之前好像没怎么见过就是multiset来定义一个数组让r去找对应的l找到的将r与l的差值另外存一个数组这个multiset数组存完需要排序容易忽视然后累加出答案即可。CF1903C Theofanis Nightmare看到样例中的第二组数据我的灵感就来了我问自己是不是只要从后往前和不为0的就划分为1个子串这样和就最大了然后我用第一组数据粗略的看了一下感觉可以然后我就把代码写出来了结果样例一都没过。因为我会将-6和7加在一起导致后面的系数少了所以我在想有没有一种方法可以既让这个子串是正的又让后面子串的系数尽可能大事实是我根本想不出来。这题的核心观察是在这个位置切一刀假如是i那么i后面的所有数的系数都加1也就是说ai1、ai2、……、一直到n-1的系数都加上1所以在i位置切一的贡献值就是后缀和从n-1到i然后问题就变得简单了我们只需要判断这个位置的后缀和是否大于0大于0说明有利那么就加到答案上。可以不用写后缀和数组因为是从右往左顺序下来的也就是说只要一个变量就足够了。但是这也有一点很容易出错的地方代码里如果不特殊处理那么所有数和sum如果是一个负数那么ans就不会加上它这样我们会少加上所有数的和因为我们是在初始子串为本身上开始切的所以这个和不可或缺我们可以通过sum判断里加上||i0但是不能在循环结束直接加sum因为如果sum为正会多加一个所有数的和。CF1901C Add, Divide and Floor这题我没什么很好的思路我一直困在两个数之间的关系比如说3、4这种相差1的是不是只用一步就可以将这两个数化为一致用什么数又试了几个样例我发现4、5又有些不同然后我就被困住了。如果我想到用他们本身就好了3、4我让x3这样操作一次后3不变4就变成3。也就是说我要找到数组中的最小值然后每次操作都用这个最小值去操作数组其他数造成的结果就是其他数都会向最小值靠拢。那双向奔赴岂不是操作步骤更少但是我们的操作只能让数减小不能增大。代码里用到了一个求数组最小大值在这题挺好用的办法*min_element(a.begin(),a.end())这样就不用多写一个循环了。CF2264C Madamants Skating Dynasty这题真是难到我了。起初我是连题目都没看懂啊。我没想到是所有可能数的和。比如说321可以是1的父节点22的父节点3也可以是1的父节点是32的也是3。这两个树的成本和就是答案成本就是根减去子321的两个树的成本就是2和3答案就是5。搞清楚这个之后好像除了找到所有的树我就没有啥别的办法了。仔细观察我们可以发现aj到aiaj为父类这条边会在很多树里出现并且个数如果能算出来的话那么贡献值就知道了。首先我们要知道总共有多少条边(n-1)!然后我们对i这个位置进行研究本来比i大的都可以作为他的父类也就是n-i个所以这个时候我们就知道了aj到ai这条边有多少条了(n-1)!/(n-i-1)因为如果所有边去掉没有ai到aj的那是不是就剩下aj到ai然后我们就可以固定ai那么可以选择的父类就不只aj然后每个父类都可以用上述方法求出贡献值接着我们只要遍历子类就能得出所有的边的贡献值我们可以遍历到这个子位置的时候求一个后缀和就是所有可能父类的边的成本我们就都可以统计了。代码里有一难点和痛点MOD都给我写烦了/n-i-1的时候不能直接MOD而是要用到费马小定理a−1≡aMOD−2(modMOD)要求MOD必须是质数然后就是求cnt的-1次也就是模逆元模板见代码https://codeforces.com/contest/2264/submission/392579735这个真是有点难理解。然后你就会切这一道题了。