牛客多校11 - Jellyfish and its dream（差分，思维）

https://ac.nowcoder.com/acm/contest/38727/J

题意
给定一个长度为 n 的环形数组 a[]，每个位置 ai = {0, 1, 2}。
如果对于 $\left(a_i+1\right)\mathrm{mod}3=a_{(i+1)\mathrm{mod}n}$, 就可以令 $a_i\leftarrow$ $\left(a_i+1\right)\mathrm{mod}3$，也就是如果后面位置 (%n) 比当前位置大1 (%3)，那么当前位置就可以+1。
问，是否可以经过若干次上述操作，使得所有数相同？

思路
让所有数都相同，也就是让差分都变为0。
一共有 3 个数，分别考虑每种变化：
$a_i=0,a_{i+1}=1$，变为 $a_i=1,a_{i+1}=1$;
简记为：(0, 1) -> (1, 1);
(1, 2) -> (2, 2);
(2, 0) -> (0, 0);

对应的差分变化为：
(0, 1) -> (1, 0);
(1, 1) -> (2, 0);
(2, -2) -> (0, 0); 不考虑取模的话，相当于 (2, 1) -> (0, 0)；

那么由变化1可以发现，1 的位置可以直接移动。
而两个 1 可以构成一个 2，两个 2 和一个 1 可以变成两个 0。

所以要先消去所有的 2，再把剩余的 2/3 个 1 都变成 2，然后用其余的 1/3 个 1 和其配对，都变成 0。

所以 1 的个数要大于等于 2 的个数，然后减去 2 的个数之后保证是 3 的倍数（但是不明白为什么不用考虑后者也是对的？

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 2000010, mod = 1e9+7;
int T, n, m;
int a[N], d[N];

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> n;
		for(int i=0;i<n;i++) cin >> a[i];
		
		for(int i=0;i<n;i++) d[i] = (a[i] - a[(i-1+n)%n] + 3) % 3;
		
		int cnt1 = 0, cnt2 = 0;
		for(int i=0;i<n;i++)
		{
			if(d[i] == 1) cnt1 ++;
			else if(d[i] == 2) cnt2 ++;
		}
		if(cnt1 < cnt2) cout << "No\n";
		else{
			cnt1 -= cnt2;
			if(cnt1 % 3 == 0) cout << "Yes\n";
			else cout << "No\n";
		}
	}
	
	return 0;
}
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

经验
把所有数都变成相同的，要知道考虑差分。