B. Array Craft题目的意思理解就卡住了我首先我们要弄清楚题目说的最大前缀位置的含义在所有前缀和 S1,S2,…,Sn 中取最大值然后取最小的下标i 使得 Si 等于这个最大值。也就是说我们要找到第一次出现全局最大前缀和的位置。那么最大后缀位置的概念就是取到最大后缀和的最大i另外最大后缀和可以等价于Si-Sn。构造的思路看到xy这样会让人想到分段再加上要求数组只有1或-1这样我们就不男想到分段用-1的震荡性去构造数组。前段交替-1使得y位置的前缀和为0或1让这个值最小。然后中段全部用一也就是y到x之间在这个区间内我们构造的Sx最大。后段继续交替用-1是都后面前缀和不会超过这个Sx。B. Evanescent这道题是之前div3的第二题现在看来我当时没做出来的很大一部分原因是因为情况没有考虑完整我当时考虑到了最优的情况字符x左右两边的字符一样并且x与他们不同。但是除了这一种情况其实还有一种就是当x独立成块。我当时是把这种独立成块的情况与随便哪一个的情况搞混了。现在分析一下当我们删掉独立成块的x那么f数组的数量就会减少1如果这个x并非独立成块那么就不会影响结果长度。B. Corner Twist我第一个想法就是用两个二维数组用来存储a和b然后我感觉少了一个关键的观察但是想不出来。我发现这里有一个翻译的错误题目里说的是1加上角落上的数字mod3的值。但是样例解释中确实先加1在mod3小问题以样例为准。上述的关键观察就是在操作中有一个东西一直保持不变这是我没观察到的下次可以从这个角度考虑。这个值就是a中每行每列的和mod3的值所以我们只需要对比b中的每行每列的和mod3是否与a对应的相等。B. OIE Excursion如果我能左右横跳那岂不是包过。就是说如果两个相邻守卫之间有空档期就是计时器归零的回合不同那么我就可以左右横跳这时候这两个首位后面的一个守卫我就可以忽略。虽然但是我的思路还不够完善。可以反复横跳这一个想法后不应该考虑第三个守卫而是一段守卫这段守卫的特征是m一致。也就是说接下来考虑的是我们能否通过这一段守卫因为反复横跳可以跳过其他守卫因为我们走路一格需要一秒设这段守卫的长度为l那么通过则需要l1秒。那么可行性判断就有根据了因为守卫的计时器是m小于l1则不能通过。(我的理解稍微有点问题就是一开始我认为周期不一样起始时间一样但是实际恰好相反CF1935B Informatics in MAC我一开始的思路是假如数组里没有0和有0的情况。当数组里没有0时随便分因为最大都是0。但是如果数组里有0那么0的个数至少为k不然不可能每段相同。假设数组的MEX为m简单来说分成两段时最好的因为此时只需要判断前段是否包含0~m-1后端是否包含0~m-1前端的长度该怎么得出我们可以用贪心思路就是另第一段最短并且包含0~m-1找到哪个断点再判断断点之后的包含情况即可。CF2219A Grid L我觉得关键点是找不变的东西但是我没找到。它就是线段总段数网格的段数与给定数量的直线线段与直角线段的段数总和他们俩应该是一样的。那么就可以列出一个等式。再列等式之前。可以把两部分都先单独用字母表示。用mn表示此时n行m列水平的线段数此时每行有m1个有n行那么就是n*m1垂直的段数此时每列有n1个有m行那么就是m*n1总和就是2nmnm。然后就是用pq计算总段数p是1q是2那么总段数就是p2q。两个总段数相等2nmnmp2q然后再根据左边的形式我们尝试将左边变成AxB的形式。先左右两边各乘2然后再加1。此时问题就变成了找到两个因数乘积等于2p4q1。左边就变成了2m1x2n1。细节补充因为m大于等于1n也大于等于1那么A就大于等于3B亦是如此所以我们就可以从3开始遍历。我在提交的时候还发现了一个点需要注意我们输出的nm是有条件限制的这个限制与pq有关也就是说这个限制是一开始就有的。具体的说假如我们的长的总段数比直角线段的个数那么这个是不成立的因为这样的话放不下那么多个直角线段。CF1933D Turtle Tenacity: Continual Mods是不是只要第二个数是第一个数的因数就行了因为这样第一次算mod就等于0然后0mod其他的数还是0。但是有一个结论我忽略了导致不对当两个数相mod时rmodyr小于y结果不变如果r大于等于y此时取模后的值会小于y。所以只要中途有一个余数小于剩余所有的数那么计算玩所有y这个值不改变。假设数组中的最小值为mn。然后情况1mn只出现一次那么我们就可以把mn放在首位然后这样最终值只能是mn输出yes。情况2mn出现的次数至少两次并且数组有个值不是mn的倍数。设这个值为x那么我们可以这样去构造序列xmn其他元素。这样构造为什么可以x mod mn的值小于mn所以这个数比剩下的元素都要小那么最终的值就不会等于0输出yes。情况3每个值都是mn的倍数无法避免0。因为怎么排列总会出现0。CF1922B Forming Triangles要满足条件选出的三条边能构成三角形要满足两边之和大于第三边。我感觉可以从小到大遍历数组固定两条边然后找数组中比这两条边之和小的值。我的结局是超时可能与我漏掉这个性质有关系数组里每条边的值是2的ai次。这个条件可以帮我们简化过程。该如何操作以达到简化的目的假设三条边的位置为ijk那么此时一定有2 的 ai次 加 2 的 aj 次 小于等于 2 的 j1 次加上一个小于等于自己的数肯定小于等于这个数乘上2。然后要满足三角形的性质ak的值必须小于等于aj但是k要在ij的后面也就是ak大于等于aj所以ak只能等于aj。但是这样做可以说有个前提ai要小于aj不然不充分因为还有一种情况是三条边相等。当ai等于aj的时候他们的和就等于2的aj1次但是这个结论推不出ai小于aj的这种情况所以两种情况要分开写而且他们的计算方式也不同。CF2218E The 67th XOR Problem题目的意思就是我们对一个长度为n的数组操作n-1次每次选一个数删掉剩下的数异或这个被删掉的数我们要做的就是找到一个合适的顺序使得剩下的最后一个数尽可能的大。要是每个数组的结果都只由数组内两个数组成就好了。你赢了异或。证明之前得先知道异或的一些性质异或运算具有结合律以及交换律。假如数组只有两个数那么答案就是这两个数的异或这很好理解。根据归纳思维我们假设一个长为k的数组这个数组的里的元素有a1,a2,…,ak。我们对它进行题目中的操作选中一个元素aix删除它然后数组其他每个值异或xa1^x,a2^x,……,ak-1^x。那么从结论出发现在数组的大难就是(ap^x)^(aq^x)再根据交换律与结合律结果也等于ap^aq(q!p)可以证明归纳是对的。其实这里可以把x看成除了pq以外的所有值这样跟好理解一点。然后就可以遍历整个数组找到最大的那一个。这题感觉就是对异或运算结合律和交换律的灵活运用再就是数学归纳思维显然我没做出这题是因为我这两者皆缺。CF1916C Training Before the Olympiad看到这题我在想要解决masha和olya的要求得先知道怎么改变操作后的数因为按照数学的思维和除2再乘2结果是不变的但是这是整形也就是说值会改变。比如说1和2的和是3除以2是1乘以2是2所以从结果上来看就是从3变成了2变小了。所以只要两数和为奇数就会变小这样的话要让剩下最后一个数字最小的话最好是奇数和偶数相互配对然后多出来的就自己与自己配对。我的思路并不是最优的解法因为这里面还有博弈的存在这是我没想到的这是两个人同时操作的数组。也就是说想让数最大的那个人会想办法阻止另一个人将数组变得更小也就是把他的奇数用了也就是这个人一定会选两个奇数如果可以的情况下。所以当奇数的数量是3时那么每轮操作都只会对结果减少1从我举得例子就可以看出1奇1偶的选择会让结果减少1并且奇数的数量减少3。所以我们可以考虑奇数的数量来判断答案会不会减少减少多少。CF2217C Grid Covering这道题我的思路比较倾向于用题目中的nm和ab之间的关系来求解但是具体是什么关系我卡在这了。其实更核心的原因是没有将两步跳跃看成一组。为什么题目的要求两种跳跃需要交替进行所以怎么看经过两次操作之后的净收益都是ij——》iajb过的点一定属于H{ta mod ntb mod m}这个t是常数表示加上t个at个b。然后我们要计算的是H里有几个点可以分开行列来计算。先看行每次行跳跃加a然后经过多少次会回到原来的行n/gcdna。同理列的答案是m/gcdmb。所以要让行跟列同时回到原点需要lcm也就是两者的最小公倍数。然后最多覆盖的格子数为2H从左上角往右下方移动的过程中有两种移动方式所以会多经过H个点。总共2H。那么怎么才算覆盖所有点光光是2H比所有格子数nm多是不充分的但是如果比nm少那一定是NO。然后就是数学公式的运用我们设g1为gcdnag2为gcdmbdgcdn/g1m/g2。又lcmxyxy/gcdxy。所以Hnm/g1g2d。根据2H小于等于nm。可以得到g1g2d小于等于2。第一种情况g1g2d都等于1此时肯定全覆盖。第二种情况等于2。合理的是d为2其他为1此时Hnm/2所以2H正好填满。其他情况会出现2Hnm但是两个平移集合无法经过所有的格子所以NO。
