社区讨论

70pts WA on#8~10求助

P2786英语1(eng1)- 英语作文参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mmc1vz8z
此快照首次捕获于
2026/03/04 21:06
6 天前
此快照最后确认于
2026/03/07 14:10
3 天前
查看原帖
CPP
#include<bits/stdc++.h>
//hash版本 
using namespace std;
const int mod=1e9+7,base=131;
typedef unsigned long long ull;
struct node
{
	int id,point;
	ull h;
}a[100001];
ull hashe(string s)
{
	int len=s.size();
	ull ans=0;
	for(int i=0;i<len;i++)ans=(ans*base+ull(s[i]))%mod;
	return ans;
}
bool cmp(node a,node b)
{
	return a.h<b.h;
}
map<string,int>p; 
int n,pp,ans;
string s;
void work(string s)
{
	int len=s.size();
	for(int i=0;i<len;i++)
	{
		string now="";
		while(i<len&&(s[i]!='!'&&s[i]!='?'&&s[i]!=','&&s[i]!='.'&&s[i]!=' '))now+=s[i++];
		int l=1,r=n,pos,find=hashe(now);
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(a[mid].h<=find)pos=mid,l=mid+1;
			else r=mid-1;
		}
		if(a[pos].h==find)ans=(a[pos].point+ans)%pp;
	}
}
int main()
{
	cin>>n>>pp;
	for(int i=1;i<=n;i++)
	{
		string tmp;
		int point;
		cin>>tmp>>point;
		int cnt=hashe(tmp);
		a[i].id=i;
		a[i].point=point;
		a[i].h=cnt;
	}
	sort(a+1,a+n+1,cmp);
	while(getline(cin,s))
	{
		work(s);
	}
	cout<<ans%pp;
	return 0;
}
rt,hash+二分,不知道为什么没过
代码有点丑勿喷

回复

0 条回复,欢迎继续交流。

正在加载回复...