求思路证伪(玄关)
查看原帖
求思路证伪(玄关)
519986
Luxe877楼主2024/12/1 17:37

rt,这个思路不能过大样例,会在对应的 #13 和 #19 WA 掉。(也就是说大概 60pts)

我的思路是对于每个连续而相同的 t1,it_{1,i} 块和 t2,it_{2,i} 块(如样例1中 t1,1t1,3t_{1,1} \sim t_{1,3} 都为 11t1,4t1,4t_{1,4} \sim t_{1,4} 都为 00,就分别为两个个块),然后按照分的块贪心。

贪心思路是:对于每个两个块(t1t_1t2t_2 的),如果两个块中都是 00,直接暴力比对一样的个数,否则取两个块中 00 的个数的最小值和 11 的个数的最小值加到答案里,并将两个块中 0011 的数量都减去这两个最小值(因为拿去匹配了,后面不会用到)。

下一步就是比较两个块的右边界谁更前,将更前的块的指针指向下一个块(比如 [1,3](t1)[1,3] (t_1的)[2,2](t2)[2,2](t_2的) 比对时,将指向 t2t_2 的块的指针后移一个,即使其指向下一个块 )

最终当有一个 tt 的块被匹配完时就输出答案。

具体代码暂时先不给,(没时间重写了,赛时写200行好难写回来)

2024/12/1 17:37
加载中...