9
难度大概是橙黄黄绿吧。感谢金钩大佬在百忙之中出思维好题给我们。
T1
Difficulty：3- / Easy
Tag：-
假设存在一个 xxx 使得满足 pi>n−xp_i\gt n-xpi >n−x 的数量大于 xxx。
注意到是排列，所以不可能。
所以修改显然不优。
所以最优解是不把任何平台修改接收平台，答案就是 pi≤ip_i\le ipi ≤i 的数量。
时间复杂度：O(n+q)O(n+q)O(n+q)。
T2
Difficulty：3.4 / Easy
Tag：-
脑电波题。
注意到如果 nnn 是奇数，出现的数只有奇数和 000 可以这么构造：
[n,n−2,...,9,7,5,3,1,0,1,3,5,7,9,...,n−2,n][n,n-2,...,9,7,5,3,1,0,1,3,5,7,9,...,n-2,n][n,n−2,...,9,7,5,3,1,0,1,3,5,7,9,...,n−2,n]
偶数同理。
然后注意到把这两块拼出来，中间有三个 000，而最左边和最右边的空的距离恰好是 n+1n+1n+1，刚好能放进 nnn。所以构造如下（这里展示 n=11n=11n=11 的）：
[9,7,5,3,1,11,1,3,5,7,9,10,8,6,4,2,0,11,2,4,6,8,10][\red{9,7,5,3,1}\green{,11,}\red{1,3,5,7,9}\blue{,10,8,6,4,2},0\green{,11,}\blue{2,4,6,8,10}][9,7,5,3,1,11,1,3,5,7,9,10,8,6,4,2,0,11,2,4,6,8,10]
时间复杂度：O(∑n)O(\sum n)O(∑n)。
T3
Difficulty：3.5 / Easy
Tag：隔板法
首先计算长度为 nnn 的方程数。
其实就是求 n+A1+A2+...+An+1=Sn+A_1+A_2+...+A_{n+1}=Sn+A1 +A2 +...+An+1 =S，Ai≥0,An>0A_i\ge 0,A_n\gt 0Ai ≥0,An >0 的整数解数量。容斥一下，分别计算 n+...=Sn+...=Sn+...=S 与 n+...=S−1n+...=S-1n+...=S−1 的非负整数解数量。这里讨论前者。
移一下项，A1+A2+...+An+1=S−nA_1+A_2+...+A_{n+1}=S-nA1 +A2 +...+An+1 =S−n。根据隔板法，答案为 (Sn)S\choose n(nS )。
所以总数为 ∑n=1S(Sn)−∑n=1S(S−1n)=2S−2S−1=2S−1\sum_{n=1}^S {S\choose n}-\sum_{n=1}^S {S-1\choose n}=2^S-2^{S-1}=2^{S-1}∑n=1S (nS )−∑n=1S (nS−1 )=2S−2S−1=2S−1。第二问就是在问满足 ∑n=1m(Sn)−∑n=1m(S−1n)>k\sum_{n=1}^m {S\choose n}-\sum_{n=1}^m {S-1\choose n}\gt k∑n=1m (nS )−∑n=1m (nS−1 )>k 的最小的 mmm。
注意到 (Sn)S\choose n(nS ) 增长极快，当 SSS 较大时，m=2m=2m=2 时原式就已经超过 10910^9109 了。所以组合数怎么实现都行。
我使用了一种十分拟人的 O(mS)O(m\sqrt S)O(mS ) 实现求组合数。能过就是好算法
时间复杂度：O({∅,∅,∅,{∅},{∅,∅,{∅}}}×S)O(\{\varnothing, \varnothing, \varnothing, \{\varnothing\}, \{\varnothing, \varnothing, \{\varnothing\}\}\}\times\sqrt S)O({∅,∅,∅,{∅},{∅,∅,{∅}}}×S )。
T4
不会。
我这沙子还是学霸？ {自恋}
）
有帮助，赞一个