AtCoder Beginner Contest 055 D - Menagerie -枚举
D - Menagerie
Time limit : 2sec / Memory limit : 256MB
Score : 500 points
Problem Statement
Snuke, who loves animals, built a zoo.
There are N animals in this zoo. They are conveniently numbered 1 through N, and arranged in a circle. The animal numbered i(2≤i≤N−1) is adjacent to the animals numbered i−1 and i+1. Also, the animal numbered 1 is adjacent to the animals numbered 2 and N, and the animal numbered N is adjacent to the animals numbered N−1 and 1.
There are two kinds of animals in this zoo: honest sheep that only speak the truth, and lying wolves that only tell lies.
Snuke cannot tell the difference between these two species, and asked each animal the following question: "Are your neighbors of the same species?" The animal numbered i answered si. Here, if si is o
, the animal said that the two neighboring animals are of the same species, and if si is x
, the animal said that the two neighboring animals are of different species.
More formally, a sheep answered o
if the two neighboring animals are both sheep or both wolves, and answered x
otherwise. Similarly, a wolf answered x
if the two neighboring animals are both sheep or both wolves, and answered o
otherwise.
Snuke is wondering whether there is a valid assignment of species to the animals that is consistent with these responses. If there is such an assignment, show one such assignment. Otherwise, print -1
.
Constraints
- 3≤N≤105
-
s is a string of length N consisting of
o
andx
.
Input
The input is given from Standard Input in the following format:
N
s
Output
If there does not exist an valid assignment that is consistent with s, print -1
. Otherwise, print an string t in the following format. The output is considered correct if the assignment described by t is consistent with s.
-
t is a string of length N consisting of
S
andW
. - If ti is
S
, it indicates that the animal numbered i is a sheep. If ti isW
, it indicates that the animal numbered i is a wolf.
Sample Input 1
Copy
6
ooxoox
Sample Output 1
Copy
SSSWWS
For example, if the animals numbered 1, 2, 3, 4, 5 and 6 are respectively a sheep, sheep, sheep, wolf, wolf, and sheep, it is consistent with their responses. Besides, there is another valid assignment of species: a wolf, sheep, wolf, sheep, wolf and wolf.
Let us remind you: if the neiboring animals are of the same species, a sheep answers o
and a wolf answers x
. If the neiboring animals are of different species, a sheep answers x
and a wolf answers o
.
Sample Input 2
Copy
3
oox
Sample Output 2
Copy
-1
Print -1
if there is no valid assignment of species.
Sample Input 3
Copy
10
oxooxoxoox
Sample Output 3
Copy
SSWWSSSWWS
题意:
给你一个长度为n的由'x'和'o'组成的字符串,o代表相同,x代表相反。请你找出这样一个n个字符组成的序列,该序列由W与S组成,代表狼与羊,若在该位置上为狼且其两边的动物不相同,它会说谎,(即对应字符为o),若相同,则对应的字符为x,如果是羊,则其会说真话。请找出任何一个这样的序列输出,如果没有则输出-1
思路:
枚举前两个位置(狼狼、羊羊、狼羊、羊狼),将整个序列填满后检验第一个位置和最后一个位置的描述适合符合,是则输出并停止,若四种均无法成功则输出-1
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[300005],ans[300005];
int n;
char dao(char a){
if(a=='S') return 'W';
if(a=='W') return 'S';
}
int deal(){
for(int i=2;i<n;i++){
if(s[i]=='o'){
if(ans[i]=='S'){
ans[i+1]=ans[i-1];
}
else{
ans[i+1]=dao(ans[i-1]);
}
}
else {
if(ans[i]=='S'){
ans[i+1]=dao(ans[i-1]);
}
else{
ans[i+1]=ans[i-1];
}
}
}
int flag1=0,flag2=0;
if(ans[1]=='S'){
if(s[1]=='o'){
if(ans[2]==ans[n]){
flag1=1;
}
}
else{
if(ans[2]==dao(ans[n])){
flag1=1;
}
}
}
else {
if(s[1]=='o')
if(ans[2]!=ans[n]) {
flag1=1;
}
else
if(ans[2]!=dao(ans[n])){
flag1=1;
}
}
if(ans[n]=='S'){
if(s[n]=='o'){
if(ans[1]==ans[n-1]){
flag2=1;
}
}
else{
if(ans[1]==dao(ans[n-1])){
flag2=1;
}
}
}
else {
if(s[n]=='o'){
if(ans[1]==dao(ans[n-1])){
flag2=1;
}
}
else{
if(ans[1]==ans[n-1]){
flag2=1;
}
}
}
if(flag1&&flag2) return 1;
return 0;
}
int main(){
scanf("%d%s",&n,s+1);
ans[1]='S',ans[2]='S';
if(deal()){
printf("%s\n",ans+1);
return 0;
}
ans[1]='S',ans[2]='W';
if(deal()){
printf("%s\n",ans+1);
return 0;
}
ans[1]='W',ans[2]='S';
if(deal()){
printf("%s\n",ans+1);
return 0;
}
ans[1]='W',ans[2]='W';
if(deal()){
printf("%s\n",ans+1);
return 0;
}
printf("-1\n");
return 0;
}
上一篇: 详解 Python 与文件对象共事的实例
下一篇: ssh框架实现文件上传下载实例代码
推荐阅读
-
AtCoder Beginner Contest 055 D - Menagerie -枚举
-
AtCoder Beginner Contest 163 D - Sum of Large Numbers(递推&找规律)
-
AtCoder Beginner Contest 182----D. Wandering
-
AtCoder Beginner Contest 176 D-Wizard in Maze(双端队列)
-
AtCoder Beginner Contest 160(A~D)
-
AtCoder Beginner Contest 162(A~D)
-
AtCoder Beginner Contest 160(A~D)
-
AtCoder Beginner Contest 162(A~D)
-
AtCoder Beginner Contest 176 D-Wizard in Maze(双端队列)