这四题都是easy难度的，但还是很适合初学者好好练习的！【老师布置的题目原来不是按难度排序的..】
一、Stack
就是给定一个入栈顺序，去判断给定的出栈顺序可不可能实现
Sample Input
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0
Sample Output
Yes
No
Yes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <iostream>
#include <stack>
using namespace std;
stack<int> mystack;
void Stackjudge(int q[1000],int num){
while(!mystack.empty()){
mystack.pop();
}
int i,j;
int flag1=0;
int test;
int first=0;
for(i=1;i<num+1;i++){
if(i!=q[0]){
mystack.push(i);
}
else{
first=i;
break;
}
}
if(!first){
cout<<"No"<<endl;
return;
}
for(j=1;j<num;j++){
if(q[j]>q[j-1]){
for(i=first+1;i<num+1;i++){
mystack.push(i);
if(i==q[j]){
mystack.pop();
first=i;
flag1=1;
}
}
if(!flag1){
cout<<"No"<<endl;
return;
}
}
flag1=0;
if(q[j]<q[j-1]){
test=mystack.top();
if(test==q[j]){
mystack.pop();
}
else{
cout<<"No"<<endl;
return;
}
}
}
std::cout<<"Yes"<<endl;
}
int main ()
{
int i;
int Q[1000];
while(1){
int num;
cin>>num;
if(num==0){
break;
}
while(1){
cin>>Q[0];
if(Q[0]==0){
break;
}
for(i=1;i<num;i++){
cin>>Q[i];
}
Stackjudge(Q,num);
}
cout<<endl;
}
return 0;
}
|
二、最短路径
股票经纪人对谣言的过分反应是周知的。你受雇找一种在股市中散布谣言的方法，使之以最快的速度传播给所有的人。
你必须把谣言先传给一个最合适的人
输入：
3 //三个人 2 2 4 3 5 //1号人有2个联系人，和2号花时间4,和3号花时间5 2 1 2 3 6 //2号人…… 2 1 2 2 2 5 3 4 4 2 8 5 3 1 5 8 4 1 6 4 10 2 7 5 2
输出：
3 2 //先传给3号，最多花时间2 3 10
分析：任意两点间求出最短路径(Floyd?) 。
找点：到任意点都有路径。“谣言传播”总耗时等于这些路径的最大值。
目标：使这个最大值最小的某个点。
这题不太想做…直接给floyd的算法吧
1
2
3
4
5
6
7
| for(k=0;k<n;k++)
for(i=0;i<n;i++)
for( j=0;j<n;j++)
if (d[i][j]>d[i][k]+d[k][j])
d[i][j]=d[i][k]+d[k][j];
|
三、DFS
Sum it up
求出所有可能的加法可能
Sample Input
4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
0 0
Sample Output
Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE
Sums of 400:
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int n,t,a[13],b[13],flag=1;
void dfs(int num,int k,int sum)
{
if(sum==0){
printf("%d",b[0]);
for(int i=1;i<num;i++)
printf("+%d",b[i]);
cout<<endl;
flag=0;
}
for(int i=k;i<n;i++){
if((i==k||a[i]!=a[i-1])&&sum-a[i]>=0){
b[num]=a[i];
dfs(num+1,i+1,sum-a[i]);
}
}
}
int main()
{
while(1){
cin>>t>>n;
if(t==0&&n==0)
break;
for(int i=0;i<n;i++)
cin>>a[i];
printf("Sums of %d:\n",t);
dfs(0,0,t);
if(f) {
printf("NONE\n");
}
}
return 0;
}
|
四、Dijkstra变形题
POJ - 1511 Invitation Cards（Dijkstra变形题）
因为不太熟悉C++的容器，并且本题要求存储的数据量极大，二重矩阵十分浪费空间且运行时间不过关，需要使用其他的数据结构，所以参考了以下博客。
这道题主要就让自己知道怎样构建“数组链表”
这里就提取几行关键的数据结构代码，博客中没有注释，我稍微写了一点点注释。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| vector<edge> map[maxn];
typedef pair<int,int> P;
map[a].push_back(edge(a,b,c));
priority_queue<P,vector<P>,greater<P> > Q;
Q.push(P(0,1));
while(!Q.empty()){
int v=Q.top().second;
Q.pop();
if(visited[v]) continue;
visited[v]=true;
for(int i=0;i<map[v].size();i++){
edge e=map[v][i];
if(dist[e.t]>dist[v]+e.c){
dist[e.t]=dist[v]+e.c;
Q.push(P(dist[e.t],e.t));
}
}
}
|
当然本题还要求各个点到源点的最短距离，这时我们可以用一个思路：反图，我们将原图中的所有边的方向反转，此时对远点使用Dijkstra算法则可得到其余各点到源点的最短距离。 大家自己画张图就可以很好得理解啦！