CF2155C The Ancient Wizards' Capes 题解

lucasincyber · 2025-10-19 10:48:26 · 题解

题目传送门

思路

首先，有一个显然的性质：相邻两个巫师的 a 之差 \le 1。这里证明略。那我们就可以发现：

1. 如果 a_i - a_{i-1} = 1，那 i 和 i - 1 方向相同，都向左；
2. 如果 a_i - a_{i-1} = 0，那 i 和 i-1 方向相反；
3. 如果 a_{i-1} - a_i = 1，那 i 和 i - 1 方向相同，都向右。

这样就可以分类讨论第一个的方向，最后再判断是否满足条件。答案最大为 2。时间复杂度 \mathcal{O}(n)。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, mod = 676767677;

int t, n;
int a[N], cntl[N], cntr[N];
bool st[N];

bool check()
{
    for (int i = 1; i <= n + 1; i++)
        cntl[i] = cntr[i] = 0;
    for (int i = 1; i <= n; i++)
        cntl[i] = cntl[i - 1] + (st[i] == 0);
    for (int i = n; i; i--)
        cntr[i] = cntr[i + 1] + (st[i] == 1);
    for (int i = 1; i <= n; i++)
    {
        if (cntl[i - 1] + cntr[i + 1] + 1 != a[i])
        {
            return 0;
        }
    }
    return 1;
}

void solve()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i < n; i++)
    {
        if (abs(a[i] - a[i + 1]) > 1)
        {
            printf("0\n");
            return;
        }
    }
    st[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] == a[i - 1]) st[i] = !st[i - 1];
        else st[i] = st[i - 1];
    }
    int ans = 0;
    if (check()) ans++; 
    st[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] == a[i - 1]) st[i] = !st[i - 1];
        else st[i] = st[i - 1];
    }
    if (check()) ans++;
    printf("%d\n", ans);
}

int main()
{
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}