更好阅

记录一些自己做过感觉不是很清晰的题目。

ARC193C Grid Coloring 3

考虑题目中给出的十字覆盖正着计数很困难，所以正难则反，倒过来做。

考虑反过来的第一次操作相当于把一个颜色相同的十字上的颜色都换成 $0$（我们把 $0$ 定义为可以表示任何数的颜色）。进一步，我们考虑恰好有 $r$ 行 $c$ 列为“主色”，我们一定可以把它们全部变成 $0$。

接着我们就可以只改变一行或一列的颜色了，比如我们要染一行，就找一个“主色”列，对于这一行和这一列操作。由于操作逆序，所以“主色”列总会被覆盖为主色。这样我们可以直接把主色的 $r$ 行 $c$ 列给删掉，把问题转化成在一个 $n \times m$ 的网格中，每次删一列或是一行。当然为了符合原问题，我们有一些限制，即 $n \times m$ 网格中不能存在一行或一列均为“主色”。

我们可以考虑 DP，令 $f_{n, m, 0/1}$ 表示删减 $n \times m$ 的网格，以及是否有主色的限制。为了方便，我们将这一维 $0/1$ 称作 $t$。

接着思考怎么转移。首先如果分行、列两种情况讨论的话十分麻烦，我们不妨只考虑行，如果要考虑列时我们把矩阵旋转一下让列变成行即可。那么假设我们选择了其中 $r$ 行，由于我们只能删除颜色相同的一行，所以这 $r$ 行内每个行内的格子颜色都要相等。再考虑“主色”的限制，这 $r$ 行的情况就是 $(C - t)^r$，其中 $C$ 为题目中的颜色限制。那么剩下的 $n - r$ 行中我们只能选择列了，并且由于前 $r$ 行都不是主色，所以我们选择列的时候就可以不考虑主色，即 $f_{m,n - r, 0}$。

但此时又有一个限制是这 $n - r$ 行中不能每一行的颜色不能相同，所以我们需要再加一个维度 $0/1$ 表示是否限定当前每一列颜色相同。则我们要分为 $f_{n,m,t,0}$ 和 $f_{n,m,t,1}$ 两种情况转移。对于 $f_{n, m, t, 0}$ 根据上述解释可以从 $(C - t)^r \times f_{m, n-r, 0, 1}$ 转移过来；对于 $f_{n, m, t, 1}$ 我们还要分两种情况讨论。

一种是枚举的 $r$ 行的颜色全部相同，这种情况的方案数就是 $(C - t) \times f_{m, n - r, 1, 1}$。原因是我们定义的 $t = 1$ 这维限制每一行、每一列不全为钦定色，另一维则限制每一列颜色不全相同，$t = 1$ 其实就起到了每一行不全为钦定色的效果。

另一种是枚举的 $r$ 行颜色不全相同，这种情况的转移就是 $[(C - t)^r - (C - t)] \times f_{m, n - r, 0, 1}$。

然后要注意我们所有的枚举 $r$ 行操作都要乘上一个 $C_{n}^{r}$，所以我们在 DP 前预处理一下组合数和 $C$ 的次方即可。

const int N = 410, Mod = 998244353;
LL n, m, c;
LL f[N][N][2][2], pw[2][N], C[N][N]; 

void init() {
    rep(i, 0, N - 1) {
        C[i][0] = 1;
        rep(j, 1, i) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % Mod;
    }
    pw[0][0] = pw[1][0] = 1;
    rep(i, 1, N - 1) {
        pw[0][i] = pw[0][i - 1] * c % Mod;
        pw[1][i] = pw[1][i - 1] * (c - 1) % Mod;
    }
    memset(f, -1, sizeof f);
}

LL dp(int n, int m, int t, int p) {
    LL &u = f[n][m][t][p];
    if (u != -1) return u;
    u = pw[t][n];
    if (p) u = (u + Mod - (c - t)) % Mod;
    rep(r, 1, n - 1) {
        LL tmp = pw[t][r], tmp2 = c - t, res = 0;
        if (!p) res = (res + tmp * dp(m, n - r, 0, 1) % Mod) % Mod;
        else {
            res = (res + (tmp - tmp2) * dp(m, n - r, 0, 1) % Mod) % Mod;
            res = (res + tmp2 * dp(m, n - r, 1, 1) % Mod) % Mod;
        }
        u = (u + res * C[n][r] % Mod) % Mod;
    }
    return u;
}

int main() {
    n = read(), m = read(), c = read();
    c %= Mod;
    init();
    LL ans = 1;
    rep(i, 1, n - 1) rep(j, 1, m - 1) {
        LL tmp = C[n][i] * C[m][j] % Mod;
        LL tmp2 = (dp(n - i, m - j, 1, 0) + dp(m - j, n - i, 1, 1)) % Mod;
        ans = (ans + tmp * tmp2 % Mod) % Mod;
    }
    printf("%lld\n", ans * c % Mod);
    return 0;
}

P12012 [Ynoi April Fool’s Round 2025] 牢爱

注意到有效的查询长度是很短的，原因是设长度为 $len$，当 $2^{len} > v \times len$ 时根据鸽巢原理就一定是有解的，$v$ 上限为 $1000$，所以当 $len > 13$ 时无脑 Yuno。

对于 $len \leq13$ 的部分我们可以做一个 $DP$，设 $f_{i, j}$ 表示用前 $i$ 个数能否凑出 $j$，有转移 $f_{i, j} = f_{i - 1, j} | f_{i - 1, j - a_i - 1}$。

判断能否取出两个无交子集我们只需判断是否存在 $f_{i - 1, j}$ 和 $f_{i - 1, j - a_i - 1}$ 同时为 True 即可。因为在这种情况下我们给右边的集合取一个 $a_i$，然后再把两个集合的重复部分删掉就成功了。

然后对于这个修改可以使用拓展欧拉定理：$a^b \equiv a^{b \bmod \varphi(n) + \varphi(n)} \pmod n$，这可以在 数学 - 比翼の鼠 中找到。

煮波煮波拓展欧拉定理还是太吃操作了，有没有更简单的做法。有的兄弟，有的。

不妨暴力一些直接预处理出 $g_{v, i}$ 表示 $v^3$ 再开 $i$ 次立方的结果，然后对于每次区间立方的操作我们用一个树状数组维护一下即可。

其实拓展欧拉定理的方式也要用树状数组维护。

const int N = 100010;
int n, m, v;    
int a[N], val[2010][25];
bitset<15010> state;

struct BIT {
    int tr[N]; 
    BIT() { memset(tr, 0, sizeof tr); }
    void add(int x, int k) {
        for (; x <= n; x += lowbit(x)) tr[x] += k;
    }
    int query(int x) {
        int res = 0;
        for (; x; x -= lowbit(x)) res += tr[x];
        return res;
    }
} btree;

int calc(int x, int p) {
    for (int i = 24; i >= 0; i --)
        if (p >> i & 1) x = val[x][i];
    return x + 1;
}

signed main() {
    n = read(), m = read(), v = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    for (int i = 0; i <= v; i ++) val[i][0] = i * i % v * i % v;
    for (int j = 1; j <= 24; j ++)
        for (int i = 0; i <= v; i ++) val[i][j] = val[val[i][j - 1]][j - 1];
    while (m --) {
        int op, l, r; op = read(), l = read(), r = read();
        if (op == 1) {
            if (r - l + 1 > 13) { puts("Yuno"); continue; }
            state.reset(); state.set(0, 1);
            bool f = false;
            for (int i = l; i <= r; i ++) {
                int tmp = calc(a[i], btree.query(i));
                if ((state & (state << tmp)).any()) { f = true; break; }
                state = state | (state << tmp);
            }
            if (f) puts("Yuno"); else puts("Yuki");
        } else {
            btree.add(l, 1); btree.add(r + 1, -1);
        }
    }
    return 0;   
}

P11971 「ALFR Round 7」T4 xor xor

非常好问题，使我旋转。

通过思考会发现当区间 $[l, r]$ 内 $0$ 和 $1$ 的数量都 $\geq k$ 时答案就是 $2^k - 1$，否则 $0$ 与 $1$ 一定有一个大于 $k$，另一个小于 $k$。

下文以 $0$ 多为例。

多尝试几组数据会发现一定存在最优的构造使得一个数全为 $0$，而另一个数的理想状态是要把所有的 $1$ 放到高位，但这样可能就凑不足 $k$ 位了。

虽然遭遇挫折但我们注意到这个数的形式一定是前面有一些数然后后面是一段后缀的 $0$。我们不妨二分出这段后缀 $0$ 的开始，然后就做完了。

const int N = 1000010, Mod = 1e9 + 7;
int n, q, s[N][2], pw[N], h[N][2];
char str[N];

int calc(int l, int r, int c) {
    if (l > r) return 0;
    return s[r][c] - s[l - 1][c];
}

int calc2(int l, int r, int c) {
    return (h[r][c] - h[l - 1][c] * (pw[r - l + 1] + 1) % Mod + Mod) % Mod;
}

signed main() {
    n = read(), q = read();
    scanf("%s", str + 1);
    for (int i = 1; i <= n; i ++) {
        int c = str[i] - '0';
        s[i][0] = s[i - 1][0] + 1 - c, s[i][1] = s[i - 1][1] + c;
        pw[i] = (pw[i - 1] * 2 + 1) % Mod;
        h[i][0] = (h[i - 1][0] * 2 + 1 - c) % Mod, h[i][1] = (h[i - 1][1] * 2 + c) % Mod;   
    }

    int Case = 0;
    while (q --) {
        int l = read(), r = read(), k = read(), c = 0;
        if (calc(l, r, 0) >= k) {
            if (calc(l, r, 1) >= k) { printf("%d\n", pw[k]); continue; }
            else c = 1;
        }
        int L = l, R = r;
        while (L < R) {
            int mid = L + R + 1 >> 1;
            if (calc(l, mid - 1, c) + r - mid + 1 >= k) L = mid;
            else R = mid - 1;
        }
        printf("%lld\n", (pw[calc(l, L - 1, c)] * (pw[r - L + 1] + 1) % Mod + calc2(L, r, c)) % Mod);
    }
    return 0;
}

P11955 「ZHQOI R1」覆盖

超级喵喵题，喵喵喵。

先考虑 AB 性质，考虑设 $f(k)$ 表示 $n = 2^k$ 时的答案，这里引用一张学长画的图。

对于当前的第 $k$ 层我们可以将一些 $k - 1$ 层的延续下来，使得除了收尾其余部分都是两两相连。容易得到此时新加的操作数为 $2^{k - 2} + 1$，所以有 $f(k) = f(k - 1) + 2^{k - 2} + 1$。

现在考虑如果询问区间怎么做，或者说怎么把 AB 性质进行推广。

我们不妨模拟一下 $n$ 从 $[2^{k - 1}, 2^{k} - 1]$ （记作 $[L, R]$）的线段树形态，我们会发现只有对于前 $2^{k - 2}$ 个数我们需要增加答案，所以我们可以得到 $[L, R]$ 的答案为 $f(k - 1) \times (R - L + 1) + \sum_{i = 1}^{2^{k - 2}}(R - L + 1 - i)$。后面这段是等差数列，可以直接算。

当然也有可能我们凑不满 $[L, R]$，遇到了 $[L, x](x < R)$ 的形式，此时答案为 $f(k - 1) \times (x - L + 1) + \sum_{i = 1}^{2^{k - 2}}max(x - L + 1 - i, 0)$。

所以对于所有的询问 $[l, r]$ 我们按照这个过程算一遍即可。单次复杂度为 $\operatorname{log}(r)$，总复杂度为 $q\operatorname{log}(r)$。

注意中间计算过程会爆 long long。

const int N = 110, Mod = 353442899;
int q, f[N];

void prework() {
    f[1] = 2;
    for (int i = 2; i <= 62; i ++) f[i] = (f[i - 1] + (1ll << i - 2) + 1) % Mod;
}

int calc(int x) {
    int ans = x;
    for (int i = 2; i <= 62; i ++) {
        int l = 1ll << i - 1, r = (1ll << i) - 1;
        if (l > x) break;
        if (r <= x) {
            if (i == 2) { ans += 5; continue; }
            int tmp = (__int128)(r - l + r - l + 1 - (1ll << i - 2)) * (1ll << (i - 2)) / 2 % Mod;
            ans = (ans + (__int128)f[i - 1] * (r - l + 1) % Mod) % Mod;
            ans = (ans + tmp) % Mod;
        } else {
            if (i == 2) { ans += 2; continue; }
            int d = min(x - l, (LL)(1ll << i - 2));
            int tmp = (__int128)(x - l + x - l + 1 - d) * d / 2 % Mod;
            ans = (ans + (__int128)f[i - 1] * (x - l + 1) % Mod) % Mod;
            ans = (ans + tmp) % Mod;
        }
    }
    return ans;
}

void solve() {
    int l = read(), r = read();
    printf("%lld\n", (calc(r) - calc(l - 1) + Mod) % Mod);
}

signed main() {
    prework();
    q = read();
    while (q --) solve();
    return 0;
}

P10794 『SpOI - R1』架子鼓可以站 C

首先操作完成后的直径一定要经过根，否则可以进行操作增加答案。

因此我们考虑最后的直径一定是占用根的两个子树，然后我们会发现进行两次以上的操作并无意义。并且根据直觉，进行两次操作一定不劣于一次和零次，所以我们只需要考虑进行两次操作的情况即可。

我们可以将操作分为两种情况，一种是两次操作都在同一个子树中，另一种是在两个不同的子树中。后者只需要分别求两棵子树内的直径，而前者则较为复杂。

先考虑我们要干什么。根据上文推导我们的核心目标是找到两条边集不相等的最长链，而由于我们两次操作都在同一子树中，所以我们相当于要在这个子树中断开一条边，然后将整棵树分为两部分，求最大的直径和。

这很可以树形 DP，首先求出 $f_u$ 表示 $u$ 子树内的直径，$g_u$ 为 $u$ 为根的最长链。

然后你要考虑如何求 $u$ 上方的直径，显然要换根。我们设 $k_u$ 为不包含 $u$ 为根子树的直径，考虑如何从一个 $k_u$ 转移到 $k_v$，分三种情况。

1. $k_v = k_u$
2. 考虑 $v$ 的兄弟子树的内部直径，有 $k_v = \max{f_{brother_v}}$
3. 考虑从兄弟方向和父亲方向选两条最长链，其中父亲方向只能选出一条。我们不妨从父亲方向和兄弟方向处理出前三长的链，然后找出前两条能用的就行了。

实现起来稍微有点细节。

const int N = 200010;
int T, n, res;
vector<int> G[N]; 
int g[N], f[N], h[N][3], p[N][3], k[N];
vector<int> pre[N], suf[N];

void init() {
    memset(h, 0, sizeof h); memset(p, 0, sizeof p);
    for (int i = 1; i <= n; i ++) G[i].clear(), pre[i].clear(), suf[i].clear();
}

void upd(int u, int v, int w) {
    if (w >= h[u][0]) {
        h[u][2] = h[u][1], p[u][2] = p[u][1];
        h[u][1] = h[u][0], p[u][1] = p[u][0]; 
        h[u][0] = w, p[u][0] = v;
    } else if (w >= h[u][1]) {
        h[u][2] = h[u][1], p[u][2] = p[u][1];
        h[u][1] = w, p[u][1] = v;
    } else if (w > h[u][2]) {
        h[u][2] = w, p[u][2] = v;
    }
}

void dfs(int u) {
    f[u] = g[u] = 0, k[u] = -INF;
    int m = G[u].size();
    pre[u].resize(m), suf[u].resize(m);
    for (int i = 0; i < m; i ++) {
        int v = G[u][i]; 
        dfs(v);
        f[u] = max(f[u], g[u] + g[v] + 1); f[u] = max(f[u], f[v]);
        g[u] = max(g[u], g[v] + 1);
        upd(u, v, g[v] + 1);
        pre[u][i] = f[v], suf[u][i] = f[v];
    }
    for (int i = 1; i < m; i ++) pre[u][i] = max(pre[u][i], pre[u][i - 1]);
    for (int i = m - 2; i >= 0; i --) suf[u][i] = max(suf[u][i], suf[u][i + 1]);
}

int calc(int u, int v, int cnt) {
    int s = 0, res = 0;
    for (int i = 0; i < 3; i ++) {
        if (p[u][i] == v) continue;
        s ++, res += h[u][i];
        if (s >= cnt) break;
    } 
    return res;
}

void dp(int u, int d) {
    upd(u, 0, d);
    int m = G[u].size();
    for (int i = 0; i < m; i ++) {
        int v = G[u][i];
        k[v] = k[u];
        if (i) k[v] = max(k[v], pre[u][i - 1]);     
        if (i + 1 < m) k[v] = max(k[v], suf[u][i + 1]);
        k[v] = max(k[v], calc(u, v, 2));
        dp(v, calc(u, v, 1) + 1);
    }
    res = max(res, f[u] + k[u] + 2);
}

void solve() {
    init(); n = read();
    for (int i = 1; i < n; i ++) G[read()].push_back(i + 1);
    int maxv = -INF; res = 0; 
    for (auto u : G[1]) {
        dfs(u);
        res = max(res, maxv + f[u] + 2);
        maxv = max(maxv, f[u]);
        k[u] = -INF;
        dp(u, 0);
    }
    res = max(res, maxv + 1);
    printf("%d\n", res);
}

int main() {
    T = read();
    while (T --) solve();
    return 0;
}

AGC025D - Choosing Points

先只对一个 $D$ 进行考虑，会发现此时如果把每个点和所有不能到达的点连边，则相当于选出一个独立集。

设 $D = 4^p \times q\ (q \bmod 4 \ne 0)$，则对于点 $(0, 0)$ 它所连边的点可以表示为 $(2^p \times a, 2^p \times b)$，且满足 $a^2 + b^2 = q$。此时对于 $q$ 进行讨论。

• 若 $p \bmod 4 = 1$，则此时由于 $a, b \bmod 2 = 0 \ or\ 1$，所以 $a$ 和 $b$ 一定不同奇偶。稍加思考会发现一个坐标同奇偶的 $(x, y)$ 一定会连到不同奇偶的点，两个集合独立，所以是一个二分图。
• 若 $p \bmod 4 = 2$，则此时 $a$ 和 $b$ 一定都是奇数。这时同奇偶的 $(x, y)$ 一定只会向同奇偶的点连边，同样是二分图。
• 若 $p \bmod 4 = 3$，不存在这种情况。

所以我们可以直接进行二分图染色。对于两个 $D$ 的情况就分别对两个图染色，根据这样每个点的染色最多只有四种情况，根据抽屉原理一定能找到解。

const int N = 1010;
int n, d1, d2;
int c[N][N][2], cnt[2][2];

void work(int op, int d) {
    int k = 0;
    while (d % 4 == 0) d /= 4, k ++;
    if (d % 4 == 3) return;
    k = 1 << k;
    if (d % 4 == 1) {
        rep(i, 1, n) rep(j, 1, n) c[i][j][op] = ((i - 1) / k + (j - 1) / k) & 1;
    } else {
        rep(i, 1, n) rep(j, 1, n) c[i][j][op] = ((i - 1) / k) & 1;
    }
}

int main() {
    cin >> n >> d1 >> d2; n <<= 1;
    work(0, d1); work(1, d2);
    rep(i, 1, n) rep(j, 1, n) cnt[c[i][j][0]][c[i][j][1]] ++;
    int x = -1, y = -1;
    rep(i, 0, 1) rep(j, 0, 1) if (cnt[i][j] >= n * n / 4) x = i, y = j;
    int cnt = 0;
    rep(i, 1, n) rep(j, 1, n) 
        if (c[i][j][0] == x && c[i][j][1] == y) {
            printf("%d %d\n", i - 1, j - 1), cnt ++;
            if (cnt >= n * n / 4) return 0;
        }
    if (cnt != n * n / 4) puts("D & A");
    return 0;
}

CF2094H

1900 分根号分治题，可惜我没做出来（其实主要还是没想到第二种预处理）。

对于一个询问显然直接循环做没有前途，原因是会遍历很多 useless 状态无法改变 $k$。不妨考虑如何快速从一个 useful 状态跳到另一个 useful 状态。

首先会发现 $k \leq 100000$，这代表所有询问实际上都比较小，所以它们的约数也都比较小。比较自然的有一种类似序列自动机的预处理，设 $ne_{i, j}$ 为 $i$ 及它后面 $j$ 第一次出现的位置。转移是轻松的。

这样做是 $O(nV)$ 的。我们考虑这个做法的瓶颈在于值域 $V$ 太大了，所以我们不妨根号分治。只处理值域 $\leq B$ 的情况。而对于值域 $> B$ 的情况我们可以类似筛法地把求出 $pos_x$ 表示 $x$ 在 $a$ 中的所有因数。

然后对于询问，按照最开始提到的思路做即可。需要注意的是我们每次需要在 $pos$ 中二分，所以还要加个 $\log$。整个时间复杂度是 $O(nB + \frac{nV}{B} + q\log V(\log n + B))$。$B$ 随便取个 $250$ 就跑的很快了。

const int N = 100010, B = 250;
int n, q, a[N];
int ne[N][B];
vector<int> divs[N], pos[N];

void solve() {
    n = read(), q = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    for (int i = 1; i <= B; i ++) ne[n + 1][i] = n + 1;
    for (int i = 1; i <= n; i ++) {
        if (a[i] > B) 
            for (int j = a[i]; j <= N - 10; j += a[i])
                pos[j].push_back(i);
    }
    for (int i = n; i >= 1; i --) {
        for (int j = 1; j <= B; j ++) ne[i][j] = ne[i + 1][j];
        if (a[i] <= B) ne[i][a[i]] = i;
    }
    while (q --) {
        int k = read(), l = read(), r = read();
        LL ans = 0;
        for (int p = l; ; ) {
            int R = r + 1;
            for (auto x : divs[k]) 
                if (x <= B) R = min(R, ne[p][x]);
            auto it = lower_bound(pos[k].begin(), pos[k].end(), p);
            if (it != pos[k].end()) R = min(R, *it);
            ans += 1ll * (R - p) * k;
            p = R;
            if (p > r) break;
            while (k % a[p] == 0) k /= a[p];
        }   
        printf("%lld\n", ans);
    }
    for (int i = 1; i <= n; i ++) {
        if (a[i] > B) 
            for (int j = a[i]; j <= N - 10; j += a[i])
                pos[j].clear();
    }
}

int main() {
    for (int i = 2; i <= N - 10; i ++)
        for (int j = i; j <= N - 10; j += i)
            divs[j].push_back(i);
    int T = read(); 
    while (T --) solve();
    return 0;
}

CF2093G

简单 Trie 树练习题，Rating 1900，自己做出。

看到异或和最大值显然往 Trie 树方面思考。考虑对于每一个 $i$ 在 trie 上查询 $1 \sim i - 1$ 能满足 $a_{j} \oplus a_i \geq k$ 的最靠近 $i$ 的 $j$。插入是简单的，查询时根据 $k$ 的每一位分讨，设当前 $a_i$ 这一位的值为 $u$，$k$ 为 $c$。则若 $c = 0$ 说明我们往 $u \oplus 1$ 方向走一定满足条件，那么我们应该取 $u \oplus 1$ 方向的最大 $j$；如果向 $u$ 方向走则继续递归处理。对于 $c = 1$ 则限定我们必须往 $u \oplus 1$ 方向走。

于是我们在插入的时候多维护一个 $maxv_p$ 表示 $p$ 为根子树内的最大 $j$。

const int N = 200010, M = 32;
int n, k, a[N];
int tr[N * M][2], idx = 1, ed[N * M], maxv[N * M], pre[N * M];

void insert(int num, int id) {
    int p = 1; pre[1] = -1;
    for (int i = 30; i >= 0; i --) {
        int c = num >> i & 1;
        if (!tr[p][c]) tr[p][c] = ++ idx;
        pre[tr[p][c]] = p, p = tr[p][c];  
    }
    maxv[p] = id;
    while (p != -1) {
        int q = pre[p];
        maxv[q] = max(maxv[q], maxv[p]);
        p = q;
    }
}

int query(int num, int k) {
    int p = 1, ans = 0;
    for (int i = 30; i >= 0; i --) {
        int c = k >> i & 1, u = num >> i & 1;
        if ((!c & 1)) {
            ans = max(ans, maxv[tr[p][u ^ 1]]); 
            p = tr[p][u]; 
        } else {
            p = tr[p][u ^ 1];           
        }
    }
    ans = max(ans, maxv[p]);
    return ans;
}

void init(int p) {
    maxv[p] = 0;
    if (tr[p][0]) init(tr[p][0]), tr[p][0] = 0;
    if (tr[p][1]) init(tr[p][1]), tr[p][1] = 0;
}

void solve() {
    init(1); idx = 1;
    n = read(), k = read();
    rep(i, 1, n) a[i] = read();
    int ans = INF;
    rep(i, 1, n) {
        insert(a[i], i);
        int x = query(a[i], k);
        if (!x) continue;
        ans = min(ans, i - x + 1);
    }
    printf("%d\n", ans == INF ? -1 : ans);
}

int main() {    
    int T = read();
    while (T --) solve();
    return 0;
}

CF2092D

贪心，Rating 1800。

做这个题的时候头有点晕，想了半天没发现 ABC 是一个万能的拓展，所以我们只要构造 ABC 即可，构造不出来就无解。

const int N = 310;
int T, n;
char s[N];

void solve() {
    n = read(); scanf("%s", s + 1);
    map<char, int> cnt;
    bool f = false;
    for (int i = 1; i < n; i ++) {
        if (s[i] != s[i + 1]) f = true;
        cnt[s[i]] ++;
    } cnt[s[n]] ++;
    if (!f) { puts("-1"); return; }
    if (cnt['I'] == cnt['L'] && cnt['L'] == cnt['T']) { puts("0"); return; }
    int sum = 'I' ^ 'L' ^ 'T'; vector<int> ans;
    for (int i = 2; i <= n; i ++) {
        if (s[i - 1] == s[i]) continue;
        int x = s[i - 1], z = s[i], y = sum ^ (x ^ z), p = i - 1; 
        ans.push_back(p); cnt[y] ++;
        while (cnt[x] != cnt[y] || cnt[y] != cnt[z] || cnt[x] != cnt[z]) {
            if (cnt[x] > cnt[z]) ans.push_back(p), cnt[z] ++, swap(y, z);
            else ans.push_back(++ p), cnt[x] ++, swap(x, y); 
        } 
        break;
    }
    printf("%d\n", ans.size());
    for (auto x : ans) printf("%d\n", x);
}

int main() {
    T = read();
    while (T --) solve();
    return 0;
}