CF1270G Subset with Zero Sum(构造&思维)题解

发布于 2021-10-30  44 次阅读


题目大意

给你 $n$ 个整数 $a_1,a_2 \dots a_n$,第 $i$ 个整数 $a_i$ 满足 $i-n \le a_i \le i-1$。

找到这些整数的一个非空子集,使得它们的和为 $0$。如果有多个子集满足条件,输出任意一个。

$1 \le n \le 10^6$。

解题思路

首先我们发现这个题最特殊的地方就是 $i-n \le a_i \le i-1$ 这个条件,考虑从这里下手。

对这个式子变个形吧:$-n \le a_i-i \le 1$,也就是 $1 \le i-a_i \le n$。

还是不好看,题目的限制和 $a$ 有关,我们把 $a$ 拎出来。假设 $i-a_i=j$,那么 $a_i=i-j$ 且 $j \in [1,n]$。

题目说要让 $\sum a_i=0$,那么也就是 $\sum i-j=0$。我们发现 $i$ 和 $j$ 的范围都是 $[1,n]$,因而可以考虑两两进行抵消,这个式子的第二项去消下个式子的第一项,这样最后首尾相消,形成的就是一个环。

既然想到换了,可以进而考虑建图。我们考虑建立对每个 $i$ 建立一条 $i \to j$ 的有向边,表示编号 $i$ 的式子可以抵消一个 $i$ ,但又需要 $j$ 去抵消自己产生的影响。

每个点连一条边,那么在这样一张图中就会有 $n$ 个点和 $n$ 条边,一定会出现环。由上面的推断可知,这个环上的点的 $i$ 和 $j$ 互相消掉了,就是和为 $0$ 的点,直接拓扑排序找出环即可。

Code

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}
const int N=1000005;

struct Edge{
    int vet,nxt;
}e[N<<1];

int n,edge=0,head[N];
int a[N],deg[N];
bool vis[N];
vector <int> cir;
queue <int> Q;

void addedge(int x,int y){
    e[++edge].vet=y;
    e[edge].nxt=head[x];
    head[x]=edge;
}

void Topsort(){
    while (!Q.empty()) Q.pop();
    for (int i=1;i<=n;++i) vis[i]=false;
    for (int i=1;i<=n;++i)
        if (deg[i]==0) Q.push(i);
    while (!Q.empty()){
        int x=Q.front(); Q.pop();
        vis[x]=true;
        for (int i=head[x];i;i=e[i].nxt){
            int v=e[i].vet;
            if (--deg[v]==0) Q.push(v);
        }
    }
}

int main(){
    //freopen("CF1270G.in","r",stdin);
    //freopen("CF1270G.out","w",stdout);
    int T=read();
    while (T--){
        n=read(); edge=0;
        for (int i=1;i<=n;++i) head[i]=0,deg[i]=0;
        for (int i=1;i<=n;++i) a[i]=read();
        for (int i=1;i<=n;++i){
            int j=i-a[i];
            addedge(i,j);
            ++deg[j];
        }
        Topsort(); cir.clear();
        for (int i=1;i<=n;++i)
            if (!vis[i]) cir.push_back(i);
        // 上面我加入了所有在环上的点(可能加入了多个环),
        // 这样写不会影响正确性,反正不管多少个 0 加起来总和都是 0 。
        printf("%d\n",(signed)(cir.size()));
        for (auto it : cir) printf("%d ",it);
        printf("\n");
    }
    return 0;
}

我们无法选择过去,但我们可以改变未来。