POJ题目训练·初期·基本算法

• 导语
• 涉及的知识点
• 题目
• • 1753
  • 2965
  • 1328
  • 2109
  • 2586
  • 3295
  • 1068
  • 2632
  • 1573
  • 2993
  • 2996
• 参考文献

导语

没什么好说的，做就完了，封建迷信了属于是

涉及的知识点

枚举、暴力、构造、模拟

题目

1753

题目大意：略

思路：以前做过，基本思路就是搜索，但是要用bitset来优化存储

代码

#include <iostream>
#include <bitset>
#include <queue>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int maxn=1e6+10;
typedef bitset<16> bit;
int Next[]= {0,1,-1,-4,4};
bool vis[maxn];
int main() {
    int ans=-1,cnt=0;
    bit t;
    for(int i=0; i<16; i++) {
        char ch;
        cin >>ch;
        t[i]=(ch=='b'?1:0);
    }
    queue<bit>q;
    q.push(t);
    while(!q.empty()) {
        int len=q.size();
        while(len--) {
            t=q.front();
            q.pop();
            if(t.count()==16||t.count()==0) {
                ans=cnt;
                break;
            }
            if(ans!=-1)break;
            if(vis[t.to_ulong()])continue;
            vis[t.to_ulong()]=1;
            for(int i=0; i<16; i++) {//以一维来思考比较好，二维容易有问题
                bit tmp=t;
                int x=i/4,y=i%4;
                for(int j=0; j<5; j++) {
                    if(j<3&&(y+Next[j]<0||y+Next[j]>=4))
                        continue;
                    if(j>=3&&(i+Next[j]<0||i+Next[j]>=16))
                        continue;
                    tmp.flip(y+4*x+Next[j]);
                }
                q.push(tmp);
            }
        }
        if(ans!=-1)break;
        cnt++;
    }
    if(ans!=-1)printf("%d",ans);
    else printf("Impossible");
    return 0;
}

2965

题目大意：和上一题类似，但是每次翻面改变的是一行一列

思路：对于一个+位置，如果想完全改变它需要将以它为中心的行与列全部翻一遍，共七次，以它为中心的其余位置需要各翻四次，偶数次翻与初始一样，奇数次与翻一次相同，对于每个+直接翻一次（同时操作行列），最后为1的位置即需要翻的位置，1的数量为需要翻的个数

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <queue>
using namespace std;
const int maxn=1e6+10;
int times[20],ans;
char ch;
int main() {
    for(int i=0; i<16; i++) {
        cin >>ch;
        if(ch=='+') {
            int row=i/4,col=i%4;
            for(int j=0; j<4; j++)
                times[row*4+j]^=1;
            for(int j=0; j<4; j++)
                times[col+j*4]^=1;
            times[i]^=1;
        }
    }
    for(int i=0; i<16; i++)
        if(times[i])ans++;
    cout <<ans<<endl;
    for(int i=0; i<16; i++)if(times[i])cout <<i/4+1<<" "<<i%4+1<<endl;
    return 0;
}

1328

题目大意：给出一个笛卡尔坐标系，y正半轴为海，y负半轴为岸，海上有一些海岛（视为点），给出各个海岛的横纵坐标，现在要在x轴建一些雷达，给出雷达的辐射半径，求最少需要几个雷达能实现海岛全覆盖

思路：一开始还以为是个几何题，实际上是贪心的经典的区间问题，很妙。
对于每个点，x轴上与该点距离为半径的点至少有两个，也就是说，满足该点在半径内的可取坐标范围是一个区间，那么对于每个点求出它的区间，按照从左到右排序，问题就被转换成了给出多个可交的区间，求最少需要放置几个点使各区间至少一点

代码

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
int n,d,k;
struct node {
    double ll,rr;
    bool operator<(const node t)const {//重载
        return rr<t.rr;
    }
} e[1212];
int main() {
    while(~scanf("%d%d",&n,&d)&&n&&d) {
        int ans=0;
        double rad=d,r;
        for(int i=0; i<n; i++) {
            double x,y;
            scanf("%lf%lf",&x,&y);
            if(y>rad)ans=-0x3f3f3f3f;
            e[i].ll=x-sqrt(rad*rad-y*y);
            e[i].rr=x+sqrt(rad*rad-y*y);
        }
        sort(e,e+n);
        r=e[0].rr;
        ans++;
        for(int i=1; i<n; i++) {
            if(e[i].ll>r) {
                ans++;
                r=e[i].rr;
            } else if(e[i].rr<r)r=e[i].rr;
        }
        printf("Case %d: %d\n",++k,ans<0?-1:ans);
    }
    return 0;
}

2109

题目大意：输入两个整数n,p， 1 ≤ p ≤ 1 0 101 1\le p\le 10^{101} 1≤p≤10101，求出一个整数k使得 k n = p k^n=p kn=p

思路：直接求解即可，double的范围可到300位

代码

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstdio>
using namespace std;
int main() {
    double n,p;
    while(~scanf("%lf%lf",&n,&p))
        printf("%.0f\n",pow(p,1.0/n));
    return 0;
}

2586

题目大意：公司的盈亏数据丢失，但是每月盈亏为一个固定的整数，要么盈利s要么亏损d，该公司每五个月有一张盈亏表，每次报表的盈亏情况都为亏，一年中这样的报表有8次，给出s和d，现需要确定当满足每张报表为亏的情况下，全年公司最高可盈利额为多少，如果存在，则输出最大值，否则输出"Deficit"

思路：将盈利集中在区间首部，整个区间可以分成这样的几个块： x x x x x , x x x x x , x x xxxxx,xxxxx,xx xxxxx,xxxxx,xx，分情况讨论，盈利10，亏2，盈利8，亏4，盈利6，亏6，盈利3，亏9，分别计算结果

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int s,d;
int main() {
    while(~scanf("%d%d",&s,&d)) {
        int ans=0;
        if(d>4*s)ans=10*s-2*d;
        else if(2*d>3*s)ans=8*s-4*d;
        else if(3*d>2*s)ans=6*s-6*d;
        else if(4*d>s)ans=3*s-9*d;
        else ans=-1;
        if(ans<0)printf("Deficit\n");
        else printf("%d\n",ans);
    }
    return 0;
}

3295

题目大意：输入由 p , q , r , s , t , K , A , N , C , E p,q,r,s,t,K,A,N,C,E p,q,r,s,t,K,A,N,C,E组成的逻辑表达式，小写字母为变量，大写字母为运算，给出运算表，询问该逻辑表达式是否为永真式

思路：用栈模拟运算即可，暴力遍历所有变量的取值，由于数据范围不是很大，所以可以实现

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <bitset>
#include <stack>
using namespace std;
bool K[2][2]= {0,0,0,1},A[2][2]= {0,1,1,1},C[2][2]= {1,1,0,1},E[2][2]= {1,0,0,1};
char str[121];
int main() {
    while(~scanf("%s",str)&&str[0]!='0') {
        int len=strlen(str);
        bool flag=0;
        for(int p=0; p<=1; p++) {
            for(int q=0; q<=1; q++) {
                for(int r=0; r<=1; r++) {
                    for(int s=0; s<=1; s++) {
                        for(int t=0; t<=1; t++) {
                            stack<int>S;
                            for(int i=len-1; i>=0; i--) {
                                bool x=0,y=0;
                                switch(str[i]) {
                                case 'p':
                                    S.push(p);
                                    break;
                                case 'q':
                                    S.push(q);
                                    break;
                                case 'r':
                                    S.push(r);
                                    break;
                                case 's':
                                    S.push(s);
                                    break;
                                case 't':
                                    S.push(t);
                                    break;
                                case 'K':
                                    x=S.top();
                                    S.pop();
                                    y=S.top();
                                    S.pop();
                                    S.push(K[y][x]);
                                    break;
                                case 'A':
                                    x=S.top();
                                    S.pop();
                                    y=S.top();
                                    S.pop();
                                    S.push(A[y][x]);
                                    break;
                                case 'N':
                                    x=S.top();
                                    S.pop();
                                    S.push(!x);
                                    break;
                                case 'C':
                                    x=S.top();
                                    S.pop();
                                    y=S.top();
                                    S.pop();
                                    S.push(C[y][x]);
                                    break;
                                case 'E':
                                    x=S.top();
                                    S.pop();
                                    y=S.top();
                                    S.pop();
                                    S.push(E[y][x]);
                                    break;
                                }
                            }
                            if(!S.top()) {
                                printf("not\n");
                                flag=1;
                                break;
                            }
                        }
                        if(flag)break;
                    }
                    if(flag)break;
                }
                if(flag)break;
            }
            if(flag)break;
        }
        if(!flag)
            printf("tautology\n");
    }

    return 0;
}

1068

题目大意：略

思路：当时被数据范围弄的复杂了，其实直接模拟就好了，先构造原字符串，然后按照W的规则来统计

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <bitset>
#include <stack>
using namespace std;
int t,n,a[121]= {0};
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        int str[50]= {0};
        int j,i,k,ans=0;
        for(i=1; i<=n; i++)
            scanf("%d",a+i);
        for(j=0,i=1; i<=n; i++)//把P变成01，左0右1
            for( k=0;; k++)
                if(k<a[i]-a[i-1])j++;//找右的位置
                else if(k==a[i]-a[i-1]) {//没变，是右
                    str[j++]=1;
                    break;
                }
        int len=j;
        for(int i=0; i<len; i++)//str转W
            if(str[i]) {//遇到1就回溯找到最近的0
                ans=2;
                for(int j=i-1;; j--)
                    if(str[j]==0) {
                        str[i]=str[j]=10000;//使用过后清空
                        break;
                    } else
                        ans++;//记录匹配的数量
                printf("%d ",ans/2);
            }
        putchar('\n');
    }
    return 0;
}

2632

题目大意：略

思路：直接模拟即可，但是注意坐标是反着的，并且要一次性处理完一组数据

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn=1e5+10;
int k,a,b,n,m,Next[4][2]= {0,1,1,0,0,-1,-1,0};
struct node {
    int x,y,d;
} r[121];
int vis[121][121];
char ch;
map<char,int>w;
int main() {
    cin >>k;
    w['E']=0;
    w['N']=1;
    w['W']=2;
    w['S']=3;
    while(k--) {
        cin >>a>>b>>n>>m;
        memset(vis,0,sizeof(vis));
        for(int i=1; i<=n; i++) {
            cin >>r[i].y>>r[i].x>>ch;
            r[i].d=w[ch];
            vis[r[i].x][r[i].y]=i;
        }
        bool flag=0;
        int id=0,rob2=0;
        while(m--) {
            int i,c;
            char j;
            cin >>i>>j>>c;
            if(!flag) {
                while(c--) {
                    if(j=='L')r[i].d=(r[i].d+1)%4;
                    if(j=='R')r[i].d=(r[i].d+3)%4;
                    if(j=='F') {
                        int xx=r[i].x+Next[r[i].d][0],yy=r[i].y+Next[r[i].d][1];
                        if(xx<1||xx>b||yy<1||yy>a) {
                            id=i;
                            flag=1;
                            continue;
                        } else if(vis[xx][yy]) {
                            id=i;
                            rob2=vis[xx][yy];
                            flag=1;
                            continue;
                        } else {
                            vis[r[i].x][r[i].y]=0;
                            r[i].x=xx;
                            r[i].y=yy;
                            vis[xx][yy]=i;
                        }
                    }
                }
            }
        }
        if(flag) {
            if(id&&rob2)
                cout <<"Robot "<<id<<" crashes into robot "<<rob2<<endl;
            else
                cout<<"Robot "<<id<<" crashes into the wall"<<endl;
        } else
            cout <<"OK"<<endl;
    }
    return 0;
}

1573

题目大意：略

思路：简单的模拟，按照题目的意思来即可，注意判断有环的情况下需要走的步数

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,s,ans=0,loop=0;
int vis[20][20];
char maze[20][20];
bool DFS(int x,int y) {
    if(x<1||x>n||y<1||y>m)return 1;
    if(vis[x][y]) {
        loop=ans-vis[x][y]+1;
        ans=vis[x][y]-1;
        return 0;
    }
    vis[x][y]=++ans;
    switch(maze[x][y]) {
    case 'N':
        return DFS(x-1,y);
        break;
    case 'S':
        return DFS(x+1,y);
        break;
    case 'E':
        return DFS(x,y+1);
        break;
    case 'W':
        return DFS(x,y-1);
        break;
    }
}
int main() {
    while(~scanf("%d%d%d",&n,&m,&s)&&n&&m&&s) {
        ans=loop=0;
        for(int i=1; i<=n; i++)
            scanf("%s",maze[i]+1);
        if(DFS(1,s))
            printf("%d step(s) to exit\n",ans);
        else
            printf("%d step(s) before a loop of %d step(s)\n",ans,loop);
        memset(vis,0,sizeof(vis));
    }
    return 0;
}

2993

题目大意：2996的逆推，给出坐标求棋盘

思路：输入输出太恶心了…直接模拟即可

代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cstring>
using namespace std;
char maze[100][100];
char l[50]="+---+---+---+---+---+---+---+---+",h[50]="|:::|...|:::|...|:::|...|:::|...|",m[50]="|...|:::|...|:::|...|:::|...|:::|";
int main() {
    for(int i=1; i<=17; i+=2)
        memcpy(maze[i]+1,l,sizeof(l));
    for(int i=2; i<=16; i+=4)
        memcpy(maze[i]+1,m,sizeof(m));
    for(int i=4; i<=16; i+=4)
        memcpy(maze[i]+1,h,sizeof(h));
    char str1[100]= {'\0'},str2[100]= {'\0'};
    scanf("%s %s",str1,str2);
    for(int i=0; str2[i];) {
        if(str2[i]==',') {
            i++;
            continue;
        }
        if(isupper(str2[i])) {
            int x=str2[i+1]-'a'+1,y=str2[i+2]-'0';
            maze[2*(8-y+1)][4*x-1]=str2[i];
            i+=3;
        } else {
            int x=str2[i]-'a'+1,y=str2[i+1]-'0';
            maze[2*(8-y+1)][4*x-1]='P';
            i+=2;
        }
    }
    scanf("%s %s",str1,str2);
    for(int i=0; str2[i];) {
        if(str2[i]==',') {
            i++;
            continue;
        }
        if(isupper(str2[i])) {
            int x=str2[i+1]-'a'+1,y=str2[i+2]-'0';
            maze[2*(8-y+1)][4*x-1]=tolower(str2[i]);
            i+=3;
        } else {
            int x=str2[i]-'a'+1,y=str2[i+1]-'0';
            maze[2*(8-y+1)][4*x-1]='p';
            i+=2;
        }
    }
    for(int i=1; i<=17; i++)
        printf("%s\n",maze[i]+1);
    return 0;
}

2996

题目大意：给出一个国际象棋棋盘，按照规则输出各个棋子的坐标

思路：直接模拟即可，输出的时候注意一下，黑是从上到下，白是从下到上

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
struct node {
    char x;
    int y;
};
queue<node>white[10],black[10];
int pos[]= {0,3,7,11,15,19,23,27,31};
char maze[200][200],w[]="#KQRBNP";
int main() {
    for(int i=1; i<=17; i++) {
        scanf("%s",maze[i]+1);
        getchar();
    }
    for(int i=16; i>=2; i-=2)
        for(int j=1; j<=8; j++)
            switch(maze[i][pos[j]]) {
            case 'K':
                white[1].push({j+'a'-1,8-i/2+1});
                break;
            case 'Q':
                white[2].push({j+'a'-1,8-i/2+1});
                break;
            case 'R':
                white[3].push({j+'a'-1,8-i/2+1});
                break;
            case 'B':
                white[4].push({j+'a'-1,8-i/2+1});
                break;
            case 'N':
                white[5].push({j+'a'-1,8-i/2+1});
                break;
            case 'P':
                white[6].push({j+'a'-1,8-i/2+1});
                break;
            }
    bool flag=0;
    printf("White: ");
    for(int i=1; i<=5; i++)
        while(!white[i].empty()) {
            if(!flag)flag=1;
            else printf(",");
            node t=white[i].front();
            white[i].pop();
            printf("%c%c%d",w[i],t.x,t.y);
        }
    while(!white[6].empty()) {
        if(!flag)flag=1;
        else printf(",");
        node t=white[6].front();
        white[6].pop();
        printf("%c%d",t.x,t.y);
    }
    for(int i=2; i<=16; i+=2)
        for(int j=1; j<=8; j++)
            switch(maze[i][pos[j]]) {
            case 'k':
                black[1].push({j+'a'-1,8-i/2+1});
                break;
            case 'q':
                black[2].push({j+'a'-1,8-i/2+1});
                break;
            case 'r':
                black[3].push({j+'a'-1,8-i/2+1});
                break;
            case 'b':
                black[4].push({j+'a'-1,8-i/2+1});
                break;
            case 'n':
                black[5].push({j+'a'-1,8-i/2+1});
                break;
            case 'p':
                black[6].push({j+'a'-1,8-i/2+1});
                break;
            }
    flag=0;
    putchar('\n');
    printf("Black: ");
    for(int i=1; i<=5; i++)
        while(!black[i].empty()) {
            if(!flag)flag=1;
            else printf(",");
            node t=black[i].front();
            black[i].pop();
            printf("%c%c%d",w[i],t.x,t.y);
        }
    while(!black[6].empty()) {
        if(!flag)flag=1;
        else printf(",");
        node t=black[6].front();
        black[6].pop();
        printf("%c%d",t.x,t.y);
    }
    return 0;
}

参考文献

1. Y2K Accounting Bug POJ2586
2. POJ1328-Radar Installation
3. poj2632
4. POJ2965 The Pilots Brothers’ refrigerator （精妙方法秒杀DFS BFS）
5. POJ2965的枚举解法和高效解法