社区讨论

常数从何而来

P9868[NOIP2023] 词典参与者 4已保存回复 5

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@mih6iy2n
此快照首次捕获于
2025/11/27 16:36
3 个月前
此快照最后确认于
2025/11/27 16:41
3 个月前
查看原帖
CPP
#include<bits/stdc++.h>
//#define int long long
using namespace std;

const int N=3020,mod=1e9+7,base=131;
int n,m;
struct Hash_string{
	char ch[N];
	long long hsh[N];
	void build(){
		for(int i=1;i<=m;i++){
			hsh[i]=(hsh[i-1]*base+(ch[i]-'a'))%mod;
		}
	}
	bool friend operator <(Hash_string a,Hash_string b){
		int l=1,r=n,mid,ans=-1;
		if(a.ch[1]!=b.ch[1]){
			return a.ch[1]<b.ch[1];
		}
		while(l<=r){
			mid=(l+r)>>1;
			if(a.hsh[mid]==b.hsh[mid])ans=mid,l=mid+1;
			else r=mid-1;
		}
		if(ans==m)return 0;
		return a.ch[ans+1]<b.ch[ans+1];
	}
};
Hash_string mx[N],mi[N];
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		getchar();
		for(int j=1;j<=m;j++){
			mx[i].ch[j]=mi[i].ch[j]=getchar();
		}
		
		sort(mx[i].ch+1,mx[i].ch+1+m,greater<int>());
		sort(mi[i].ch+1,mi[i].ch+1+m,less<int>());
		
		
		mx[i].build();
		mi[i].build();
	}
	for(int i=1;i<=n;i++){
		int f=1;
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			if(!(mi[i]<mx[j])){
				f=0;
				break;
			}
		}
		putchar(f+'0');
	}
	return 0;
}
请不要提及其他做法
本人仅想知道本代码的常数从何而来
提交记录
https://www.luogu.com.cn/record/249931357

回复

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

正在加载回复...