首页 > 代码库 > 清北模拟题4
清北模拟题4
更正：第三组：不存在相同的字符|str|=26，26<=n<=100
题解：kmp+矩阵乘法（类似 GT算法，只需将 GT算法的代码（ps：GT算法是一道题）进行一下修改）。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define MAXN 10100#define MAXM 110#define M 1000000007using namespace std;int dp[MAXN][MAXM];int fail[MAXM];int trs[MAXN][26];char str[MAXN];void xx(int &x,int y){ x+=y; if (x>=M) x-=M;}int main(){ int n; while (~scanf("%d%s",&n,str+1)) { memset(dp,0,sizeof(dp)); int m=strlen(str+1); fail[1]=0; for (int i=2;i<=m;i++) { int p=fail[i-1]; while (p && str[p+1]!=str[i]) p=fail[p]; if (str[p+1]==str[i]) fail[i]=p+1; } memset(trs,-1,sizeof(trs)); memset(trs[0],0,sizeof(trs[0])); for (int i=0;i<m;i++) trs[i][str[i+1]-‘a‘]=i+1; for (int i=0;i<=m;i++) for (int j=0;j<26;j++) if (trs[i][j]==-1) trs[i][j]=trs[fail[i]][j]; dp[0][0]=1; for (int i=0;i<n;i++) for (int j=0;j<m;j++) for (int k=0;k<26;k++) xx(dp[i+1][trs[j][k]],dp[i][j]); long long ans=0; long long x=1; for (int i=n;i>=0;i--) { ans = (ans+x*dp[i][m])%M; if (i)x=x*26%M; } printf("%d\n",(int)((x-ans)%M+M)%M); }}
更正：输出的顺序保证a<b
更正：输出样例：0 1000000006
题解：类似斐波那契数列，进行一下变形。加上矩阵乘法。（数据很大）
#include<cstdio>#include<iostream>#define M 1000000007using namespace std;long long b[3][3],c[3][3],ans[3][3];long long n;void work(long long n){ b[1][1]=ans[1][1]=0; b[1][2]=ans[1][2]=1; b[2][1]=ans[2][1]=1; b[2][2]=ans[2][2]=1; while(n) { if(n&1) { for(int k=1;k<=2;k++) for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) c[i][j]=(c[i][j]+(ans[i][k]%M*b[k][j]%M))%M; for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) ans[i][j]=c[i][j],c[i][j]=0; } for(int k=1;k<=2;k++) for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) c[i][j]=(c[i][j]+(b[i][k]%M*b[k][j]%M))%M; for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) b[i][j]=c[i][j],c[i][j]=0; n/=2; } long long ans1=(ans[1][2])%M,ans2=(ans[1][1]+ans[1][2])%M; cout<<min(ans1,ans2)<<" "<<max(ans1,ans2);}int main(){ cin>>n; work(n); return 0;}
更正：模数1000000007
题解：考试的时候这个题全部爆零。当时以为是二分图匹配的题，结果是树形dp，被题目坑了一把。
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#define maxn 100010#define mod 1000000007#define ll long longusing namespace std;ll T,P,n,head[maxn],num,f[maxn][2],g[maxn][2],L,R[maxn],l,r[maxn],son[maxn];struct node{ ll v,pre;}e[maxn*2];void Add(ll from,ll to){ num++;e[num].v=to; e[num].pre=head[from]; head[from]=num;}void xx(){ num=0; memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); memset(head,0,sizeof(head));}void DP(ll now,ll from){ g[now][0]=1; ll mx,sum; for(int i=head[now];i;i=e[i].pre) { ll v=e[i].v; if(v==from)continue; DP(v,now); mx=max(f[v][1],f[v][0]);sum=0; if(mx==f[v][1])sum+=g[v][1]; if(mx==f[v][0])sum+=g[v][0]; g[now][0]=g[now][0]*sum%mod; f[now][0]+=mx; } L=0;l=1;ll S=0; for(int i=head[now];i;i=e[i].pre) if(e[i].v!=from)son[++S]=e[i].v; R[S+1]=0; r[S+1]=1; for(int i=S;i>=1;i--) { ll v=son[i];sum=0; mx=max(f[v][1],f[v][0]); if(mx==f[v][1])sum+=g[v][1]; if(mx==f[v][0])sum+=g[v][0]; R[i]=R[i+1]+mx; r[i]=r[i+1]*sum%mod; } for(int i=1;i<=S;i++) { ll v=son[i]; mx=L+f[v][0]+R[i+1]+1; if(mx>f[now][1]) { f[now][1]=mx; g[now][1]=l*g[v][0]%mod*r[i+1]%mod; } else if(mx==f[now][1]) g[now][1]=(g[now][1]+l*g[v][0]%mod*r[i+1]%mod)%mod; sum=0; mx=max(f[v][1],f[v][0]); if(mx==f[v][1])sum+=g[v][1]; if(mx==f[v][0])sum+=g[v][0]; l=l*sum%mod; L+=mx; }}int main(){ cin>>T>>P; while(T--) { cin>>n; ll u,v; xx(); for(int i=1;i<n;i++) { cin>>u>>v; Add(u,v); Add(v,u); } DP(1,0); ll sum,mx; mx=max(f[1][0],f[1][1]); sum=0; if(mx==f[1][0]) sum+=g[1][0],sum%=mod; if(mx==f[1][1]) sum+=g[1][1],sum%=mod; if(P==1) cout<<mx<<endl; if(P==2) cout<<mx<<" "<<sum<<endl; } return 0;}
清北模拟题4
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。