A回文串
按照长度的奇偶性，回文串有两种类型：
长度为偶数的回文串 所有字母出现次数都为偶数
长度为奇数的回文串 除了最中间的字母出现次数为奇数 其他都是偶数
我们枚举最后得到的回文串的长度的奇偶性。如果是奇数，还需要枚举最中间的字母是什么。总共27种情况。
对于每种情况，由于最终每个字母的出现次数的奇偶性确定了，所以插入哪些字母也就确定了。
除了最中间的位置，将字符串左半边按照字母从小到大的顺序排序，右半边由左半边对称得来。
长度为偶数的回文串 所有字母出现次数都为偶数
长度为奇数的回文串 除了最中间的字母出现次数为奇数 其他都是偶数
我们枚举最后得到的回文串的长度的奇偶性。如果是奇数，还需要枚举最中间的字母是什么。总共27种情况。
对于每种情况，由于最终每个字母的出现次数的奇偶性确定了，所以插入哪些字母也就确定了。
除了最中间的位置，将字符串左半边按照字母从小到大的顺序排序，右半边由左半边对称得来。
B闹钟
首先只有当N为奇数且K=0时无解，否则一定有解。
考虑对于每个学号的人，如何判断学号为x的人有没有可能成为单身狗：
设cntl=x-1为学号比ta小的人数，cntr=n-x为学号比ta大的人数。
若cntl=1或cntr=1，由于不存在两个学号相邻的单身狗，所以学号为x的人一定不是单身狗，因为学号为1或者学号为n的人只可能与x成为cp。
否则，我们考虑当x为单身狗的时候，剩下来最少能有几只单身狗：
发现按照…(x-4,x-3),(x-2,x-1),x,(x+1,x+2),(x+3,x+4)…这样配对一定是最优的。
那么若x为单身狗，整个班级中至少有(cntl mod 2)+(cntr mod 2)+1只单身狗。若K大于等于这个值，那么x就有可能成为单身狗。
N<=100时暴力计算即可。
N大的时候，当cntl和cntr都大于1时，可以按照cntl与cntr的奇偶性分类快速计算。
也可以按照N和K分情况讨论。需要注意一些corner case，比如N=3，K=1。
考虑对于每个学号的人，如何判断学号为x的人有没有可能成为单身狗：
设cntl=x-1为学号比ta小的人数，cntr=n-x为学号比ta大的人数。
若cntl=1或cntr=1，由于不存在两个学号相邻的单身狗，所以学号为x的人一定不是单身狗，因为学号为1或者学号为n的人只可能与x成为cp。
否则，我们考虑当x为单身狗的时候，剩下来最少能有几只单身狗：
发现按照…(x-4,x-3),(x-2,x-1),x,(x+1,x+2),(x+3,x+4)…这样配对一定是最优的。
那么若x为单身狗，整个班级中至少有(cntl mod 2)+(cntr mod 2)+1只单身狗。若K大于等于这个值，那么x就有可能成为单身狗。
N<=100时暴力计算即可。
N大的时候，当cntl和cntr都大于1时，可以按照cntl与cntr的奇偶性分类快速计算。
也可以按照N和K分情况讨论。需要注意一些corner case，比如N=3，K=1。
C bananice
将问题转化为有多少个小于X的数闪耀点数为K。最终答案为小于R+1的减去小于L的。
注意到一个数小于X，要么它的位数小于X的位数，要么从高位到低位比较，一定存在一个位置，满足这个位置之前的位置上的数码都相等，且这个位置上这个数的数码小于X的数码。
我们可以把小于X的数字分成O(n)类： （n为X的位数）
若X=233
? ?? 1?? 20? 21? 22? 230 231 232
每一类数都是一个前缀的数码被确定了，其他数码随便填的形式。
对于每一类数，我们分别计算闪耀点数恰好为K的个数。
我们计算出前缀中有多少个数码是闪耀的，那么就可以知道问号中有几个数码要求是闪耀的。假设10个数码中闪耀的数码个数为c，问号中要求a个数码闪耀，b个数码不闪耀，那么方案数为C(a+b,a)*(c^a)*((10-c)^b)。
预处理阶乘以及阶乘的逆元后，可以做到O(1)计算组合数模意义下的值。
注意到一个数小于X，要么它的位数小于X的位数，要么从高位到低位比较，一定存在一个位置，满足这个位置之前的位置上的数码都相等，且这个位置上这个数的数码小于X的数码。
我们可以把小于X的数字分成O(n)类： （n为X的位数）
若X=233
? ?? 1?? 20? 21? 22? 230 231 232
每一类数都是一个前缀的数码被确定了，其他数码随便填的形式。
对于每一类数，我们分别计算闪耀点数恰好为K的个数。
我们计算出前缀中有多少个数码是闪耀的，那么就可以知道问号中有几个数码要求是闪耀的。假设10个数码中闪耀的数码个数为c，问号中要求a个数码闪耀，b个数码不闪耀，那么方案数为C(a+b,a)*(c^a)*((10-c)^b)。
预处理阶乘以及阶乘的逆元后，可以做到O(1)计算组合数模意义下的值。
D买东西
可以发现如果所有物品的价值和重量都确定了，那么题目就变成了一个经典的二分问题。
二分答案 ans ，问题转化为判断是否存在一个大小是 k 的集合 S 满足 wi的和/vi的和>=ans，可以转化为 wi-vi*ans的和>=0，直接按照这个值对每个物品排序即可，复杂度为 O(n log n log T) ，其中 T 为二分的值域大小。
对于原来的题目，我们发现无论使用多少次仙术，最终的局面都可以用下面的方法等价：先决定是否使用第一种仙术，再决定使用多少次第二种仙术。由于第二种仙术连续使用至少 n 次都是没有意义的，等价的局面数就是 2n 个。
如果我们先枚举这 2n 个局面，并对每个进行二分，复杂度为 O(n^2 log n log T) 。我们考虑如何减少二分次数，为此，在枚举前先对每个局面判断是否会使答案变大。这里的判断可以用当前的最优答案进行二分之后的操作，复杂度为每次 O(n log n) ，并对每个会使答案变大的局面进行二分，否则就直接跳过这个局面。
一个结论是，如果我们随机打乱枚举局面的顺序，期望需要二分的局面个数是 O(log n) 的。因此我们这样做的复杂度就是期望 O(n^2log n+nlog nlog T) 的。注意到复杂度只在后一部分有期望，而后一部分的远小于前一部分，所以退化的可能性是非常低的。
当然可以用类似快速排序的做法把排序的log去掉。然而由于n远小于T，暴力枚举加上这个优化仍然会超时。
二分答案 ans ，问题转化为判断是否存在一个大小是 k 的集合 S 满足 wi的和/vi的和>=ans，可以转化为 wi-vi*ans的和>=0，直接按照这个值对每个物品排序即可，复杂度为 O(n log n log T) ，其中 T 为二分的值域大小。
对于原来的题目，我们发现无论使用多少次仙术，最终的局面都可以用下面的方法等价：先决定是否使用第一种仙术，再决定使用多少次第二种仙术。由于第二种仙术连续使用至少 n 次都是没有意义的，等价的局面数就是 2n 个。
如果我们先枚举这 2n 个局面，并对每个进行二分，复杂度为 O(n^2 log n log T) 。我们考虑如何减少二分次数，为此，在枚举前先对每个局面判断是否会使答案变大。这里的判断可以用当前的最优答案进行二分之后的操作，复杂度为每次 O(n log n) ，并对每个会使答案变大的局面进行二分，否则就直接跳过这个局面。
一个结论是，如果我们随机打乱枚举局面的顺序，期望需要二分的局面个数是 O(log n) 的。因此我们这样做的复杂度就是期望 O(n^2log n+nlog nlog T) 的。注意到复杂度只在后一部分有期望，而后一部分的远小于前一部分，所以退化的可能性是非常低的。
当然可以用类似快速排序的做法把排序的log去掉。然而由于n远小于T，暴力枚举加上这个优化仍然会超时。
std
A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40364032
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=37101592
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=37101592
全部评论
(0) 回帖