NOIP2015提高组题解

\(D1T1\) 神奇的幻方\((OK)\)

\(D1T2\) 信息传递\((OK)\)

\(D1T3\) 斗地主\((OK)\)

\(D1T4\) 斗地主增强版\((OK)\)

\(D2T1\) 跳石头\((OK)\)

\(D2T2\) 子串\((OK)\)

\(D2T3\) 运输计划

只剩下一道毒瘤题了,\(NOIP\)每年都会有一道大数据结构题劝退\(?\)

\(D1T1\)就开一个二维数组从第一个数开始根据题意模拟就好了.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int a[40][40];
int main(){
    int n=read(),i=1,j=n/2+1;a[i][j]=1;
    for(int now=2;now<=n*n;++now){
        if(i==1&&j!=n){
            a[n][j+1]=now;
            i=n;j=j+1;continue;
        }
        if(j==n&&i!=1){
            a[i-1][1]=now;
            i=i-1;j=1;continue;
        }
        if(i==1&&j==n){
            a[2][j]=now;
            i=2;j=n;continue;
        }
        if(i!=1&&j!=n){
            if(!a[i-1][j+1]){
                a[i-1][j+1]=now;
                i=i-1;j=j+1;
            }
            else{
                a[i+1][j]=now;
                i=i+1;j=j;
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

\(D1T2\)都知道答案就是图中最小环的长度,那么怎么找到图中的最小环呢?注意这是有向图,不就是\(tarjan\)模板题了么?然后还有\(dfs\),并查集等其它优秀做法,我不会.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=200005;
int a[N];
int tim,top,num,dfn[N],low[N],st[N],color[N],size[N];
inline void tarjan(int u){
    dfn[u]=low[u]=++tim;st[++top]=u;
    int v=a[u];
    if(!dfn[v]){
        tarjan(v);
        low[u]=min(low[u],low[v]);
    }
    else if(!color[v]){
        low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        color[u]=++num;
        ++size[num];
        while(st[top]!=u){
            color[st[top]]=num;
            ++size[num];--top;
        }
        --top;
    }
}
int main(){
    int n=read(),ans=n;
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
    for(int i=1;i<=num;++i)if(size[i]>1)ans=min(ans,size[i]);
//注意不要把大小为1的强连通分量(环)算进去了
    printf("%d\n",ans);
    return 0;
}

\(D1T3\)这道题我大概做了两三个小时,被坑的地方发在本题的讨论区了(就是顺子不是越长越好\(!!!\)).然后再稍微注意一下搜索(出牌)顺序.最后当你把所有什么单顺子,双顺子,三个的,四个的都出完了之后,剩下的每种牌一定要么是1个,要么是2个,这时直接统计个数累加进答案即可,不要每次再搜下去了,会\(T\)飞.

写完这道题之后又把代码直接交到数据加强版,发现只错了两个点,把数据下下来之后(嗯,面对数据编程),发现一个点是两个炸弹一次出完(即一个炸弹带两对牌),还有一个点忘记了,总之就是我之前的程序写的带牌默认带的是不同种类的牌,稍微改一个地方就好了.

直接放加强版\(AC\)代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int n,ans,sum[20];
inline int check3(){
    for(int i=3;i<=13;++i)
        if(sum[i]>=3&&sum[i+1]>=3)return i;
    return 0;
}
inline int check2(){
    for(int i=3;i<=12;++i)
        if(sum[i]>=2&&sum[i+1]>=2&&sum[i+2]>=2)return i;
    return 0;
}
inline int check_sz(){
    for(int i=3;i<=10;++i)
        if(sum[i]&&sum[i+1]&&sum[i+2]&&sum[i+3]&&sum[i+4])return i;
    return 0;
}
inline int check_zd(){
    for(int i=1;i<=14;++i)
        if(sum[i]==4)return i;
    return 0;
}
inline int check_san(){
    for(int i=1;i<=14;++i)
        if(sum[i]>=3)return i;
    return 0;
}
inline void dfs(int now){
    if(now>=ans)return;
    int sz=check_sz();
    if(sz){//单顺子
        int i=sz,cnt=0;
        for(;i<=15;++i){
            if(sum[i]){
                ++cnt;
                if(cnt>=5){//不是越长越好,所以每种合法长度都要搜
                    for(int j=sz;j<=i;++j)--sum[j];
                    dfs(now+1);
                    for(int j=sz;j<=i;++j)++sum[j];
                }
            }
            else break;
        }
    }
    int y=check2();
    if(y){//双顺子
        int i=y,cnt=0;
        for(;i<=15;++i){
            if(sum[i]>=2)sum[i]-=2,cnt+=2;
            else break;
        }
        dfs(now+1);
        for(int j=y;j<i;++j)sum[j]+=2;
    }
    int x=check3();
    if(x){//三顺子(不是飞机,不能带牌)
        int i=x,cnt=0;
        for(;i<=15;++i){
            if(sum[i]>=3)sum[i]-=3,cnt+=3;
            else break;
        }
        dfs(now+1);
        for(int j=x;j<i;++j)sum[j]+=3;
    }
    int san=check_san();
    if(san){//三个带一个或一对,一对不能是王炸
        sum[san]-=3;
        for(int i=2;i<=14;++i){
            if(sum[i]>=2){
                sum[i]-=2;
                dfs(now+1);
                sum[i]+=2;
            }
        }
        for(int i=0;i<=14;++i){
            if(sum[i]>=1){
                sum[i]-=1;
                dfs(now+1);
                sum[i]+=1;
            }
        }
        sum[san]+=3;
    }
    int zd=check_zd();
    if(zd){//四个带两个或两对,同样一对不能是王炸
        sum[zd]-=3;//四个可以先做3个的带
        for(int i=2;i<=14;++i){
            if(sum[i]>=2){
                sum[i]-=2;
                dfs(now+1);
                sum[i]+=2;
            }
        }
        for(int i=0;i<=14;++i){
            if(sum[i]>=1&&i!=zd){
                sum[i]-=1;
                dfs(now+1);
                sum[i]+=1;
            }
        }
        sum[zd]+=3;
        sum[zd]-=4;//再来搜索做4个的带
        for(int i=2;i<=14;++i){
            if(sum[i]>=2){
                sum[i]-=2;
                for(int j=i;j<=14;++j){
                    if(sum[j]>=2){
                        sum[j]-=2;
                        dfs(now+1);
                        sum[j]+=2;
                    }
                }
                sum[i]+=2;
            }
        }
        for(int i=0;i<=14;++i){
            if(sum[i]>=1){
                --sum[i];
                for(int j=i;j<=14;++j){
                    if(sum[j]>=1){
                        --sum[j];
                        dfs(now+1);
                        ++sum[j];
                    }
                }
                ++sum[i];
            }
        }
        sum[zd]+=4;
    }
    for(int i=0;i<=14;++i)if(sum[i])++now;
    ans=min(ans,now);
}
int main(){
    int T=read(),n=read();
    while(T--){
        for(int i=0;i<=15;++i)sum[i]=0;
        for(int i=1;i<=n;++i){
            int x=read(),y=read();
            if(x==1)x=14;++sum[x];
        }
        ans=n;dfs(0);printf("%d\n",ans);
    }
    return 0;
}

\(D2T1\)恩,就是二分答案的模板题了.二分 最小跳跃距离的最大值\(mid\)后,如果有两个石头的距离小于\(mid\),那么就把其中后面的那块石头去掉(显然去后面的比去前面的更优).

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=50005;
int L,n,m,a[N],b[N];
inline bool check(int mid){
    for(int i=1;i<=n;++i)b[i]=a[i];b[n+1]=L;
    int cnt=0;
    for(int i=1;i<=n+1;++i){
        if(b[i]-b[i-1]<mid){
            ++cnt;b[i]=b[i-1];
        }
    }
    return cnt<=m;
}
int main(){
    L=read(),n=read(),m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    int l=0,r=L,ans,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

\(D2T2\)一道很好的\(dp\),自己做了一下午都不会,看完题解豁然开朗.设\(f[i][j][k][0/1]\)表示当前考虑到\(A\)串的第\(i\)个字符,匹配到\(B\)串的第\(j\)个字符,这\(j\)个字符是划分成了\(k\)段选出来的,当前第\(i\)个字符选/不选时的方案数.

\(f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]\),当前第\(i\)个字符不选的话,不管你前面第\(i-1\)个字符选或者不选都能转移过来.

当\(A[i]=B[j]\)时,\(f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k-1][1]+f[i-1][j-1][k][1]\),如果选择当前第\(i\)个字符,而且这个字符正好能够匹配,那么如果这个字符单独成段,那么不管你前面第\(i-1\)个字符选或者不选都能转移过来(即\(f[i-1][j-1][k-1][0]+f[i-1][j-1][k-1][1]\)),如果当前这个字符跟上一个字符一起成段,那么上面那个字符必选(即\(f[i-1][j-1][k][1]\)).

当\(A[i]\)不等于\(B[j]\)时,\(f[i][j][k][1]=0.\)

然后直接开数组\(1000*1000*200*2\)是开不下的,根据套路(\(i\)只能从\(i-1\)转移过来的时候),第一维要么滚动要么滚掉.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int mod=1e9+7;
const int N=1005;
int n,m,K;ll f[2][N][205][2];
char s1[N],s2[N];
int main(){
    n=read();m=read();K=read();
    scanf("%s%s",s1+1,s2+1);
    f[0][0][0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=min(i,m);++j){
            for(int k=0;k<=min(j,K);++k){
                f[i&1][j][k][0]=(f[(i-1)&1][j][k][0]+f[(i-1)&1][j][k][1])%mod;
                if(s1[i]==s2[j])f[i&1][j][k][1]=(f[(i-1)&1][j-1][k][1]+f[(i-1)&1][j-1][k-1][0]+f[(i-1)&1][j-1][k-1][1])%mod;
                else f[i&1][j][k][1]=0;
            }       
        }
    }
    printf("%lld\n",(f[n&1][m][K][0]+f[n&1][m][K][1])%mod);
    return 0;
}

NOIP2015提高组题解

原文：https://www.cnblogs.com/PPXppx/p/11779233.html