Codeforce 1270 G. Subset with Zero Sum（数学 + 建图构造 + 思维）

题目大意：有一个数组a，满足 $i - n \leq a_i \leq i - 1$，求该序列的一个子集使得这个子集和为0。

转变一下式子得到： $1 \leq i - a_i \leq n$，对每个 $a_i$，建一条从 $i$ 到 $i - a_i$ 的边，由于每个点都有出度，整个图必定有环。

对于环可以得到：
$i_1 - a_1 = i_2$
$i_2 - a_2 = i_3$
$i_3 - a_3 = i_4$
…
$i_n - a_n = i_1$

求和得到 $a_1 + a_2 + ... + a_n = 0$，因此环上所有点即是解，在这个限制条件下必定有解

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int t,n,a[maxn],to[maxn],vis[maxn],sta[maxn],top;
vector<int> g;
int main() {scanf("%d",&t);while(t--) {scanf("%d",&n);g.clear();for(int i = 1; i <= n; i++)vis[i] = 0,to[i] = 0;for(int i = 1; i <= n; i++) {scanf("%d",&a[i]);a[i] = i - a[i];to[i] = a[i];}int p = 1,top = 0;while(!vis[p]) {sta[++top] = p;vis[p] = 1;p = to[p];}do{g.push_back(sta[top]);}while(sta[top--] != p);printf("%d\n",g.size());for(int i = 0; i < g.size(); i++) {printf("%d%s",g[i],i == g.size() - 1 ? "\n" : " ");}}
}