Codeforces Global Round 15 - D. Array Differentiation

题意

给定一个长度为$n$的序列$\lbrace a_n \rbrace$,问是否存在长度为$n$的序列$\lbrace b_n\rbrace $,使得序列${a_n}$中的每一个数$a_i$,都存在一组$(j, k)$($j,k$可以相等),$b_j-b_k=a_i$,若有则输出$YES$,否则输出$NO$。

思路

本题很妙,题解是将序列转化到图的问题去理解。

我们将$a_i=b_j-b_k$​,看作从$b_j$​连一条有向边到$b_k$​​。

我们暂时忽略边的方向性,可以发现,当某个连边方式合法时,相当于存在一张$n$​​个点$n$​​条边的连通图,且其中一定有至少一个环

我们可以设这个环中有$m$​​个顶点,顶点标号依次为$v_1,v_2,\dots,v_m$​​​​。

由于首尾相接,环的顶点应该满足这个条件:

如果考虑方向性:

  • $b_i - b_j = a_i, \text{an edge from (i) to (j)}$

  • $b_i - b_j = -a_i, \text{an edge from (j) to (i)}$​

由上,我们通过给$a_i$​​​分配正负值(等效于在$b$​​中对$b_j,b_k$​​​连边)或分配$0$​​​(环内不包括这个点),来实现连边和判断是否存在一个环,如下所示:

到这里,一个直接的办法是,由于$n$​​非常小,我们可以利用$3$​​进制对环的状态进行压缩。

首先,假设存在一个环,且大小为$m$。

然后,对于环内的点,我们可以设为$1,2,3,\dots,m$​,如下构造:

  • $b_1 = 0$
  • $b_2 = b_1 - s_1 * a_1$​
  • $b_3 = b_2 - s_2 * a_2$
  • $…$
  • $b_m = b_{m - 1} - s_{m - 1} * a_{m-1}$​

其中,$s_i \in \lbrace -1, 1\rbrace$​​​​​​,代表边的方向性。

对于$a_i = \lbrace 1,2,3,6\rbrace $的情况,$s_i = \lbrace 1,1,1,-1\rbrace $是其中一个方案:

image-20210914165537239

由此,枚举每一种可能的情况,判断是否有环存在即可,时间复杂度$O(n3^n)$​。

本题也可使用背包实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
//#define int long long
using namespace std;

clock_t START_TIME, END_TIME;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
std::cout << head << ", ";
Print(rail...);
}

int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}

int t, n, a[maxn];
signed main(void)
{
t = read();
//START_TIME = clock();
while(t--)
{
n = read();
for(int i = 1; i <= n; i++) a[i] = read();
int mask = 1, gs = -1;
for(int i = 1; i <= n; i++) mask *= 3;
for(int i = 1; i < mask; i++)
{
int ms = i, sum = 0;
for(int k = 1; k <= n; k++)
{
int flag = ms % 3; ms /= 3;
if(flag == 1) sum += a[k] * 1;
if(flag == 2) sum += a[k] * (-1);
}
if(sum == 0){
gs = 1;
printf("YES\n");
break;
}
}
if(gs == -1) printf("NO\n");
}
//END_TIME = clock();
//printf("%.5lf ms\n", (double)(END_TIME - START_TIME) / CLOCKS_PER_SEC * 1000);
return 0;
}

如果你觉得还不错,就请咕咕的作者喝杯咖啡吧QAQ