社区讨论
常数从何而来
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 条回复,欢迎继续交流。
正在加载回复...