AT_arc069_b [ABC055D] Menagerie 题解

small_john · 2023-04-24 19:30:12 · 题解

分析

其实很简单。

我们只要知道了前两个动物的种类，就可以推出所有动物的种类。那么思路就是，枚举前两个动物的种类即可。

但如果每种情况都讨论的话未免太复杂，所以我们考虑一种简化方法。

找规律得，如果设 S 为 1，W 为 0，o 为 1，x 为 0，则第三个动物种类为 (a_2+b_1+b_2)\bmod 2，所以递推式为 b_i = (b_{i-1}+b_{i-2}+a_{i-1})\bmod 2。

推出所有动物的种类之后，还要进行验证，前两个动物往前两个在环的情况下与其他的不一样，需要特判。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n;
bool a[N],b[N];
char in[N];
bool ok(int x,int y)
{
    b[1] = x,b[2] = y;
    for(int i = 3;i<=n;i++)
        b[i] = (a[i-1]+b[i-1]+b[i-2])%2;
    return b[1]==(a[n]+b[n]+b[n-1])%2&&b[2]==(a[1]+b[1]+b[n])%2;
}
void print()
{
    for(int i = 1;i<=n;i++)
        if(b[i]) cout<<'S';
        else cout<<'W';
}
signed main()
{
    cin>>n>>(in+1);
    for(int i = 1;i<=n;i++)
        a[i] = (in[i]=='o');
    for(int i = 0;i<=1;i++)
        for(int j = 0;j<=1;j++)
            if(ok(i,j))
                return print(),0;
    cout<<-1;
    return 0;
}