因为一些事情补了三天终于补完辣><

 

---

 

 

DAY1

T1神奇的幻方

超级水的模拟题......一次过

#include
      
       #include
       
        #include
        
         using namespace std;int map[40][40]={
    0};int main(){    int n,head[2];    scanf("%d",&n);    map[1][n/2+1]=1;    head[0]=1;head[1]=n/2+1;    for(int i=2;i<=n*n;i++)    {        if(head[0]==1&&head[1]!=n){map[n][head[1]+1]=i;head[0]=n;head[1]+=1;continue;}        if(head[0]!=1&&head[1]==n){map[head[0]-1][1]=i;head[0]-=1;head[1]=1;continue;}        if(head[0]==1&&head[1]==n){map[head[0]+1][head[1]]=i;head[0]+=1;continue;}        if(!map[head[0]-1][head[1]+1]){map[head[0]-1][head[1]+1]=i;head[0]-=1;head[1]+=1;continue;}        map[head[0]+1][head[1]]=i;head[0]+=1;    }    for(int j=1;j<=n;j++)    {        for(int i=1;i<=n;i++)            printf("%d ",map[j][i]);        printf("\n");    }    return 0;}
        
       
      

T2信息传递

挺巧妙的一个dfs，原理就是同一个环里每个点走一圈回到本身的距离相等，再注意判断是否已经在已知环里即可。

#include
      
       #include
       
        #include
        
         #include
         
          const int M=2e5+10;using namespace std;int n,a[M],len,t=M,huan[M],h=0,now=0;int ok[M];int read(){    int f=1,ans=0;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}    return ans*f;}void dfs(int x){    ok[x]=now;    huan[x]=h;    if(ok[a[x]]){        if(huan[a[x]]==h)t=min(t,now-ok[a[x]]+1);        return;    }    now++;    dfs(a[x]);}int main(){    n=read();    for(int i=1;i<=n;i++)a[i]=read();    for(int i=1;i<=n;i++)    {        if(!ok[i]){now++;h++;dfs(i);}    }    printf("%d",t);    return 0;}
         
        
       
      

T3斗地主

这一年的NOIP提高最后补完的一道题...之前一直不敢写，但是zsn写完后说其实没有想象中的那么难，所以我的代码基本也是她的思路吧（orz zsnuo)，挺好理解的dfs，就是自己想不到:(

#include
      
       #include
       
        #include
        
         using namespace std;int sum[15],tot,a[5];int read(){    int ans=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}    return ans*f;}int da(){    bool f=0;    if(sum[0]==2)f=true;    memset(a,0,sizeof(a));    for(int i=0;i<=13;i++)a[sum[i]]++;    int num=0;    while(a[4]&&a[2]>=2){f=false;a[4]--;a[2]-=2;num++;}    while(a[4]&&a[1]>=2){a[4]--;a[1]-=2;num++;}    while(a[4]&&a[2]){f=false;a[4]--;a[2]--;num++;}    if(f)a[2]--,num++;    while(a[3]&&a[2]){a[3]--;a[2]--;num++;}    while(a[3]&&a[1]){a[3]--;a[1]--;num++;}    return num+a[1]+a[2]+a[3]+a[4];}void dfs(int st){    if(st>=tot)return;    int t=da();    tot=min(tot,st+t);    for(int i=2;i<=13;i++){        int ne=i;        while(sum[ne]>=3)ne++;        if(ne-i>=2){            for(int j=i+1;j<=ne-1;j++){                for(int k=i;k<=j;k++)sum[k]-=3;                dfs(st+1);                for(int k=i;k<=j;k++)sum[k]+=3;            }        }    }    for(int i=2;i<=13;i++){        int ne=i;        while(sum[ne]>=2)ne++;        if(ne-i>=3){            for(int j=i+2;j<=ne-1;j++){                for(int k=i;k<=j;k++)sum[k]-=2;                dfs(st+1);                for(int k=i;k<=j;k++)sum[k]+=2;            }        }    }    for(int i=2;i<=13;i++){        int ne=i;        while(sum[ne])ne++;        if(ne-i>=5){            for(int j=i+4;j<=ne-1;j++){                for(int k=i;k<=j;k++)sum[k]--;                dfs(st+1);                for(int k=i;k<=j;k++)sum[k]++;            }        }    }}int main(){    int tt,n,ai,bi;    tt=read();n=read();    while(tt--){        memset(sum,0,sizeof(sum));        for(int i=1;i<=n;i++){            ai=read();bi=read();            if(ai==1)sum[13]++;                else if(ai)sum[ai-1]++;                    else sum[0]++;        }        tot=25;        dfs(0);        printf("%d\n",tot);    }    return 0;}
        
       
      

 

---

 

 

Day2

T1跳石头

这道题直接二分跳跃的最大距离，然后判断能否通过移走不超过m块石头来使得最大跳跃距离不小于当前答案。当然二分的细节需要特别注意。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int a[50008];int read(){    int ans=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}    return ans*f;}int main(){    int n,m,len,i,j,aa;    len=read();n=read();m=read();    for(int i=1;i<=n;i++)a[i]=read();    a[0]=0;a[n+1]=len;    int l=0,r=len;    while(l
          
           >1;        while(i<=n)        {            j=i+1;            while(a[j]-a[i]
           
            <=n+1)j++; aa+=j-i-1; i=j; } if(aa<=m)l=mid; else r=mid; } printf("%d",l); return 0;}
           
          
         
        
       
      

T2子串

感觉自己的dp很弱，可能没法讲得很清楚QAQ，所以还是直接甩别人的吧~

然后因为第一维都只和i-1有关，所以直接开成滚动的，每次再^1就不会MLE辣。

#include
      
       #include
       
        #include
        
         const int mod=1e9+7;using namespace std;char a[1002],b[202];int f[2][202][202],s[2][202][202];int main(){    int n,m,k,no=1;    scanf("%d %d %d",&n,&m,&k);    scanf("%s %s",a+1,b+1);    f[0][0][0]=1;    for(int i=1;i<=n;i++){        f[no][0][0]=1;        for(int j=1;j<=i&&j<=m;j++){            for(int kk=1;kk<=k&&kk<=j;kk++){                if(a[i]==b[j])s[no][j][kk]=(s[no^1][j-1][kk]+f[no^1][j-1][kk-1])%mod;                else s[no][j][kk]=0;                f[no][j][kk]=(f[no^1][j][kk]+s[no][j][kk])%mod;            }        }        no^=1;    }    printf("%d",f[no^1][m][k]);    return 0;}
        
       
      

T3运输计划

没错最后一题日常看......(Zsnuo dalao太强啦><)二分答案+lca，看完基本就懂啦！

#include
      
       #include
       
        #include
        
         using namespace std;const int N=3e5+5;struct point{    int next,to,w;}e[N*2];int n,m,ai,bi,ci,tot=0;int deep[N],gr[N][22],dis[N][22];int st[N],ed[N],fa[N],dist[N],first[N],sum[N];bool ok[N];int read(){    int f=1,ans=0;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}    return ans*f;}void ins(int u,int v,int wi){    tot++;e[tot].next=first[u];e[tot].to=v;first[u]=tot;e[tot].w=wi;    tot++;e[tot].next=first[v];e[tot].to=u;first[v]=tot;e[tot].w=wi;}void dfs(int x){    ok[x]=1;    for(int i=1;(1<
         
          <=deep[x];i++){        gr[x][i]=gr[gr[x][i-1]][i-1];        dis[x][i]=dis[x][i-1]+dis[gr[x][i-1]][i-1];    }    for(int i=first[x];i;i=e[i].next){        int p=e[i].to;        if(ok[p])continue;        gr[p][0]=x;        deep[p]=deep[x]+1;        dis[p][0]=e[i].w;        dfs(p);    }}int lca(int x,int y,int num){    if(deep[x]>deep[y])swap(x,y);    int d=deep[y]-deep[x];    for(int i=0;(1<
          
           <=d;i++)        if((1<
           
            =0;i--){ if((1<
            
             <=deep[x]&&gr[x][i]!=gr[y][i]){ dist[num]+=dis[x][i]+dis[y][i]; x=gr[x][i];y=gr[y][i]; } } dist[num]+=dis[x][0]+dis[y][0]; return gr[x][0];}void add(int x){ for(int i=first[x];i;i=e[i].next){ if(e[i].to==gr[x][0])continue; add(e[i].to); sum[x]+=sum[e[i].to]; }}bool check(int x){ int num=0,mx=0; for(int i=1;i<=n;i++)sum[i]=0; for(int i=1;i<=m;i++) if(dist[i]>x){ num++;mx=max(mx,dist[i]-x); sum[st[i]]++;sum[ed[i]]++;sum[fa[i]]-=2; } add(1); for(int i=1;i<=n;i++) if(sum[i]==num&&mx<=dis[i][0])return 1; return 0;}int main(){ n=read();m=read(); for(int i=1;i<=n-1;i++){ ai=read();bi=read();ci=read(); ins(ai,bi,ci); } dfs(1); for(int i=1;i<=m;i++){ st[i]=read();ed[i]=read(); fa[i]=lca(st[i],ed[i],i); } int L=0,R=0; for(int i=1;i<=m;i++)R=max(R,dist[i]); while(L<=R){ int mid=(L+R)>>1; if(check(mid))R=mid-1; else L=mid+1; } printf("%d",L); return 0;}