文章

5

粉丝

409

获赞

7

访问

49.3k

头像
字符串哈希表上做前缀和
推荐阅读
P1738 华东师范大学2020年机试题
发布于2020年6月28日 19:53
阅读数 12.6k

#include<cstdio>
#include<cstring>


using namespace std;		

int pre[50005][26]={};
char s[50005];
int main()
{
	//freopen("1.txt","r",stdin);
	scanf("%s",s);

	for(int i=1;i<=strlen(s);i++)
	{
		char c = s[i-1];
		int cur = (c-'a');
		for(int j=0;j<26;j++)
		{
			pre[i][j] = pre[i-1][j] + (j==cur);//比赛时这出大bug了,简洁至上
		}
	}
	
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		bool flag = true;
		for(int i=0;i<26;i++)
		{

			int hx = pre[b][i]-pre[a-1][i],hy = pre[d][i]-pre[c-1][i];

			if( hx!= hy )
			{
				flag = false;
				break;
			}
		}
		
		if(flag)
			printf("DA\n");
		else
			printf("NE\n");
	}
	
		
}

1.注意q中给出的abcd起始为1

2.数据量大用c读入,不然容易tle

登录查看完整内容


登录后发布评论

2 条评论
18117221377
2021年9月3日 22:08

服气,50000*4的数据也需要用c读,是我太年轻了crying

赞(0)
Yangyylj
2021年5月19日 21:56

同学你好!请问你能解释一下这个意思嘛?谢谢!!

赞(0)