十一挑战赛#23 题解
T1
按题意枚举即可。
T2
观察到 aia_iai 的值域较小,考虑先将所有值为 aia_iai 的装进 tait_{a_i}tai 的桶里。
接下来直接枚举 b1+b2b_1+b_2b1 +b2 的值,值域是 [2,10000][2,10000][2,10000],然后扫一遍桶过去就可以了。
T3
考虑枚举最后所有石头放在哪个位置,然后前缀后缀和跑一遍就行了。
T4
很显然,对于一盏灯的操作只会是全是加法或全是减法,不然不优。
我们令 ci=(ai−bi) mod mc_i=(a_i-b_i) \bmod mci =(ai −bi )modm,这就是一盏灯减法的代价,则它加法的代价为 (m−ci) mod m(m-c_i)\bmod m(m−ci )modm,则总共的花费次数就是使用加法的代价最大值加上使用减法的代价最大值。
我们将 cic_ici 排序,显然我们应该选前若干个用减法,其它的用加法,枚举即可。
T5
显然,我们可以对迷宫进行 bfs,如果走的方向相对应的颜色和该格子相同,那么花费为 000,否则为 111,那么用 deque 做一个 0-1 bfs 就行了。
T6
一开始应该是数据造假了,不然看这么简单的题不可能大佬们 (和 AI 们) 都过不去。
根据限制二,我们只要枚举修改哪一个字符串,再加起来就行了。
我们重点于关注限制三:容易发现,只要和相邻的两个字符串符合要求就行了。那么我们就考虑将 mmm 个字母分成 333 部分:必须选的,必须不选的,可选可不选的。设可选可不选的个数为 xxx,那么根据限制一,修改该字符串的方案总数就是 2x−12^x-12x−1(减掉于原来相同的)。
最后,通过观察可以发现,可选可不选的字母就是左右两边的字符串都有的字母个数,可以用二进制压一下,取并就行了。