CF1383D 题解

题意

给定一个长度为 $n$ 的序列 $a$，选出 $a$ 中的若干个元素使得和为零。

数据范围 ：$1 \le n \le 10^6$，$i - n \le a_i \le 1 - i$

题解

构造题，$i - n \le a_i \le 1 - i$，即 $1 \le i - a_i \le n$ 。我们让 $i$ 向 $i - a_i$ 连边，这样显然形成环的时候和就是 $0$，时间复杂度 $\Theta(n)$。

CODE

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

inline int read();
#define N 1000010
#define pb push_back

int n, a[N], vis[N];
vector<int> res;

int main() {
	for (int T = read(); T --; ) {
		n = read();
		for (int i = 1; i <= n; i ++) {
			a[i] = i - read(), vis[i] = 0;
		}

		int x = 1;
		while (!vis[x]) vis[x] = 1, x = a[x];
		res.clear(), res.pb(x), x = a[x];
		while (x != res[0]) res.pb(x), x = a[x];

		printf("%d\n", res.size());
		for (auto i : res) {
			printf("%d ", i);
		}
		puts("");
	}
	return 0;
}

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}