B. Good times Good times思路分析这道题的思路给我很深的印象要使得x*y之后数字的种类不变最好的办法就是构造出两个x拼凑在一起。我们就可以令y为1^m1。这样就可以实现上面所说的了。1335C - Two Teams Composing题目分析我一开始的思路是这道题围绕着一个数组展开从这个数组里选择2*x个数作为第一组与第二组的内容第一组的数字不能有重复第二个数组里的数字必须重复两组的大小需要一致。请我们求出x的最大值。思路分析我们需要求出两个数。设d为种类个数mx为数量最多的种类的数量。将分组分为两种情况1.我们不在第二队里借人也就是说d-1x然后mxx。所以答案就是mind-1mx。2.我们在第二队伍里借人这样就变成了dx,mxx1。所以答案就在这两个值取最小。最后我们在这两种情况里取最大值即可。1490C - Sum of Cubes题目分析这题的要求是判断给出的数能否被两个数的立方和所表示。思路分析因为x最大也就12个零x开立方根也就3个零所以枚举没问题。在这里我们可以枚举a然后判断b是否为整数。我们可以使用powxxx1.0/3但是在这里需要注意的点就是可能有浮点的差距所以我们要对b1在进行判断。在枚举的过程中i必须开long long否则溢出就会导致循环条件一直成立导致死循环。B. Dreamoon and WiFi看完题目我认为只是单纯的遇到问号概率就乘以0.5因为每个问号都代表着两种情况并且题目要求的是抵达指定位置的概率是多少。但看完示例后才知道概率的计算要先求出每一种可能的值然后再找到其中抵达的占比。要知道有多少个可行的情况直接罗列全部显然是不现实的我们可以将其转移因为目标值由确定的值与问号组成而所有问号的结果由与-的个数决定所以我们可以找问号中目标有多少个在x为目标的个数q为问号的个数再除以所有可能的情况2^q就行了。那么这个x该怎么求呢设确定的值为cur、所有问号中的个数为x、问号的个数为q、目标值为target那么-的个数就可以用q-x来表示。那么就可以得到一个等式curx-q-xtarget。根据这个等式得到x。算组合数的时候可以用到二维数组构造杨辉三角这样完全避免了用除法计算阶乘时可能产生的精度误差妙啊1899C - Yarik and Array我一开始纠结的点都在如何分这个数组但是如果把每一种情况模拟出来是一件非常不健康的事。我们再仔细的观察题目考虑分数组这个方向是对的但是这应该只作为我们解题的引入我们要找出奇偶性交替出现的也就是说两个相邻的数字的奇偶性不能一致也就是我们遇到相同的奇偶就在此断开。这相当于原数组按照奇偶的位置分成若干个数组任意段内的任意连续子数组都是合法的。关键的转化来了对每一段独立求最大子数组和然后去所有段的最大值。即kadane算法curmaxa[i],cura[i])ansmax(cur,ans)CF279B Books我一开始的思路是计算后缀和然后使用二分法找到答案。但是我漏了一个关键题目要求的是任意子数组我的思路相当于将有边界定为n了。正确的做法应该是滑动窗口。这是怎么得出来的因为我们求的是任意长度的数组所以我们需要滑动有边界找到大于休息时间或者不存在的点然后在滑动左边界直到小于休息时间。CF489C Given Length and Sum of Digits...看到题目出现的最大最小值很容易想到用贪心去做但是我一开始也就想到这里了。怎么去构造他们我就想不出来了。还有就是关于不可行性判断m位每位最大是‘9’所以得满足sm*9。然后就是构造最小值贪心的分配原则是高位尽可能地小同时保证低位能凑够剩余的和我们从高位递减的去分配每一位。我们可以假设还有rain需要分配然后还有left位。那么这left位能提供left*9所以这一位需要rain-left*9不然后面所有位都填9和都不够。所以第一位就是max1rain-left*9非第一位就是max0rain-left*9因为不能有前导零。构造最大值这一位取min9rain就行因为我们已经保证了sm*9。不放心我们再做一个max的检验。CF1526B I Hate 1111这道题我只看得到浅层的含义我感觉我只停留在模拟思路的一个原因是数学思维不是很熟悉这题还有一个原因是我没有将问题转移的思路这道题因为1111以上的数都能用11和111表示所以原问题就可以等价为11a111bx。然后呢我们应该尝试给答案简化判断可行性我们可以从ab入手那该怎么做呢如果有一个解 (a,b)并且 b≥11那么我们可以把 b 减少 11同时 aa 增加 111。化简可得这么操作等式的结果不变。因此只要存在解就一定存在一个解使得 0≤b≤10。CF4B Before an Exam这道题一开始我就看出来可行性的判断需要最大值的和还有最小值的和与规定的和进行比较。最大最小值的和必须满足包含规定值。答案构造思路我们假设她每天学mintime此时还需学习的时间rem sumtime - minsum规定时长和mintime的总和遍历每一天每天最多可以增加 maxtime最长学习时间- mintime最短学习时间每次增加rem与最多可以增加两者取最小直到rem变为零。CF1497C1 k-LCM (easy version)很好奇我是怎么想到三等分的。若不是三的倍数的话无法三等分。我应该考虑的是怎么构造出三个数相加得到n并让他们的最小公倍数小于n/2。这种涉及到2的我就应该想到引入奇偶性假如n是奇数先拆成两个数n与n-1这样从两个变成三个就可以通过将n-1拆成两个n-1/ 2因为这n-1一定是偶数并且这三个数的最大公倍数因为有一的存在就变成了后面两数的最大公倍数。假如n为偶数上述思路可沿用至此n/2n/4n/4这三个数的最大公倍数为n/2可行。但是我思考到这里漏了一点要写出n/4这个答案还得满足n是4的倍数因为偶数不一定能整除4。所以这种情况需单独分出来剩下不能整除4的情况因为偶数%4只有两种情况2和0所以当其等于2时我们就可以将n分为2、n-2然后将n-2对半分。
B. Good times Good times思路分析这道题的思路给我很深的印象要使得x*y之后数字的种类不变最好的办法就是构造出两个x拼凑在一起。我们就可以令y为1^m1。这样就可以实现上面所说的了。1335C - Two Teams Composing题目分析我一开始的思路是这道题围绕着一个数组展开从这个数组里选择2*x个数作为第一组与第二组的内容第一组的数字不能有重复第二个数组里的数字必须重复两组的大小需要一致。请我们求出x的最大值。思路分析我们需要求出两个数。设d为种类个数mx为数量最多的种类的数量。将分组分为两种情况1.我们不在第二队里借人也就是说d-1x然后mxx。所以答案就是mind-1mx。2.我们在第二队伍里借人这样就变成了dx,mxx1。所以答案就在这两个值取最小。最后我们在这两种情况里取最大值即可。1490C - Sum of Cubes题目分析这题的要求是判断给出的数能否被两个数的立方和所表示。思路分析因为x最大也就12个零x开立方根也就3个零所以枚举没问题。在这里我们可以枚举a然后判断b是否为整数。我们可以使用powxxx1.0/3但是在这里需要注意的点就是可能有浮点的差距所以我们要对b1在进行判断。在枚举的过程中i必须开long long否则溢出就会导致循环条件一直成立导致死循环。B. Dreamoon and WiFi看完题目我认为只是单纯的遇到问号概率就乘以0.5因为每个问号都代表着两种情况并且题目要求的是抵达指定位置的概率是多少。但看完示例后才知道概率的计算要先求出每一种可能的值然后再找到其中抵达的占比。要知道有多少个可行的情况直接罗列全部显然是不现实的我们可以将其转移因为目标值由确定的值与问号组成而所有问号的结果由与-的个数决定所以我们可以找问号中目标有多少个在x为目标的个数q为问号的个数再除以所有可能的情况2^q就行了。那么这个x该怎么求呢设确定的值为cur、所有问号中的个数为x、问号的个数为q、目标值为target那么-的个数就可以用q-x来表示。那么就可以得到一个等式curx-q-xtarget。根据这个等式得到x。算组合数的时候可以用到二维数组构造杨辉三角这样完全避免了用除法计算阶乘时可能产生的精度误差妙啊1899C - Yarik and Array我一开始纠结的点都在如何分这个数组但是如果把每一种情况模拟出来是一件非常不健康的事。我们再仔细的观察题目考虑分数组这个方向是对的但是这应该只作为我们解题的引入我们要找出奇偶性交替出现的也就是说两个相邻的数字的奇偶性不能一致也就是我们遇到相同的奇偶就在此断开。这相当于原数组按照奇偶的位置分成若干个数组任意段内的任意连续子数组都是合法的。关键的转化来了对每一段独立求最大子数组和然后去所有段的最大值。即kadane算法curmaxa[i],cura[i])ansmax(cur,ans)CF279B Books我一开始的思路是计算后缀和然后使用二分法找到答案。但是我漏了一个关键题目要求的是任意子数组我的思路相当于将有边界定为n了。正确的做法应该是滑动窗口。这是怎么得出来的因为我们求的是任意长度的数组所以我们需要滑动有边界找到大于休息时间或者不存在的点然后在滑动左边界直到小于休息时间。CF489C Given Length and Sum of Digits...看到题目出现的最大最小值很容易想到用贪心去做但是我一开始也就想到这里了。怎么去构造他们我就想不出来了。还有就是关于不可行性判断m位每位最大是‘9’所以得满足sm*9。然后就是构造最小值贪心的分配原则是高位尽可能地小同时保证低位能凑够剩余的和我们从高位递减的去分配每一位。我们可以假设还有rain需要分配然后还有left位。那么这left位能提供left*9所以这一位需要rain-left*9不然后面所有位都填9和都不够。所以第一位就是max1rain-left*9非第一位就是max0rain-left*9因为不能有前导零。构造最大值这一位取min9rain就行因为我们已经保证了sm*9。不放心我们再做一个max的检验。CF1526B I Hate 1111这道题我只看得到浅层的含义我感觉我只停留在模拟思路的一个原因是数学思维不是很熟悉这题还有一个原因是我没有将问题转移的思路这道题因为1111以上的数都能用11和111表示所以原问题就可以等价为11a111bx。然后呢我们应该尝试给答案简化判断可行性我们可以从ab入手那该怎么做呢如果有一个解 (a,b)并且 b≥11那么我们可以把 b 减少 11同时 aa 增加 111。化简可得这么操作等式的结果不变。因此只要存在解就一定存在一个解使得 0≤b≤10。CF4B Before an Exam这道题一开始我就看出来可行性的判断需要最大值的和还有最小值的和与规定的和进行比较。最大最小值的和必须满足包含规定值。答案构造思路我们假设她每天学mintime此时还需学习的时间rem sumtime - minsum规定时长和mintime的总和遍历每一天每天最多可以增加 maxtime最长学习时间- mintime最短学习时间每次增加rem与最多可以增加两者取最小直到rem变为零。CF1497C1 k-LCM (easy version)很好奇我是怎么想到三等分的。若不是三的倍数的话无法三等分。我应该考虑的是怎么构造出三个数相加得到n并让他们的最小公倍数小于n/2。这种涉及到2的我就应该想到引入奇偶性假如n是奇数先拆成两个数n与n-1这样从两个变成三个就可以通过将n-1拆成两个n-1/ 2因为这n-1一定是偶数并且这三个数的最大公倍数因为有一的存在就变成了后面两数的最大公倍数。假如n为偶数上述思路可沿用至此n/2n/4n/4这三个数的最大公倍数为n/2可行。但是我思考到这里漏了一点要写出n/4这个答案还得满足n是4的倍数因为偶数不一定能整除4。所以这种情况需单独分出来剩下不能整除4的情况因为偶数%4只有两种情况2和0所以当其等于2时我们就可以将n分为2、n-2然后将n-2对半分。
