abc055d <枚举>

标签：tasks int abc055d long ans contests arc069

https://atcoder.jp/contests/abc055/tasks/arc069_b
使用二进制枚举会更加简洁, 要有从进制角度思考问题的习惯

// https://atcoder.jp/contests/abc055/tasks/arc069_b
// 枚举, 尝试前两个动物的4种组合, 通过前两个动物的假设推出剩下的动物, 而后检查是否存在冲突
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n; 
string s;
int ans[N];   // 0 sheep 1 wolf

// 第一个动物为i, 第二个为j
bool check(int i, int j)
{
    ans[1] = i, ans[2] = j;
    for (int i = 2; i <= n; i ++)
    {
        if (s[i-1]=='o' && ans[i]==0 || s[i-1]=='x' && ans[i]==1) ans[i+1] = ans[i-1];
        else ans[i+1] = ans[i-1] ^ 1;
    }
    if (s[0]=='o' && ans[1]==0 || s[0]=='x' && ans[1]==1) ans[0] = ans[2];
    else ans[0] = ans[2] ^ 1;
    // ans0 为推断出的n, ansn+1 为推断出的1, 检查这两端是否冲突
    return ans[0]==ans[n] && ans[1] == ans[n+1];
}

void solv()
{
    cin >> n >> s;
    for (int i = 0; i < 2; i ++)
        for (int j = 0; j < 2; j ++)
            if (check(i, j))
            {
                for (int i = 1; i <= n; i ++)
                    if (ans[i]) cout << "W";
                    else cout << "S";
                cout << endl;
                return;
            }
    cout << -1 << endl;

}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}

标签：tasks,int,abc055d,long,ans,contests,arc069
From： https://www.cnblogs.com/o2iginal/p/17495914.html