A. African sort
B. Combination of Physics and Maths
C. Data Structure
D. Easy construction
E. Fibonacci Partition
首先如果要有解，k必须是n(n+1)/2 % n，因为长度为n 的子区间只有一个，也就是P 本身，而P 本身的元素和就是n(n+1)/2。
然后假设k 满足上述条件，此时是一定有解的。如果n 是奇数，可知k=0，令P = {n, 1, n-1, 2, n-2, ...} 即可；如果n是偶数，可知k=n/2，令P = {n, n/2, 1, n-1, 2, n-2, ...} 即可。
F. Grid Coloring
G. Harmony Pairs
H. Harmony Pairs
I. Interesting Stirling Task
J. Josephus Transform
首先考虑如何求一个 k-约瑟夫变换。注意到每次取出来的数字是剩下所有数字的第几个其实是可以算出来的。不妨设上一个被取出来的数字是当时的第 pos 个（初始设为 1），当前还剩下 cnt 个数字，那么下一个被选出来的数应该是当前剩下的所有数字中的第 (pos-1+k-1) % cnt + 1 个，这个可以用线段树或者树状数组来求，所以求一个k-约瑟夫变换的复杂度是 O(n log n) 的。
然后要连续进行 x 次置换，注意到置换是满足结合律的，所以可以用快速幂来算，这部分时间复杂度就是 O(n log x) 的。
所以总的时间复杂度是 O(nm(log n + log x)) 的。
K. K-bag
全部评论
(1) 回帖