Codeforce错题集

CF2244D Yaroslav and Productivity写完这道题我感觉我对dp动态规划的理解又多了一些。动态规划的题有两个核心1.最优子结构一个大问题可以由多个子问题的最优解组合而成。在本题中的体现就是位置i的最优解只需要知道i1处“当前翻转为偶数次的最大值”和“当前翻转为奇数次的的最大值”。右侧子问题必须是它自身的最优解才能保证组合起来是全局最优。2.重叠子问题求解的过程中同一个子问题可能被重复计算好几次dp通过存储避免这一点同时这也是动态区别于分治的核心点。体现在这道题就是在位置i的左边可能有好几个点都依赖i但是我们用了dp0dp1来储存他们所以从右往左只用算一遍。假如判断出是动态规划我们该怎么做关键是状态转移方程如何从已知状态推导出目前状态也就是递推公式。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-j1。要采纳这个元素有前提条件每个元素都有自己的【lr】与【uv】左秩满足不在【lr】里右秩满足在【uv】里这样这个元素合理。题目拆解完了现在轮到思路。对于固定长度m我们查找是否存在长度为m的有效子段存在。使用贪心算法从左到右扫描维护当前已经选好的长度len那么下一个要判断的元素jlen1用两个条件判断思考为什么此时右秩可以用来判断因为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.对于每个位置ia【i】在a中出现的次数为b【i】2.同时a【i】大于等于1小于等于n。关于这题我一开始以为b中每一组数字一样的数就对应a中的一种数这个思路是错的我举个例子数组b{2222}这样的话其实是分成两组的4/22第一种出现两次第二种在i3开始出现两次。所以我的思路一开始就错了。正确的思路应该是从题目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如果x0那么先手呈必败状态反之先手呈必胜态。这个结论是打开这题的钥匙。那么有几种方法的判断通过数下标个数哪些下标X异或a[i]a[i]的下标。在判断之前有一个特殊情况可以分出来当a的长度为1时这时候直接输出0因为无法操作。当x0的时候不是必败而是只有一种方法使对方走向必败就是全零所有ba。D. Binary String Battle这题我在看到11111 k4的样例时我认为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)≥rk−(r−1)k1也就是说Bob可以帮数量至少变为k1那么字符串就永远无法变为所有零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我一开始建立表格好像更加的麻烦。这题有一个方法就是把这些矩形都引入坐标系每块板子左下角的坐标标为xy覆盖的区域就可以标记成x到xay到yb。判断两个方向是否重叠xOverlap(max(x1​,x2​)min(x1​a,x2​a))yOverlap(max(y1​,y2​)min(y1​b,y2​b))若xOverlap yOverlap则说明俩个板块重叠与题目的保证冲突忽略。若xOverlapx方向重叠需要y方向不重叠且间隙长度能被b整除此时y的间隙的长度可表达为min⁡(y1b,y2b)−max⁡(y1,y2)min(y1​b,y2​b)−max(y1​,y2​)思考此值一定为正因为y方向不重叠若yOverlapy方向重叠需要x方向不重叠且间隙长度要能被a整除X 空隙长度可表达为min⁡(x1a,x2a)−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表中找到一个值使得所有数都可达并且步数最小的那一个就是答案。