ABC055

[ABC055D] Menagerie

题面翻译

题目描述

Snuke，一个喜欢动物的人，建立了一个动物园。

一共有n个动物在动物园中，编号 \(1-n\) ，被按顺序围成一个圈。

有两种动物：诚实的羊只说真话，不诚实的狼只说假话。

Snuke无法区别这两种动物，他问每只动物以下问题：“你旁边的两只动物是同一种吗？”第i只动物的答案为 \(Si\) 。如果 \(Si\) 为“o”，则表示相同，“x”则相反。

此外，若羊回答“o”，相邻的生物则都是羊或都是狼，而“x”则相反。若狼回答“x”，相邻的生物则都是羊或狼，而“o”则相反。

Snuke想知道是否有一种可行的排列方式。如果有，输出这种排列。如果没有，则输出“-1”。

注：“S”表示羊，“W”表示狼。

题目描述

すぬけくんは動物が好きなので動物園を作りました。

この動物園では $ 1,2,3, ..., N $ の番号を割り振られた $ N $ 匹の動物が円環状に並べられています。 $ i (2≦i≦N-1) $ 番の動物は $ i-1 $ 番の動物と $ i+1 $ 番の動物と隣り合っています。また、$ 1 $ 番の動物は $ N $ 番の動物と $ 2 $ 番の動物と隣り合っており、$ N $ 番の動物は $ N-1 $ 番の動物と $ 1 $ 番の動物と隣り合っています。

動物園には本当のことしか言わない正直者の羊と、嘘しか言わない嘘つきの狼の 2 種類の動物がいます。

すぬけくんには羊と狼の区別がつかないので、それぞれの動物に両隣の動物が同じ種類かどうかを訪ねたところ、$ i $ 番目の動物は $ s_i $ と答えました。$ s_i $ が o ならば両隣の動物が同じ種類であると、x ならば異なる種類であると $ i $ 番の動物が言ったことを示します。

より形式的には、羊は両隣の動物がどちらも羊あるいはどちらも狼のとき o と答え、そうでないとき x と答えます。 狼は両隣の動物がどちらも羊あるいはどちらも狼のとき x と答え、そうでないとき o と答えます。

これらの回答結果と矛盾しないような各動物の種別の割り当てが存在するか、すぬけくんは気になっています。存在するならば一例を示し、存在しないならば -1 を出力しなさい。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ s $

输出格式

$ s $ と矛盾しないような各動物の種類の割当てが存在しないならば -1 を出力してください。 存在するならば以下の形式で文字列 $ t $ を出力してください。 $ t $ で示される割り当てが $ s $ と矛盾しないならば正解となります。

• $ t $ は長さ $ N $ で S と W のみからなる文字列
• $ t_i $ が S ならば $ i $ 番の動物が羊であることを、W ならば狼であることを示す

样例 #1

样例输入 #1

6
ooxoox

样例输出 #1

SSSWWS

样例 #2

样例输入 #2

3
oox

样例输出 #2

-1

样例 #3

样例输入 #3

10
oxooxoxoox

样例输出 #3

SSWWSSSWWS

提示

制約

• $ 3 ≦ N ≦ 10^{5} $
• $ s $ は o と x のみからなる長さ $ N $ の文字列

Sample Explanation 1

例えば $ 1,2,3,4,5,6 $ 番の動物がそれぞれ羊、羊、羊、狼、狼、羊であるとき発言と矛盾しません。その他、狼、羊、狼、羊、狼、狼であるようなときも矛盾しません。 両隣が同じ種類の動物のとき羊は o と発言し、狼は x と発言すること、 両隣が異なる種類の動物のとき羊は x と発言し、狼は o と発言することに注意してください。 

Sample Explanation 2

存在しない場合は -1 を出力してください。

思路

思路转载自：[AT_arc069_b ABC055D] Menagerie 题解 - 洛谷专栏 (luogu.com.cn)

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

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

前两个动物的种类	第 22 个动物的回答	第 33 个动物的种类
SS	o	S
SS	x	W
SW	o	W
SW	x	S
WS	o	W
WS	x	S
WW	o	S
WW	x	W

找规律得：如果设\(S=1,W=0,o=1，x=0\)，则第三个动物种类为\((a_2+b_1+b_2)mod\ 2\)，可以得到递推式： \[ b_i=(b_{i-1}+b_{i-2}+a_{i-1})mod\ 2 \] 推出所有动物的种类之后，还要进行验证，第一、二个动物再往前两个在环的情况下是否一样，需要特判。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e11;
int n;
string s;
bool a[MAXN],b[MAXN];
//b数组代表的是动物种类，a数组代表的是第i个动物说的话是真是假
//判断函数
bool check(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;
    }
    //这里需要特判推导出来的1、2是否与实际一致
    if((b[1]==(a[n]+b[n]+b[n-1])%2)&&(b[2]==(a[1]+b[1]+b[n])%2)){
        return true;
    }
    return false;
}
//输出函数
void print(){
    for(int i=1;i<=n;i++){
        if(b[i])cout<<"S";
        else cout<<"W";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>s;
    s=" "+s;
    //进行初始化，如果为o，初始化为1
    for(int i=1;i<=n;i++){
        a[i]=(s[i]=='o');
    }
    //枚举1、2号动物所有可能情况
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            if(check(i,j)){
                print();
                return 0;
            }
        }
    }
    cout<<-1;
    return 0;
}