洛谷题解 | AT_arc069_b [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
2

样例输出 #1

SSSWWS
1

样例 #2

样例输入 #2

3
oox
1
2

样例输出 #2

-1
1

样例 #3

样例输入 #3

10
oxooxoxoox
1
2

样例输出 #3

SSWWSSSWWS
1

提示

制約

• $ 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 を出力してください。

题目思路

解法一

首先读取输入，然后通过循环遍历输入的字符串，将每个字符代表的动物按其类型放入数组中。

接着，再创建一个数组，用于存储每只动物的回答。通过一个四重循环来模拟每只动物的回答过程。

如果找到了满足条件的排列，就通过遍历数组并将其转换为字符串输出。

如果没有找到满足条件的排列，输出 $\text{-1}$。

解法二

首先读取输入，然后开始遍历所有可能的动物园排列。如果某只动物的回答和它旁边的两只动物的回答相同，则这只动物是羊；如果不同，则这只动物是狼。

接着，判断动物园的排列是否满足题目中的条件。

如果某一种排列通过了所有的判断，则输出这种排列。如果没有找到满足条件的排列，则输出 $\text{-1}$。

AC 代码

解法一

#include
using namespace std;
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
typedef long long lint;
typedef complex <double> P;
typedef pair <int,int> pint;
int out[114514],pat[114514];
string s;
string sw="SW";
int n;
int main()
{
	cin >> n >> s;
	rep(i,n){
		if(s[i] == 'o') pat[i] = 0;else pat[i] = 1;
	}
	pat[n] = pat[0];
	pat[n + 1] = pat[1];
	rep(i,4){
		out[0] = i / 2;out[1] = i % 2;
		REP(j,1,n+1){
			out[j + 1] = (pat[j] + out[j] + out[j - 1]) % 2;
		}
		if(out[0] == out[n] && out[1] == out[n + 1]){
			string ret = "";
			rep(j,n) ret += sw[out[j]];
			cout << ret << endl;
			return 0;
		}
	}
	cout << -1 << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

解法二

#include 
using namespace std;
typedef signed long long ll;
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
int N;
string S;
string T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin >> N >> S;
	FOR(i,4) {
		if(i == 0) T = "SS";
		if(i == 1) T = "SW";
		if(i == 2) T = "WS";
		if(i == 3) T = "WW";
		for(j = 1;j < N - 1;j++) {
			if((T[j] == 'S') ^ (S[j] == 'o')){
				T.push_back('S' + 'W' - T[j - 1]);
			}
			else {
				T.push_back(T[j - 1]);
			}
		}
		
		if((T[N - 1] == 'S') ^ (S[N - 1] == 'o')){
			if(T[N - 2] == T[0]) continue;
		}
		else {
			if(T[N - 2] != T[0]) continue;
		}
		if((T[0] == 'S') ^ (S[0] == 'o')){
			if(T[N - 1] == T[1]) continue;
		}
		else {
			if(T[N-1] != T[1]) continue;
		}
		cout << T << endl;
		return;
		
	}
	cout << -1 << endl;
	
}
int main(int argc,char** argv){
	string s;
   int i;
	if(argc == 1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s += argv[i + 1],s += '\n';
	FOR(i,s.size()) ungetc(s[s.size() - 1 - i],stdin);
	solve();
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

---

创作不易，白嫖不好，各位的支持和认可，就是我创作的最大动力，如果喜欢我的文章，给个关注吧！

冰焰狼 | 文

如果本篇博客有任何错误，请批评指教，不胜感激 ！