总时间限制: 20000ms 单个测试点时间限制: 1000ms 内存限制: 262144kB
描述
有 N 个升级了 AI 的机器人,编号为 1,2,...,N,它们围成一圈,每个机器人都有两个邻居。准确地讲,编号为 i(2<= i <=N-1)的机器人的邻居的编号为 i-1 和 i+1,编号为 1 的机器人的邻居的编号为 2 和 N,编号为 N 的机器人的邻居的编号为 1 和 N-1。
这 N 个机器人有两种型号,T 型号的机器人永远说真话,F 型号的机器人永远说假话。按一下机器人头顶的按钮,机器人会说一句话,意思是它的两个邻居是否是同一种型号。准确地讲,如果 T 型机器人的两个邻居都是 T 型或者都是 F 型,那么机器人会说 y,否则会说 n。如果 F 型机器人的两个邻居都是 T 型或者都是 F 型,那么机器人会说 n,否则会说 y。
你分不清每个机器人的型号,所以按下了每个机器人头顶的按钮,让每个机器人都说了话,其中第 i 个机器人说的话是 si。现在你可以根据这些信息来判断机器人的型号。
输入
第一行一个整数 ,表示机器人的数量。
第二行一个长度为 N 的字符串 s1,s2,...sN,si 表示编号为 i 的机器人说的话。
输出
如果至少存在一个方案能够满足条件,那么输出一个字符串表示这种方案。如果有多个方案,任意输出一个方案。如果没有任何一个方案可以满足条件,输出 -1。
一个满足条件的方案是指,确定每个机器人的型号后,每一个机器人说的话都满足这个型号的要求。即 T 型机器人说真话,F 型机器人说假话。
一个方案的输出字符串 T=t1,t2,...,tN 需要满足:
1、T 的长度为 N,只包含字母 T 或者 F
2、如果 ti='T',表示第 i 个机器人的型号是 T;如果 ti='F',表示第 i 个机器人的型号是 F。
数据范围:
30% 的数据,N=6
100% 的数据,3<= N <=100
我使用了一种枚举的方法,只有70分,求帮忙查查错!
#include<iostream>
using namespace std;
int n,l=1,g,h;
bool flag=0;
int main(){
cin>>n;
char a[n];
bool b[n];
for(int i=0;i<n;i++)cin>>a[i];
for(int i=1;i>=0;i--){
for(int j=1;j>=0;j--){
b[0]=i;
b[1]=j;
l=1;
while(l<=n-1){
g=l-1;
h=l+1;
if(b[l]==0&&a[l]=='y'&&b[g]==0)b[h]=1;
if(b[l]==0&&a[l]=='n'&&b[g]==0)b[h]=0;
if(b[l]==0&&a[l]=='y'&&b[g]==1)b[h]=0;
if(b[l]==0&&a[l]=='n'&&b[g]==1)b[h]=1;
if(b[l]==1&&a[l]=='y'&&b[g]==0)b[h]=0;
if(b[l]==1&&a[l]=='n'&&b[g]==0)b[h]=1;
if(b[l]==1&&a[l]=='y'&&b[g]==1)b[h]=1;
if(b[l]==1&&a[l]=='n'&&b[g]==1)b[h]=0;
l++;
}
if(b[n-1]==1&&a[n-1]=='n'&&b[n-2]!=b[0])flag=1;
if(b[n-1]==1&&a[n-1]=='y'&&b[n-2]==b[0])flag=1;
if(b[n-1]==0&&a[n-1]=='n'&&b[n-2]==b[0])flag=1;
if(b[n-1]==0&&a[n-1]=='y'&&b[n-2]!=b[0])flag=1;
if(flag==1){
for(int s=0;s<n;s++){
if(b[s]==1)cout<<'T';
else cout<<'F';
}
return 0;
}
}
}
cout<<-1;
return 0;
}