算法竞赛入门经典第四章例题(6/6)
Ancient Cipher
感悟:要读原题,,,刘大爷翻译有些坑,,不读原题不太能理解,题目可以让相同字母映射到任意字母;
1 |
|
Hangman Judge
感悟:学到了判断是否为string终点用npos;
1 |
|
The Dole Queue
感悟:发救济金,熟练运用小技巧;
1 |
|
Message Decoding
感悟:学到函数思想的强大,更加仰慕刘大爷;
1 |
|
Spreadsheet Tracking
感悟:模拟题,开始用刘大爷的第一种做法强行模拟来做,用udebug总错,(get到一点是异或换数当两个数相同时全会变为零;)在看了第二种方法后,发现两种方法对于单点被移动到矩阵外的态度不同,第二总方法将所有步骤离线,询问时再全重复一次,只关注单点移动,当移动到矩阵外时任然认为存在,而全模拟时到外面就不记录了;试验后发现并没有移动到外面的操作,两种在uva上都能a掉。
离线: 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
using namespace std;
int h, l, n;
const int Ma = 1e4;
struct ml{
char s[5];
int r, l, rr, ll, a;
int x[Ma];
}cmd[Ma];
bool solve(int &hh, int &ll){
for(int i = 0; i < n; i++){
int ad = 0, bd = 0;
if(cmd[i].s[0] == 'E'){
if(hh == cmd[i].r && ll == cmd[i].l)
hh = cmd[i].rr, ll = cmd[i].ll;
else if(hh == cmd[i].rr && ll == cmd[i].ll)
hh = cmd[i].r, ll = cmd[i].l;
}
else {
for(int j = 0; j < cmd[i].a; j++){
if(cmd[i].s[0] == 'I'){
if(cmd[i].s[1] == 'R' && cmd[i].x[j] <= hh)ad++;
else if(cmd[i].s[1] == 'C' && cmd[i].x[j] <= ll)bd++;
}
if(cmd[i].s[0] == 'D'){
if(cmd[i].s[1] == 'R'){
if(cmd[i].x[j] == hh)return false;
else if(cmd[i].x[j] < hh)ad--;
}
else {
if(cmd[i].x[j] == ll)return false;
else if(cmd[i].x[j] < ll)bd--;
}
}
}
}
hh += ad, ll += bd;
}
return true;
}
int main(){
int tot = 0;
while(~scanf("%d%d", &h, &l) && h){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%s", cmd[i].s);
if(cmd[i].s[0] == 'E')
scanf("%d%d%d%d", &cmd[i].r, &cmd[i].l, &cmd[i].rr, &cmd[i].ll);
else {
scanf("%d", &cmd[i].a);
for(int j = 0; j < cmd[i].a; j++)
scanf("%d", &cmd[i].x[j]);
}
}
int m;
scanf("%d", &m);
if(tot != 0)putchar('\n');
printf("Spreadsheet #%d\n", ++tot);
while(m--){
int nn, ll;
scanf("%d%d", &nn, &ll);
printf("Cell data in (%d,%d) ", nn, ll);
if(solve(nn, ll))printf("moved to (%d,%d)\n", nn, ll);
else puts("GONE");
}
}
return 0;
}
全模拟: 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
using namespace std;
typedef pair<int, int> pai;
const int Ma = 1100;
const int Mod = 100000;
int hls[Ma][Ma], hl[Ma][Ma], ans[Ma][Ma], h, l;
bool aim[Ma];
void Copy(char type, int a, int b){
if(type == 'R')
for(int i = 1; i <= l; i++)
hls[a][i] = hl[b][i];
else
for(int i = 1; i <= h; i++)
hls[i][a] = hl[i][b];
}
void Delate(char type){
memcpy(hl, hls, sizeof(hls));
int lim = type == 'R' ? h : l, cnt = 0;
for(int i = 1; i <= lim; i++)
if(!aim[i])Copy(type, ++cnt, i);
if(type == 'R')h = cnt;
else l = cnt;
}
void ins(char type){
memcpy(hl, hls, sizeof(hls));
int lim = type == 'R' ? h : l, cnt = 0;
for(int i = 1; i <= lim; i++){
if(aim[i])Copy(type, ++cnt, 0);
Copy(type, ++cnt, i);
}
if(aim[lim + 1])Copy(type, ++cnt, 0);
if(type == 'R')h = cnt;
else l = cnt;
}
int main(){
int tot = 0;
memset(hls, 0, sizeof(hls));
while(~scanf("%d%d", &h, &l) && h != 0){
stack<pai>v;
memset(hls, 0, sizeof(hls));
memset(ans, 0, sizeof(ans));
for(int i = 1; i <= h; i++){
for(int j = 1; j <= l; j++){
hls[i][j] = i * Mod + j;
}
}
int n;
scanf("%d", &n);
while(n--){
char s[10];
scanf("%s", s);
if(s[0] == 'E'){
int r1, l1, r2, l2;
scanf("%d%d%d%d", &r1, &l1, &r2, &l2);
int t = hls[r1][l1]; hls[r1][l1] = hls[r2][l2], hls[r2][l2] = t;
if(r1 <= h && l1 <= l && (r2 > h || l2 > l))v.push({r2, l2});
else if(r2 <= h && l2 <= l && (r1 > h || l1 > l))v.push({r1, l1});
}
else {
memset(aim, 0, sizeof(aim));
int nn;
scanf("%d", &nn);
for(int i = 0; i < nn; i++){
int t; scanf("%d", &t);
aim[t] = true;
}
if(s[0] == 'D')Delate(s[1]);
else ins(s[1]);
}
}
for(int i = 1; i <= h; i++){
for(int j = 1; j <= l; j++){
ans[hls[i][j]/Mod][hls[i][j]%Mod] = i * Mod + j;
}
}
while(!v.empty()){
pai a = v.top();
v.pop();
if(hls[a.first][a.second])
ans[hls[a.first][a.second]/Mod][hls[a.first][a.second]%Mod] = a.first * Mod + a.second;
}
if(tot != 0){putchar('\n');/*fprintf(p, "\n");*/}
int m;
scanf("%d", &m);
printf("Spreadsheet #%d\n", ++tot);
while(m--){
int hh, ll;
scanf("%d%d", &hh, &ll);
printf("Cell data in (%d,%d) ", hh, ll);
/*fprintf(p, "Cell data in (%d,%d) ", hh, ll);*/
if(!ans[hh][ll]){printf("GONE\n");/*fprintf(p, "GONE\n");*/}
else {printf("moved to (%d,%d)\n", ans[hh][ll]/Mod, ans[hh][ll]%Mod);
/*fprintf(p, "moved to (%d,%d)\n", ans[hh][ll]/Mod, ans[hh][ll]%Mod);*/}
}
}
return 0;
}
A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)
感悟:恶心大模拟,,,细节超多,,详情可看https://alberts97.github.io/lrj-ch4-0/
1 |
|