点击跳转比赛
前言
本次竞赛难度T1、T2难度为简单，T3、T4难度为中档，T5、T6难度为困难.各位选手可以通过这次竞赛摸底自己的实力.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
下面是正文题解部分：
T1 这是一种病：字符串模拟
点击跳转
模拟，判断有没有 APT 在其中就行.
时间复杂度：O(∣S∣)O(|S|)O(∣S∣)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2 找到最小值：函数化简
点击跳转
推一下式子， F(a,b)=a−c−c−b+2c=a−bF(a,b)=a-c-c-b+2c=a-bF(a,b)=a−c−c−b+2c=a−b，所以函数的值为 a,ba,ba,b 的差，与 ccc 无关.
对于每次询问，时间复杂度：O(1)O(1)O(1).
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3 规律数列：高精递推
点击跳转
显然规律是将上一个数+3,*3,+3,*3...
结果太大了，用 long long 也存不下.
我们可以尝试用数组模拟+3和*3操作.
但是如果每次查询都进行 NNN 次运算就浪费太大了.
我们可以预处理，这样每次查询就只需要直接输出答案了.
对于预处理，时间复杂度：O(N2)O(N^2)O(N2).
对于每次查询，时间复杂度：O(N)O(N)O(N).
总时间复杂度：O(TN+N2)O(TN+N^2)O(TN+N2).
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T4 废品回收：贪心策略
点击跳转
贪心，将价值减去价格，每次挑选最大的即可（注意！不需要拿满 kkk 件！如果处理这个废品后的收益小于等于 000 就不要再拿了）
时间复杂度：O(NlogN)O(N\log N)O(NlogN).
当然，你也可以使用堆来实现在线得出最优解（O(NlogN)O(N\log N)O(NlogN)），或者用背包DP（O(N×Vi)O(N\times V_i)O(N×Vi )），以下给出背包DP的代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T5 计数改良：组合数学
点击跳转
20PTS
深搜，参考下面的代码.
对于每次查询，时间复杂度：O(3N)O(3^N)O(3N).
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
40PTS
我们发现前四个测试点答案也就不超过 151515 种，考虑记忆化.
对于每次查询，时间复杂度：O(1)O(1)O(1) 或 O(3N)O(3^N)O(3N).
总时间复杂度：O(3N)O(3^N)O(3N).
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
100PTS
既然最终答案能记忆化，那能不能每个过程都记忆化一遍呢？
我们可以记录第 iii 位每种 357357357 出现情况的种类数，分类讨论.
将 357357357 都出现的情况记作 AAA，将 357357357 出现两个的情况记作 BBB，将 357357357 出现一个的情况记作 CCC.
AAA：
1. 可以由上一个 AAA 填上 3,5,73,5,73,5,7 获得，情况数 ×3\times 3×3.
2. 可以由上一个 BBB 填上所缺的数获得.
BBB：
1. 可以由上一个 BBB 填上 3,5,73,5,73,5,7 中的两个数字获得，情况数 ×2\times 2×2.
2. 可以由上一个 CCC 填上所缺的数获得.
CCC：
可以由一个都没有获得.
对于每次查询，时间复杂度：O(1)O(1)O(1).
预处理时间复杂度：O(N)O(N)O(N).
总时间复杂度：O(N)O(N)O(N) .
如果你嫌内存占用太大了，你可以多花费 O(TlogT)O(T\log T)O(TlogT) 的时间复杂度转离线，把空间复杂度降至 O(1)O(1)O(1).
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
120PTS
Macw老师提出来一个快速的办法，理论上可以通过 T=1,N≤10107T=1,N\le 10^{10^7}T=1,N≤10107 的数据！
首先是随便选取 357357357 中的任意一位，总共有 3N3^N3N 种情况.
然后减去只选择两个数的，即只选 353535 的，只选 373737 的和只选 575757 的，共有 3×2N3\times 2^N3×2N 种情况.
我们发现只选一个数的情况多选了一次，所以需要加回，即将结果 +3+3+3.
这样就可以以 O(logN)O(\log N)O(logN) 的时间复杂度求出答案了！
我们注意到 109+710^9+7109+7 与 2,32,32,3 均互质，所以对于更大的数可以用费马小定理来将 NNN 降至 109+510^9+5109+5 以内.
对于每次查询，时间复杂度：O(logN)O(\log N)O(logN) .
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T6 加固：多维动态规划
点击跳转
这道题得90分的同学大多就是因为没有特判n = 1 的情况，这次也算是提醒了大家看测试点数据的重要性了。
下面给出 222 种对于这道题的解法：
AAA：三维动态规划
在这个问题中，我们需要最大化在森林环形结构中小猪家园存活后保留的金币总数。由于家园是环形的，每个小猪有两个邻居，强化一个小猪的家会从其两个邻居那里各拿走 c 个金币。我们的目标是决定哪些小猪的家应该被强化，使得在攻击后幸存的家园中的金币总数最大.
为了解决这个问题，我们可以使用动态规划（DP）。我们需要记录到当前小猪为止，考虑强化或不强化当前小猪时，能够获得的最大金币数。由于问题涉及环形结构，我们可以将其转化为线性问题，通过两次DP处理来解决.
动态规划状态定义
我们使用三维数组 dp[i][j][k] 来表示状态，其中：
* i 表示当前考虑到第 i 只小猪.
* j 表示第 i-1 只小猪是否被强化（0 表示未强化，1 表示强化）.
* k 表示第 i 只小猪是否被强化（0 表示未强化，1 表示强化）.
状态转移方程
* 如果第 i 只小猪不强化 (k = 0)：
* 如果第 i-1 只小猪强化 (j = 1)：dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][1][1] - 2*c)
* 如果第 i-1 只小猪不强化 (j = 0)：dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][0][1])
* 加上第 i 只小猪的初始金币：dp[i][0][0] += a[i]
* 如果第 i 只小猪强化（k = 1）：
* 如果第 i-1 只小猪强化 (j = 1)：dp[i][1][0] = max(dp[i-1][1][0] - 2*c, dp[i-1][0][0]) - 2*c
* 如果第 i-1 只小猪不强化 (j = 0)：dp[i][1][0] = max(dp[i-1][0][0], dp[i-1][0][1]) - 2*c
* 加上第 i 只小猪的初始金币：dp[i][1][0] += a[i]
注意：这里的 dp[i][1][0] 应该是 dp[i][1][1]，因为我们在考虑第 i 只小猪强化的情况.
修正后的状态转移方程为：
* dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][0][0]) + a[i]
* dp[i][0][1] = max(dp[i-1][1][1] - 2*c, dp[i-1][0][1]) + a[i]
* dp[i][1][0] = max(dp[i-1][1][0] - 2*c, dp[i-1][0][0]) - 2*c + a[i] (这种情况实际不会用到，因为 k 表示当前小猪的强化状态)
* dp[i][1][1] = max(dp[i-1][1][1] - 2*c, dp[i-1][0][1]) - 2*c + a[i]
由于我们只关心最后一只小猪之前的状态，并且我们最终需要的结果是在第 n 只小猪考虑强化或不强化时的最大值，所以最终答案应该从 dp[n][0][0], dp[n][0][1], dp[n][1][0] (这里实际上不需要考虑，因为最终小猪不能单独强化而不考虑最后一个邻居), dp[n][1][1] - 2*c (如果第 n 只小猪强化，并且考虑从第 1 只小猪不再拿走金币的情况) 中选取.
边界条件
* 初始化 dp[1][...] 时，由于第 0 只小猪不存在（环形结构），我们需要单独处理第一只小猪的情况.
时间复杂度：O(N)O(N)O(N).
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
BBB：二维动态规划
这种解法是我通过观察Macw老师的代码想到的（真是太妙啦！）.
在这个问题中，我们需要最大化在森林环形结构中小猪家园存活后保留的金币总数。由于家园是环形的，每个小猪有两个邻居，且强化一个小猪的家会从其两个邻居那里各拿走 m 个金币（题目中的 c 在此解答中用 m 表示，以与代码一致）。我们的目标是决定哪些小猪的家应该被强化，使得在攻击后幸存的家园中的金币总数最大。
由于问题涉及环形结构，直接应用动态规划（DP）会比较复杂。为了简化问题，我们可以将环形结构拆分为两个线性问题：
1. Case A：假设不强化第1只小猪的家园。
2. Case B：假设强化第1只小猪的家园。
对于每种情况，我们可以使用动态规划来计算到第 n 只小猪时能够获得的最大金币数。
动态规划状态定义
我们使用二维数组 dp[i][j] 来表示状态，其中：
* i 表示当前考虑到第 i 只小猪。
* j 表示第 i 只小猪是否被强化（0 表示未强化，1 表示强化）。
状态转移方程
* 如果第i只小猪不强化 (j = 0)：
* dp[i][0] = max(dp[i-1][0], dp[i-1][1])
* 如果第i只小猪强化 (j = 1)：
* dp[i][1] = max(dp[i-1][0] + a[i], dp[i-1][1] + a[i] - 2*m)
其中，a[i] 表示第 i 只小猪家里初始的金币数。
边界条件
* 对于Case A：
* dp[1][0] = 0（不强化第1只小猪）
* dp[1][1] = -∞（禁用强化第1只小猪的情况）
* 对于Case B：
* dp[1][0] = -∞（禁用不强化第1只小猪的情况）
* dp[1][1] = a[1]（强化第1只小猪）
考虑环形特性
在 Case B 中，由于我们假设强化了第1只小猪，当计算到第 n 只小猪时，还需要考虑从第 n 只小猪到第1只小猪的额外金币扣除（因为它们是邻居）。但由于我们是线性处理，这个额外的扣除已经在 dp[n][1] 的计算中隐含处理了（即如果第 n 只小猪也强化，那么从 dp[n-1][1] 到 dp[n][1] 的转移已经扣除了 2m）。因此，在最终比较 Case A 和 Case B 的结果时，不需要再额外处理环形特性。
时间复杂度：O(N)O(N)O(N).
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
希望各位能在期末考试中获得一个好成绩！
