T1 大型の组合：数学
难度：红 下位
正解
本题看似是一道求组合公式的题，利用 CN1C_N^1CN1 公式即可得出结果。但是看看数据范围，long long 都做不到啊，只能用 string 来存。这里可以用组合的性质：CN1C_N^1CN1 等于 NNN。因此这道题输入什么就输出什么即可。
时间复杂度：O(1)O(1)O(1)
预计得分：100pts100pts100pts
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2 危险の试剂：数论
难度：橙 中位
题意说明
就是让你求出弹珠最多能在试剂瓶里分裂几次，如果不能激活就输出 −1-1−1。
体积公式
在特殊说明部分已经给出了球体、直圆柱体的体积计算公式了，直接带入即可。需要注意的是，由于 π\piπ 和 43\frac{4}{3}34 是小数，因此需要使用 double 进行存储。
球体体积计算公式如下：
V1=43πr13V_1=\frac{4}{3}\pi{r_1}^3 V1 =34 πr1 3
直圆柱体体积计算公式如下：
V0=πr02hV_0=\pi{r_0}^2h V0 =πr0 2h
特殊说明部分已说明不计球体之间的空隙，因此试剂瓶最多可以容纳 ⌊V1V0⌋\lfloor \frac{V_1}{V_0}\rfloor⌊V0 V1 ⌋ 个球。当可容纳球的数量不足 111 个时，说明不能激活，直接输出 −1-1−1。
代入计算：
特殊性质 A
因为在这个性质中，h=r0=k=r1h=r_0=k=r_1h=r0 =k=r1 ，通过简单的计算可得：
maxx<1maxx\lt1 maxx<1
因此不可以所有药剂都不可激活，全部输出 −1-1−1 即可。
时间复杂度：O(T)O(T)O(T)
预计得分：28pts28pts28pts
正解 | 枚举法（推荐）
由于 kkk 值的范围较小（≤106\le10^6≤106），可以直接采用枚举的方式找出最多可以分裂多少次，其时间是 logloglog 级的。
时间复杂度：O(T×logkyuanzhuqiu)O(T\times log_k^{\frac{yuanzhu}{qiu}})O(T×logkqiuyuanzhu )
预计得分：120pts120pts120pts
正解 | 数学法
我们可以采用换底公式来解答这个问题。根据换底公式：
logbN=logaNlogab\log_bN=\frac{\log_aN}{\log_ab} logb N=loga bloga N
可得，篮球最多可分裂的秒数是：
logs=⌊logmaxxlogk⌋\log s=\lfloor\frac{\log maxx}{\log k}\rfloor logs=⌊logklogmaxx ⌋
在此之后，我们需要验证计算结果是否超过实际分裂的最大数量，如果分裂秒数为负数，则直接设为 −1-1−1。
时间复杂度：O(T)O(T)O(T)
预计得分：120pts120pts120pts
注意：虽然这份代码时间复杂度更低，但是由于多次的数学计算，可能导致精度丢失，面对没有 Special Judge 的或者精度要求更高的题目题目可能会 WA，所以不推荐这种解法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3 重要の春联：模拟
难度：红 中位
正解
这是一道简单的输出题，找到公式直接输出即可。然而，作者似乎并不满意1e9的数据范围，把数据大小开到1e12，因此需要 long long 储存。右下角的坐标根据图片模拟易得：横坐标是横幅的宽+竖幅的长+横幅的宽；竖坐标是竖幅的长+横幅的长。
时间复杂度：O(1)O(1)O(1)
预计得分：140pts140pts140pts
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T4 时空の穿越：矩阵
难度：绿 下位
题意简化
给定序列 FFF，有：
Fi={1,1≤(i≤5)Fi−1+2×Fi−2+3×Fi−3+5×Fi−4+8×Fi−5,(i≥6)\begin{equation*} F_i= \begin{cases} 1, & 1\le (i\le 5)\\ F_{i-1}+2\times F_{i-2}+3\times F_{i-3}+5\times F_{i-4}+8\times F_{i-5}, & (i \ge 6)\\ \end{cases} \end{equation*} Fi ={1,Fi−1 +2×Fi−2 +3×Fi−3 +5×Fi−4 +8×Fi−5 , 1≤(i≤5)(i≥6)
求 AnsAnsAns，其中：
Ans={FNmod 232,FNmod 232<231(FNmod 232)−232,FNmod 232≥231\begin{equation*} Ans= \begin{cases} F_N\mod 2^{32}, & F_N\mod 2^{32}\lt 2^{31}\\ (F_N\mod 2^{32})-2^{32}, & F_N\mod 2^{32}\ge 2^{31}\\ \end{cases} \end{equation*} Ans={FN mod232,(FN mod232)−232, FN mod232<231FN mod232≥231
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
暴力代码
很显然的一个递推式子。直接模拟一下即可。
时间复杂度：O(TN)O(TN)O(TN)
空间复杂度：O(N)O(N)O(N)
预计得分：30pts30pts30pts
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
空间优化
显然 dpidp_idpi 只与 dpi−1,dpi−2,dpi−3,dpi−4,dpi−5dp_{i-1},dp_{i-2},dp_{i-3},dp_{i-4},dp_{i-5}dpi−1 ,dpi−2 ,dpi−3 ,dpi−4 ,dpi−5 有关。所以我们只需要记录 666 个数即可。
时间复杂度：O(TN)O(TN)O(TN)
空间复杂度：O(1)O(1)O(1)
预计得分：30pts30pts30pts
正解
由线性递推联想到矩阵加速。
回忆一下斐波那契数列的矩阵加速：定义矩阵：
[FnFn−1]\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} [Fn Fn−1 ]
得到：
M×[Fn−1Fn−2]=[FnFn−1]M \times \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} =\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} M×[Fn−1 Fn−2 ]=[Fn Fn−1 ]
根据矩阵乘法，得到：
M1,1×Fn−1+M1,2×Fn−2=FnM2,1×Fn−1+M2,2×Fn−2=Fn−1M_{1,1} \times F_{n-1}+ M_{1,2} \times F_{n-2} = F_n \\ M_{2,1} \times F_{n-1} + M_{2,2} \times F_{n-2} = F_{n-1} M1,1 ×Fn−1 +M1,2 ×Fn−2 =Fn M2,1 ×Fn−1 +M2,2 ×Fn−2 =Fn−1
所以得到：
M=[1110]M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} M=[11 10 ]
于是问题转化为：
[11]×Mn−1\begin{bmatrix} 1 \\ 1 \end{bmatrix} \times M^{n-1} [11 ]×Mn−1
矩阵快速幂即可。
类似地，我们定义矩阵：
[FnFn−1Fn−2Fn−3Fn−4]\begin{bmatrix} F_n \\ F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \end{bmatrix} Fn Fn−1 Fn−2 Fn−3 Fn−4
得到：
M×[Fn−1Fn−2Fn−3Fn−4Fn−5]=[FnFn−1Fn−2Fn−3Fn−4]M \times \begin{bmatrix} F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \\ F_{n-5} \end{bmatrix} = \begin{bmatrix} F_n \\ F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \end{bmatrix} M× Fn−1 Fn−2 Fn−3 Fn−4 Fn−5 = Fn Fn−1 Fn−2 Fn−3 Fn−4
根据矩阵乘法，得到：
M1,1×Fn−1+M1,2×Fn−2+M1,3×Fn−3+M1,4×Fn−4+M1,5×Fn−5=FnM2,1×Fn−1+M2,2×Fn−2+M2,3×Fn−3+M2,4×Fn−4+M2,5×Fn−5=Fn−1M3,1×Fn−1+M3,2×Fn−2+M3,3×Fn−3+M3,4×Fn−4+M3,5×Fn−5=Fn−2M4,1×Fn−1+M4,2×Fn−2+M4,3×Fn−3+M4,4×Fn−4+M4,5×Fn−5=Fn−3M5,1×Fn−1+M5,2×Fn−2+M5,3×Fn−3+M5,4×Fn−4+M5,5×Fn−5=Fn−4M_{1,1} \times F_{n-1} + M_{1,2}
\times F_{n-2} + M_{1,3} \times F_{n-3} + M_{1,4} \times F_{n-4} + M_{1,5} \times F_{n-5}=F_n\\ M_{2,1} \times F_{n-1} + M_{2,2} \times F_{n-2} + M_{2,3} \times F_{n-3} + M_{2,4} \times F_{n-4} + M_{2,5} \times F_{n-5}=F_{n-1}\\ M_{3,1} \times F_{n-1} + M_{3,2} \times F_{n-2} + M_{3,3} \times
F_{n-3} + M_{3,4} \times F_{n-4} + M_{3,5} \times F_{n-5}=F_{n-2}\\ M_{4,1} \times F_{n-1} + M_{4,2} \times F_{n-2} + M_{4,3} \times F_{n-3} + M_{4,4} \times F_{n-4} + M_{4,5} \times F_{n-5}=F_{n-3}\\ M_{5,1} \times F_{n-1} + M_{5,2} \times F_{n-2} + M_{5,3} \times F_{n-3} + M_{5,4} \times F_{n-4} +
M_{5,5} \times F_{n-5}=F_{n-4} M1,1 ×Fn−1 +M1,2 ×Fn−2 +M1,3 ×Fn−3 +M1,4 ×Fn−4 +M1,5 ×Fn−5 =Fn M2,1 ×Fn−1 +M2,2 ×Fn−2 +M2,3 ×Fn−3 +M2,4 ×Fn−4 +M2,5 ×Fn−5 =Fn−1 M3,1 ×Fn−1 +M3,2 ×Fn−2 +M3,3 ×Fn−3 +M3,4 ×Fn−4 +M3,5 ×Fn−5 =Fn−2 M4,1 ×Fn−1 +M4,2 ×Fn−2 +M4,3 ×Fn−3 +M4,4 ×Fn−4 +M4,5 ×Fn−5 =Fn−3 M5,1 ×Fn−1
+M5,2 ×Fn−2 +M5,3 ×Fn−3 +M5,4 ×Fn−4 +M5,5 ×Fn−5 =Fn−4
所以得到：
M=[1235810000010000010000010]M = \begin{bmatrix} 1 & 2 & 3 & 5 & 8\\ 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ \end{bmatrix} M= 11000 20100 30010 50001 80000
于是问题转化为：
Mn−5×[11111]M^{n-5} \times \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ 1 \end{bmatrix} Mn−5× 11111
矩阵快速幂即可。
时间复杂度：O(TlogN)O(T \log N)O(TlogN)
空间复杂度：O(1)O(1)O(1)
预计得分：100pts100pts100pts
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T5 可恶の施工：最小生成树、贪心
难度：绿 中位
题意简化
给定一个无向带权连通图，求在保证图连通的前提下，最少删除多少条边使得剩余边的总权值不超过给定的限制 ppp。若无法满足条件，输出 -1。
关键观察
* 最优解的结构一定是 保留权值较小的边，同时保证图的连通性。
* 这与 最小生成树 (MST) 的性质一致：MST 是权值和最小的连通子图。
* 因此，问题转化为：在 MST 的基础上，尽可能多地保留权值小的额外边，使得总权值不超过 ppp。
算法思路
1. 构建最小生成树：
* 使用 Kruskal 算法求出 MST，记录其权值和 sumMSTsum_{\text{MST}}sumMST 和使用的边数 n−1n-1n−1。
* 若 sumMST>psum_{\text{MST}} > psumMST >p，直接输出 -1（无解）。
2. 贪心添加额外边：
* 将 非 MST 边 按权值从小到大排序。
* 依次尝试添加这些边，直到总权值超过 ppp。
* 最终删除的边数为 总边数 mmm - 保留的边数。
时间复杂度分析
* Kruskal 算法：排序边 O(mlogm)O(m \log m)O(mlogm)，并查集操作 O(mα(n))O(m \alpha(n))O(mα(n))，总体 O(mlogm)O(m \log m)O(mlogm)。
* 贪心添加额外边：遍历至多 mmm 条边，O(m)O(m)O(m)。
* 总复杂度：O(T⋅mlogm)O(T \cdot m \log m)O(T⋅mlogm)，其中 TTT 为测试用例数量。
部分分策略
测试点 数据范围 特殊性质 可用算法 预计得分 1-2 N,M≤10N, M \leq 10N,M≤10 无 暴力枚举删边组合 10pts 3-4 N,M≤100N, M \leq 100N,M≤100 无 枚举保留边数 + Kruskal 30pts 5 N≤105,M≤2e5N \leq 10^5, M \leq 2e5N≤105,M≤2e5 所有边权相等 贪心保留最多边 25pts 6 M=N−1M = N-1M=N−1（树结构） 树边权和是否超过 ppp 直接判断 sum≤psum \leq psum≤p 10pts 7-10 N≤105,M≤2e5N \leq 10^5, M
\leq 2e5N≤105,M≤2e5 无 正解算法 100pts
特殊性质说明：
* 性质 A：所有边权相等时，保留尽可能多的边即可，无需考虑权值大小。
* 性质 B：图为树时，若 sumMST>psum_{\text{MST}} > psumMST >p 则无解，否则必须保留全部树边（不能删除任何边，否则不连通）。
正解代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T6 散落の字符：MANACHER算法、大模拟
难度：蓝 中位
题意说明
本次题目比较复杂，需要我们计算以下问题的答案。
1. 通过迷宫的最小花费 sumsumsum。
2. 转换 sumsumsum 并拼接到 sss 后面，转换 sss 为 01 字符串。
3. 计算转换为偶回文串最小花费 fff 的值。
4. 连接 ttt 和 sss，计算最长回文串 lll 的值。
走迷宫
这一部分采用任何搜索算法均可。期待大家给出出题组没做出来的 dp 的办法。以下是 dijkstra 的做法：
转换与拼接
这一部分直接采用模拟即可。一个字符的ASCII码值为偶数是 mod 2\bmod2mod2 的结果为 000，否则为 111。
计算 F 的值
在这一步中，我们需要推理一下。数据保证 sss 可以转化为偶回文串，说明 s+minas + min_as+mina 的结果是偶数或者拼接后的 sss 的中间值为 000。如果是第二种可能，就只需要保证其它部分是偶回文串即可。
因此无论如何，只要保证拼接后的 sss 是一个回文串即可保证是偶回文串。我们只需要从 i=0i=0i=0 一直到 i=∣s∣÷2i=|s|\div2i=∣s∣÷2 遍历一遍，找到改变成偶回文串的最小花费。对于每个第 iii 项，我们只需考虑是改变成 0 还是 1 的花费更小。
计算 L 的值
暴力做法：枚举每一段 l 中的子串。代码如下：
时间复杂度：O(∣l∣2)O(|l|^2)O(∣l∣2)
预计得分：50pts50pts50pts
我们可以使用 Manacher 算法来解决 lll 的计算。回文自动机的 Manacher 算法可以在 O(N)O(N)O(N) 时间中解决最长回文子串问题。
下面就是模板的 Manacher 算法了（这里使用 % 避免边界问题，若有想要深入学习的请见：这里）：
时间复杂度：O(∣l∣)O(|l|)O(∣l∣)
预计得分：200pts200pts200pts
正解
时间复杂度：O(n×m×logn×m))O(n\times m\times \log{n\times m}))O(n×m×logn×m))
预计得分：200pts200pts200pts
