题目:
wbq 最近的家庭作业是写一篇文章.
理所当然,他发现写文章很无聊,写了两个小时后,
他意识到他写的 N 个单词的文章完全由字母 A 和 B 组成,所以可怜的 wbq 决定用文章做一些有趣的计数.
对于一个单词,wbq 对一对相同的字母画弧线相连,并且只能从上方画.
一个给定的单词是好的,当且仅当每个字母可以连接到另一个与它相同的字母,
同时没有两条弧线相交。帮 wbq 数一数有多少单词是好的。
Input
第一行一个整数?表示有?个单词.
接下来?行每行一个字符串表示一个单词.
Outpupt
一行一个整数表示有多少单词是好的.
对于所有的数据:1 ≤ ? ≤ 100,设每个单词的长度为 x,那么2 ≤ ? ≤ 100000,并且这? 个单词的长度总和≤ 1 000 000
想法:
一个好单词一定是偶数,从中间断开,向两边判断是否相同
例如:ABAABA
第一次断:
ABA ABA
发现两边完全相同,则是一个好单词,如果不同,则剩下的两部分继续进行同样的操作,直至剩下的为奇数
代码:
#include<bits/stdc++.h>
using namespace std;
int n,k,ans=0;
string a;
inline bool f(int l,int r)
{
if((r-l+1)&1) return 0;
int i=(l+r)/2,j=i+1;
while(i>=0)
{
if(a[i]!=a[j]) break;
i--;j++;
}
if(i<0) return 1;
f(l,i);f(j,r);
return 1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
k=a.length();
if(f(0,k-1)) ans++;
}
cout<<ans;
return 0;
}
求求各位大佬看看哪出了问题