T0:难度不是太大，关键思维要灵活。
考试状态不是太好，改题时觉得没那么难。是可以想的。
T1:语文题。题意理解要去猜测含义。找特殊的地方。
卡特兰数，DP可做。
合法指全部匹配。
发现左边右边必须放的括号数一定。其余可以分配。
枚举给左边x个（，y个），则右边也已确定，
然后卡特兰即可。
Code：
#include<bits/stdc++.h> #define F(i,a,b) for(int i=a;i<=b;++i) #define LL long long #define pf(a) printf("%lld ",a) #define phn puts("") using namespace std; /** 特判题*/ #define int LL int n,m; #define N 100010 char s[N]; const int mod=1e9+7; int jc[N],inv[N]; int qpow(int x,int k){int s=1;for(;k;k>>=1,x=x*x%mod)if(k&1)s=s*x%mod;return s;} int MO(int x){return x<mod?x:x-mod;} void Parise(){ jc[0]=1;const int maxn=5e3; F(i,1,maxn)jc[i]=jc[i-1]*i%mod; inv[maxn]=qpow(jc[maxn],mod-2); for(int i=maxn;i>0;--i)inv[i-1]=inv[i]*i%mod; } int C(int x,int y){ if(x<y)return 0; if(x==y||y==0)return 1; return jc[x]*inv[y]%mod*inv[x-y]%mod; } int Cat(int x,int y){ return MO(C(x+y,y)-C(x+y,y-1)+mod); } signed main(){ Parise(); scanf("%lld%lld%s",&n,&m,s+1); int t=0,a=0,b=0; F(i,1,m){ if(s[i]=='(')++t; else if(t>0)--t; else ++a; } t=0; for(int i=m;i>0;--i){ if(s[i]==')')++t; else if(t>0)--t; else ++b; } LL ans=0; int res=n-m-a-b,resgl=res>>1; if(res<0||res&1){ return puts("0"),0; } F(x,0,resgl){ F(y,0,x){ ans=(ans+Cat(a+x,y)*Cat(b+resgl-y,resgl-x))%mod; } } ans=(ans%mod+mod)%mod; printf("%lld ",ans); } /* g++ 1.cpp ./a.out 2000 1 ( 4 4 (()) 4 3 ((( */
T2：DP好题。状态定义好题。
两种操作，*2和+1,求质因数分解中2的次数的期望。
题意转化：转化为2进制，求最低位的1,即lowbit在哪位的期望。
考试想的数位DP，但是很难写。
改变状态定义是打开思路，或优化DP的手段。
*2好处理，关键+1会进位。
所以状态要能够描述进位。
如果从最低位开始记录连续的1的个数，当加多了以后会对高位产生影响，
但是高位没有记录。
N<=200,+1的影响有限，最多+200。加到第9位最多一次。
因为高位可能有连续的1,所以不能只记录后9位。
由于要向高位进位，记录高位（9th开始）连续的1的信息。
开始没想到为什么要记录了连续的0.
因为如果后8位为0,则lowbit在高位。记录连续0可以知道lowbit。
那么f[n][s][j][k], f[200][1<<8][200+30][0/1]即可.
O(n*(n+30)*(2^8))
整理一下，看看状态是怎么描述这个过程的。
+1进位少，因为高位几乎不受影响，并且根据n<=200可以知道+1影响的范围，所以关注的只有低位是谁，和对高位的进位。
好的状态定义只关注需要关注的，从而描述出整个过程，建立出模型。
只关注低位也是一种类似取余的思想。
Code：
#include<bits/stdc++.h> #define F(i,a,b) for(int i=a;i<=b;++i) #define LL long long #define pf(a) printf("%d ",a) #define PF(a) printf("%lld ",a) #define phn puts("") using namespace std; int a,n; double P,ans; double f[202][1<<8][1<<8][2]; #define DP f[i][s][j] int bin[1<<8]; const double eqs=1e-4; int main(){ scanf("%d%d%lf",&a,&n,&P);P/=100; const int low=(1<<8)-1; int c=1,t=(a>>8)&1; for(int i=9;a>>i;++i){ if(((a>>i)&1)==t){/** 第9位开始*/ ++c; }else break; } f[1][a&low][c][t]=1.0; F(i,1,n)F(s,0,low)F(j,1,i+30){ t=s+1; if(t<=low){ F(k,0,1)f[i+1][t][j][k]+=DP[k]*(1-P); }else{ f[i+1][t&low][1][1]+=DP[0]*(1-P); f[i+1][t&low][j][0]+=DP[1]*(1-P); } t=(s>>7)&1; F(k,0,1){ if(t==k){ f[i+1][(s<<1)&low][j+1][t]+=DP[k]*P; }else{ f[i+1][(s<<1)&low][1][t]+=DP[k]*P; } } } double ans=0; for(int i=1,j=1;j<=8;++j,i<<=1)bin[i]=j; F(i,n+1,n+1)F(s,0,0)F(j,1,n+30){ ans+=DP[0]*(7+j+1)+DP[1]*8; } F(i,n+1,n+1)F(s,1,low)F(j,1,n+30){ ans+=(DP[0]+DP[1])*(bin[s&-s]-1); } printf("%.8lf ",ans); } /* g++ 2.cpp ./a.out 1 1 50 5 3 0 5 3 25 */
T3：
发现类似树，图论这些找性质的题不是总能想出来。没有思路时去找性质。从特殊到一般拓展。
手模，发现奇环一定不行。
判定奇环的技巧：黑白染色。
然后就不会了。。。
考虑每一个联通块。先考虑简单环。最长链是直径。
图的直径是最长的两点间最短路。
发现多个环套在一起，结论成立。
对于多个联通块，两条链可以合并，长度为总和。
考虑求直径。这里开始想麻烦了。观察数据范围，n*m<=1e8.
直接枚举所有点bfs.复杂度是没问题的。
Code：
#include<bits/stdc++.h> #define F(i,a,b) for(int i=a;i<=b;++i) #define pf(a) printf("%d ",a) #define phn puts("") using namespace std; /** 判奇环：黑白染色。 联通块直径：所有点bfs。 SB错误 应该输出ans，而不是mx 变成了最后一个联通块的直径。。。 */ int n,m; #define N 2002 #define M 400010 int to[M],fir[M],head[N],cnt; char vis[N]; int sta[N],top; int dl[N<<1],dis[N]; void add(int x,int y){to[++cnt]=y;fir[cnt]=head[x];head[x]=cnt;} int BW(int x){ for(int i=head[x],v;i;i=fir[i]){ if(vis[v=to[i]]==-1){ vis[v]=vis[x]^1; if(!BW(v))return 0; } else if(vis[v]==vis[x])return 0; } return 1; } void Push(int x){ sta[++top]=x;vis[x]=1; for(int i=head[x],v;i;i=fir[i])if(!vis[v=to[i]])Push(v); } int getdis(int x){ int hd=1,tl=0,mx=0; memset(dis,0x3f,sizeof(dis)); dl[tl=1]=x;dis[x]=0; while(hd<=tl){ int u=dl[hd++]; for(int i=head[u],v;i;i=fir[i]) if(dis[v=to[i]]>dis[u]+1) { mx=max(mx,dis[v]=dis[u]+1),dl[++tl]=v;} } return mx; } int main(){ scanf("%d%d",&n,&m); int x,y; F(i,1,m)scanf("%d%d",&x,&y),add(x,y),add(y,x); int ok=1; memset(vis,-1,sizeof(vis)); F(i,1,n){ if(vis[i]==-1){ vis[i]=1; if(!BW(i)){ok=0;break;} } } if(!ok)return puts("-1"),0; memset(vis,0,sizeof(vis)); int ans=0,mx; F(i,1,n)if(!vis[i]){ Push(i); mx=0; F(j,1,top)mx=max(mx,getdis(sta[j])); ans+=mx;top=0; } printf("%d ",ans); } /* g++ 3.cpp ./a.out 5 4 1 2 2 3 3 4 3 5 4 6 1 2 2 3 1 3 3 4 2 4 1 4 */