CF 521 题解
A我们固定 $s$ ,循环位移所有 $t$,发现答案就是相同的字母对数。而循环位移 $s$ 是本质不变的,所以答案乘个 $n$ 就好了。所以你构造的串中每个字母都要保证是 $s$ 中出现次数最大的,设这样的字母有 $c$ 个,答案显然是 $n^c$。B从高到低位贪心一定是最优的。对于每个点,我们可以通过判断周围点是否存在来确定这个点是否可以取走,每次取走能取的最大/最小后更新周围的点即可。C...
A我们固定 $s$ ,循环位移所有 $t$,发现答案就是相同的字母对数。而循环位移 $s$ 是本质不变的,所以答案乘个 $n$ 就好了。所以你构造的串中每个字母都要保证是 $s$ 中出现次数最大的,设这样的字母有 $c$ 个,答案显然是 $n^c$。B从高到低位贪心一定是最优的。对于每个点,我们可以通过判断周围点是否存在来确定这个点是否可以取走,每次取走能取的最大/最小后更新周围的点即可。C...
A手玩一下样例,我们从大到小确定每个数:将确定的数挪到序列的最前面,设确定了 $x$ 个数,那么 $x \times x$ 的方格的数都没用了,并且剩下的是一个 L 形方格。剩下的 L 形方格内对角线一定是最大值,所以我们只需要每次取最大值,将这个数和已经确定的数的 $\gcd$ 删掉即可。注意要删两次。B可以猜测一下选择方案一定是前面可能有某些增加值的地方,后面值就一直不变了。所以我们先一...
上午打比赛的时候感冒了十分难受。。于是发挥非常差。A如果偶数层也是确定的话直接让 $a_i = h_i-h_{f_i}$ 就好了。否则我们考虑偶数层是干什么的:它可以让它所有儿子统一减少一个数。于是对于每个点统计出儿子节点的最小值,将这个点赋成最小值即可。B考虑如果确定了左上角 $2 \times 2$ 的矩阵,那么前两行剩下的格子的每一列的字符集就确定了,贪心分配一下。然后剩下的行每个 $...
A设点 $i$ 有 $a_i$ 个糖果。对于每个起点 $s$ ,只需要能计算出对于每个点 $t$,完成所有任务所需要的最短时间,取 max 即可。而计算这个时间相当于是先转几圈,然后找一个距离它最近的当做最后一次的任务。可以加强到 $10^5$,观察一下 $s \to s+1$ 的变化即可。B这个程序相当于每次取这个点最前面的保证和是非负的一段区间。所以想让它掉进坑一定是前面一堆 $0$,然...
A两人策略不会互相造成影响,最优策略是每个人每次拿一个。判断是否 $n_1 \leq n_2$ 即可。B先考虑如何计算一个排列的 $f$:设一个位置左边和右边第一个比他小的位置为 $ls_i,rs_i$,答案就是 $\sum_{i=1}^n a_i(rs_i-ls_i-1)$。另一种思考思路是从小往大放,每次相当于将选出的位置分成左右两个连通块,每次得到的贡献是它所在的连通块跨过它的区间个数...