一道很有意思的模拟题啊。
思路很重要。
首先，我们只要知道连续两只动物的身份，就可以根据 \(s\) 推出所有动物的身份。
不妨假设我们知道第一只和第二只动物的身份，一共有几种情况呢？
用 \(1\) 代表羊，\(0\) 代表狼。
那么，共有 \(2^2=4\) 种情况，分别为：
00 01 10 11
然后我们分别推出每个动物的身份，再判断是否合法即可。
接下来讲实现。
为了方便，用 \(pair\) 数组 \(nxt\) 记录该坐标紧邻的两个位置。
从第三个位置起，每个位置可根据前两位推出。
分类讨论一下：
\(1°\) 若前一位是羊，即 ans[i - 1] == 1。
-
若
s[i - 1] == 'o'，说明第 \(i - 1\) 位紧邻的两位身份相同，则ans[i] == ans[i - 2] -
否则，紧邻的两位身份不同，则
ans[i] = 1 - ans[i - 2]，以此即可。
\(2°\) 否则前一位是狼，即 ans[i - 1] == 0。
-
若
s[i - 1] == 'x'，狼说谎话，说明第 \(i - 1\) 位紧邻的两位身份相同，则ans[i] == ans[i - 2] -
否则，身份不同，则
ans[i] = 1 - ans[i - 2]。
这样就构造完了。
最后，怎样判断是否合法呢？
此时，\(nxt\) 数组便起到作用了。
若当前位为羊，\(s_i\) 为 '\(o\)' 则相邻两位相同，否则不同。
若当前位为狼，\(s_i\) 为 '\(x\)' 则相邻两位相同，否则不同。
判断即可。
合法就输出。
Code:
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
using namespace std;
const int N = 1e5 + 10;
int n; string s;
pii nxt[N];
int ans[N];
// 1 羊 2 狼
inline bool check() {
for (int i = 1; i <= n; ++i) {
int x = nxt[i].first;
int y = nxt[i].second;
if (ans[i]) {
if (s[i] == 'o') {
if (ans[x] != ans[y])
return false;
} else {
if (ans[x] == ans[y])
return false;
}
} else {
if (s[i] == 'x') {
if (ans[x] != ans[y])
return false;
} else {
if (ans[x] == ans[y])
return false;
}
}
}
return true;
}
inline bool solve(int a, int b) {
ans[1] = a; ans[2] = b;
if (ans[1] == 1) {
if (s[1] == 'o') ans[n] = ans[2];
else ans[n] = 1 - ans[2];
} else {
if (s[1] == 'o') ans[n] = 1 - ans[2];
else ans[n] = 1 - ans[2];
}
for (int i = 3; i < n; ++i) {
if (ans[i - 1] == 1) {
if (s[i - 1] == 'o') ans[i] = ans[i - 2];
else ans[i] = 1 - ans[i - 2];
} else {
if (s[i - 1] == 'x') ans[i] = ans[i - 2];
else ans[i] = 1 - ans[i - 2];
}
}
if (check()) return true;
else return false;
}
inline void write() {
for (int i = 1; i <= n; ++i) {
if (ans[i]) printf("S");
else printf("W");
}
}
int main() {
scanf("%d", &n);
cin >> s;
s = " " + s;
for (int i = 1; i <= n; ++i) {
if (s[i] == 'o') ans[i] = 1;
else ans[i] = 0;
}
nxt[1] = {n, 2};
nxt[n] = {n - 1, 1};
for (int i = 2; i < n; ++i)
nxt[i] = {i - 1, i + 1};
if (solve(1, 1)) write();
else if (solve(0, 0)) write();
else if (solve(1, 0)) write();
else if (solve(0, 1)) write();
else printf("-1");
return 0;
// Yeah
}