P3718 [AHOI2017初中组]alter

Ofnoname · 2022-01-27 17:11:10 · 题解

神题，我感觉很阴。

二分答案，答案最小为1，最大为全部长度。如果答案可行则减小上界，否则增大下界。

判断答案是否可行：从左往右更新长度，当我们发现当前长度超过要求长度的时候，应该取反哪一个？

如图，当遍历到第四个F时，允许的最长长度为3。此时长度为4，那么只有两种情况：

• 下一个点仍然同色，即本节点是一长段同色块里的中间点。把自身反转，使得下一个点从1开始计算长度是最优的。

• 下一个点颜色不同，即本节点这一段刚好比最大长度大1，被两端不同字母包围。那么不应反转自己，这样下一个点的起始长度本来是1却变成了2，当然是不利的（同样也不能反转这一段开头的）。此时反转这一段里除掉两端的任意点都可以。

但是这样存在一个问题，如果允许的最大长度是1。出现连续一段时（只有两个），除掉两端没有其他点，而反转哪一个都不一定是正确的。上述方法失效了。

对1特判时，这个时候我们直接换一种思路。满足长度为1的序列只有两种：字符N或F开头，并且N和F交替出现。直接检查原字符串能否在k次内转化为两个之一，若可以则答案为1，否则再进行二分答案。

int N, k;
char s[MAX], t[MAX];

bool Judge(int maxlen)
{
    copy(s, s+N, t); //只修改字符串的拷贝
    for (int i=0, tm=0, len=0; i < N; i++) {
        if (i==0 || t[i] != t[i-1]) len = 1;
        else len++;

        if (len > maxlen) {
            if (i != N-1 && t[i]==t[i+1])
                t[i] = (t[i]=='N'?'F':'N');
            //t[i]!=t[i+1]时，修改任意位置都可以，且不影响后面判断，干脆不去真的修改
            if (++tm > k) return 0; //一定会消耗一次次数
        }
    } return 1;
}

bool Judge1() {
    int f[2] = {};
    //将字符串转化为"NFN.."和"FNF.."所需次数
    for (int i = 0; i < N; i++) {
        f[i&1] += s[i]=='N';
        f[(i&1) ^ 1] += s[i]=='F';
    }return f[0]<=k || f[1]<=k;
}

int main() {
    cin >> N >> k >> s;
    if (Judge1()) // 1的情况
        puts("1");
    else { // 其他情况
        int l = 2, r = N;
        while (l < r) {
            int mid = (l + r) >> 1;
            Judge(mid) ? r = mid : l = mid + 1;
        } cout << l;
    }
}