190930模拟题解

T1：你在跟朋友玩一个记忆游戏。 朋友首先给你看了n个长度相同的串，然后从中等概率随机选择了一个串。 每一轮你可以询问一个位置上的正确字符，如果能够凭借已有的信息确定出朋友所选的串，那么游戏就结束了，你的成绩就是所用的轮数。 由于你实在太笨，不会任何策略，因此你采用一种方法，每次等概率随机询问一个未询问过的位置的字符。 现在你想知道，在这种情况下，你猜出结果所需的期望次数。

状压DP，预处理一个f数组表示询问某个状态之后可以确定多少个串，然后暴力转移即可

Code：

#include<bits/stdc++.h> #define db double #define ll long long using namespace std; inline int read(){ int res=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();} while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();} return res*f; } const int S=1<<20; char st[55][25]; ll same[S]; int s[S]; db f[S]; int main(){ int n=read(); for(int i=1;i<=n;i++) scanf("%s",st[i]); int len=strlen(st[1]); int all=(1<<len)-1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j){ int ss=0; for(int k=0;k<len;k++) if(st[i][k]==st[j][k]) ss|=(1<<k); same[ss]|=(1ll<<(i-1)); } for(int i=all;~i;i--) for(int j=0;j<len;j++) if(i&(1<<j)) same[i^(1<<j)]|=same[i]; same[0]=(1LL<<n)-1; for(int i=0;i<=all;i++) for(int j=0;j<n;j++) if(same[i]&(1ll<<j)) ++s[i]; for(int i=all;~i;i--){ int ss=0; for(int j=0;j<len;j++) if(!(i&(1<<j))) ++ss; if(ss && s[i]) for(int j=0;j<len;j++) if(!(i&(1<<j))) f[i]+=((db)(s[i]-s[i^(1<<j)])/s[i]+(db)s[i^(1<<j)]/s[i]*(f[i^(1<<j)]+1.0))/ss; } printf("%.10f\n",f[0]); return 0; }

T2： 有n个点，每个点有参数d，表示其度数最多为d，求构成1，2，…，n个点的无向生成树的方案数

生成树有几种做法：矩阵树，生成函数，组合数学，purfer序列 本题“度数最多为d”的限制非常强，直接导致生成函数和矩阵树爆掉 考虑purfer序列，显然就是构成一个长度为i-2的purfer序列的方案数，又因为每一种序列都是合法的purfer序列，所以只需要构造一个普通序列即可 设$dp[i][j][k]$表示考虑前i个点，j个点在purfer序列中，purfer序列长度为k 转移类似背包，枚举这个点在purfer序列中出现的次数l，则就是把l个板插到k个数中，用插板法可知选这个点的转移系数就为$C_{k+l}^k$

Code：

#include<bits/stdc++.h> #define ll long long #define mod 1000000007 using namespace std; inline int read(){ int res=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();} while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();} return res*f; } inline ll add(ll x,ll y){x+=y;if(x>=mod) x-=mod;return x;} inline ll dec(ll x,ll y){x-=y;if(x<0) x+=mod;return x;} inline ll mul(ll x,ll y){return 1ll*x*y%mod;} inline void inc(ll &x,ll y){x+=y;if(x>=mod) x-=mod;} inline void Dec(ll &x,ll y){x-=y;if(x<0) x+=mod;} inline void Mul(ll &x,ll y){x=1ll*x*y%mod;} const int N=105; int d[N]; ll dp[N][N][N],c[N][N]; int n; inline void init(){ for(int i=0;i<=n;i++){ c[i][0]=1; for(int j=1;j<=i;j++) c[i][j]=add(c[i-1][j],c[i-1][j-1]); } } inline void file(){ freopen("neuron.in","r",stdin); freopen("neuron.out","w",stdout); } int main(){ init();n=read(); for(int i=1;i<=n;i++) d[i]=read(); dp[0][0][0]=1; init(); for(int i=0;i<=n;i++) for(int j=0;j<=i;j++) for(int k=0;k<=n-2;k++) if(dp[i][j][k]){ inc(dp[i+1][j][k],dp[i][j][k]); for(int l=0;l<=d[i+1]-1 && l+k<=n-2;l++) inc(dp[i+1][j+1][k+l],mul(dp[i][j][k],c[k+l][k])); } cout<<n<<" "; for(int i=2;i<=n;i++) cout<<dp[n][i][i-2]<<" "; return 0; }

T3：动态维护一个字符串的区间不同子串个数，支持末尾加字符 把所有last相同的点放到一棵splay中，则一次修改就是access，然后套个主席树维护答案即可 就是有点长

#include<bits/stdc++.h> #define ll long long #define pi pair<ll,int> #define last last2 #define fi first #define se second using namespace std; inline int read(){ int res=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();} while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();} return res*f; } const int N=2e5+5; char s[N]; int L[N<<1],rt1[N],rt2[N],len; struct President_tree{ struct seg{int l,r,siz;ll sum;}tr[15000000]; #define ls(k) tr[k].l #define rs(k) tr[k].r #define mid (l+r>>1) int cnt; inline int cpy(int k){cnt++;tr[cnt]=tr[k];return cnt;} int update(int k,int l,int r,int ql,int qr,int v){ k=cpy(k); if(ql<=l && r<=qr){tr[k].sum+=v;++tr[k].siz;} else{ if(ql<=mid) ls(k)=update(ls(k),l,mid,ql,qr,v); if(mid<qr) rs(k)=update(rs(k),mid+1,r,ql,qr,v); } return k; } pi query(int k,int l,int r,int pos){ if(!k) return pi(0,0); if(l==r) return pi(tr[k].sum,tr[k].siz); pi ans; if(pos<=mid) ans=query(ls(k),l,mid,pos); else ans=query(rs(k),mid+1,r,pos); return pi(ans.fi+tr[k].sum,ans.se+tr[k].siz); } }tr1,tr2; namespace LCT{ int ls[N],rs[N],fa[N],last[N]; inline void copy(int x,int y){last[x]=last[y];} inline int isrs(int x){return rs[fa[x]]==x;} inline bool isroot(int x){ if(!x) return true; return ls[fa[x]]!=x && rs[fa[x]]!=x; } inline void rotate(int x){ int y=fa[x],z=fa[y],b=ls[y]==x?rs[x]:ls[x]; if(z && !isroot(y)) (ls[z]==y?ls[z]:rs[z])=x; fa[x]=z,fa[y]=x;b?fa[b]=y:0; if(ls[y]==x) rs[x]=y,ls[y]=b; else ls[x]=y,rs[y]=b; } inline void splay(int x){ int rt=x; while(!isroot(rt)) rt=fa[rt]; swap(last[rt],last[x]); while(!isroot(x)){ while(!isroot(fa[x])){ if(isrs(x)==isrs(fa[x])) rotate(fa[x]); else rotate(x); } rotate(x); } } inline void access(int x,int id){ rt1[id]=rt1[id-1];rt2[id]=rt2[id-1]; for(int y=0;x;y=x,x=fa[x]){ splay(x); if(L[x] && last[x]){ int l=last[x]-L[x]+1,r=last[x]-L[fa[x]]; if (l>1) rt1[id]=tr1.update(rt1[id],1,len,1,l-1,r-l+1); rt2[id]=tr2.update(rt2[id],1,len,l,r,r); } if(rs[x]) last[rs[x]]=last[x]; rs[x]=y; last[y]=0;last[x]=id; } } inline void link(int x,int y){splay(x);fa[x]=y;} inline void cut(int x){splay(x);last[ls[x]]=last[x];fa[ls[x]]=fa[x];ls[x]=0;} } using namespace LCT; namespace SAM{ int fa[N<<1],ch[N<<1][26],last=1,tot=1; inline void inc(int c,int id){ int p=last,np=++tot;L[np]=L[p]+1;last=np; for(;p&& !ch[p][c];p=fa[p]) ch[p][c]=np; if(!p){fa[np]=1;LCT::link(np,1);} else{ int q=ch[p][c]; if(L[q]==L[p]+1){fa[np]=q;LCT::link(np,q);} else{ int nq=++tot;L[nq]=L[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); LCT::cut(q);LCT::copy(nq,q); fa[nq]=fa[q];LCT::link(nq,fa[nq]); fa[q]=fa[np]=nq;LCT::link(q,nq);LCT::link(np,nq); for(;p && ch[p][c]==q;p=fa[p]) ch[p][c]=nq; } } LCT::access(np,id); } } char str[5]; int main(){ int t=read(); scanf("%s",s+1);int m=read(); int l=strlen(s+1);len=l+m; for(int i=1;i<=l;i++) SAM::inc(s[i]-'a',i); ll ans=0; for(int i=1;i<=m;i++){ int op=read(); if(op==1){ scanf("%s",str); str[0]=(str[0]-'a'+ans*t)%26+'a'; SAM::inc(str[0]-'a',++l); } else{ int x=read(),y=read(); x=(x-1+ans*t)%l+1;y=(y-1+ans*t)%l+1; pi ans1=tr1.query(rt1[y],1,len,x),ans2=tr2.query(rt2[y],1,len,x); ans=(ll)(y-x+2)*(y-x+1)/2-ans1.fi-ans2.fi+(ll)(x-1)*ans2.se; cout<<ans<<"\n"; } } return 0; }