Good Bye 2019 - Subset with Zero Sum

http://codeforces.com/contest/1270/problem/G

题意：给出一个数组 $a$，每个数满足 $i-n\leq a_i \leq i-1$。找出一个和为 0 的子集.

首先，这些数的范围就摆明了要把它们转化到 1 到 n 的范围，但并不能直接加减偏移量来转化，那样就会始终还是一个子集求和的问题。

本题重点就在于把和为0与环的首尾相接联系起来。

先说结论，把 $a[i]$ 变为 $b[i]=i-a[i]$ ，则 $b[i]$ 在 1 到 n 之间。并且有 $a[i]=i-b[i]$ ，从 i 指向 b[i] ，找到一个环，取环上点即是答案。

证明很简单，把 $a[i]$ 的和式转化为 $i-b[i]$ 的和式，最终最后一个 $b[i]$ 与开头的 $i$ 相等，中间也都抵消了，最终和为 0 .

因为 $b[i]$ 是 1 到 n 之间的，所以每个点都有且仅有一个出度，则必定存在环，且从任意点出发一直走，最终都能走到环。

本题在于，要构造出一种 $a[i]$ 的拆分方式，并以此构造有向边，将 $a-b$ 变为一条 $a$ 指向 $b$ 的有向边并跳到 $b$，这样就可以使得一条路径最终只剩下首尾两个值，达到中间值都抵消的目的。$a$ 和 $b$ 必须要是一样的性质，例如 $a[i]=2^a-2^b$，由 $a$ 指向 $b$，找环，同样可以使 $\sum a[i]=0$。只是本题没有必要构造得这么麻烦。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int T;
int n, a[maxn];
int vis[maxn];
vector<int>ans;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		ans.clear();
		fill(vis, vis + n + 1, 0);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			a[i] = i - a[i];	//a[i]变b[i]
		}
		int i;
		for (i = 1; !vis[i]; vis[i] = 1, i = a[i]);//找环入口
		int st = i;
		while (1) {	//输出环
			ans.push_back(i);
			i = a[i];
			if (i == st)break;
		}
		printf("%d\n", (int)ans.size());
		for (int u : ans)printf("%d ", u);
		printf("\n");
	}
	return 0;
}