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

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

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

对于环可以得到：
$i_1 - a_1 = i_2$i1​−a1​=i2​
$i_2 - a_2 = i_3$i2​−a2​=i3​
$i_3 - a_3 = i_4$i3​−a3​=i4​
…
$i_n - a_n = i_1$in​−an​=i1​

求和得到 $a_1 + a_2 + ... + a_n = 0$a1​+a2​+...+an​=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" : " ");
		}
	}
}