POJ题目训练·初期·基本算法
导语
没什么好说的，做就完了，封建迷信了属于是
涉及的知识点
枚举、暴力、构造、模拟
题目
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;
}
参考文献
- Y2K Accounting Bug POJ2586
- POJ1328-Radar Installation
- poj2632
- POJ2965 The Pilots Brothers’ refrigerator （精妙方法秒杀DFS BFS）
- POJ2965的枚举解法和高效解法