【UVA-101】解题报告（模拟）
原始题目
题目大意
有\(n\)个积木，初始放在\(0,1,2 \cdots n-1\)位置上，有四种搭积木操作 - move a onto b
where a and b are block numbers, puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.
把a和b上的积木放回原来位置，再将a放置到b上。
move a over b
where a and b are block numbers, puts block a onto the top of the stack containing block b, after returning any blocks that are stacked on top of block a to their initial positions.
把a上的积木放回原来位置，再将a放置在b所在的积木堆上。
pile a onto b
where a and b are block numbers, moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to their initial positions prior to the pile taking place. The blocks stacked above block a retain their order when moved.
把b上的积木放回原来位置，再将a和a之上的积木块一起放在b上（保持相对顺序）。
pile a over b
where a and b are block numbers, puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. The blocks stacked above block a retain their original order when moved.
把a和a之上的积木块一起放在b所在的积木堆上（保持相对顺序）。
直至遇到quit停止操作，输出最后每个位置上的积木状态。
解题思路
- 由于不涉及积木块放置在指定位置的操作，还原必定到原有位置且原有位置为空（易证），不用考虑木块放回的特殊情况。
- 注意判断是否在同一堆上，违法命令不进行任何实际操作
- 模拟四种操作即可
解题代码
- 数组模拟四种操作
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <iostream>
#include <iomanip>
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-a;i>=a;--i)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define np next_permutation
#define ms(x,a) memset((x),a,sizeof((x)))
#define all(x) x.begin(),x.end()
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
const int maxl=26;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
int n,m,a,b;
string s1,s2;
int top[maxn],bottom[maxn],place[maxn],mmp[maxn];
void initial(){
rep(i,0,n) top[i]=bottom[i]=place[i]=i;
rep(i,0,n) mmp[i]=-1;
}
void solve(int aa,int bb,int index){
switch(index){
case 1:
{
while(mmp[aa]!=-1){
int next=mmp[aa];
mmp[aa]=mmp[next];
mmp[next]=-1;
top[next]=bottom[next]=place[next]=next;
}
while(mmp[bb]!=-1){
int next=mmp[bb];
mmp[bb]=mmp[next];
mmp[next]=-1;
top[next]=bottom[next]=place[next]=next;
}
mmp[bb]=aa;
int start=top[place[aa]];
if(start==aa) top[aa]=-1;
else{
while(mmp[start]!=aa) start=mmp[start];
mmp[start]=-1;
}
place[aa]=place[bb];
}
break;
case 2:
{
while(mmp[aa]!=-1){
int next=mmp[aa];
mmp[aa]=mmp[next];
mmp[next]=-1;
top[next]=bottom[next]=place[next]=next;
}
while(mmp[bb]!=-1) bb=mmp[bb];
mmp[bb]=aa;
int start=top[place[aa]];
if(start==aa) top[aa]=-1;
else{
while(mmp[start]!=aa) start=mmp[start];
mmp[start]=-1;
}
place[aa]=place[bb];
}
break;
case 3:
{
while(mmp[bb]!=-1){
int next=mmp[bb];
mmp[bb]=mmp[next];
mmp[next]=-1;
top[next]=bottom[next]=place[next]=next;
}
mmp[bb]=aa;
int start=top[place[aa]];
if(start==aa) top[aa]=-1;
else{
while(mmp[start]!=aa) start=mmp[start];
mmp[start]=-1;
}
while(mmp[bb]!=-1){
place[mmp[bb]]=place[bb];
bb=mmp[bb];
}
}
break;
case 4:
{
while(mmp[bb]!=-1) bb=mmp[bb];
mmp[bb]=aa;
int start=top[place[aa]];
if(start==aa) top[aa]=-1;
else{
while(mmp[start]!=aa) start=mmp[start];
mmp[start]=-1;
}
while(mmp[bb]!=-1){
place[mmp[bb]]=place[bb];
bb=mmp[bb];
}
}
break;
}
}
int main(){
while(cin>>n){
initial();
while(cin>>s1&& s1[0]!='q'){
cin>>a>>s2>>b;
if(place[a]==place[b]) continue;
if(s1[0]=='m' && s2[1]=='n') solve(a,b,1);
if(s1[0]=='m' && s2[1]=='v') solve(a,b,2);
if(s1[0]=='p' && s2[1]=='n') solve(a,b,3);
if(s1[0]=='p' && s2[1]=='v') solve(a,b,4);
}
rep(i,0,n){
cout<<i<<":";
if(top[i]==-1) cout<<endl;
else {
int start=top[i];
cout<<" "<<start;
while(mmp[start]!=-1){
start=mmp[start];
cout<<" "<<start;
}
cout<<endl;
}
}
// cout<<endl;
}
} - vector模拟两种操作
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#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define np next_permutation
#define cl(x,a,n) memset(x,a,sizeof(int)*n)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<string,string> pss;
const int maxn=30;
int n;
vector<int> pile[maxn];
void find_block(int a,int &p, int & h) {// 引用形式返回ouke和高度
for( p=0;p<n;p++){
for(h=0;h<pile[p].size();h++){
if(pile[p][h]==a ) return;
}
}
}
void clear_above(int p,int h){
for(int i=h+1;i<pile[p].size();i++){
int b=pile[p][i];
pile[b].pb(b);
}
pile[p].resize(h+1);
}
void pile_onto(int p,int h,int p2){
for(int i=h; i<pile[p].size();i++){
pile[p2].pb(pile[p][i]);
}
pile[p].resize(h);
}
void print(){
for(int i=0;i<n;++i){
printf("%d:",i);
for(int j=0;j<pile[i].size();j++) printf(" %d",pile[i][j]);
printf("\n");
}
}
int main(){
int a,b;
cin>>n;
string s1,s2;
rep(i,0,n) pile[i].pb(i);
while(cin>>s1>>a>>s2>>b){
int pa,pb,ha,hb;
find_block(a,pa,ha);
find_block(b,pb,hb);
if(pa==pb) continue; //feifa
if(s2=="onto") clear_above(pb,hb);
if(s1=="move") clear_above(pa,ha);
pile_onto(pa,ha,pb);
}
print();
return 0;
}
收获与反思
- 大模拟，输出注意PE。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！