Noip2009提高组总结

2024-03-06 18:41:26

　　Noip2009的题目还是有一定难度的，主要是搜索和最短路都是我的弱项，不检查第一遍下来只做了150分，还是这句话，素质和读题的仔细程度决定了分数。仔细想想，我们化学老师说的话没错，或许题目你都会做，但是你在考试时犯下的各种错误终将导致你的失败，所以，提高个人编程的素质，对于我来说才是目前最重要的事。

T1：潜伏者

　　第一题是极简单的字符串操作题，读题仔细一点，注意各种规则即可AC，但是在做的时候自己犯了一点小错误，结果只有90分，这是不应该的！

#include <cstdio>

#include <cstring>

char s1[105],s2[105],w[105];

int hash[26],flag[26],ap[26];

int main(){

    scanf("%s",s1); scanf("%s",s2);

    for(int i=0;i<strlen(s1);i++){

        if(ap[s1[i]-'A']==1&&hash[s1[i]-'A']!=s2[i]-'A'){puts("Failed");return 0;}

        ap[s1[i]-'A']=1;

        hash[s1[i]-'A']=s2[i]-'A';

    }

    for(int i=0;i<26;i++)if(!ap[i]){puts("Failed");return 0;}

    for(int i=0;i<26;i++){

        if(flag[hash[i]]){puts("Failed");return 0;}

        flag[hash[i]]=1;

    }

    scanf("%s",w);

    for(int i=0;i<strlen(w);i++)printf("%c",(char)(hash[w[i]-'A']+(int)'A'));

    return 0;

}

T2：Hankson的趣味题

　　第一遍用暴力，拿了六十分，看了网上的题解，需要素数分解，然后是一些比较复杂的范围求解，个人感觉没必要，然后尝试了一下只枚举sqrt(n)，且判断是否是约数，如果是进行一次计算，并计算其对应的相乘为n的数是否成立，否则continue，然后神奇般地AC了，所以有时候没必要想得太过复杂，认真思考，或许最简单的方法才是最有效的。

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

void init(int &x){

    char c;

    while(c=getchar(),c<'0'||c>'9'); x=c-'0';

    while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';

}

int gcd(int x,int y){return y==0?x:gcd(y,x%y);}

int lcm(int x,int y){return x/gcd(x,y)*y;}

int main(){

    int T,a0,a1,b0,b1;

    scanf("%d",&T);

    while(T--){

        int cnt=0;

        init(a0);init(a1);init(b0);init(b1);

        int k=sqrt(b1);

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

            if(b1%i!=0)continue;

            if(gcd(i,a0)==a1&&lcm(i,b0)==b1)cnt++;

            int tmp=b1/i;

            if(tmp!=i&&gcd(tmp,a0)==a1&&lcm(tmp,b0)==b1)cnt++;

        }

        printf("%d\n",cnt);

    }

    return 0;

}

T3：最优贸易

　　想得过于复杂，结果码不出程序，暴力拿了0分，汀神说最短路就好啦，然后醒悟，正向建图SPFA一遍求到某点路上的最小值，反向建图同理求得从终点到此处的最大值，然后枚举每一个点进行计算比较一下即可。

#include <cstdio>

#define Q_MAX 100000

int m1[1000005],next1[1000005],end1,head1[100005];

int m2[1000005],next2[1000005],end2,head2[100005];

int num[100005],used[100005],Q[Q_MAX],h,r;

int min[100005],max[100005];

void add1(int a,int b){m1[end1]=b;next1[end1]=head1[a];head1[a]=end1++;}

void add2(int a,int b){m2[end2]=b;next2[end2]=head2[a];head2[a]=end2++;}

void Q_push(int k){

    if(used[k]){return;}

    used[k]=1; Q[r]=k;

    r=(r+1)%Q_MAX;

}

int Q_pop(void){

    int t=Q[h];

    used[t]=0;

    h=(h+1)%Q_MAX;

    return t;

}

int main(){

    int i,j,n,m,a,b,c;

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

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

        head1[i]=head2[i]=-1;

        max[i]=-1000000;

        min[i]=1000000;

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

    }

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

        scanf("%d%d%d",&a,&b,&c);

        a--,b--;

        if(c==2){

            add1(a,b); add1(b,a);

            add2(a,b); add2(b,a);

        }else add1(a,b),add2(b,a);

    }

    min[0]=num[0];

    Q_push(0);

    while(h!=r){

        i=Q_pop();

        for(a=head1[i];a!=-1;a=next1[a]){

            j=m1[a];

            if(min[j]>min[i])min[j]=min[i],Q_push(j);

            if(min[j]>num[j])min[j]=num[j],Q_push(j);

        }

    }

    max[n-1]=num[n-1];

    Q_push(n-1);

    while(h!=r){

        i=Q_pop();

        for(a=head2[i];a!=-1;a=next2[a]){

            j=m2[a];

            if(max[j]<max[i])max[j]=max[i],Q_push(j);

            if(max[j]<num[j])max[j]=num[j],Q_push(j);

        }

    }

    for(i=a=0;i<n;i++)if(a<max[i]-min[i])a=max[i]-min[i];

    printf("%d\n",a);

    return 0;

}

T4：靶形数独

　　这道题的搜索很巧妙，如果直接搜索判重过于复杂而且会超时，想想八皇后的位运算搜索方法，应用在这道题上刚好，而且简化许多，用hs，ss表示横排，竖排上已有的数字，用nine表示每个小方格中已有的数字，而h表示该处是否被占据，然后就用lowbit计算低位空，依次进行dfs，每当k=10即搜索完成时更新最大值即可。

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std;

int a[10][10],h[10],hs[10],ss[10],nine[10],hash[10],q[10],ans=-1,st=511;

int ten(int x){return (int)log2(x)+1;}

void f(){

    int c=a[5][5]*10;

    for(int k=2;k<=5;k++){

        for(int i=k;i<=10-k;i++)c+=(4+k)*(a[i][k-1]+a[i][11-k]);

        for(int j=k;j<=10-k;j++)c+=(4+k)*(a[k-1][j]+a[11-k][j]);

        c+=(4+k)*(a[k-1][k-1]+a[k-1][11-k]+a[11-k][k-1]+a[11-k][11-k]);

    }

    if(c>ans)ans=c;

}

void dfs(int k){

    if(k==10)f();

    else{

        int i=hash[k],j,get,num,pos,p;

        pos=st&~h[i]; p=pos&-pos;

        h[i]|=p; j=ten(p);

        get=st&~(hs[i]|ss[j]|nine[(i-1)/3*3+(j-1)/3+1]);

        while(get){

            num=get&-get;

            get^=num;

            a[i][j]=ten(num);

            hs[i]|=num; ss[j]|=num;

            nine[(i-1)/3*3+(j-1)/3+1]|=num;

            if(pos==p)dfs(k+1); else dfs(k);

            hs[i]^=num; ss[j]^=num;

            nine[(i-1)/3*3+(j-1)/3+1]^=num;

        }h[i]^=p;

    }

}

int main(){

    int k=1;

    for(int i=1;i<=9;i++)

    for(int j=1;j<=9;j++){

        hash[i]=i;

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

        if(a[i][j]){

            h[i]|=1<<(j-1);

            if(((hs[i]|ss[j]|nine[(i-1)/3*3+(j-1)/3+1])&(1<<(a[i][j]-1)))==1){printf("-1\n");return 0;}

            hs[i]|=1<<(a[i][j]-1);

            ss[j]|=1<<(a[i][j]-1);

            nine[(i-1)/3*3+(j-1)/3+1]|=1<<(a[i][j]-1);

        }else q[i]++;

    }

    for(int i=1;i<9;i++)for(int j=i+1;j<=9;j++)

    if(q[hash[i]]>q[hash[j]])swap(hash[i],hash[j]);

    while(q[hash[k]]==0)k++;dfs(k);

    printf("%d\n",ans);

    return 0;

}

注意点：

　　1.最短路的几种算法都要熟悉起来，并且要可以很快码出来；

　　2.对于位置搜索优化时可以考虑位运算；

3.读题一定要清楚仔细，宁愿多花几分钟，也不要因读错题走冤枉路；

　　4.循环队列记得进队出队都要取模。

码农公寓

相关文章