CF1784F 不需要注意力的做法

liangbowen · 2026-01-26 20:13:41 · 题解

讲课题，大概是丢了三个条件，然后说这个就是充要条件。这个堆数值也太恶心了吧！所以就自己想了一下，得到了如下奶龙做法。我觉得这个做法是最容易的啊，怎么没人这样做呢。

编充要条件

考虑改成对操作序列计数，为了不重不漏，要对每个本质不同的集合选出一个代表元，然后对代表元计数。于是考虑如下打表程序（其中 A 是操作 1，B 是操作 2）：

int n, k; vector <int> A; map <vector <int>, vector <int>> mp;
void erase(int x) {
    vector <int> T;
    for (int i = 0; i < x; i++) T.push_back(A[i]);
    for (int i = x + 2; i < A.size(); i++) T.push_back(A[i]);
    A = T;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int S = 0; S < (1 << k); S++) {
        A.clear(); for (int i = 1; i <= 2 * n; i++) A.push_back(i);
        for (int i = 0; i < k; i++) if (S >> i & 1) erase(0); else erase(A.size() / 2 - 1);
        mp[A].push_back(S);
    }
    printf("%d\n", (int)mp.size());
    for (auto [sta, vec] : mp) {
        for (int i : sta) printf("%d ", i); puts("");
        for (int S : vec) {for (int i = 0; i < k; i++) putchar((S >> i & 1) ? 'A' : 'B'); puts("");}
    }
    return 0;
}

输入 10 5，截取某一项：

5 6 7 8 9 16 17 18 19 20
AABBB
ABABB
BAABB
ABBAB
BABAB

很难不发现 AB 的数量不变。回到原题，手玩发现 ABB 与 BAB 是等价的，我们考虑将所有 ABB 变成 BAB，就得到了一个代表元，例如上面例子的代表元即为 BABAB。

看起来直接做完了，然而换个输入就爆了？发现只有 k>n/2 时会爆，且爆的时候总是形如打表结果的一个后缀，此时前面 1\sim n 的部分总是被删光了。考虑如下打表程序：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define mems(x, v) memset(x, v, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef long double wisdom;

int n, k; vector <int> A; map <vector <int>, vector <int>> mp;
void erase(int x) {
    vector <int> T;
    for (int i = 0; i < x; i++) T.push_back(A[i]);
    for (int i = x + 2; i < A.size(); i++) T.push_back(A[i]);
    A = T;
}
bool valid(int S) {
    for (int i = 0; i + 2 < k; i++) if ((S >> i & 1) && !(S >> (i + 1) & 1) && !(S >> (i + 2) & 1)) return false;
    return true;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int S = 0; S < (1 << k); S++) {
        A.clear(); for (int i = 1; i <= 2 * n; i++) A.push_back(i);
        for (int i = 0; i < k; i++) if (S >> i & 1) erase(0); else erase(A.size() / 2 - 1);
        mp[A].push_back(S);
    }
    printf("%d\n", (int)mp.size());
    for (auto [sta, vec] : mp) {
        int tot = 0; for (int S : vec) if (valid(S)) tot++;
        if (tot >= 2) {
            printf("[%d] ",(int)vec.size()); for (int i : sta) printf("%d ", i); puts("");
            for (int S : vec) {for (int i = 0; i < k; i++) putchar((S >> i & 1) ? 'A' : 'B'); puts("");}
        }
    }
    return 0;
}

其中一个：

[8] 15 16 17 20 21 22
BBBAAAAB
ABBAAAAB
BABAAAAB
AABAAAAB
BBAAAAAB
ABAAAAAB
BAAAAAAB
AAAAAAAB

随便输点数，只要你是正常人都能注意到：出现错误，是因为前半段删除过程中 AB 打架了，串的一个前缀可以任意选择。那直接钦定前缀这一坨全由 A 来删除即可。要钦定多长？设长度为 t，相当于 1\sim 2t 全滚蛋了，直到 k\le n/2 就转成上面的正常情况了。

也就是，设序列最小值为 x，则 t=\frac{2n-2(2n-x+1)}2=x-n-1，注意这里要满足 x>n+1 且 x 为奇数。

然后还要保证 x 是最小值。

先删掉 1\sim 2t，此时 x 一定在剩余元素的中间。于是限制是这样的：保证序列不存在 ABB，且不会删到 x，且把 2t+1\sim x-1 全删掉。第三个条件相当于限制了 A 的总数。对于第二个条件，发现实质是在间隔之间维护了一个指针，初始指在 x-0.5 的位置，显然第一步一定是 A 所以初始指在 x+0.5 的位置；来个 A 就 +1，来个 B 就 -1，要保证前缀和非零。

Fun Fact：不是啊，我草，我题解都写完了，我还以为自己科研了一个新做法呢，结果 TM 的官方题解就是这个做法？？？那为啥洛谷题解没有啊？？？那就这样吧，诶。