评测数据下载：https://yunpan.cn/cvVysDxL7F3KC （提取码：b07f）
分析：
T1 KMP+矩阵乘法（参考 BZOJ 1009 GT考试）
T2 斐波那契数列变形（数据很大，要用矩阵乘法），注意判一下
T3 不是匈牙利，而是树形dp，自己慢慢悟吧
T4 蒟蒻只会30分的做法：求图的直径，再/2，就是ans
更正：第三组：不存在相同的字符|str|=26，26<=n<=100
更正：输出的顺序保证a<b
更正：输出样例：0 1000000006
更正：模数1000000007
T1
60分代码：
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=1e5+7; const int mod=1e9+7; int n,cnt,len; char str[N],pat[N]; ll f[N]; void dfs(int now){ if(now==n){ if(++cnt>=mod) cnt%=mod; return ; } bool flag=(now<len-1)|(!equal(str+now-len+1,str+now,pat)); for(char x='a';x<='z';x++){ if(!flag&&x==pat[len-1]) continue; str[now]=x; dfs(now+1); } } ll fpow(ll a,ll p){ ll res=1; for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod; return res; } int main(){ freopen("helloworld.in","r",stdin); freopen("helloworld.out","w",stdout); while(scanf("%d",&n)==1){ scanf("%s",pat); len=strlen(pat); cnt=0; if(!n){puts("0");continue;} if(n<=5){ dfs(0); printf("%d ",cnt); } else if(len==1){ printf("%d ",fpow(25,n)); } else{ f[0]=1; for(int i=1;i<=len;i++) f[i]=f[i-1]*26%mod; for(int i=len;i<=n;i++) f[i]=(f[i-1]*26-f[i-len]+mod)%mod; printf("%d ",(int)f[n]); } } return 0; }
Std
AC代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 10100 #define MAXM 110 #define MOD 1000000007 int dp[MAXN][MAXM]; int fail[MAXM]; int trs[MAXN][26]; char str[MAXN]; inline void deal(int &x,int y){ x+=y; if(x>=MOD) x-=MOD; } int main(){ freopen("helloworld.in","r",stdin); freopen("helloworld.out","w",stdout); 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++) deal(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])%MOD; if(i)x=x*26%MOD; } printf("%d ",(int)((x-ans)%MOD+MOD)%MOD); } return 0; }
T2
AC代码：
#include<cstdio> #include<cstring> #include<iostream> #ifdef unix #define LL "%lld" #else #define LL "%I64d" #endif using namespace std; #define ll long long #define N 3 const ll mod=1e9+7; ll a[N][N],b[N][N],c[N][N]; ll p,q,a1,a2,n; inline const ll read(){ register ll x=0,f=1; register char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void work(){ a[1][1]=0;a[1][2]=q;a[2][1]=1;a[2][2]=p; b[1][1]=0;b[1][2]=q;b[2][1]=1;b[2][2]=p; while(n){ if(n&1){ for(int i=1;i<=2;i++){ for(int j=1;j<=2;j++){ for(int k=1;k<=2;k++){ c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod; } } } memcpy(a,c,sizeof c); memset(c,0,sizeof c); } for(int i=1;i<=2;i++){ for(int j=1;j<=2;j++){ for(int k=1;k<=2;k++){ c[i][j]=(c[i][j]+b[i][k]*b[k][j]%mod)%mod; } } } memcpy(b,c,sizeof c); memset(c,0,sizeof c); n>>=1; } } int main(){ freopen("gcd.in","r",stdin); freopen("gcd.out","w",stdout); p=1;q=1;a1=1;a2=2; n=read();ll bf=n; if(n==1){printf("1 1");return 0;} if(n%mod==0){printf("1 ");printf(LL,n-1);return 0;} n-=1; work(); ll ans1=(a[1][1]%mod+a[2][1]%mod)%mod; n=bf; work(); ll ans2=(a[1][1]%mod+a[2][1]%mod)%mod; if(ans1>ans2) swap(ans1,ans2); printf(LL,ans1);putchar(' ');printf(LL,ans2); return 0; }
T3
AC代码1：
#include<cstdio> #include<cstring> #include<vector> #define ll long long using namespace std; const int N=1e5+10; const int mod=1e9+7; const int inf=0x3f3f3f3f; struct node{ int v,next; }e[N<<1]; int T,opt,n,tot,head[N],q[N],fa[N],mx[N][2],dp[N][2]; inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void add(int x,int y){ e[++tot].v=y,e[tot].next=head[x],head[x]=tot; } void work(){ int h=0,t=1; q[1]=1; while(h<t){ int now=q[++h]; for(int i=head[now];i;i=e[i].next){ int v=e[i].v; if(v==fa[now]) continue; fa[v]=now; q[++t]=v; } } for(int i=t;i;i--){ int now=q[i]; dp[now][0]=0; int mx0=0,mx1=0,dp0=1,dp1=0; for(int i=head[now];i;i=e[i].next){ int v=e[i].v; if(v==fa[now]) continue; mx0+=mx[v][1]; dp0=(ll)dp0*dp[v][1]%mod; } dp[now][0]=dp0; mx[now][0]=mx0; vector<int> vec1,vec2; int delta=inf; for(int i=head[now];i;i=e[i].next){ int v=e[i].v; if(v==fa[now]) continue; vec1.push_back(dp[v][1]); vec2.push_back(dp[v][1]); delta=min(delta,mx[v][1]-mx[v][0]); } int vsize=vec1.size(); for(int i=1;i<vsize;i++) vec1[i]=(ll)vec1[i]*vec1[i-1]%mod; for(int i=vsize-2;i>=0;i--) vec2[i]=(ll)vec2[i]*vec2[i+1]%mod; int cnt=0; for(int i=head[now];i;i=e[i].next){ int v=e[i].v; if(v==fa[now]) continue; if(mx[v][1]-mx[v][0]==delta) dp1=(dp1+(ll)(cnt?vec1[cnt-1]:1)*(cnt==vsize-1?1:vec2[cnt+1])%mod*dp[v][0])%mod; cnt++; } mx[now][1]=mx0-delta+1; dp[now][1]=dp1; if(mx[now][0]==mx[now][1]) dp[now][1]=(dp[now][0]+dp[now][1])%mod; if(mx[now][0]>mx[now][1]) dp[now][1]=dp[now][0],mx[now][1]=mx[now][0]; } } int main(){ freopen("hungary.in","r",stdin); freopen("hungary.out","w",stdout); T=read();opt=read(); while(T--){ memset(dp,0,sizeof dp); memset(mx,0,sizeof mx); memset(fa,0,sizeof fa); memset(head,0,sizeof head); tot=0; n=read(); for(int i=1,x,y;i<n;i++) x=read(),y=read(),add(x,y),add(y,x); work(); opt==1?printf("%d ",mx[1][1]):printf("%d %d ",mx[1][1],dp[1][1]); } return 0; }
ylf‘sAC代码：
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #define maxn 100010 #define mod 1000000007 #define ll long long using 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]; ll init(){ ll x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='0')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } void Add(ll from,ll to){ num++;e[num].v=to; e[num].pre=head[from]; head[from]=num; } void Clear(){ 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);//x不连儿子 儿子们可连可不连 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; } //x连某个儿子 这个不选 其他的连或者不连 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() { freopen("hungary.in","r",stdin); freopen("hungary.out","w",stdout); T=init();P=init(); while(T--){ n=init(); ll u,v;Clear(); for(int i=1;i<n;i++){ u=init();v=init(); 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; }
T4
30分代码：
#include<cstdio> using namespace std; const int N=205; const int inf=0x3f3f3f3f; inline int max(int a,int b){return a>b?a:b;} inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int f[N][N]; int main(){ freopen("radius.in","r",stdin); freopen("radius.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=inf; for(int i=1,x,y,z;i<=m;i++){ x=read();y=read();z=read(); if(f[x][y]>z) f[y][x]=f[x][y]=z; } for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i!=j&&j!=k&&i!=k){ if(f[i][j]>f[i][k]+f[k][j]){ f[i][j]=f[i][k]+f[k][j]; } } } } } int d=0; for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++){ if(f[i][j]!=inf) d=max(d,f[i][j]); } } double ans=d/2.0; printf("%.2lf",ans); return 0; }
Std
AC代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXV 170000 #define MAXE 170000 #define MAXN 900 #define PROB "radius" #define INF 0x3f3f3f3f struct Edge{ int np,val; Edge *next; bool flag; }E[MAXE],*V[MAXV]; int m,n; int map[MAXN][MAXN]; struct aaa { int x,y,d; }el[MAXE]; int tope=-1,topl=-1; void addedge(int x,int y,int z){ el[++topl].x=x; el[topl].y=y; el[topl].d=z; E[++tope].np=y; E[tope].val=z; E[tope].next=V[x]; V[x]=&E[tope]; E[++tope].np=x; E[tope].val=z; E[tope].next=V[y]; V[x]=&E[tope]; } void init(){ int i,j,k; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ for(k=1;k<=n;k++){ if(map[j][k]>map[j][i]+map[i][k]) map[j][k]=map[j][i]+map[i][k]; } } } } pair<int,int> seg[MAXN]; int tops=-1,rg; void set_range(int x){ tops=-1; rg=x; } void add_seg(int x,int y){ tops++; if(x>y)throw "E"; seg[tops].first=x; seg[tops].second=y; } bool full(){ int i,x=0; sort(seg,&seg[tops+1]); for(i=0;i<=tops;i++){ if(x<seg[i].first)return false; if(x>seg[i].second)continue; x=seg[i].second+1; } if(x>rg)return true; return false; } int main(){ freopen(PROB".in","r",stdin); freopen(PROB".out","w",stdout); int i,j,k,x,y,z; scanf("%d%d",&n,&m); memset(map,INF,sizeof(map)); for(i=0;i<m;i++){ scanf("%d%d%d",&x,&y,&z); addedge(y,x,z*2); map[x][y]=map[y][x]=min(map[x][y],z*2); } for(i=1;i<=n;i++) map[i][i]=0; init(); int l,r,mid; l=0;r=10000006; int flag=-1; while (l+1<r){ mid=(l+r)/2; flag=0; for(i=0;i<=topl;i++){ set_range(el[i].d); for(j=1;j<=n;j++){ x=mid-map[el[i].x][j]; y=mid-map[el[i].y][j]; if(x<0&&y<0){ add_seg(0,el[i].d); break; } if(x>=el[i].d||y>=el[i].d) continue; if(x+y>=el[i].d) continue; add_seg(max(0,x+1),min(el[i].d,el[i].d-y-1)); } if(!full())flag=1; if(flag==1) break; } if(flag==0){ l=mid; continue; } if(flag==1){ r=mid; continue; } } double ans=r/2.0; printf("%.2lf",ans); return 0; }