CF1889A. Qingshan Loves Strings 2

发布时间 2023-10-30 10:21:07作者: ydtz

不妨考虑什么时候会无解!

显然当原序列 \(0,1\) 数量不同,或者序列总长为奇数时会无解!

否则我们设 \(l=1,r=n\)!开始回文配对!

如果配上了就直接删掉!并把左右端点向内移动!

如果两者都是 \(0\),就在末尾加上 \(01\)!都是 \(1\) 就加最前面!

以在末尾加入举例!此时如果开头是 \(01\) 就会多消掉两个数字!如果是 \(00\) 数字数量就不变,但是由于 \(0,1\) 数量相同,所以总会向后挪到 \(01\)!故此时一定有解!

数据范围很小!暴力操作即可!

推必要条件加强约束获得更多条件!