[AGC068C] Ball Redistribution

Genius_Star · 2026-09-05 15:20:29 · 题解

或许更好的阅读体验。

感觉很多题解直接讲结论，怎么想到的一概不说？？？这里给一个有思维链的做法。

思路：

只给了最终状态而判定初始状态，显然不能正着做，考虑倒着还原。

你发现这个将球 x_j 放入盒子 x_{j \bmod k + 1} 中，如果建立 i \to pos_i（pos_i 是 i 所在的盒子），那么一次操作就相当于创建了一个环，而我们这个图是内向基环树森林。

具体的，倒着从 n 开始做，设当且到 i：

• 如果 i 在某个环内：那么说明 i 所在环上的点恰好就是这次操作的球，因为如果不是的话，是之前某个位置操作的，那么到 i 这里的球 x 在操作一次后就会跑到 x 那去了，而不是还在 i 这；所以会把 i 所在的环全部断掉，然后环上点增加到 i 的边，表示之前这些球都在 i 内。

• 否则 i 不在任何一个环内，那么：

  • 否则 i 盒子之前有球，经过这次操作后形成了一个环，而这个环我们不知道具体是哪个，所以任何一个都行；所以回退的话是选择一个环，然后把这个环断掉，然后环上点增加到 i 的边。

• 显然，如果此时存在一个点 j 指向 i 且 j 不在任何一个环中就无解，因为操作了之后一定是环。

于是我们要尽可能避免最后那种情况，即操作到 i 时尽可能不存在 j 不在环中指向它；对于最后状态的图，先找到 i 所在的点，其有一些儿子 j \in son_i，我们想要把 j \to i 的边尽可能多的断掉，最多剩一条，且那一条最后必须在换上。

那么显然只有 j 和 i 一起在环上的时候才可以把 j \to i 的边断掉，因为可以用之前一次点的断环操作。

怎么才能保证 j 和 i 在一个环上呢，注意到，如果一次任意断环操作，是断的和 i 不在一个连通块内的环的话，会把那个环彻底断掉且连向 i，无法创造一个新的环，也就无法使得某两个特定点在一个连通块内。

否则，如果断的是 i 所在连通块的环的话，你会发现，设 i 一路跳父亲跳到环上的点是 p，那么会新增一个 i \to p \to i 的环；于是考虑能否使用断所在连通块的环创造一些边在环上。

而对于在环上的断环操作，你会形成一个 i \to i 的自环，不会影响环在当前连通块的存在性，所以没问题。

具体的，想要使得 j \to i 在环上，那么必须存在一个 j 子树内 k > i（比 i 先操作），此时会新增 k \to j \to i \to p \to k 的环（p 定义同上，即在环上的点），然后之后再操作的话就会把 j \to i 的边断掉了。

于是对于任何一个点 i，和它的每个儿子 j，子树内都必须存在至少一个 k > i 先操作把 j \to i 的边断掉，或者说最后一次操作后 j \to i 在一个环上，然后马上操作 i，此时也是合法的。

于是我们得到了一个充要条件，定义 mx_v 表示 v 子树编号最大点，对于每个点 u，它的所有儿子 v 都要满足 mx_v > u。

直接 O(n) 检查即可。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) (x) & (-(x))
#define popcnt(x) __builtin_popcount(x)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2.5e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int T, n;
int nxt[N], mx[N];
int vis[N], cyc[N];
vector<int> E[N];
inline void dfs(int u){
    vis[u] = 1;
    mx[u] = u;
    for(auto v : E[u]){
        dfs(v);
        mx[u] = max(mx[u], mx[v]);
    }
}
inline void solve(){
    n = read();
    for(int i = 1; i <= n; ++i){
        vis[i] = cyc[i] = 0;
        E[i].clear();
        nxt[i] = read();
    }
    for(int i = 1; i <= n; ++i){
        if(vis[i])
          continue;
        int x = i;
        while(!vis[x]){
            vis[x] = i;
            x = nxt[x];
        }
        if(vis[x] != i)
          continue;
        cyc[x] = 1;
        int y = nxt[x];
        while(y != x){
            cyc[y] = 1;
            y = nxt[y];
        }
    }
    for(int i = 1; i <= n; ++i){
        vis[i] = 0;
        if(cyc[i])
          continue;
        E[nxt[i]].push_back(i);
    }
    for(int i = 1; i <= n; ++i){
        if(vis[i])
          continue;
        dfs(i);
    }
    for(int u = 1; u <= n; ++u){
        for(auto v : E[u]){
            if(mx[v] < u){
                puts("No");
                return ;
            }
        }
    }
    puts("Yes");
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}