POJ 1013 Counterfeit Dollar
链接： http://poj.org/problem?id=1013
题意：有一打硬币，其中有一个是假币，质量可能较轻，也可能较重。通过三次称重将假币找出。
由于计算机很难模仿人的想法来实现问题。这道题我纠结了很久。
最后我是通过一一枚举的笨方法做的。就是从A硬币开始到L硬币结束，一一假设其为假币，其中又分为轻和重。当符合三次称重之后便找到了假币。
后来看网上有人是将三次称重这样实现的：给这十二枚硬币赋初值。如果是even，那么硬币值不变。如果是up，那么左边的自加，右边的自减。由于对于不确定的硬币还要做下一次测试。所以通过三次测试之后，偏离初值最大的必然为假币
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int main ()
{
int n,i,j,k;
cin>>n;
while(n--)
{
char al[3][20],ar[3][20],a[3][10];
int v[15]= {0},visit[15]= {0};
bool flag=true;
for (i=0; i<3; i++)
cin>>al[i]>>ar[i]>>a[i];
for (i=0; i<24; i++)
{
flag=true;
v[i/2]=(i%2==0?-1:1);
for (k=0; k<3; k++)
{
int left=0,right=0;
for (j=0; j<strlen(al[k]); j++)
left+=v[al[k][j]-'A'];
for (j=0; j<strlen(ar[k]); j++)
right+=v[ar[k][j]-'A'];
if (strcmp(a[k],"even")==0 && left!=right) flag=false;
if (strcmp(a[k],"up")==0 && !(left>right)) flag=false;
if (strcmp(a[k],"down")==0 && !(left<right)) flag=false;
}
v[i/2]=0;
if (flag) break;
}
if (!(i%2)) printf("%c is the counterfeit coin and it is light. \n",i/2+'A');
else printf("%c is the counterfeit coin and it is heavy. \n",i/2+'A');
}
return 0;
}
POJ 1028 Web Navigation
链接： http://poj.org/problem?id=1028
模拟网页的前进、后退、访问等功能。其实就是栈的一个简单运用
不过在做的时候要注意一个细节，就是无法后退或者无法前进的时候，页面不做反应，即停留在原先初始的地方。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
int main ()
{
string str,now;
stack<string> back;
stack<string> forward;
now="http://www.acm.org/";
while(cin>>str)
{
if (str=="QUIT") break;
if (str=="VISIT")
{
back.push(now);
cin>>now;
cout<<now<<endl;
while(!forward.empty())
forward.pop();
}
if (str=="BACK")
{
if (back.empty())
cout<<"Ignored"<<endl;
else
{
forward.push(now);
now=back.top();
back.pop();
cout<<now<<endl;
}
}
if (str=="FORWARD")
{
if (forward.empty()) cout<<"Ignored"<<endl;
else
{
back.push(now);
now=forward.top();
forward.pop();
cout<<now<<endl;
}
}
}
return 0;
}
POJ 1045 Bode Plot
链接： http://poj.org/problem?id=1045
一道数学公式推导题（要注意G++编译器double类型要用 .f 输出）
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
double vs,r,c,w,vr;
int i,t;
scanf("%lf %lf %lf %d",&vs,&r,&c,&t);
for(i=1;i<=t;i++)
{
scanf("%lf",&w);
vr=c*r*w*vs/sqrt(1+c*r*w*c*r*w);
printf("%.3lf\n",vr);//C++用.lf
}
return 0;
}
POJ 1068 Parencodings
链接： http://poj.org/problem?id=1068
括号匹配，给你一串括号。然后按照右括号的顺序写出一串数字，其中对应的数字代表在右括号前面左括号的数量
按照右括号的顺序求另一串数字，对应的数字代表成对的括号当中包含了几对括号（包括本身）
这也是一道栈的运用的题目。左括号入栈，右括号出栈，在出栈的同时需要记录数据
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
struct node
{
char ch;
int x;
};
int main ()
{
int t,n,i,j;
cin>>t;
while (t--)
{
int x[21]={0},s=0,p[44]={0};
cin>>n;
for (i=0; i<n; i++)
{
cin>>x[i+1];
for (j=s; j<s+x[i+1]-x[i]; j++)
p[j]=1;
s=j+1;
}
stack<node> ss;
node temp;
temp.ch='(';
temp.x=0;
ss.push(temp);
for (i=0; i<2*n; i++)
if (p[i]==1)
{
temp.ch='(';
temp.x=0;
ss.push(temp);
}
else
{
node first,next;
first=ss.top();
ss.pop();
next=ss.top();
ss.pop();
first.x++;
next.x+=first.x;
cout<<first.x<<" ";
ss.push(next);
}
cout<<endl;
}
return 0;
}
POJ 1657 Distance on Chessboard
链接： http://poj.org/problem?id=1657
在国际象棋中，王、后、车、象分别有不同的走法，分别求一个位置到另一个位置他们走的步数。走不到为Inf
这道题其实就是要注意两点：
1. 可能起始点和终点为同一个点
2. 其中只可能是象走不到，象的走法要注意。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main ()
{
int t;
cin>>t;
while(t>0)
{
char a,c;
int b,d;
int x,y;
cin>>a>>b>>c>>d;
x=fabs(a-c);
y=fabs(b-d);
int j1,j2,j3;
j1=x>y?x:y;
if (x==0 && y==0) j2=0;
else if (x==0 || y==0) j2=1;
else if (x==y) j2=1;
else j2=2;
if (x==0 && y==0) j3=0;
else if (x==0 || y==0) j3=1;
else j3=2;
cout<<j1<<" "<<j2<<" "<<j3<<" ";
if (x==y) printf("%d\n",x==0?0:1);
else if ((y-x)%2==0) cout<<"2"<<endl;
else cout<<"Inf"<<endl;
t--;
}
return 0;
}
POJ 2665 Trees
链接： http://poj.org/problem?id=2665
校门外的树，这道题区域没有重合
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int main ()
{
int i,j,l,m;
while(cin>>l>>m)
{
if (l==0 && m==0) break;
while(m--)
{
int a,b;
cin>>a>>b;
l-=(b-a)+1;
}
cout<<l+1<<endl;
}
return 0;
}
POJ1936 All in All
链接： http://poj.org/problem?id=1936
两串字符串。从母串当中去掉不相关的字符能否得到子串？
设两个指针，分别沿着母串和子串移动。当子串到头时，便表示可以。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int main ()
{
char sub[100010],str[100010];
int i,j,l1,l2;
while(cin>>sub>>str)
{
l1=strlen(sub);
l2=strlen(str);
i=j=0;
while(i<l1 && j<l2)
{
if (sub[i]==str[j])
{
i++;
j++;
}
else j++;
}
if (i!=l1) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}