一、7.14 周四 1603B
固定的寻找方式，就是思路简单并且代码也简单⚠️ 这里比自己过去碰到的麻烦一点，就是要分情况讨论
（1）我的思路：n = x * k + y，就是可能一直找不到
（2）答案的思路：
X > y的时候，可以直接n = x + y，⚠️ 我想法的最简单的构造方法，只适合x大于y的情况，然后x，小于y就是回头自信性质，
x <= y的时候，总结出了 x <= n <= y，这个是自己总结出来了
关键是构造的n的方法
① 偶数必然会有一个除二的操作，就是构造n的时候就是会有这样的操作
二、7.16 周六 1582D
特定的构造方法，不能是0，也不能是太大
不存在0怎么利用，应该是提示构造的方法，必然是比较复杂的情况构造的时候，能够用上的限制条件⚠️ 单数的时候的构造方法
答案：
因为要求具体的方案，所以必然是很容易的出来b的各个元素的值❎ 不是求方案数，这种必然是dp
只要数字值不要太大，说明就是找到一种合理的方案就行了，不要求最优的方案
（1）偶数：直接配对，构造一种0的方法
直接就是-aj,ai构造，这个是两个数构造0最简单的方法，第一个样例也提示了这种方法，有些样例会有所提示，当然也有red herring
（2）奇数：单独拿出来最后三个数，然后构造一种0的方法
三个数都不等于0，必然有两个是等于正数或者负数，然后选着两个数来固定构造就行了✅ 这个性质也关键，就是找到ai + aj != 0
（3）代码：
② 就是三个元素的两两组合，直接通过if条件语句列举三种情况，就是可以避免很多边界情况✅ 这是三个元素枚举的方法
① 两重for循环，一个break只会提前终止一个for循环✅ 代码写起来并没有那么简单，还是有一些技巧的
三、7.18 周一 1555D
答案：
（1）卧槽，这个只有abc三个字母 + 回文串的限制 -> 刚好推出来一个结论，必然是abcba..这种形式
（2）代码，也是见过的：
三种枚举的方式，三种正确答案
然后判断当前字符串和正确答案的相同 = 1，不同的 = 0✅ 这个在lc每日一题看过，就是获取两个字符串任意区间里面字母不同的个数，o(n)的做法
求前缀和，然后o(1)的出来答案
3、写代码
负数取模：((a - b) % mod + mod) % mod，不是(a - b + mod) % mod，这种是可能 + mod还是负数就会gg，就是如果是mod是大于a-b的这个负数，那是可以的
四、7.24 周日 1707A
⚠️ 我想到了是反向处理，就是要从后面往前考虑，这样就是更加能够顾局全局✅ 就是因为当前的这个决定就是选或者不选会影响后面的决定的，所以就是从后面往前面的话，就是能够只考虑当前的这个数字，关键是需要考虑什么东西，就是从后往前预处理什么东西，这个是题目的关键✨总结：反向处理最小的符合要求的值，这是反向预处理的方式
答案：
这里从后往前看的是，ak当前这道题目，需要的最小的iq值，就是预处理这个最小的iq值 -> 当正向处理的时候，当前的iq值大于预期最小的iq值，就是可以去ak，否则就是不能ak，否则会影响后面的ak数量。✅ 不能透支未来
（1）预处理的出来的这个值，是保证未来的选择都能选上，就是舍弃当下的选择✅ 就是预处理，就是处理出来最小的这个值，这样就是只要当前的值>=这个最小的值，就是能够把未来的所有的数字都给囊括进来，这是反向处理的逻辑，找到最小的符合要求的数值
五、7.25周一 1503A
（0）从整体考虑，最后必然是n / 2个左括号，n / 2个右括号，所以就是1的时候不会影响a、b的括号差；但是0的时候是会影响的，所以就是在0的时候交替，就是可以平衡括号差
① 构造题的思考方法：一看就是构造题，✅ 还是考虑最终答案有哪些限制，很重要的一点就是左括号数量和右括号数量相等
（1）先考虑1的处理，必然是先形成()，就是整体来看先形成就是()的处理
（2）结论：(1) 的话就前一半放左括号，后一半放右括号 = 保证括号序列的两个性质；(0) 的话就看哪边左括号少就把左括号给哪边就行✅ 保证就是左边的括号大于等于右边的括号 -> 通过后序的验证保证括号序列的第二个性质
（3）判断是否合法
（7.26周二）cfca打卡
我的思考
⚠️ 一个数组的gcd和lcm就是遍历数组不断的用两个数进行操作
（1）一个数组的最大公约数：res = 0,for() res = gcd(a[I],res);✅ 0可以整除任何的数，所以gcd(a[I],0) = a[I]
（2）一个数组的数的最小公倍数呢？res = 1,for() res = find(res,a[I])最小公倍数✅ 1和x的最小公倍数必然是x，find(a[i],1) = a[i]
最小公倍数：a * b / gcd(a,b)，
1、easy version
（1）最容易想到的是n % 4 == 0的时候，直接分成三份
（2）然后是奇数，直接n/2下取整
（3）然后是偶数里面的2的倍数✅ 偶数的倍数可以遍历4的倍数，然后再遍历2的倍数，就能全部遍历完所有的偶数
2、hard version
转换为easy version，因为就是LCM是取公倍数的最大的值最为结果，所以k - 3个1，就转换为easy✅ 考察最大lcm的构造的技巧，就是只关注其中的三个数，就能够构造出任意的和
7.27周三
1482C
答案：
（0）只要将任意一个数的数量控制在 = baseline就行了
（1）从全局出发，任意选择一种全局方案之后，如果存在有人违背限制，必然是只有一个人f✅ 因为这里要求严格大于，就是根据一半数的原理，就是只有可以出现一个人违背，这是这个题目的关键
（2）对于f，只要f存在的一天有其他方案，就是交换其他天 + 把f的个数控制在等于baseline就行了✅ 因为就是f等于baseline的话，就是因为是上取整，所以就是其他的天数假设g，必然是<=f，所以必然成立
✨总结：这里充分利用了就是baseline的特殊性，就是只有一个f是可能超过baseline + 只要f = baseline，其他的数字就是<= baseline，这是 / 2的特殊性，ca题的常用思考套路
（1）对于2、3这种数字，就是可以额让常规的题目变得有一些处理的trick，比如就是palindrome、len = 3的构造，然后这里的m / 2，就是可以通过一个数限制住剩下的所有的数字✅ 对于这种2、3的数字要特别敏感，就是这种ca题目中特别需要敏感
3、代码：
（1）10^5的级别的int，不能存储，会超过内存，这是常见的
❎ 我的想法：贪心想法不一定成立，不是全局最优
1、先把只有一个选择的选完
1、优先填选择多的，选里面的出现选择出现次数少的
7.28周四
1481C
思路还是有一点点，但是确定的清晰的思路没有
答案：
（0）✅ 这种后面会影响前面选择的题目，就是可以从后往前考虑，常用的greedily的技巧
① 因为最后一个元素开始考虑，前面的元素不会对最后一个元素影响，就是可以额简化很多思考的细节✅ 就是从后往前考虑
（1）从后往前思考⚠️ 因为就是后面的painter会影响前面的painter，但是后面的painter一旦确定了，就是和前面的是没有关系的
（2）关键的一块plank是最后一块c[m]，因为就是最后一块必然会喷在，bx = c[m]的板子上，因为不受前面的影响；
① 然后前面所有的无效的painter（bx != ax && cj != bx）都喷在最后一块木板上，
代码：
（1）双端队列是deque，然后是单独的一个声明的文件❎ 不是dequeue，这是自己ide错误的
7.29周五
（1）%运算的性质：(a % b) > (b % a) -> a < b，并且可以确定a的值，a % b = a
① 确定了大小关系，那a % b必然是等于a，这是模运算的一个特点，相当于a的值已经确定了✅ 就是两个数互相模运算，必然能够确定一个数的值
（2）最后n的确定，就是剩下的没有填写的那个位置
1407C
7.30周六
Len的倍数，可能是负数，也可能是0倍
⚠️ cfca，就是只有三次操作，必然是一种固定的操作方法
1、三次，说明三次操作必然可以达到这个效果，有一个固定的三次操作的方法
（1）先把a1删除
（2）然后把所有的ai(i >= 2)就是设置成(1-n)ai
（3）然后(n - 1)ai（I >= 2）
2、实际上>=2次操作，任意次操作都是可以的✅ 这是最本质的方法，就是乘以两次倍数，两次的倍数差 -1，刚好长度就是差1
（1）先加上（-n * ai），(1 - n) * ai
（2）然后加上(n - 1) * ai
3、❎ 一次操作也可以，直接就是 + -ai就行了⚠️ 一次操作不行，因为就是直接加(n)的倍数，就是没法保证消除
8.1周一
1371D
（1）一直按着斜线填写，就是在前面的cfca题目见过这种，就是常见的填写套路✅ 斜线的方式，就是必然是对角线
（3）结论，就是按照斜线遍历，只有两种结果，分析样例能够分析出来
（2）代码：按照斜线遍历的代码
① 正常：I++,j = (j + 1) % mod
② 特判I == n：I == 0,j = (j + 1) % mod✅ 就是这里就是移动到下一个斜线的起点
8.2周二
1364C
母题：连续序列，缺失的数，反向思考
（1）
自己的想法：✅ ac了
（1）❎ 确定数的范围，从最后一个数来确定；
（2）⚠️ 对于缺失的地方b[I]有两种情况，一种是ai变化的地方，就是填写；一种是直接从0开始填写
答案：
（1）就是ai != ai - 1，必然是bi = ai-1，否则不会转变
这是缺失的数字，逆向思考，最重要的规律
（2）剩下的bi中没有出现的数字，按照升序填写
模拟样例出现的
（3）⚠️ 没有不符合的情况？✅ 必然能够找到对应的结果
8.5周五
1353D
8.7周日
1352G
（1）关键是相邻的2<=，那自然想到奇偶数，✅ 关键是转弯的地方的处理
（1所以就是奇数下降；）
（2）然后偶数的话，因为要求要求<=4，所以就是第一个符合要求的偶数就是4，然后2，6,8
（3）✅ 正常的是差值 = 2，奇偶转换的过程中，就是1、4、2、6，这样必然能够满足
8.11周四
1348C
（0）✅ 本题本质考察字典序的比较，通过字典序比较的规则，逆向思维构造
① 字典序的题目还是挺反人类的，就是需要多做这类题目
（1）字典序最小的定义：只要第一个字符就是尽量小，整个字符串就是最小的✅ 只看第一个字符，第一个字符最小的那个肯定是字典序最小的
① 比如abc > abbc，这是字典序的特点，第三个字符已经可以判断大小了
（2）思路：
① 判断当前的前k小的字符是否是相同，如果不相同，就是直接的出来答案✅ 因为不相同的话，必然不能均分，只有就是直接接在后面，才能就是让最大的值，最小
② 前k小不相同的话，看剩下的n - k个，如果不相同，就是直接放在一个字符串后面；如果相同，就是均分✅ 因为如果有不同，我们需要让后面大的字符就是尽量放在后面，因为我们这里是只看max，所以就是贪心的就是放在最后面
8.12周五
1334C
一、暴力
（1）根据条件，考虑最后一个，就是最后一个monster的爆炸是没法利用的✨为了让这个浪费的爆炸损失尽量小
二、贪心
（2）✅ 如果能够环形的话，除了第一个，其他的要消失需要的子弹其实都是固定的，这个固定的意思是：只要这些monster是放在中间，就是需要的都是固定的 -> 所以贪心优化的只能是优化断开连接的第一个位置，这个非常巧妙
三、代码
（1）拆环成链
8.13周六
1327C
答案：
（1）2nm必然是可行的，那就是要选一种最简单代码编写的方式，就是处理好这个问题✅ 这种就是只要在一定范围内操作完成的，必然是ca题，想出来一种构造方式就行了
（2）特定的方式：
① 处理这个不出边界：就是让所有的chips都融合到一个点✅ 撞墙的ca题经常这样处理
② 然后遍历整个格子
③ 次数 = n * m + n + m - 3，必然足够的
我的思考：
（1）每次走一个，必然能够走完
（2）卡在抢这边这个怎么写？max，就是不太好操作

【7.6周三】cf构造题1600分段
1、1698D
❎ 只能使用指定操作，来完成本来很简单的事情⚠️ 无序也是可以的，这里有序是为了打乱，就是不让你通过本来的顺序来找a[i] = i，就是出题人为了出题而做的操作
interactive problem？什么意思，就是输入一行处理一行，不能就是全部输入进来
题意：
（1）打乱的数组不知道；
⚠️ 啥玩意，完全看不懂题目，我第一次就是做交互题，果然1600分段的题目还是比较难，就是上来就是迎头一棒✅ 本质就是一个二分题，就是脑经急转弯，只能操作15次
答案：
（1）通过数据范围log(10^4) = 14,符合题目要求，得出用binary search
（2）找二分的check条件，就是列举出来包含和不包含答案的区间，找规律，就是通过找例子，然后猜出来能够区分的规律；然后证明✅ 猜的这个过程是最关键的，然后才是猜二分区间的依据
（3）证明话：
① 对于当前区间[l,r]，就是一次交换贡献是0（一个或者0个元素在[l,r]里面）；或者是2（两个元素都在区间里面）
② 固定的这个点的贡献，必然是a[i] = i，所以如果在区间里面，必然是+1
2、1671D
❎ 思路比较容易，关键是如何用代码描述⚠️ 自己ide思路还没有总结到essence，所以就是不好写
（1）在两个数之间，就是插入递增或者递减的数字，就是不会增加sum；剩下的数字在贪心插入到最小增加sum的位置

答案：
（1）再扩展一点，就是对于任何插入的数字a，只要是在minv <= a <= maxv，必然能够找到一个位置就是插入之后+0✅ 只要考虑最大值和最小值，就简单很多
（2）对于1-x，就是只要把1和x插入进去，构成的新的序列之后，剩下的数字，必然是在1-x之间，所以插入的时候必然是+0
（3）只要找到最小的代价插入1和x就行了，关键是代码实现：✅ 代码实现也是比较有技巧的，然后边界也比较多，值得回味
规定先1后x，reverse在做一遍就是先x后1
然后遍历x的位置，就是插入在i - 1,i位置之间；然后1有两种可能，一种是前面的最小的方案，一种是同样插入到i - 1,i之间

3、1660E
答案：
（1）平移不会改变相对位置（各个对角线是固定的） + 各个对角线的坐标位置的遍历，也是有技巧的✅ 这个正方向 + 这种移动方式是常考的，就是这是一个相对位置的性质
（1）找到与主对角线（从左上往右下）平行的斜线中1最多的，因为平移不会消耗burl，贪心最优移动到1最多的斜线

7.6周三

1、1368C
（1）自己的思路：
需要一种固定的构造方式，然后就是递推？
没有要求最少，只要想出来一种方案就行了✅ 这种只需要想到一种构造方案的题目，题目给出来的样例的构造方案必然是red herring
题目中的构造思路是一种，red herring，我自己要想出来一种构造思路，就是能够符合题目要求，同时就是用代码写起来也是比较舒服的
① 第一种构造方法错误了：读错了题目，是每个grey的格子有偶数个邻居，不是总共有偶数个
② 我的构造方法对于题目条件，又陷入了循环，说明这种构造方法是不可行的
（2）答案的构造思路
关键是每个格子的周围是even个grey的格子，一个正方形一共四条边，所以even只有2或者4两种可能，这是构造的关键线索
Even = 2的话，就是正常的正方形的格子的角；even = 4的话，就是两个正方形的格子公共的角；这样就容易构造出符合要求的方案
2、1368B
① 第一种方法：末尾加s⚠️ 又是样例出来的red herring，构造题的常用出题套路
⚠️ 超出了内存的限制？❎ 这种每个单词只用一个字母因为是最优的？✅ 前面加一个c的话，相当于加了很多单词，所以并不是单纯的加s就行了
快速幂实现
⚠️ 快速幂的板子
② 答案的方案
（1）如果是没有重复字母：abcde，简单情况✅ 就是乘法的最大值法则原理
（2）有重复字母，就是针对这个特定的codeforces的单词想出了一种特定的办法，但是没有扩展性，纯考思维，就是小学数奥讨论题

3、1352F
构造的方法容易想，关键是代码描述的方法
关键是边界0，就是n0\n1\n2分别为0的时候，处理的边界情况，这是这个题目的难点
（1）对于0x0,00x这种，就是直接在处理n2的时候，就是先是1，然后是n2个就能够处理
（2）对于x00这种情况就是只能特判
4、1325C
什么意思，题目都没有看懂
啥玩意，完全看不懂，就是树的构造题，确实比较难想，就是需要对树有本能的习惯的思考
看了网上的题解还是看不懂
5、1283C
⚠️ 关键就是这个问题，就是怎么o(1)，或者nlogn找到不同 + 保证剩下的是不同的，需要构造一种寻找的方案
（1）✅ 先处理产生边界的数据，先处理isolated的点，就是连接到任意一个可行的点，就是让出度和入度的数组里面不存在相同的数✅ 这个处理是这个思路最关键的地方，就是先处理掉阻碍的数字
（2）后面就是o(n)配对

7.4周一

构造体的关键就是要从0想到一种完成的方法，就是完成当前的题目，这是最重要的，就是这种从0开始思考出解题思路的过程，才是最锻炼思维的过程✅ 也就是贪心解法的思考过程，就是基本都是贪心题
1、1426D
关键是没法nlogn的时间复杂度找到区间和为0的区间✅ 看到连续的区间和的题目，就是必然要用前缀和
区间和，就是前缀和，[l,r],Pr - P(l - 1) = 0,转换一下,Pr = P(l - 1),所以就是出现相同的，就需要插入一个数，就是让后面的前缀和重新在一个维度，避免和前面的重复
（1）这种方法必然是最优，因为每个区间和为0的必然需要至少一次操作，这里我每次都是一次操作就解决了，所以就是最优的✅ 关键是想到这种操作方法，这是最难的，贪心的
（2）一定要cut off掉前面的prefix，因为就是可能存在后面的prefix和前面的这段一样的，就是这样是不允许的，因为中间加了一个非常大的数字✅ 所以就是要把前面的所有的都去掉，从新开始
通过代码描述思路的写代码的方式，也是特别有技巧，就是特比的巧妙的
区间和累加，需要注意爆int的问题，经常出现
✅ 技巧就是：判断sum[I] == sum[j]，用hash表的方式来记录，用空间换时间

2、1419D2

（1）这个贪心的方法，其实是没有证明的， 就是想出来的一种可行的构造方法
（2）就是前面的相同的元素插入到后面的n - len / 2个元素中就是有相同元素也是没有关系的，就是后面在统计个数的时候就是直接忽略就行了，就是保证就是在最优操作下还是没法获得cnt++就是这个意思✅ 所以就是这种操作是最有效的
❎ 元素相同的情况下，怎么处理？就是元素相同的处理，是增加题目难度的重要方法✅ 其实还是从easy版本的方法进行改进，就是对相等的值进行处理，对前面的方法进行改进，甚至是证明完全一样的✨总结：这是难题的思考步骤，就是先想简单版本的解法，然后就是在简单版本上面来修改
⚠️ 输出从新构造序列后的方案，这种题目自己做的很少，就是完全没有思路✅ 其实题目考察就是找到一种构造的思路，就是确定一种贪心的最优的构造方法，就是这个贪心思考这种构造方法的过程是思维题的难点，也是重点
⚠️ 先构造好optimal的序列，然后再统计符合条件的个数，就是确定最优的方案

3、1400C
⚠️ 只要有一个位置是0就行了，那这里又是出现了连环的问题？应该是思考的对象不够简洁
先通过s构造w，这一步我是能够想到的✅ 我想到了一半，还是挺厉害的，先判断必然能够确定的位置
然后判断w是否能够构造出s，就是直接按照题目走一一遍，然后直接判断对比✅ 这个是排序是异曲同工，就是都是整体走一遍看结果是否一样，判断是否合法✨总结：这种判断的方法就是从整体考虑，而不是从当前的这个w[i] = 0的细节角度考虑，就是从整体判断是否相等，就是这种思路很巧妙
（1）这种从整体判断的思维，是特别巧妙的，就是特别简单的
（2）对于重构原来数据的题目，就是判断是否合法的时候，就是先重构，然后在原路推导，然后看推导出来的是否和题目汇总的一样，从而判断是否符合条件✅ 这是常用技巧，就是重构原来数据题目的常用方法
（3）只考虑单个的这个条件就是会陷入连环推导的问题；但是整体考虑就是先构造出来，然后再判断，就是可以避免这个问题

4、1399D
A掉了，就是思路正确，然后描述思路的代码也是因为有了队列，就是很快✅ 就是这种就是潜移默化的进步
正常的cf题目的做题的过程：
（1）通过模拟样例理解题意 + 思考答案构造的思路⚠️ 这里构造题会难一点，有点像小学奥数
0️⃣ 一般cf的题目的题意需要通过模拟第一个样例来理解，就是题意一眼都是比较难理解的
① ❎ 绝对不要想着自己拿到一个新的题目就是能够瞬间想到思路，这是电视剧美化的✅ 就是模拟样例，然后思考出来思路，这是正常的思考方式，也是碰到新题目的正确的思考方式，也是面试微软这种公司需要锻炼的思路，就是肯定是hi新的题目，肯定需要现场思考出来，所以就是转胡总外企的考察方式✨总结：这个找思路的过程，很多时候就是小学的数奥的级别，就是这是cf的构造体比较难的地方
（2）思考用代码如何描述自己的思路⚠️ 这里就是考验代码能力，就是用代码描述解题思路的能力
① 就是描述的对象是cf构造题就是难点，就是可以让你就是写代码的思路宽广不少，这个在写lc的题目的时候就是有很强烈的感觉
（3）debug代码，最锻炼代码能力的环节
5、1372C
✅ 一次非常成功的贪心题目的尝试，就是思路是贪心的，就是猜他贪心的方法，y总的经验还是挺有用的
竟然过了test2，说明这种贪心还是有点作用的，就是自己的贪心猜出来的方法还是挺有用的，就是贪心就是先猜，然后直接提交验证是否真的正确，如果正确再去证明
看正确的输出之后，直接ac掉了
（1）只要cnt>=2，就是只需要两次就行了，因为整体一次，然后包含所有的本来相同的一次，这是min的方法
（2）有一种特定的贪心的方法，就是交换的方法，可以保证两次之内必然能够交换成功