CF2244D Yaroslav and Productivity
写完这道题我感觉我对dp动态规划的理解又多了一些。动态规划的题有两个核心1.最优子结构，一个大问题，可以由多个子问题的最优解组合而成。在本题中的体现，就是位置i的最优解只需要知道i+1处“当前翻转为偶数次的最大值”和“当前翻转为奇数次的的最大值”。右侧子问题必须是它自身的最优解，才能保证组合起来是全局最优。2.重叠子问题，求解的过程中，同一个子问题可能被重复计算好几次，dp通过存储避免这一点，同时这也是动态区别于分治的核心点。体现在这道题就是，在位置i的左边可能有好几个点都依赖i，但是我们用了dp0，dp1来储存他们，所以从右往左只用算一遍。假如判断出是动态规划我们该怎么做？关键是，状态转移方程，如何从已知状态推导出目前状态，也就是递推公式。
CF2190A Sorting Game
（本来觉得这没啥好写的）因为这道题是div1的第一道，我当时就被唬住了，题目完全看不懂，更不知道我学的知识有哪些能帮助我，我觉得这是我需要克服的。如果已经排好序，那么先手的Alice必输，如果未排序，那么Alice将一步排好序。看出这一点就表明题目只分了两种情况。那就简单了。
首先我需要找到字符串中0的个数z，然后，判断0到z-1有没有出现1，或者z到n-1有没有出现0。假如没有，则归为第一种情况直接判Bob赢。假如有则归为第二种情况。
第二种情况，我要找到字符串里错位的下标（以1为起点的下标），然后存入数组按升序输出。
CF2249A Rank Subsequence
面对dv1，我一开始的方向竟然是对的——贪心，只不过题目太复杂我不知道该怎么入手了。既然如此，让我先来拆解题目题目。子数组的长度m，左秩的概念就是子数组中选定元素的下标j，右秩则是m-j+1。要采纳这个元素有前提条件，每个元素都有自己的【l，r】与【u，v】，左秩满足不在【l，r】里，右秩满足在【u，v】里，这样这个元素合理。
题目拆解完了，现在轮到思路。对于固定长度m，我们查找是否存在长度为m的有效子段存在。使用贪心算法，从左到右扫描，维护当前已经选好的长度len，那么下一个要判断的元素j=len+1，用两个条件判断（思考：为什么此时右秩可以用来判断？因为m被我们固定了。）。对于m的判断顺序，可以从n往下搜索，第一个成立的就是答案。
CF2158B Split
让我们设某个值x在整个序列中一共出现了cnt【x】 次。让我们分类，如果这个数是奇数，那么无论分到p多少次，p和q肯定是1奇1偶，所以贡献值为1。如果这个数是偶数，分到p的数是奇数时那么q也是奇数，所以贡献值为2。
所以我们需要统计数组出现次数为奇数的个数odd，以及出现次数为偶数的个数even。答案分为两种情况，如果odd大于0和odd等于0。
CF2137D Replace with Occurrences
![]()
给定长度为n的数组b需要我构造长度为n的数组a。要满足的条件有：
1.对于每个位置i，a【i】在a中出现的次数为b【i】；
2.同时a【i】大于等于1，小于等于n。
关于这题，我一开始以为b中每一组数字一样的数就对应a中的一种数，这个思路是错的，我举个例子，数组b={2，2，2，2}，这样的话，其实是分成两组的，4/2=2，第一种出现两次，第二种在i=3开始出现两次。所以我的思路一开始就错了。
正确的思路应该是从题目b对a的’依赖‘反推出a对b的，我们需要把相同的b值分为k个一组。在答案数组中用不同的值去填充。
B. Add 0 or K
根据题目的描述，我把它进行了转化，我可以在数组a的每个值上加0或者k，使得，数组a中的每个数的最大公约数大于1。我第一时间想到了奇数变偶数，就是将a中的每个数从奇数变成偶数，这有个前提条件是k为奇数，因为只有奇数加上奇数才等于奇数，所以只要我遍历a数组，是偶数的加上0（跳过），奇数就加上k。但是如果k是偶数，我就没什么思路了。
CF2239A Nim Game Is XOR Game
看的我眼花缭乱，感觉和走钢丝一样，我刚把前两个条件理清楚，再看样例，为什么b1得等于0？没想到还得满足XOR，这一个条件。首先这里有一个概念，关于nim游戏以及其分支，求数组里的数异或和x，如果x=0，那么先手呈必败状态，反之，先手呈必胜态。这个结论是打开这题的钥匙。那么有几种方法的判断通过，数下标个数，哪些下标？X异或a[i]<a[i]的下标。在判断之前，有一个特殊情况可以分出来，当a的长度为1时，这时候直接输出0，因为无法操作。当x=0的时候，不是必败，而是只有一种方法使对方走向必败，就是全零，所有b=a。
D. Binary String Battle
这题我在看到11111 k=4的样例时我认为Alice必输，因为我在想如果alice没有办法一步将所有数变成0那么Bob总有办法把1变成0。但是实际上结论是：设s中1的个数为cnt因为Alice能将长度为k的任何子段变为0，所以只要2*k大于n，那么Alice必赢。否则，只有当cnt小于k时。让我们来证明这个结论：
长度为k的子串的交集；当2k大于n时，交集非空，大小为2k-n，就是说，每个大小为k的子段都包含这个位置；2k小于n时，没有交集。
当2k小于等于n时，此时没有一个位置被所有子串包含。此时如果cnt小于或等于k，那么Alice一定会赢，因为Alice可以将这些1一次性变为零。如果cnt大于k，那么Alice一次操作玩一定会剩下r个1，并且这r个1一定存在长度为k的连续子串不包含当前的所有 1。所以Bob操作一次后可以将这个子串的个数剩c个，c小于等于r-1，操作完之后1的数量r+(k−c)≥r+k−(r−1)=k+1，也就是说，Bob可以帮数量至少变为k+1，那么字符串就永远无法变为所有零，Bob胜。
当2k大于n时，此时任何一个子串长度为k都包含一个公共区域，记作I。Alice的策略就是，每次优先将I外的1变为0，若I的外部1的数量大于k，那么就消除任意k个1。Bob的每次操作只能在I外增加最多n-k个1，为什么？这张图可以帮助理解，所以Alice消除的速度是要大于Bob增加的，一旦I外的1不超过k了，那么Alice一次操作就能将I外所有的1变为零，此时Bob再操作只能将整个字符串1的个数变为k，也就是说Alice赢了。
B. Good Start
我一开始建立表格好像更加的麻烦。这题有一个方法就是把这些矩形都引入坐标系，每块板子左下角的坐标标为（x，y），覆盖的区域就可以标记成x到x+a，y到y+b。判断两个方向是否重叠，
xOverlap=(max(x1,x2)<min(x1+a,x2+a))；
yOverlap=(max(y1,y2)<min(y1+b,y2+b))；
若xOverlap && yOverlap，则说明俩个板块重叠，与题目的保证冲突，忽略。
若xOverlap（x方向重叠）
需要y方向不重叠，且间隙长度能被b整除，此时y的间隙的长度可表达为
min(y1+b,y2+b)−max(y1,y2)min(y1+b,y2+b)−max(y1,y2)，（思考：此值一定为正？因为y方向不重叠）
若yOverlap（y方向重叠）
需要x方向不重叠，且间隙长度要能被a整除，X 空隙长度可表达为
min(x1+a,x2+a)−max(x1,x2)min(x1+a,x2+a)−max(x1,x2)
若两者都不成立，就是两个方向都不重叠
需要x方向的间隙能被a整除 或者 y方向的间隙能被b整除。
C. Chipmunk Theo and Equality
我思考后，发现这道题的关键是找到平衡点，就是说x，最终数组说有数的值。看完ai提供的思路，我发现，我一开始的思路大致是对的，但是对解决问题提供的贡献还不够。
题解的思路：对每个数进行BFS搜索，为什么BFS？每次操作有两种+1再/2，和/2，这也就导致了每个数能到达的不同值数量很少，这就是为什么用BFS，时间复杂度在可接受范围内，使用BFS有。使用BFS会涉及到一个问题，如果这个+1和/2的操作一直进行，那么数字会在1和2之间循环，导致代码超时，所以，应该加一个操作，来保护，在数字达到1和2这两个数字后结束BFS。
然后记录其可以到达的所有值，然后放入hash表中，准确的来说是累加进一个全局hash表中。然后对于结果，从hash表中找到一个值，使得所有数都可达，并且步数最小的那一个就是答案。
