Codeforces Global Round 15 D. Array Differentiation
题意：给定一个序列 \(a_1,a_2,...,a_n\)? ，问是否存在一个序列 \(b_1, b_2, ..., b_n\)? ，使得对任意 \(a_i\)? ，都有 \(b_j - b_k = a_i \ (1 \leq j、k \leq n)\)? 。
分析：对于任意一个 \(a_i\)? ，都存在一个关系，把 \(b_i\)? 看作点权， \(a_i\)? 看作边权，如果 \(b_j - b_k = a_i\)? ，则从 \(j\)? 向 \(k\)??? 连一条边。则问题变成了一张 \(G(n, n)\)?? 图，那么图中一定存在一个环(弱连通图上)，由于关系是相减的，如果存在序列 \(b\)? ，那么环上所有边权之和在同方向下一定为 \(0\)??? (枚举方向，也就是正负号，枚举箭头方向保持一致)，只要存在这么一条环即可。
Code
// cur表示枚举到了哪个点，sum表示环上贡献总和，is_loop表示目前是否形成环
bool check (int cur, int sum, int is_loop) // 可能存在空环
{
if (cur > n)
return sum == 0 && is_loop; // 贡献总和为0且形成了环
bool res = false;
res |= check(cur+1, sum, is_loop); // 环上不包含这个点
res |= check(cur+1, sum + a[cur], 1); // 环上包含，且该值在环上的贡献为正数
res |= check(cur+1, sum - a[cur], 1); // 环上包含，且该值在环上的贡献为正数
return res;
}
void solve ()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
puts(check(1, 0, 0) ? "YES" : "NO");
}