站外题:运行会卡住
  • 板块学术版
  • 楼主wvwit
  • 当前回复14
  • 已保存回复14
  • 发布时间2023/2/25 16:17
  • 上次更新2023/10/23 23:49:07
查看原帖
站外题:运行会卡住
928914
wvwit楼主2023/2/25 16:17

题目:

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;
}

求求各位大佬看看哪出了问题

2023/2/25 16:17
加载中...