oj-acm专项分类练习 算法虐我千百遍，我待算法如初恋。。。
HLG 1547 基础数据结构——单链表（2）
题目链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1547
Description1997-1998 年欧洲西南亚洲区预赛之后，举办了一场隆重的聚会。主办方发明了一个特殊的方式去挑选那些自愿去洗脏碟子的参赛选手。先让那些选手一个挨着一个的排成一条队。 每个选手都获得一个编号，那些编号是从2开始的，第一个的编号是2 ，第二个人的编号是3，第三个人的编号是4，以此类推。
第一个选手将被问到他的编号（编号为2）。他将不用去清洗了，直接参加聚会，但是他身后的所站的位置是2的倍数的人必须去厨房（那些人的编号分别为4， 6， 8 等等）。然后在那队伍中的下一个选手必须报数。他回答3，他可以离开去参加聚会，但是在他身后的每个是三的倍数的选手将会被选上（那些人的编号分别为9,15,21等等）。下一个被选上的人的编号是5，并且将可以离开去参加聚会，但是在他身后并且站的位置是5的倍数的人将会被选上去清洗碟子（那些人的编号分别为19,35,49等等）.下一个被选上的人的编号是7，并且将可以离开去参加聚会，但是在他身后并且站的位置是7的倍数的人将会被选上去清洗碟子，以此类推。
让我们称那些没有被选上去洗碟子的那些选手的编号为幸运数字。继续这个挑选的方式，那些幸运的数字是2， 3， 5， 7， 11 ， 13， 17等等的递增序列。 为下一次的聚会寻找幸运数字！
Input
本题有多组测试数据，每组测试数据包含一个整数n，1<=n<=3000。
Output
对于每组测试数据输出一个数字，代表对应的幸运号码。
Sample Input
1
2
10
20
Sample Output
2
3
29
83
思路
暴力破解
两层for循环
#include <iostream>
using namespace std;
#define MAX 50000
int a[MAX+50]={0};
int b[3010];
int main()
{
int i,j,calc=0;
for(i=2;i<MAX;i++)
{
if(a[i]==0)
{
a[i]=1;
b[calc++]=i;
if(calc>=3000)
break;
int flag=0;
for(j=i+1;j<MAX;j++)
{
if(a[j]==0)
{
flag++;
if(flag==i)
{
a[j]=1;
flag=0;
}
}
}
}
}
while( cin>> i )
{
cout<<b[i-1]<<endl;
}
}
HLG 1182 栈
试题链接:http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1182
Description
给定一个从1开始的连续整数列1、2、3、4……n。
将上述数列按顺序入栈，中途栈顶元素可以出栈。
再给定一个出栈序列，判断此序列是否合法。
例如，将n设为4。即得到数列1、2、3、4。
再给定出栈序列1、3、4、2。
可以看出，此出栈序列合法。
过程如下，先将数列1、2、3、4中的元素1入栈，再将其出栈。
然后将元素2、3入栈，将元素3出栈。
最后将元素4入栈，再把栈内的仅余元素4、2出栈。
整个过程中，元素按照1、3、4、2的顺序出栈。证明其合法。
Input
输入包括多组测试用例。
对于每组测试用例，第一行包含一个整数n<100，代表从1开始的连续整数列长度。
第二行包含一个长度为n的数列，代表出栈序列。出栈序列的各元素在区间[1,n]内且不重复。
Output
若出栈序列合法，则输出Yes。
否则，输出No。
Sample Input
4
1 3 4 2
Sample Output
Yes
Hint
“Yes”,”No”注意大小写
#include<iostream>
#include<stack>
using namespace std;
int main()
{
int n,gq[101];
while(cin>>n)
{
stack<int>ls;
for(int i=0;i<n;i++)
cin>>gq[i];
int t=0;
for(int j=1;j<=n;j++)
{
ls.push(j);
while(!ls.empty()&&ls.top()==gq[t])
{
ls.pop();
t++;
}
}
if(ls.empty())
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
总结
每次在A题的时候，都会碰到用 while(scanf(“%d%d”,&n,&m)!=EOF) {…} 来判断结束标志的 用while(~scanf(“%d%d”,&n,&m)) {…} 一样可以判断结束标志。。。