【2020省选模拟】题解Stargazer的博客-

T1：

把前序遍历左右看做括号序列，就是
$0le sle m-2$

0≤s≤m−2，折线容斥即可

#include<bits/stdc++.h> using namespace std; #define cs const #define pb push_back #define pii pair<int,int> #define fi first #define se second #define ll long long namespace IO{  cs int rlen=1<<20|1; char ibuf[rlen],*ib,*ob; inline char gc(){ (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,rlen,stdin)); return (ib==ob)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0;bool f=0; while(!isdigit(ch))f=ch=='-',ch=gc(); while(isdigit(ch))res=(res*10)+(ch^48),ch=gc(); return f?-res:res; } } using IO::read;  cs int mod=998244353; inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;} inline int dec(int a,int b){return a<b?a-b+mod:a-b;} inline int mul(int a,int b){return (ll)a*b%mod;} inline void Add(int &a,int b){a=a+b>=mod?a+b-mod:a+b;} inline void Dec(int &a,int b){a=a<b?a-b+mod:a-b;} inline void Mul(int &a,int b){a=(ll)a*b%mod;} inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))if(b&1)Mul(res,a);return res;} inline int Inv(int x){return ksm(x,mod-2);} char xx; cs int N=2e7+5; int fac[N],ifac[N]; inline void init_fac(){  ifac[0]=fac[0]=1; for(int i=1;i<N;i++)fac[i]=mul(fac[i-1],i);  ifac[N-1]=Inv(fac[N-1]); for(int i=N-2;i;i--)ifac[i]=mul(ifac[i+1],i+1); } inline int C(int n,int m){return (n<0||m<0||n<m)?0:mul(fac[n],mul(ifac[m],ifac[n-m]));} inline int calc(int x,int y){return C(x+y,x);} int n,m; char yy; inline void move1(int &x,int &y){swap(x,y),x++,y--;} inline void move2(int &x,int &y){swap(x,y),x-=m-1,y+=m-1;} int main(){ init_fac();  n=read(),m=read(); int res=calc(n-1,n-1),x=n-1,y=n-1; while(x>=0&&y>=0){ move1(x,y),Dec(res,calc(x,y)); move2(x,y),Add(res,calc(x,y)); }  x=n-1,y=n-1; while(x>=0&&y>=0){ move2(x,y),Dec(res,calc(x,y)); move1(x,y),Add(res,calc(x,y)); }cout<<res<<'n';return 0; } 

T2：

把关键点提出来状压，每个答案枚举关键点计算
先floyd预处理每种状态的最短路可以方便转移

#include<bits/stdc++.h> using namespace std; #define cs const #define pb push_back #define pii pair<int,int> #define fi first #define se second #define ll long long #define bg begin namespace IO{  cs int rlen=1<<22|1; char ibuf[rlen],*ib,*ob; inline char gc(){ (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,rlen,stdin)); return (ib==ob)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0;bool f=0; while(!isdigit(ch))f=ch=='-',ch=gc(); while(isdigit(ch))res=(res*10)+(ch^48),ch=gc(); return f?-res:res; } } using IO::read; template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;} template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}  cs int N=405,M=(1<<16)|5,T=34; bool isgt[N]; int dis[N][N],f[M][T],g[T][T],ans[N][N],inf; int v[T],z[T],gt[N],ky[N],ban[N]; int n,m,K,q,lim; int d[M][T][T]; int main(){ #ifdef Stargazer freopen("lx.in","r",stdin); freopen("my.out","w",stdout); #endif  n=read(),m=read(),K=read(),lim=1<<K; memset(g,127/2,sizeof(g)); memset(dis,127/2,sizeof(dis)),inf=dis[0][0]; for(int i=1;i<=n;i++)dis[i][i]=0; for(int i=1;i<=m;i++){ int u=read(),v=read(),w=read(); chemn(dis[u][v],w),chemn(dis[v][u],w); } for(int i=0;i<K;i++){   v[i]=read(),z[i]=read();   isgt[v[i]]=1;   gt[v[i]]|=1<<i,ky[z[i]]|=1<<i; } for(int k=1;k<=n;k++)if(!isgt[k]) for(int i=1;i<=n;i++)if(i!=k) for(int j=1;j<=n;j++)if(j!=k&&j!=i) chemn(dis[i][j],dis[i][k]+dis[k][j]); for(int i=0;i<K;i++) for(int j=0;j<K;j++){   d[0][i][j]=dis[z[i]][z[j]];   d[0][i+K][j]=dis[v[i]][z[j]];   d[0][i][j+K]=dis[z[i]][v[j]];   d[0][i+K][j+K]=dis[v[i]][v[j]]; } for(int s=1;s<lim;s++){ int (*D)[T]=d[s],(*pre)[T]=d[s^(s&(-s))]; for(int i=0;i<K+K;i++) for(int j=0;j<K+K;j++)    D[i][j]=pre[i][j]; int u=__builtin_ctz(s); if((gt[v[u]]&s)==gt[v[u]]) for(int i=0;i<K+K;i++) for(int j=0;j<K+K;j++){ int vl=D[i][u+K]+D[u+K][j]; chemn(D[i][j],vl),chemn(D[j][i],vl); } } for(int t=0;t<K;t++){ memset(f,127/2,sizeof(f));   f[ky[z[t]]][t]=0; for(int s=1<<t;s<lim;s=(s+1)|(1<<t)){ for(int i=0;i<K;i++)if(((s>>i)&1)&&f[s][i]<inf){ int vl=f[s][i],*D=d[s][i]; for(int j=0;j<K;j++)if(!((s>>j)&1)){ if((gt[z[j]]&s)==gt[z[j]])chemn(f[s|ky[z[j]]][j],vl+D[j]); } for(int j=0;j<K;j++) if((gt[v[j]]&s)==gt[v[j]])chemn(g[t][j],vl+D[j+K]); } } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(isgt[i]){ans[i][j]=-1;continue;} if(!isgt[j]){    ans[i][j]=dis[i][j]; for(int a=0;a<K;a++) for(int b=0;b<K;b++){ if(!isgt[z[a]])chemn(ans[i][j],dis[i][z[a]]+g[a][b]+dis[v[b]][j]); } } else{    ans[i][j]=inf; int b; for(b=0;b<K;b++)if(v[b]==j)break; for(int a=0;a<K;a++){ if(!isgt[z[a]])chemn(ans[i][j],dis[i][z[a]]+g[a][b]); } } if(ans[i][j]>=inf)ans[i][j]=-1; }  q=read(); while(q--){ int s=read(),t=read();   cout<<ans[s][t]<<'n'; }return 0; } 

T3：

分治，map+哈希维护一下每种字符之间合法交换之后的字符以及个数即可

#include<bits/stdc++.h> using namespace std; #define cs const #define pb push_back #define pii pair<int,int> #define fi first #define se second #define ll long long #define bg begin namespace IO{  cs int rlen=1<<22|1; char ibuf[rlen],*ib,*ob; inline char gc(){ (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,rlen,stdin)); return (ib==ob)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0;bool f=0; while(!isdigit(ch))f=ch=='-',ch=gc(); while(isdigit(ch))res=(res*10)+(ch^48),ch=gc(); return f?-res:res; } inline int readstring(char *s){ char ch=gc();int top=0; while(isspace(ch))ch=gc(); while(!isspace(ch)&&ch!=EOF)s[++top]=ch,ch=gc();  s[top+1]='';return top; } } using IO::read; using IO::readstring; template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;} template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}  cs int m1=1e9+7,m2=1e9+9; inline int add1(int a,int b){return a+b>=m1?a+b-m1:a+b;} inline int add2(int a,int b){return a+b>=m2?a+b-m2:a+b;} inline int dec1(int a,int b){return a<b?a-b+m1:a-b;} inline int dec2(int a,int b){return a<b?a-b+m2:a-b;} inline int mul1(int a,int b){return (ll)a*b%m1;} inline int mul2(int a,int b){return (ll)a*b%m2;} cs pii bs=pii(5,13); inline pii operator +(cs pii &a,cs pii &b){return pii(add1(a.fi,b.fi),add2(a.se,b.se));} inline pii operator -(cs pii &a,cs pii &b){return pii(dec1(a.fi,b.fi),dec2(a.se,b.se));} inline pii operator *(cs pii &a,cs pii &b){return pii(mul1(a.fi,b.fi),mul2(a.se,b.se));}  cs int N=100005; char str[N]; int n;ll ans; pii pw[N]; struct Map{ static cs int mod=10260817; int adj[mod],nxt[N<<1],vl[N<<1],stk[N<<1],top,cnt;  pii to[N<<1]; inline void clear(){ while(top)adj[stk[top--]]=0;   cnt=0; } void insert(pii x,int k){ int p=((ll)x.fi*19260817+x.se)%mod; for(int e=adj[p];e;e=nxt[e])if(to[e]==x){vl[e]+=k;return;}   stk[++top]=p;nxt[++cnt]=adj[p],adj[p]=cnt,to[cnt]=x,vl[cnt]=k; } int query(pii x){ int p=((ll)x.fi*19260817+x.se)%mod; for(int e=adj[p];e;e=nxt[e])if(to[e]==x)return vl[e]; return 0; } }f[6]; inline int id(int a,int b){ switch(a){ case 1:return b==2?0:1; case 2:return b==1?2:3; case 3:return b==1?4:5; }assert(0); } struct hs{  pii pre[N],suf[N]; int n,ps,del,p[N],s[N]; void clear(){n=del=0;} void push(char x){ int c=x-'a'+1; if(kd==0)ps++;else ps--; if(n&&s[n]==c)p[++del]=c,n--; else s[++n]=c,pre[n]=pre[n-1]*bs+pii(c,c),suf[n]=suf[n-1]+pii(c,c)*pw[n-1],p[++del]=-1; } void back(){ if(del){ if(kd==0)ps--;else ps++; if(p[del]>0)s[++n]=p[del],pre[n]=pre[n-1]*bs+pii(p[del],p[del]),suf[n]=suf[n-1]+pii(p[del],p[del])*pw[n-1]; else n--;del--; } } inline pii hasl(int l,int r){ return pre[r]-pre[l-1]*pw[r-l+1]; } int kd; void move(int p){ if(kd==0){ while(ps>p)back(); while(ps<p)push(str[ps+1]); } else{ while(ps<p)back(); while(ps>p)push(str[ps-1]); } } }A,B,C; inline pii calc(hs &a,char x,hs &b,int kd){  a.push(x); int l=1,r=min(a.n,b.n),res=0; while(l<=r){ int mid=(l+r)>>1; if(a.hasl(a.n-mid+1,a.n)==b.hasl(b.n-mid+1,b.n))l=mid+1,res=mid; else r=mid-1; }  pii now; if(kd==0)now=a.pre[a.n-res]*pw[b.n-res]+b.suf[b.n-res]; else now=a.suf[a.n-res]+b.pre[b.n-res]*pw[a.n-res];  a.back();return now; } void solve(int l,int r){ if(l==r)return; int mid=(l+r)>>1;  A.move(mid);C.clear(); for(int i=mid;i>=l;i--){   A.back(); for(int j=1;j<=3;j++)if(j!=str[i]-'a'+1){    f[id(str[i]-'a'+1,j)].insert(calc(A,'a'+j-1,C,0),1); }   C.push(str[i]); }  B.move(mid+1);C.clear(); for(int i=mid+1;i<=r;i++){   B.back(); for(int j=1;j<=3;j++)if(j!=str[i]-'a'+1){     ans+=f[id(j,str[i]-'a'+1)].query(calc(C,'a'+j-1,B,1)); }   C.push(str[i]); } for(int i=0;i<6;i++)f[i].clear(); solve(l,mid),solve(mid+1,r); } int main(){ #ifdef Stargazer freopen("lx.in","r",stdin); #endif  pw[0]=pii(1,1); for(int i=1;i<N;i++)pw[i]=pw[i-1]*bs;  n=readstring(str);A.kd=0,B.kd=1,B.ps=n+1; for(int i=1;i<=n;i++)A.push(str[i]); for(int i=n;i>=1;i--)B.push(str[i]); solve(1,n);  cout<<ans<<'n'; return 0; }