P3718 [AHOI2017初中组]alter

· · 题解

做一下本省历年的初中题捏=w=

说句实话出的挺不负责的，四题里面基本上都有两题原题（恼

首先这题可能你会想到一个奇怪的贪心，就是我们每次修改，肯定会在一个连续的块里面修改，那么我们修改哪个点呢？我们可能会直观的贪心，想到修改当前最长块的中点。现在这个块分成三个块了（取反的单独算一个块）。块长度用堆维护，时间复杂度 O(n\log_2n)。对于块长为 1 或 2 不能修改在块中，必然在边缘上，所以特判即可。

但是这个算法显然是错的，hack 

Input:
9 2
NNNNNNNNN
Output:
2

不能贪心，那么由于这题最大值最小显然我们考虑二分，而且上面这样修改给我们的二分提供了判定的启示。我们令 check(x) 为答案是否小于等于 x。很显然，对于一个连续的块中我们会每次在 (x+1), 2(x+1)\dots k(x+1) 的位置取反。那么也就是说对于一个块，如果长度为 l，则需要取反 \left\lfloor\dfrac{l}{x+1}\right\rfloor 下。累加一下和就能得到答案。

不过这个时候就有个问题了，如果块长度恰好为 (x+1) 的倍数，那么会在最后一个位置取反，会影响到下一个块的长度，这样就很麻烦，事实上并不会这样。当 x\ge 2 时，我们可以把最后一个取反位往前移一下，比如说 x = 2，有一个为 NNNNNN 的序列，本来应该是 NNFNNF，后面的连续块必然是 F 的，这样就会改变后面连续块的长度。不过我们变成 NNFNFN，这样就避免了这个问题。

不过当 x = 1 时，我们这样就必然会和后面的连起来，也就是说 check(1) 是不准确的。这不好。所以我们可以特判一下 x = 1 的情况。注意到 x = 1 的序列必然能变成 NFNFNFNF... 或者是 FNFNFNFN... 的样子。显然我们不会取反同样位置两次，我们统计原序列与这两个序列有多少不同位置，数量是否小于等于 k，先特判再二分即可。

不过加了这个特判后一定要注意在二分之中要判断答案是否已经取到了 2。因为当答案取到 2 后，下一个 mid 就会取 1，而且 check(1) 可能能行。但是我们的特判说明是不行的。我试了试不加这个答案等于 2 的特判是 84pts，看到讨论区有个 hack 数据，来搬上来：

Input:
7 2
FNNFNNF
Output:
2

在二分的时候，如果按照刚才的算法 check(1) 可行，但是实际上是不对的。所以必须要在答案等于 2 时停止二分，否则就会二分到 1 上。

代码：

//SIXIANG
#include <iostream> 
#define MAXN 200000
#define QWQ cout << "QWQ" << endl;
using namespace std;
int a[MAXN + 10], bl[MAXN + 10], n, k, pika, c1 = 0, c2 = 0, tot = 0, ct = 1;
char o;
bool check(int x) {
    int rest = 0;
    for(int p = 1; p <= tot; p++)
        rest += (bl[p] / (x + 1));
    return (rest <= k);
}
int twofen() {
    int l = 1, r = n, mid, ans = 114514;
    while(l <= r) {
        int mid = (l + r) >> 1;
        bool pwp = check(mid);
        if(mid == 2 && pwp) {//答案等于 2 的特判
            ans = 2;
            break;
        }   
        if(pwp) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}
int main() {
    cin >> n >> k;

    for(int p = 1; p <= n; p++) {
        cin >> o;
        a[p] = (o == 'N');
        if(a[p] == pika) c1++;
        else if(a[p] == (!pika)) c2++;
        pika ^= 1;//不同的位数
    }
    if(c1 <= k || c2 <= k) {//对 1 的特判
        cout << 1 << endl;
        return 0;
    }

    for(int p = 2; p <= n; p++) {
        if(a[p] == a[p - 1]) ct++;
        else bl[++tot] = ct, ct = 1;
    }
    bl[++tot] = ct;//计算每个块的长度
    cout << twofen() << endl;
}

总而言之也不太难，小细节有点多，多考虑一下也不难 pwp

第一次提交不小心把第一个 hack 写错了(*/ω＼*)