不知道能改出来几道题。
最近总是头痛，晕乎乎的，状态不好。
感觉天天都在卡常骗分……
D1T1 integer
还写不出压位，先放个没压位的68分代码：
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=1e6+7,maxm=11e7+107;
int n,W;
char cc; ll ff;
template<typename T>void read(T& aa) {
aa=0;cc=getchar();ff=1;
while((cc<‘0‘||cc>‘9‘)&&cc!=‘-‘) cc=getchar();
if(cc==‘-‘) ff=-1,cc=getchar();
while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar();
aa*=ff;
}
int sum[maxm],ql,qr,qx;
void ud(int pos) {sum[pos]=sum[pos<<1]+sum[pos<<1|1];}
void pd(int pos,int l,int r) {
// if(sum[pos]!=0&&sum[pos]!=r-l+1) return;
if(sum[pos<<1]+sum[pos<<1|1]==sum[pos]) return;
int mid=(l+r)>>1;
if(sum[pos]==0) sum[pos<<1]=sum[pos<<1|1]=0;
else sum[pos<<1]=mid-l+1,sum[pos<<1|1]=r-mid;
}
int q(int pos,int l,int r) {
if(!sum[pos]) return 0;
if(sum[pos]==r-l+1) return 1;
int mid=(l+r)>>1;
pd(pos,l,r);
if(ql<=mid) return q(pos<<1,l,mid);
else return q(pos<<1|1,mid+1,r);
}
/*
void debug() {
printf("debug:\n");
For(i,1,20) ql=qr=i,printf("%d ",q(1,1,W));
printf("\n");
}
*/
void chge(int pos,int l,int r) {
if(l==r) {
sum[pos]+=qx;
return;
}
int mid=(l+r)>>1;
pd(pos,l,r);
if(ql<=mid) chge(pos<<1,l,mid);
else chge(pos<<1|1,mid+1,r);
ud(pos);
}
int find(int pos,int l,int r) {
if(qx==1&&sum[pos]==(r-l+1)) return 0;
if(qx==-1&&sum[pos]==0) return 0;
if(l==r) return l;
int mid=(l+r)>>1,rs=0;
pd(pos,l,r);
if(ql<=mid) rs=find(pos<<1,l,mid);
if(!rs) rs=find(pos<<1|1,mid+1,r);
return rs;
}
void rml(int pos,int l,int r) {
if(l>=ql&&r<=qr) {
if(qx==1) sum[pos]=0;
else sum[pos]=(r-l+1);
return;
}
int mid=(l+r)>>1;
pd(pos,l,r);
if(ql<=mid) rml(pos<<1,l,mid);
if(qr>mid) rml(pos<<1|1,mid+1,r);
ud(pos);
}
void get_chge(ll x,int pos) {
int p;
For(i,0,31) {
if(x&1) {
ql=pos; qr=W;
p=find(1,1,W);
ql=qr=p;
chge(1,1,W);
// printf("chge: %d , %d\n",p,qx);
// debug();
if(p!=pos) {
ql=pos; qr=p-1;
rml(1,1,W);
// printf("rml: %d~%d , %d\n",ql,qr,qx==1? 0:1);
// debug();
}
}
x>>=1; pos++;
}
}
int main() {
freopen("integer.in","r",stdin);
freopen("integer.out","w",stdout);
int op; ll x,y;
read(n); W=n+100;
read(op); read(op); if(op==4) W=30*n+100;
read(op);
For(i,1,n) {
read(op);
read(x);
if(op==1) {
read(y); y++;
if(x>0) qx=1;
else qx=-1,x=-x;
get_chge(x,y);
}
else {
ql=qr=x+1;
printf("%d\n",q(1,1,W));
}
}
fclose(stdin); fclose(stdout);
return 0;
}
D2T2 queue
双hash取模只有40，hash unsigned long long自然溢出有60
分得满得用Trie……
对于trie里面的每个点处理出一个后继指针表示其删掉当前字符串的第一个字符它会跳到哪一个点
我们可以发现，如果我新建一个节点p，表示串s[1~len]，那么之前trie中一定存在s[2~len]
所以每次新建点的时候算这个后继指针是不会出问题的
40分的双hash
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=3e5+7,maxs=1e7+7,maxt=57;
const ll Bs=7,M1=998244353,M2=1e9+7,mod=998244353;
ll n,m,a[maxn],b[maxs],ld[maxn],rd[maxn],W=50;
char s[maxs];
char cc; ll ff;
template<typename T>void read(T& aa) {
aa=0;cc=getchar();ff=1;
while((cc<‘0‘||cc>‘9‘)&&cc!=‘-‘) cc=getchar();
if(cc==‘-‘) ff=-1,cc=getchar();
while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar();
aa*=ff;
}
ll mo1(ll x) {while(x>=M1) x-=M1;return x;}
ll mo2(ll x) {while(x>=M2) x-=M2;return x;}
struct T{
ll x,y;
T(){}
T(ll x,ll y):x(x),y(y){}
T operator + (const T& b) const{return T(mo1(x+b.x),mo2(y+b.y));}
T operator - (const T& b) const{return T(mo1(x-b.x+M1),mo2(y-b.y+M2));}
T operator * (const T& b) const{return T(x*b.x%M1,y*b.y%M2);}
bool operator < (const T& b) const{return x==b.x? y<b.y:x<b.x;}
}mi[maxt],D[maxt];
map<T,int> G[maxt];
/*
void chge(int x,int y,int o) {
int lenx=1,leny,pos;
T X=T(0,0),Y;
while(x&&lenx<W) {
X=X+T(a[x],a[x])*mi[lenx-1];
leny=1; pos=y; Y=T(0,0);
while(pos&&lenx+leny<=W) {
Y=Y*mi[1]+T(a[pos],a[pos]);
G[lenx+leny][X*mi[leny]+Y]+=o;
pos=rd[pos]; leny++;
}
x=ld[x]; lenx++;
}
}
*/
void chge(int x,int y,int o) {
int lenx=1,leny=1,r;
D[0]=T(0,0); T X=T(0,0);
while(y&&leny<W) {
D[leny]=D[leny-1]*mi[1]+T(a[y],a[y]);
y=rd[y]; leny++;
}
leny--;
while(x&&lenx<W) {
X=X+T(a[x],a[x])*mi[lenx-1];
r=min((int)W-lenx,leny);
For(i,1,r)
G[lenx+i][X*mi[i]+D[i]]+=o;
x=ld[x]; lenx++;
}
}
ll get_ans(int k) {
int len=strlen(s+1);
For(i,1,len) b[i]=s[i]-‘0‘;
T now=T(0,0); ll rs=1;
For(i,1,k) now=now*mi[1]+T(b[i],b[i]);
For(i,1,len-k+1) {
rs=rs*G[k][now]%mod;
if(rs==0) return rs;
now=now*mi[1]+T(b[i+k],b[i+k]);
now=now-T(b[i],b[i])*mi[k];
}
return rs;
}
int main() {
freopen("queue.in","r",stdin);
freopen("queue.out","w",stdout);
read(n); read(m);
mi[0]=T(1,1); mi[1]=T(Bs,Bs);
For(i,2,W) mi[i]=mi[i-1]*mi[1];
For(i,1,n) read(a[i]),G[1][T(a[i],a[i])]++;
int op,x,y;
For(i,1,m) {
read(op);
// cerr<<i<<": "<<clock()<<"\n";
if(op==1) {
read(x); read(y);
rd[x]=y; ld[y]=x;
chge(x,y,1);
}
else if(op==2) {
read(x); y=rd[x];
rd[x]=0; ld[y]=0;
chge(x,y,-1);
}
else {
scanf("%s",s+1);
read(x);
printf("%lld\n",get_ans(x));
}
}
// cerr<<clock()<<"\n";
fclose(stdin); fclose(stdout);
return 0;
}
60分的hash
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
#define ll unsigned long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=3e5+7,maxs=1e7+7,maxt=57;
const ll Bs=7,mod=998244353;
ll n,m,a[maxn],b[maxs],ld[maxn],rd[maxn],W=50;
char s[maxs];
char cc; ll ff;
template<typename T>void read(T& aa) {
aa=0;cc=getchar();ff=1;
while((cc<‘0‘||cc>‘9‘)&&cc!=‘-‘) cc=getchar();
if(cc==‘-‘) ff=-1,cc=getchar();
while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar();
aa*=ff;
}
ll mi[maxt],D[maxt];
map<ll,int> G[maxt];
void chge(int x,int y,int o) {
int lenx=1,leny=1,r;
D[0]=0; ll X=0;
while(y&&leny<W) {
D[leny]=D[leny-1]*mi[1]+a[y];
y=rd[y]; leny++;
}
leny--;
while(x&&lenx<W) {
X=X+a[x]*mi[lenx-1];
r=min((int)W-lenx,leny);
For(i,1,r)
G[lenx+i][X*mi[i]+D[i]]+=o;
x=ld[x]; lenx++;
}
}
ll get_ans(int k) {
int len=strlen(s+1);
For(i,1,len) b[i]=s[i]-‘0‘;
ll now=0; ll rs=1;
For(i,1,k) now=now*mi[1]+b[i];
For(i,1,len-k+1) {
rs=rs*G[k][now]%mod;
if(rs==0) return rs;
now=now*mi[1]+b[i+k];
now=now-b[i]*mi[k];
}
return rs;
}
int main() {
freopen("queue.in","r",stdin);
freopen("queue.out","w",stdout);
read(n); read(m);
mi[0]=1; mi[1]=Bs;
For(i,2,W) mi[i]=mi[i-1]*mi[1];
For(i,1,n) read(a[i]),G[1][a[i]]++;
int op,x,y;
For(i,1,m) {
read(op);
// cerr<<i<<": "<<clock()<<"\n";
if(op==1) {
read(x); read(y);
rd[x]=y; ld[y]=x;
chge(x,y,1);
}
else if(op==2) {
read(x); y=rd[x];
rd[x]=0; ld[y]=0;
chge(x,y,-1);
}
else {
scanf("%s",s+1);
read(x);
printf("%lld\n",get_ans(x));
}
}
// cerr<<clock()<<"\n";
fclose(stdin); fclose(stdout);
return 0;
}
Trie
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
#define ll unsigned long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=1e6+7,maxs=2e7+7,maxt=57;
const ll mod=998244353;
ll n,m,a[maxn],b[maxs],ld[maxn],rd[maxn],W=50,tot=6;
char s[maxs];
int son[maxs][7],sum[maxs],to[maxs];
char cc; ll ff;
template<typename T>void read(T& aa) {
aa=0;cc=getchar();ff=1;
while((cc<‘0‘||cc>‘9‘)&&cc!=‘-‘) cc=getchar();
if(cc==‘-‘) ff=-1,cc=getchar();
while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar();
aa*=ff;
}
void chge(int x,int y,int o) {
int lenx,leny,p,now,pos;
for(p=x,lenx=1;p&&lenx<W;++lenx,p=ld[p]) {
now=0;
for(pos=p;pos;pos=rd[pos]) {
if(!son[now][a[pos]]) {
son[now][a[pos]]=++tot;
to[tot]=son[to[now]][a[pos]];
}
now=son[now][a[pos]];
}
for(pos=y,leny=1;pos&&leny+lenx<=W;++leny,pos=rd[pos]) {
if(!son[now][a[pos]]) {
son[now][a[pos]]=++tot;
to[tot]=son[to[now]][a[pos]];
}
now=son[now][a[pos]];
sum[now]+=o;
}
}
}
ll get_ans(int k) {
int len=strlen(s+1),now=0; ll rs=1;
For(i,1,len) b[i]=s[i]-‘0‘;
for(int i=1;i<=k;++i) {
now=son[now][b[i]];
if(now==0) return 0;
}
for(int i=k;i<=len&&rs;now=son[to[now]][b[++i]]) rs=rs*(ll)sum[now]%mod;
return rs;
}
int main() {
freopen("queue.in","r",stdin);
freopen("queue.out","w",stdout);
read(n); read(m);
For(i,1,6) son[0][i]=i;
For(i,1,n) read(a[i]),sum[a[i]]++;
int op,x,y;
For(i,1,m) {
read(op);
if(op==1) {
read(x); read(y);
chge(x,y,1);
rd[x]=y; ld[y]=x;
}
else if(op==2) {
read(x); y=rd[x];
rd[x]=0; ld[y]=0;
chge(x,y,-1);
}
else {
scanf("%s",s+1);
read(x);
printf("%lld\n",get_ans(x));
}
}
return 0;
}
原文：https://www.cnblogs.com/Serene-shixinyi/p/8846896.html