前言
为什么现在 10/12 了我才发,问就是突发奇想(
这次比赛令我高兴的一点是没有一道 DP!!!
(可惜这场我没打完
T1 NOON
字符串遍历题,秒切
注意不要图方便用 find 然后 erase,因为 NOON 头尾相同,可能出现 NOONOON。
T2 MAPLE序列
暴力枚举 b1b_1b1 & b2b_2b2 即可,没有什么好说的,一样秒切
T3 午枫的石子合并
我还以为是石子合并原题,吃罚时了(悲
将第 iii 堆石子合并到第 i+1i+1i+1 堆时,若第 iii 堆有 xxx 个石子,操作次数为 ⌈x/k⌉⌈x/k⌉⌈x/k⌉。最终所有石子合并到第 iii 堆时,[1,i−1][1,i-1][1,i−1] 堆需从第1堆向右合并,[i+1,n][i+1,n][i+1,n] 堆需从第 nnn 堆向左合并。可预处理前缀和后缀的最小合并操作次数,枚举最终合并的位置,取最小总操作次数即可。
T4 午枫的彩排2
比较简单的一道模拟,每个舞台只用 +1+1+1 或 −1-1−1 操作更优。预处理 −1-1−1 的后缀最大值,枚举分界点 iii,取 iii 的花费加上 i+1i+1i+1 的后缀最大值的最小值。听起来有点绕,实现非常 easy。
T5 午枫勇闯移动迷宫
不难能看出是最短路,距离就是方向是否相同,若相同则两点距离为 000(不需要改变方向),否则距离为 111(改变方向),然后 BFSBFSBFS 就可以了。
T6 午枫的创造
压轴绿题,刚看的时候还以为是数学题(实际上就是)。
题目大意
给定一个字符串序列,可以修改任意位置的字符串。求有多少种修改方式,使得所有长度 ≥2 的子序列的字符集合与原序列相同。
思路
1. 二进制表示:每个字符串用二进制整数表示(字符不重复)。
2. 关键条件:所有长度 ≥2 的子序列的按位或值必须保持不变。
3. 修改规则:
* 如果要修改 a[i],必须保证 a[i] | x = b[i] | x(x 是相邻元素)。
* 对于每一位:
* 如果 a[i] | x 的某位是 0,则 b[i] 该位必须为 0。
* 如果 a[i] | x 的某位是 1 且 x 该位是 0,则 b[i] 该位必须为 0。
* 如果 a[i] | x 的某位是 1 且 x 该位是 1,则 b[i] 该位可以是 0 或 1(有 2 种选择)。
总结
可恶居然没有打完这个没有 dpdpdp 的挑战赛!!!