杭电多校第零场湘潭全国邀请赛补题记录ioian

本场题目重现于 2021湘潭全国邀请赛

根据题意处理即可

题意：长度为 \(n\) 的只含有”C”或”P”的字符串共有 (\(2^n\))个，问：这所有(\(2^n\))个字符串中含有多少个”CCPC”（每一个”CCPC”之间不能相互重叠，即”CCPCCPC”中只能算(1)个”CCPC”）

假设所有长度为(\(n\))的”CP”字符串中互不重叠的”CCPC”的个数为(\(a_n\))

若认为可以相互重叠，可以通过计算贡献的方式进行计算

首先分析x−(10k−1)，减的这个数只能是9，99，999，…

99=9 * 11999=9 * 111999…=9 * K

这些数都是9的倍数,K是个奇数，所以对结果没有影响，因此我们可以将这个问题转化为每次减9

将这些数从小到大排序，每次先从最小的开始减

例如：19 10 29 不排序从第一个开始减最后减到的最小结果就是19 10 11（因为19-9=10，与第二个数字10有重复）排序后的最小结果是1 10 11，这个在计算过程中不会出现少操作数，每个人都可以做到最佳选择

因为存在最后减完的结果一样，但是题目要求不可以出现重复的数字，所以需要再次处理每次从最小的开始减，余数不为0的每次就让第一个减到0*9+余数，第二个减到1 * 9+余数…以此类推（如果余数为0，第一个减到1 * 9，第二个减到2 * 9，以此类推）

这里的避重（避免重复）操作数可以用前n项和实现(余数为0) 例：9 18 27 化为最小结果（未对余数进行避重）分别需要的操作是 1 2 3次，总操作数=6避重的话9应该减为1 * 9，18减为2 * 9，27减为3 * 9，需要的总操作数是1+2+3=6次6-6=0，所以最后只能对这组数据进行0次操作。(余数不为0)，与上类似，只是第一个数减到0 * 9+余数…

最后总结我们需要计算的就是：

一、将每个数化到最小一共需要多少次操作（一共能减多少次9，先不考虑余数相同）二、统计余数相同的个数（对9取余 余数为0到8）三、余数相同的数字，计算去重操作数四、总操作数-避重操作数即为最后的操作数，如果为偶数，则B赢，反之，则A赢。