COCI 2023-2024

2026-08-24 08:00:00

T1

记录 $a$ 中每个值与位置的映射表。
对每个未配对的 $a_i$ 中元素的值 ， $b_j$ 进行配对，遇到存在的值 $a_{tp}$，就将 $a_{tp}$ 转化为 $b_j$ ，而后再将 $a_i$ 转化为 $a_{tp}$

T2

容易得出，二进制每一位对应不同的 $Fib$ 值，这里的 $Fib$ 数组可直接视为该位的权值

最后两位必须为 $1$ ，同时观察循环可得：最后一位不计入数字权值。
同理观察权值读取方式：也就是每个字符串中不出现连续两个 $1$ ，一旦出现视为断点

记录每个长度的连续字符串，对应的权值和以及可能出现的不同字符串数量，分别记为 $val_i$ 与 $pos_i$

容易得到转移方程：

$val_i=\sum_{j=0}^{i-2}\frac{val_j}{pos_j}\prod_{k=0}^{i-2}pos_k$

$pos_i=\sum_{j=0}^{i-2}pos_j$

转移方程可 $O(n^2)$ 得出，也可前缀和优化为 $O(n)$

将字符串拼接为不同长度的总串，记录每种长度下不同总串的数量以及权值和，分别记为 $f_i$ 与 $fpo_i$
显然 $f_1$ 无意义，因为长度为 $1$ 的字符串一定会记入到别的字符串中

容易得到转移方程：

$f_i=val_{i-1}+\sum(_{j=2}^{i-2}f_j*pos_{i-j}+val_{i-j-1}*fpo_j)$

得到答案为：

$ans_i=ans_{i-1}+\sum_{j=1}^{i-2}(f[i-j] * pos[j])$

T3

容易得到：按按钮的次数一定是递增的，同时先按按钮一定不劣

则有操作单调性，记录每次操作的按按钮次数为 $f_i$ ，根据转移方程之间的比较，可以得出两种操作的次数一定不会减少

每次考虑增加一次操作 1 或 2，注意操作 2 也就是按按钮在最后一次按按钮之后，预处理贡献，可以 $O(n)$ 得到答案

T4