ABC055
ABC055
[ABC055D] Menagerie
题面翻译
题目描述
Snuke,一个喜欢动物的人,建立了一个动物园。
一共有n个动物在动物园中,编号
,被按顺序围成一个圈。 有两种动物:诚实的羊只说真话,不诚实的狼只说假话。
Snuke无法区别这两种动物,他问每只动物以下问题:“你旁边的两只动物是同一种吗?”第i只动物的答案为
。如果 为“o”,则表示相同,“x”则相反。 此外,若羊回答“o”,相邻的生物则都是羊或都是狼,而“x”则相反。若狼回答“x”,相邻的生物则都是羊或狼,而“o”则相反。
Snuke想知道是否有一种可行的排列方式。如果有,输出这种排列。如果没有,则输出“-1”。
注:“S”表示羊,“W”表示狼。
题目描述
すぬけくんは動物が好きなので動物園を作りました。
この動物園では
の番号を割り振られた 匹の動物が円環状に並べられています。 番の動物は 番の動物と 番の動物と隣り合っています。また、 番の動物は 番の動物と 番の動物と隣り合っており、 番の動物は 番の動物と 番の動物と隣り合っています。 動物園には本当のことしか言わない正直者の羊と、嘘しか言わない嘘つきの狼の 2 種類の動物がいます。
すぬけくんには羊と狼の区別がつかないので、それぞれの動物に両隣の動物が同じ種類かどうかを訪ねたところ、
番目の動物は と答えました。 が o
ならば両隣の動物が同じ種類であると、x
ならば異なる種類であると番の動物が言ったことを示します。 より形式的には、羊は両隣の動物がどちらも羊あるいはどちらも狼のとき
o
と答え、そうでないときx
と答えます。 狼は両隣の動物がどちらも羊あるいはどちらも狼のときx
と答え、そうでないときo
と答えます。これらの回答結果と矛盾しないような各動物の種別の割り当てが存在するか、すぬけくんは気になっています。存在するならば一例を示し、存在しないならば
-1
を出力しなさい。输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
と矛盾しないような各動物の種類の割当てが存在しないならば -1
を出力してください。 存在するならば以下の形式で文字列を出力してください。 で示される割り当てが と矛盾しないならば正解となります。
は長さ で S
とW
のみからなる文字列が S
ならば番の動物が羊であることを、 W
ならば狼であることを示す样例 #1
样例输入 #1
6
ooxoox样例输出 #1
SSSWWS样例 #2
样例输入 #2
3
oox样例输出 #2
-1样例 #3
样例输入 #3
10
oxooxoxoox样例输出 #3
SSWWSSSWWS提示
制約
は o
とx
のみからなる長さの文字列 Sample Explanation 1
例えば
番の動物がそれぞれ羊、羊、羊、狼、狼、羊であるとき発言と矛盾しません。その他、狼、羊、狼、羊、狼、狼であるようなときも矛盾しません。 両隣が同じ種類の動物のとき羊は 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 找规律得:如果设
,则第三个动物种类为 ,可以得到递推式: 推出所有动物的种类之后,还要进行验证,第一、二个动物再往前两个在环的情况下是否一样,需要特判。
|