USACO Section 1.2(完全枚举)

命名那个数字 Name That Number

对于读入的一个字符串,直接判断是否合法(即长度合法且每一位上的字母对应的数字合法),合法就直接输出.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#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;
}
char ch[15],word[10005];
map<char,int>Map;
inline bool check(int len){
    for(int i=0;i<len;i++)
        if(Map[word[i]]!=(ch[i]-'0'))return false;
    return true;
}
int main(){
    Map['A']=2;Map['B']=2;Map['C']=2;
    Map['D']=3;Map['E']=3;Map['F']=3;
    Map['G']=4;Map['H']=4;Map['I']=4;
    Map['J']=5;Map['K']=5;Map['L']=5;
    Map['M']=6;Map['N']=6;Map['O']=6;
    Map['P']=7;Map['R']=7;Map['S']=7;
    Map['T']=8;Map['U']=8;Map['V']=8;
    Map['W']=9;Map['X']=9;Map['Y']=9;
    scanf("%s",ch);int len=strlen(ch),bj=0;
    while(scanf("%s",word)!=EOF){
        int lenn=strlen(word);
        if(len!=lenn)continue;
        if(check(len))printf("%sn",word),bj=1;
    }
    if(!bj)puts("NONE");
    return 0;
}

挤牛奶Milking Cows

题意:有N个农民(1<=N<=5000)挤N头牛的工作时间列表，计算以下两点(均以秒为单位):最长至少有一人在挤奶的时间段.最长的无人挤奶的时间段.(从有人挤奶开始算起)

分析:对着数据调了好久.先把每头牛的挤奶时间按照开始时间从小到大排序,然后对于牛i,如果开始时间比上一头牛的结束时间last早就直接累加当前最长挤奶时间,并更新last,否则计算无人挤奶时间,同样更新last.其中较为麻烦的是,要注意何时计算和更新两个答案.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
using namespace std;
inline int read(){
    int x=0,ch=getchar();
    return x*o;
}
const int N=5005;
struct ppx{int l,r;}a[N];
inline bool cmp(ppx x,ppx y){return x.l<y.l;}
int main(){
    int n=read();
    for(int i=1;i<=n;++i){a[i].l=read();a[i].r=read();}
    sort(a+1,a+n+1,cmp);
    int ans1=a[1].r-a[1].l,cnt1=a[1].r-a[1].l,ans2=0,cnt2=0,last=a[1].r;
    for(int i=2;i<=n;++i){
        if(a[i].l<=last){
            ans2=max(cnt2,ans2);cnt2=0;
            if(a[i].r-last>=0){
                cnt1+=a[i].r-last;
                last=a[i].r;
            }
        }
        else{
            ans1=max(cnt1,ans1);cnt1=0;
            ans2=max(cnt2,ans2);cnt2=0;
            cnt1=a[i].r-a[i].l;
            cnt2=a[i].l-last;
            last=a[i].r;
        }
    }
    ans1=max(cnt1,ans1);ans2=max(cnt2,ans2);//最后可能没更新上去
    printf("%d %dn",ans1,ans2);
    return 0;
}

方块转换 Transformations

把每一种方法都模拟出来,然后从小到大枚举每一种方法就行.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
using namespace std;
inline int read(){
    int x=0,ch=getchar();
    return x*o;
}
char a[15][15],b[15][15],c[15][15],d[15][15];
inline bool check(int k,int n){
    if(k==1){
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                c[i][j]=a[n+1-j][i];
                if(c[i][j]!=b[i][j])return false;
            }
        return true;
    }
    if(k==2){
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                c[i][j]=a[n+1-i][n+1-j];
                if(c[i][j]!=b[i][j])return false;
            }
        return true;
    }
    if(k==3){
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                c[i][j]=a[n+1-j][j];
                if(c[i][j]!=b[i][j])return false;
            }
        return true;
    }
    if(k==4){
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                c[i][j]=a[i][n+1-j];
                if(c[i][j]!=b[i][j])return false;
            }
        return true;
    }
    if(k==5){
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                c[i][j]=a[i][n+1-j];
        int bj=1;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                d[i][j]=c[n+1-j][i];
                if(d[i][j]!=b[i][j]){bj=0;break;}
            }
        if(bj)return true;
        bj=1;memset(d,sizeof(d));
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                d[i][j]=c[n+1-i][n+1-j];
                if(d[i][j]!=b[i][j]){bj=0;break;}
            }
        if(bj)return true;
        bj=1;memset(d,sizeof(d));
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                d[i][j]=c[n+1-j][j];
                if(d[i][j]!=b[i][j]){bj=0;break;}
            }
        if(bj)return true;
        return false;
    }
    if(k==6){
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                c[i][j]=a[i][j];
                if(c[i][j]!=b[i][j])return false;
            }
        return true;
    }
}
int main(){
    int n=read();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            cin>>a[i][j];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            cin>>b[i][j];
    for(int i=1;i<=6;++i)
        if(check(i,n)){
            printf("%dn",i);
            return 0;
        }
    puts("7");
    return 0;
}

回文平方数 Palindromic Squares

给定一个进制B(2<=B<=20,由十进制表示)，输出所有的大于等于1小于等于300（十进制下）且它的平方用B进制表示时是回文数的数.用’A’,’B’……表示10，11等等.

分析:直接枚举300个数然后判断平方数在B进制下是否回文即可.注意输出的第一个也要是B进制数.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
using namespace std;
inline int read(){
    int x=0,ch=getchar();
    return x*o;
}
int a[1005],b[1005];
char c[105]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J','K','L'};
inline void solve(int m,int n){
    int tot=0,bj=1,cnt=m*m;
    while(cnt){a[++tot]=cnt%n;cnt/=n;}
    for(int i=1;i<=tot/2;++i)
        if(a[tot+1-i]!=a[i]){
            bj=0;break;
        }
    if(bj){
        int tot1=0;
        while(m){b[++tot1]=m%n;m/=n;}
        for(int i=tot1;i>=1;--i)printf("%c",c[b[i]]);
        printf(" ");
        for(int i=1;i<=tot;++i)printf("%c",c[a[i]]);
        printf("n");
    }
    return;
}
int main(){
    int n=read();
    for(int i=1;i<=300;++i)solve(i,n);
    return 0;
}

双重回文数 Dual Palindromes

给定两个十进制数N (1 <= N <= 15)S (0 < S < 10000)然后找出前N个满足大于S且在两种或两种以上进制（二进制至十进制）上是回文数的十进制数.

直接枚举并判断即可,比上题还简单.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
using namespace std;
inline int read(){
    int x=0,ch=getchar();
    return x*o;
}
int a[10005];
inline bool check(int x,int y){
    int tot=0;
    while(x){
        a[++tot]=x%y;
        x/=y;
    }
    for(int i=1;i<=tot/2;++i)
        if(a[i]!=a[tot+1-i])return false;
    return true;
}
int main(){
    int n=read(),m=read();
    for(int i=m+1;;++i){
        int cnt=0;
        for(int j=2;j<=10;++j){
            if(check(i,j))++cnt;
            if(cnt>=2)break;
        }
        if(cnt>=2){
            printf("%dn",i);
            --n;
        }
        if(!n)break;
    }
    return 0;
}