100+10+20=130 rank 7

考试时T1先推了30+30的暴力高精，后来瞎代式子，发现答案就是Cmn+m−Cm−1n+m

T2情况太多了，脑子特别乱，照着3个样例调过了3个样例就WA了。。

正解又是欧拉图上各种乱搞。

T3没想到状压深度，20分暴力，正解树上的状压dp

T1

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 5005using namespace std;struct bignum{    int len,a[5005];    bignum(){
    len=0;memset(a,0,sizeof a);}    void print(){        printf("%d",a[len]);        for(int i=len-1;i;i--)            printf("%04d",a[i]);        printf("\n");    }    bignum operator * (bignum b){        bignum c;        c.len=len+b.len;        for(int i=1;i<=len;i++){            for(int j=1;j<=b.len;j++){                c.a[i+j-1]+=a[i]*b.a[j];                c.a[i+j]+=c.a[i+j-1]/10000;                c.a[i+j-1]%=10000;            }        }        while(c.a[c.len+1])c.len++;        while(!c.a[c.len])c.len--;        return c;    }    bignum operator + (bignum b){        bignum c;        c.len=max(len,b.len);        for(int i=1;i<=c.len;i++){            c.a[i]+=a[i]+b.a[i];            c.a[i+1]+=c.a[i]/10000;            c.a[i]%=10000;        }        while(c.a[c.len+1])c.len++;        return c;    }    bignum operator - (bignum b){        bignum c;        c.len=len;        for(int i=1;i<=len;i++){            c.a[i]+=a[i]-b.a[i];            if(c.a[i]<0){                c.a[i]+=10000;                c.a[i+1]--;            }        }        while(!c.a[c.len])c.len--;        return c;    }    bignum operator = (int b){        for(int i=1;i<=len;i++)a[i]=0;        len=0;        while(b){            a[++len]=b%10000;            b/=10000;        }        return *this;    }}ans1,ans2,ans;int num[10050];void work(int x,int y){    for(int i=2;i*i<=x;i++)        if(x%i==0){            while(x%i==0){                num[i]+=y;                x/=i;            }        }    if(x!=1)num[x]+=y;}int n,m;int main(){    scanf("%d%d",&n,&m);    bignum now;    ans1=1;    for(int i=n+1;i<=m+n;i++)work(i,1);    for(int i=2;i<=m;i++)work(i,-1);    for(int i=1;i<=m+n;i++)        if(num[i]){            now=i;            while(num[i]){                if(num[i]&1)ans1=ans1*now;                now=now*now;num[i]>>=1;            }        }    memset(num,0,sizeof num);    ans2=1;    for(int i=n+2;i<=m+n;i++)work(i,1);    for(int i=2;i<=m-1;i++)work(i,-1);    for(int i=1;i<=m+n;i++)        if(num[i]){            now=i;            while(num[i]){                if(num[i]&1)ans2=ans2*now;                now=now*now;num[i]>>=1;            }        }    ans=ans1-ans2;    ans.print();    return 0;}
         
        
       
      
     

T2

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 101050using namespace std;int n,m,fa[N],out[N],vis1[N],vis2[N],a[N],tot,sig,ans;int find(int x){    if(fa[x]==x)return x;    return fa[x]=find(fa[x]);}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++) fa[i]=i;    for(int i=1,u,v;i<=m;i++){        scanf("%d%d",&u,&v);        if(!u){u=++n;fa[u]=u;}        if(!v){v=++n;fa[v]=v;}        out[u]++; out[v]++;        fa[find(u)]=find(v);    }    for(int i=1;i<=n;i++){        if(!out[i])continue;        find(i);        if(fa[i]==i)a[++tot]=i;        if(out[i]&1) sig++,vis1[fa[i]]=1;        if(out[i]>2) vis2[fa[i]]=1,ans++;    }    if(tot!=1)        for(int i=1;i<=tot;i++)            if(!vis1[a[i]]){                sig+=2;                if(!vis2[a[i]])ans++;            }    ans+=sig/2;    printf("%d\n",ans);    return 0;}
         
        
       
      
     

T3

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int n,m,bit[22],tot,ans;int w[2055][25],p[2055][25],f[2055][2055];void dfs(int rt,int dep,int sta){    memset(f[rt],0,sizeof f[rt]);    if(dep==n){        for(int i=1;i
          
           >1);i++){ if(i>m)break; for(int j=0;j<=(size>>1);j++){ if(i+j>m)break; f[rt][i+j]=max(f[rt][i+j],f[rt<<1][i]+f[rt<<1|1][j]); } } dfs(rt<<1,dep+1,sta|bit[dep-1]); dfs(rt<<1|1,dep+1,sta|bit[dep-1]); for(int i=0;i<=(size>>1);i++){ if(i>m)break; for(int j=0;j<=(size>>1);j++){ if(i+j>m)break; f[rt][i+j]=max(f[rt][i+j],f[rt<<1][i]+f[rt<<1|1][j]); } } }int main(){ scanf("%d%d",&n,&m); bit[0]=1; for(int i=1;i<=20;i++)bit[i]=bit[i-1]<<1; tot=bit[n]-1; for(int i=1,now;i<=bit[n-1];i++) for(int j=n-1;j>=1;j--) scanf("%d",&w[bit[n-1]-1+i][j]); for(int i=1,now;i<=bit[n-1];i++) for(int j=n-1;j>=1;j--) scanf("%d",&p[bit[n-1]-1+i][j]); dfs(1,1,0); for(int i=0;i<=m;i++) ans=max(ans,f[1][i]); printf("%d\n",ans); return 0;}
          
         
        
       
      
     

这几天连着挂，相对比较稳定，233。

考试时一定要多想，不能怕，多拿分是关键。