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");
}