考试状态：

我今天抽签看了洛谷的…

这我能怂？？？凶中带吉，我怕考试？？我！不！怕！

看着整个机房的男同学们，我明白我是不会触发我的忌了。很好，开刷。

A. 【NOIP2012普及组真题】 质因数分解

麦芽的香气。行家啊！这题刷过的吧！！这个数据看起来是有点吓人，然而…

并没什么卵用。就是吓吓你。

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

int main(){

//    freopen("prime.in","r",stdin);

//    freopen("prime.out","w",stdout);

    int n;

    cin>>n;

    for(int i=;i<=n;i++){

        if(n%i==){

                cout<<n/i;

                return ;

        }

    }

}

仔细看题，看清楚了题目，这题就是个连printf都懒得用的水题…

好的下一个。

B. 【NOIP2012普及组真题】 寻宝

这种玩意…边看题边写…不断重构…不断修改…不断Debug

好吧，用搜索模拟一下其实就好了。

因为是边看边写，所以代码有点冗杂，有许多压根用不到的数据我也顺手存了下来。没事，反正一点点数据并不会爆炸。

#include<iostream>

#include<cstdio>

const int Mod=;

using namespace std;

struct BedRoom{

    bool Up;

    int Pointer;

    int Num;

    int Next;

}Building[][];

int Ftot[];

int n,m,x,y,ans;

void dfs(int Floor,int Room){

    //cout<<"time check "<<Floor<<" "<<Room<<" "<<ans<<endl;

    if(Floor==n){

        //cout<<"End"<<endl;

        ans+=Building[Floor][Room].Pointer;

        ans%=Mod;

        return;

    }

    int Go=Building[Floor][Room].Pointer;

    //cout<<"Go "<<Go;

    ans+=Go;

    ans%=Mod;

    if(Building[Floor][Room].Up==true){

        Go--;

    }

    //Go%=Ftot[Floor];

    int Index=Room;

    for(int i=;i<=Go;){

        //if(dfs(Floor,Building[Floor][Room].Next))

        Index=Building[Floor][Index].Next;

        if(Building[Floor][Index].Up){

            i++;

        }

    }

    dfs(Floor+,Index);

}

int main(){

//    freopen("treasure.in","r",stdin);

//    freopen("treasure.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++){

        for(int j=;j<m;j++){

            scanf("%d%d",&x,&y);

            Building[i][j].Up=x;

            if(x){

                Ftot[i]++;

            }

            Building[i][j].Num=j;

            Building[i][j].Pointer=y;

            Building[i][j].Next=j+;

            if(j+==m){

                Building[i][j].Next=;

            }

        }

    }

    scanf("%d",&x);

    dfs(,x);

    printf("%d",ans);

}

看起来是简单轻巧…实际上显然这题是需要小小的优化的。一看那个指示牌上的爆炸数据就知道，如果直接傻兮兮的模拟， 你可能会疯狂跟他绕圈子，最后的结果嘛…当然你是TLE啦！

怎么优化？把指示牌上的数字MOD掉这一层所有的有楼梯的房间的个数就好。虽然我刚打完就想到了这个优化点，并且去做了优化。但发现直接取模之后居然疯狂WA！

无奈之下，只好放弃优化。先拿下模拟辛苦分好了。

出乎意料，辛苦分给的并不低。足足五十分呀同志，一半呐！！

（废话真多）

经过WKJ的指点，所以其实在取模的时候要考虑下直接Mod出0的情况，直接成0的话就会发生奇妙的错误。所以我们不妨把他先-1，最后再加回来就是了。

#include<iostream>

#include<cstdio>

const int Mod=;

using namespace std;

struct BedRoom{

    bool Up;

    int Pointer;

    int Num;

    int Next;

}Building[][];

int Ftot[];

int n,m,x,y,ans;

void dfs(int Floor,int Room){

    //cout<<"time check "<<Floor<<" "<<Room<<" "<<ans<<endl;

    if(Floor==n){

        //cout<<"End"<<endl;

        ans+=Building[Floor][Room].Pointer;

        ans%=Mod;

        return;

    }

    int Go=Building[Floor][Room].Pointer;

    //cout<<"Go "<<Go;

    ans+=Go;

    ans%=Mod;

    if(Building[Floor][Room].Up==true){

        Go--;

    }

    Go=(Go-)%Ftot[Floor]+;

    int Index=Room;

    for(int i=;i<=Go;i=i){

        //if(dfs(Floor,Building[Floor][Room].Next))

        Index=Building[Floor][Index].Next;

        if(Building[Floor][Index].Up){

            i++;

        }

    }

    dfs(Floor+,Index);

}

int main(){

//    freopen("treasure.in","r",stdin);

//    freopen("treasure.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++){

        for(int j=;j<m;j++){

            scanf("%d%d",&x,&y);

            Building[i][j].Up=x;

            if(x==){

                Ftot[i]++;

            }

            Building[i][j].Num=j;

            Building[i][j].Pointer=y;

            Building[i][j].Next=j+;

            if(j+==m){

                Building[i][j].Next=;

            }

        }

    }

    scanf("%d",&x);

    dfs(,x);

    printf("%d",ans);

}

还行吧。代码有点冗杂，但在脑海里的逻辑还是很清晰的。

下一个。

C. 【NOIP2012普及组真题】 摆花

如果说考到以前刷过的作业是幸运，那这个简直就是幸运的1024次方了。

以前的考试考过。

#include<iostream>

#include<cstdio>

using namespace std;

const int MAXN=;

int n,m;

int a[MAXN];

int dp[MAXN][MAXN];

int main(){

    cin>>n>>m;

    for(int i=;i<=n;i++){

        cin>>a[i];

    }

    dp[][]=;

    for(int i=;i<=n;i++)

        for(int k=;k<=a[i];k++)

            for(int j=;j<=m-k;j++)

                dp[i][j+k]=(dp[i-][j]+dp[i][j+k])%;

    cout<<dp[n][m];

}

i来代表花种类，k代表花的盆数，j代表这种花放的盆数。

状态转移方程：dp[i][k]+=dp[i-1][j]

D. 【NOIP2012普及组真题】文化之旅

最短路径问题。数据量不大，弗洛伊德都可以搞定。但难点在于，文化排斥使得一些路是并不可以走的。

嗯，所以难点难住了我…没想出来，暂时搁置一下。

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

const int MAXN=;

int n,k,m,s,t;

int Map[MAXN][MAXN];

int Cultrue[MAXN];

int Dis[MAXN][MAXN];

int d[MAXN];

bool v[MAXN];

int Now[MAXN];

int main(){

memset(Map,0x3f,sizeof(Map));

int u,v,l;

//

freopen("culture.in","r",stdin);

//

freopen("culture.out","w",stdout);

scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);

//国家个数，文化种数，道路千万条，起点，终点

for(int i=;i<=n;i++){

scanf("%d",&Cultrue[i]);

Map[i][i]=;

}

for(int i=;i<=k;i++){

for(int j=;j<=k;j++){

scanf("%d",&Dis[i][j]);

}

}

for(int i=;i<=m;i++){

scanf("%d%d%d",&u,&v,&l);

Map[u][v]=min(Map[u][v],l);

Map[v][u]=min(Map[u][v],l);

}

for(int k=;k<=n;k++){

for(int j=;j<=n;j++){

for(int i=;i<=n;i++){

Map[i][j]=min((Map[i][k]+Map[k][j]),Map[i][j]);

}

}

}

cout<<Map[s][t];

}

以上，考场临时骗分的，运气不错，数据里很多都直接无视了文化，所以拿到了90分。

NOIP2012 普及组真题 4.13校模拟的相关教程结束。