CF1270G Subset with Zero Sum

巧妙的思维、构造题

题意：

给出一个长度为$n$的序列$a$，其中$a_i\in[i-n,i-1]$

现让你从中选出几个数，使得他们的和为0

题解：

发现$a_i$的范围很特殊，于是我们可以考虑把它拆成$i$和$i-a_i$两部分，其中$i$是它的正贡献，$i-a_i$是它的负贡献

构造方法是这样的：将$a_i$看作一个节点，从任意一个点出发，贪心的找可以直接用正贡献抵消它的负贡献的点，再依次往下找点，直到回到了一个已经走过的点

抽象的，可以把这$n$个点看作一张有向图（基环树），问题就变成了在上面找个简单环，$O(n)$即可解决

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e6+5;
int n,a[N];
bool v[N];

void doit(){
    vector<int> ans;
    read(n);
    for(int i=1;i<=n;i++){
        a[i]=i-read(a[i]);
        v[i]=0;
    }
    int aim=1;
    for(;!v[aim];aim=a[aim]) v[aim]=1;
    ans.push_back(aim);
    for(int i=a[aim];i^aim;i=a[i]) ans.push_back(i);
    write(ans.size());puts("");
    for(int i=0;i<ans.size();i++) write(ans[i]),putchar(' ');puts("");
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}