首页 > 代码库 > bzoj4943 [Noi2017]蚯蚓排队
bzoj4943 [Noi2017]蚯蚓排队
题面暂缺。。
正解：字符串$hash$。
我在考场上写了个$map$的$hash$被卡成$40$分，然后改成挂链版本的就$AC$了。。$mdzz$，以后$hash$再也不写$map$了。。
我们考虑使用链表来表示字符间的关系，合并和分裂都用链表来表示，这样我们可以快速找到两个字符的前$k$个和后$k$个字符。
注意到每次只会增加或减少$k^{2}$个字符串，那么我们直接把这些字符串$hash$起来即可，查询统计也很简单。
这道题好像是被骂得最惨的一道题？？
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 #define rhl (998244353) 14 #define wyh (19260817) 15 #define M (10000010) 16 #define N (300010) 17 #define il inline 18 #define RG register 19 #define ll long long 20 #define ull unsigned long long 21 22 using namespace std; 23 24 struct edge{ int nt,sum; ull v; }g[12000010]; 25 26 int head[wyh+10],a[N],lst[N],nxt[N],st1[60],st2[60],tong[10],n,m,num,fg,top1,top2; 27 ull hsh[M],bin[M],base=7; 28 char s[M]; 29 ll ans; 30 31 il int gi(){ 32 RG int x=0,q=1; RG char ch=getchar(); 33 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 34 if (ch==‘-‘) q=-1,ch=getchar(); 35 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 36 return q*x; 37 } 38 39 il void insert(RG int from,RG ull to){ 40 g[++num]=(edge){head[from],1,to},head[from]=num; return; 41 } 42 43 il void add(RG ull Hash){ 44 RG int ymd=Hash%wyh; 45 for (RG int i=head[ymd];i;i=g[i].nt) 46 if (g[i].v==Hash){ ++g[i].sum; return; } 47 return insert(ymd,Hash); 48 } 49 50 il void del(RG ull Hash){ 51 RG int ymd=Hash%wyh; 52 for (RG int i=head[ymd];i;i=g[i].nt) 53 if (g[i].v==Hash){ --g[i].sum; return; } 54 return; 55 } 56 57 il ll calc(RG ull Hash){ 58 RG int ymd=Hash%wyh; 59 for (RG int i=head[ymd];i;i=g[i].nt) 60 if (g[i].v==Hash) return g[i].sum; 61 return 0; 62 } 63 64 int main(){ 65 #ifndef ONLINE_JUDGE 66 freopen("queue.in","r",stdin); 67 freopen("queue.out","w",stdout); 68 #endif 69 n=gi(),m=gi(),fg=1,bin[0]=1; 70 for (RG int i=1;i<=10000000;++i) bin[i]=bin[i-1]*base; 71 for (RG int i=1;i<=n;++i){ a[i]=gi(),++tong[a[i]]; if (a[i]!=1) fg=0; } 72 for (RG int i=1;i<=n;++i) lst[i]=nxt[i]=i; 73 for (RG int p=1,op,x,y,k,len;p<=m;++p){ 74 op=gi(); 75 if (op==1){ 76 x=gi(),y=gi(),top1=top2=0,st1[++top1]=x,st2[++top2]=y; 77 for (RG int i=x;top1<49 && lst[i]!=i;i=lst[i]) st1[++top1]=lst[i]; 78 for (RG int i=y;top2<49 && nxt[i]!=i;i=nxt[i]) st2[++top2]=nxt[i]; 79 RG ull Hsh=0; for (RG int i=top1;i;--i) Hsh=Hsh*base+a[st1[i]]; st1[top1+1]=0; 80 for (RG int i=top1;i;--i){ 81 RG ull Hash=Hsh-a[st1[i+1]]*bin[i]; Hsh=Hash,len=i; 82 for (RG int j=1;j<=top2;++j){ 83 ++len; if (len>50) break; 84 Hash=Hash*base+a[st2[j]],add(Hash); 85 } 86 } 87 nxt[x]=y,lst[y]=x; 88 } 89 if (op==2){ 90 x=gi(),y=nxt[x],top1=top2=0,st1[++top1]=x,st2[++top2]=y; 91 for (RG int i=x;top1<49 && lst[i]!=i;i=lst[i]) st1[++top1]=lst[i]; 92 for (RG int i=y;top2<49 && nxt[i]!=i;i=nxt[i]) st2[++top2]=nxt[i]; 93 RG ull Hsh=0; for (RG int i=top1;i;--i) Hsh=Hsh*base+a[st1[i]]; st1[top1+1]=0; 94 for (RG int i=top1;i;--i){ 95 RG ull Hash=Hsh-a[st1[i+1]]*bin[i]; Hsh=Hash,len=i; 96 for (RG int j=1;j<=top2;++j){ 97 ++len; if (len>50) break; 98 Hash=Hash*base+a[st2[j]],del(Hash); 99 }100 }101 nxt[x]=x,lst[y]=y;102 }103 if (op==3){104 scanf("%s",s+1),k=gi(),len=strlen(s+1),ans=1; RG ull Hash;105 if (k==1){106 for (RG int i=1;i<=len;++i) ans=ans*(ll)tong[s[i]-48]%rhl;107 printf("%lld\n",ans); continue;108 }109 for (RG int i=1;i<=len;++i) hsh[i]=hsh[i-1]*base+s[i]-48;110 for (RG int i=1;i+k-1<=len;++i){111 Hash=hsh[i+k-1]-hsh[i-1]*bin[k];112 ans=ans*calc(Hash)%rhl;113 }114 printf("%lld\n",ans);115 }116 }117 return 0;118 }
bzoj4943 [Noi2017]蚯蚓排队
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。