CF1270G Subset with Zero Sum

标签：Subset le limits int sum Sum Zero CF1270G loop

G. Subset with Zero Sum

很妙。
一开始冲着背包去想的，显然不行。
考虑他条件给的这个 \(i − n \le a_i \le i − 1\)
化简一下得到

\[1 \le i - a_i \le n \]

题目要去求

\[\sum \limits_{i \in S} a_i = 0 \]

把所给信息往这个式子上靠。
得到

\[\sum \limits_{i \in S} i = \sum \limits_{i \in S} i - a_i \]

考虑以下性质。
如果一个图中存在一个环，那么显然有

\[\sum \limits_{i \in loop} i = \sum \limits_{i \in loop} to_i \]

其中 \(to_i\) 为 \(i\) 指向的点。
回到题目，不妨建这么一张图，\(i\) 向 \(i - a_i\) 连边。
那么如果有环
则

\[\sum \limits_{i \in loop} i = \sum \limits_{i \in loop} i - a_i \]

\[\sum \limits_{i \in loop} a_i = 0 \]

因此，建图，找环。

void solve() {
	int n;
	cin >> n;
	vector<int> to(n + 1);
	for(int i = 1, x; i <= n; ++ i) {
		cin >> x;
		to[i] = i - x;
	}
	vector<bool> vis(n + 1, 0);
	int x = 1;
	while(!vis[x]) vis[x] = true, x = to[x];
	vector<int> ans;
	do {
		ans.push_back(x);
		x = to[x];
	} while(x != ans[0]);
	cout << ans.size() << '\n';
	for(int y : ans) cout << y << ' ';
	cout << '\n';
}

标签：Subset,le,limits,int,sum,Sum,Zero,CF1270G,loop
From： https://www.cnblogs.com/Luxinze/p/17948011