CF1860

2023-08-18 22:15 作者:wukaichen888 0人读过 | 我要投稿

用小号打的，很难评价整体是赚了还是亏了

大胆猜想，两种构造方案：

()()()()......

((((......))))

解决所有情况，除了单个 () 无解特判

什么英语阅读题（恼

lj 出题人写的什么垃圾题面，一堆歧义，是给人看的？不被骂才怪（恼

将 m 分为整除 k 和余数部分

贪心地，先处理余数部分，然后处理整除部分

直接算就行

一眼题，直接按题意博弈一下

用一个树状数组优化

然后就做完了

注意特判位置中间，不能再跳的点，也开一个树状数组

当然可以不用树状数组，但我懒

直接把贡献写出来， $0-1$ 数对贡献：

$%5Csum%20p_i-%5Cfrac%7Bc1%5Ctimes(c1%2B1)%7D%7B2%7D$

$p_i$ 表第 $i$ 个 $1$ 的位置，共 $c1$ 个 $1$

然后 $1-0$ 同理，解方程易得最终 $%5Csum%20p_i$

问题变成：最少交换几次数使 $%5Csum%20p_i%3Dk$

转化一下得到：

问题变成：有 $c1$ 个 $1$ 且满足 $%5Csum%20p_i%3Dk$ 的序列与原序列最多多少个 $1$ 位置相同

这还要想，直接 dp 啊！

所以就可做了

rk73，创新高，真不戳

标签：

CF1860的评论 (共条)