題意:

有兩種動物,羊會說事實,狼會故意說謊,一群動物站成一圈(只包含狼和羊),他們沒人分別說自己旁邊的兩種動物是否相同.題目里是給出一串字符串,字符串里'X'代表站在這個位置的動物說它兩邊的動物種類不同,'O'代表站在這個位置的動物說它兩邊的動物種類相同,求符合這個字符串的動物排列方式,如果沒有輸出"-1".

解題思路:

數據范圍是1e5,沒有辦法去枚舉所有答案.

但是根據題目給出的字符串,我們只需要枚舉前兩個的情況,假設我們已經知道前兩個是什么動物,那么我們就能夠根據題目提供的他們認為兩邊的動物是否相同的信息來推出第三個動物是什么動物,以此類推,我們就在已知前兩個動物種類的情況下,求出所有位置動物情況,但是怎么驗證我們所求出的答案是否正確呢,我們需要check一下.

因為所有動物站成一圈,所以他們之間的 關系是可以循環的,也就是說,我們可以由最后兩個動物推出第一個動物的情況,進而由最后一個動物和第一個動物推出第二個動物的情況,

假如我們在這里推出來的第一.二個動物的情況和我們所枚舉的第一二個動物的情況相同,那么說明我們所求出的這個排列是可以循環的是正確的,如果不相符,就是錯誤的.

代碼:

#include <bits/stdc++.h>using namespace std;const int maxn=1e5+5;char s[maxn];int  is[maxn];bool solve(int x, int y, int len){      int i, j;      is[0]=x;      is[1]=y;      for(i=2; i<=len+1; i++)      {	 if(is[i-1])	 {	    if(s[i-1]=='o')is[i]=is[i-2];	    else is[i]=!is[i-2];	 }	 else  //前面的人說了假話	 {	    if(s[i-1]=='o')is[i]=!is[i-2];	    else is[i]=is[i-2];	 }      }	  /* for(i=0; i<len+2; i++)	   {	      PRintf(is[i]?"S":"W");	   }	   printf("/n");	   */      if(is[len]== is[0] && is[len+1]==is[1])      {	   for(i=0; i<len; i++)	   {	      printf(is[i]?"S":"W");	   }	   printf("/n");	   return 1;      }      return 0;}int main(){   int n;   scanf("%d", &n);   int i;   scanf("%s", s);   int len=strlen(s);   s[len]=s[0];   s[len+1]=s[1];   s[len+2]='/0';   int j;   for(i=0; i<2; i++)   {     for(j=0; j<2; j++)     {	if(solve(i, j, len))return 0;     }   }   printf("-1/n");}