2022 年牛客多校加赛场 J 题题解

J Jellyfish and its dream

题意：给定长度为 $nn$ 的环形序列 $a_0,a_1,\cdots ,a_{n-1}a\_0,a\_1,\backslash cdots,a\_\{n-1\}$，仅由 $0,1,20,1,2$ 构成。若 $a_i+1\equiv a_{i\mathrm{m}\mathrm{o}\mathrm{d}n+1}(\mathrm{m}\mathrm{o}\mathrm{d}3)a\_i+1\; \backslash equiv\; a\_\{i\; \backslash bmod\; n+1\}\; \backslash pmod\; 3$，则令 $a_i\leftarrow (a_i+1)\mathrm{m}\mathrm{o}\mathrm{d}3a\_i\; \backslash leftarrow\; (a\_i+1)\; \backslash bmod\; 3$。问能否经过若干次操作使得 $a_0=a_1=\cdots =a_{n-1}a\_0=a\_1=\backslash cdots=a\_\{n-1\}$。$n\le 2\times 10^{5}n\; \backslash leq\; 2\backslash times\; 10^5$。

解法：相邻加一考虑差分。设 $bb$ 数组为 $aa$ 的差分数组，最终的目标是需要让 $b_i=0b\_i=0$。则对于 $bb$ 数组中出现了 $(2,1)(2,1)$ 的情况（$b_i=2,b_{i+1}=1b\_i=2,b\_\{i+1\}=1$），则必然可以经过该操作使得 $b_i=b_{i+1}=0b\_i=b\_\{i+1\}=0$，$(1,1)(1,1)$ 变成 $(2,0)(2,0)$，而 $(0,1)(0,1)$ 变成 $(1,0)(1,0)$。而通过 $(0,1)\to (1,0)(0,1)\; \backslash to\; (1,0)$ 可以将 $11$ 平移，最终为了要消掉所有的 $22$，只能通过 $(2,1)\to (0,0)(2,1)\; \backslash to\; (0,0)$ 来完成。因而 $22$ 的数目不可以多于 $11$ 的数目。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        vector<int> a(n);
        for (int i = 0; i < n;i++)
            scanf("%d", &a[i]);
        int cnt = 0;
        for (int i = 0; i < n;i++)
            if (a[i] < a[(i + 1) % n])
                cnt++;
            else if (a[i] > a[(i + 1) % n])
                cnt--;
        if (cnt < 0)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}