T1
考虑只有第二种操作。显然可以维护 \(a_i\) 代表当前序列的第 \(i\) 个数是什么。
观察到变换只和 \(k\% 3\) 的值有关。
对于第一种操作，显然可以令 \(k\leftarrow k\% n\)。观察到这种变换将整个序列视为一个环更方便一点，于是维护变换后第一个数的下标是多少。输出时按照环的原则输出。
综合起来，就是维护 \(begin\) 代表起点，第一种操作时直接改变起点，第二种操作改变从起点开始的三个数的 \(a_i\) 即可。
T2
令 \(dp_{i,j}\) 代表前 \(i\) 个数划分了 \(j\) 段的方案数。
\[dp_{i,j}=\sum_{k=1}^{i-1}dp_{k,j-1}\times [(s_i-s_k)\text{is a multiple of j}] \]这是 \(O(n^3)\) 的，考虑优化。
根据同余的知识，\(s_i-s_k\) 是 \(j\) 的倍数当且仅当 \(s_i\equiv s_k\bmod j\)。
用一个类似 csp-s2023 T2 的技巧，加一个 \(g_{i,j}\) 辅助转移。
\[g_{i,j}=\sum dp_{k,i}[s_k\equiv j\bmod (i+1)] \]然后做完了。
T3
和之前做过的一道 CF 很像，都是类似的二分实数。
根据直觉，选择二分答案 \(k\)。
推柿子。
\[\frac{y_i-y_j}{x_i-x_j}\ge k \]\(x_i-x_j\) 有正有负很难受，排序一下。
\[y_i-y_j\ge k\times (x_i-x_j) \]\[y_i-y_i\ge k\times x_i-k\times x_j \]\[y_i-k\times x_i\ge y_i-\times x_j \]于是按照 \(y_i-k\times x_i\) 重新赋值。找一个最长不升子序列即可。
时间复杂度 \(O(n\log^2 n)\)。
T4
很好的题。
分类讨论。
-
\(k=1\)，此时答案为 \(0\)。
-
\(n\equiv 0\bmod k\)，会取走 \(k,2\times k,\cdots\)，答案很好计算。
-
\(\gcd(k,n)\ne 1\)，此时将 \(k\) 换成 \(\gcd(k,n)\) 显然是不劣的。
-
\(\gcd(k,n)=1\)，按照 \(i\bmod k\) 对整个序列分成 \(k\) 类，会按某些顺序拿每个类。直接模拟即可。
时间复杂度 \(O(M^2\log n)\)。
标签：gcd,bmod,times,ge,五月,csp,mx,dp,equiv From： https://www.cnblogs.com/BYR-KKK/p/18211555