“蔚来杯“2022牛客暑期多校训练营（加赛）J题题解

J-Jellyfish and its dream

题目大意：
一个序列只包含{0,1,2}三种数字，如果(a_i +1)%3 ==a_(i+1)%n ，就可以将a_i变成(a_i +1)%3。求一个序列经过若干次操作后所有数字能否相同。

思路：
一般序列的这种加法变换都是取差分。本题也是如此。
令差分序列b_i = (a_(i+1)%n - a_i +3)%3
对于(2，1)这种差分，比如2 1 2，可以通过改变中间的数字使其变成(0，0)
对于(1，1)这种差分，比如0 1 2，可以通过改变中间的数字使其变成(2，0)
对于(0，1)这种差分，比如0 0 1，可以通过改变中间的数字使其变成(1，0)
对于(1，0)这种差分，比如0 1 1，可以通过改变第一个数字使其变成(0，0)

因此通过(0，1)到(1，0)的差分变化可以移动差分序列中的1，使1移动到2右侧，从而出现（0，0）的差分。当差分序列全部变成0时就成功将所有的数字都变成一样的了。

容易得到当差分序列中1的个数不是3的倍数时，一定会有2或0出现。当1的个数是3的倍数时，可以通过(1，1)到
(2，0)的变化构造出2和0。

因此只要差分序列中1的个数不少于2即可。

AC代码：

#include 
const int N = 1e6 + 5;
using namespace std;

int n, cnt[3], a[N];

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cnt[1] = cnt[2] = 0;
    for (int i = 0; i < n; i++)
        cnt[(a[(i + 1) % n] - a[i] + 3) % 3]++;
    if (cnt[1] >= cnt[2])
        cout << "YES\n";
    else
        cout << "NO\n";
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    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