Ancient Cipher

UVA - 1339

感悟:要读原题,,,刘大爷翻译有些坑,,不读原题不太能理解,题目可以让相同字母映射到任意字母;

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
#include<bits/stdc++.h>
#define mem(x) memset(x, 0, sizeof(x))
using namespace std;

int main(){
char s[105], ss[105];
while(~scanf("%s%s", s, ss)){
int a[27], b[27];
mem(a), mem(b);
if(strlen(s) != strlen(ss)){
puts("NO");
continue;
}
int le = strlen(s);
for(int i = 0; i < le; i++)
a[int(s[i] - 'A')]++, b[int(ss[i] - 'A')]++;;
sort(a, a + 26);
sort(b, b + 26);
bool flag = true;
for(int i = 26; flag && i >= 0; i--)
if(a[i] != b[i])
flag = false;
if(flag)puts("YES");
else puts("NO");
}

return 0;
}

Hangman Judge

UVA - 489

感悟:学到了判断是否为string终点用npos;

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
#include<bits/stdc++.h>
using namespace std;

void guess(char s, string &ss, int &n){
if(ss.find(s) == ss.npos){
n++;
return;
}
while(ss.find(s) !=ss.npos)
ss.erase(ss.find(s), 1);
}

int main(){
int t;
while(~scanf("%d", &t) && ~t){
printf("Round %d\n", t);
string s, ss;
cin>> ss >> s;
int le = s.length();
int cs = 0;
for(int i = 0; cs < 7 && ss.length() && i < le; i++)
guess(s[i], ss, cs);
if(cs > 6)puts("You lose.");
else if(ss.length() == 0)puts("You win.");
else puts("You chickened out.");
}

return 0;
}

The Dole Queue

UVA - 133

感悟:发救济金,熟练运用小技巧;

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
#include<bits/stdc++.h>
using namespace std;

bool human[22];
int ju;

void go(int &p, int k, int db){
int t = human[p];
while(t < k)
t += human[(p = ((p + db)%ju + ju) % ju)];
}

int main(){
int n, k, m;
while(~scanf("%d%d%d", &n, &k, &m) && n){
memset(human, 1, sizeof(human));
int pa = 0, pb = n - 1;
ju = n;
while(n){
if(n != ju)putchar(',');
go(pa, k, 1);
go(pb, m, -1);
human[pa] = false, human[pb] = false;
if(pa != pb)printf("%3d%3d", pa + 1, pb + 1), n -= 2;
else printf("%3d", pa + 1), n--;
}
putchar('\n');
}

return 0;
}

Message Decoding

UVA - 213

感悟:学到函数思想的强大,更加仰慕刘大爷;

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
#include<bits/stdc++.h>
using namespace std;

char ma[8][1<<8];

char readchar(){
while(1){
char c = getchar();
if(c != '\n' && c != 'r')return c;
}
}

int readint(int n){
int m = 0;
while(n--) m = m * 2 + readchar() - '0';
return m;
}

bool readcode(){
memset(ma, 0, sizeof(ma));
ma[1][0] = readchar();
for(int i = 2; i < 8; i++){
for(int j = 0; j < (1 << i) - 1; j++){
ma[i][j] = getchar();
if(ma[i][j] == EOF)return false;
if(ma[i][j] == '\n' || ma[i][j] == '\r')return true;
}
}
}

int main(){
while(readcode()){
int le;
do{
le = readint(3);
if(le == 0)break;
do{
int code = readint(le);
if(code == (1 << le) - 1)break;
putchar(ma[le][code]);
}while(1);
}while(le);
putchar('\n');
}

return 0;
}

Spreadsheet Tracking

UVA - 512

感悟:模拟题,开始用刘大爷的第一种做法强行模拟来做,用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
#include<bits/stdc++.h>
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
#include<bits/stdc++.h>
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)

UVA - 12412

感悟:恶心大模拟,,,细节超多,,详情可看https://alberts97.github.io/lrj-ch4-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
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
158
159
160
161
162
163
#include<bits/stdc++.h>
using namespace std;
#define meau puts("Welcome to Student Performance Management System (SPMS).\n\n1 - Add\n2 - Remove\n3 - Query\n4 - Show ranking\n5 - Show Statistics\n0 - Exit\n")

const double eps = 1e-5;
map<string, bool>m, nm;
class SPMS{
private:
struct Student{
string SID, Name;
int CID;
int sx, yy, jj, dd, cx, zf;
double pjf;
int rk;
Student(string sid, int cid, string nam, int s, int y, int j, int d, double pp, int xx, int ff):SID(sid), CID(cid), Name(nam), sx(s), yy(y), jj(j), dd(d), pjf(pp), cx(xx), zf(ff){}
bool operator < (const Student t) const {
return zf < t.zf;
}
};
Student *man = NULL;
int n = 0;
int ppp = 0;
public:
SPMS(){
man = (Student*)malloc(10005*(sizeof(Student)));
n = 0;
ppp = 0;
}
static bool cmpp(SPMS::Student a, SPMS::Student b){
return a.cx < b.cx;
}
void add(){
int s, y, j, d, cid;string sid, nem;
while(1){
puts("Please enter the SID, CID, name and four scores. Enter 0 to finish.");
cin>> sid;
if(sid == "0")return;
cin>> cid >> nem >> s >> y >> j >> d;
if(m.find(sid) != m.end() && m[sid]){
puts("Duplicated SID.");
continue;
}
n++; ppp++;
m[sid] = true;
nm[nem] = true;
// if(man == NULL)man = (Student*)malloc(n*(sizeof(Student)));
// else man = (Student*)realloc(man, n*(sizeof(Student)));
man[n - 1] = Student(sid, cid, nem, s, y, j, d, (s + y + j + d) / 4.0 + eps, ppp, s + y + j + d);
}
}
void remo(){
while(1){
puts("Please enter SID or name. Enter 0 to finish.");
string tem;
cin>> tem;
if(tem == "0")return;
int tot = 0;
for(int i = 0; i < n; i++){
if(man[i].SID == tem || man[i].Name == tem){
if(m.find(tem) != m.end())m[tem] = false, nm[man[i].Name] = false;
if(nm.find(tem) != nm.end())nm[tem] = false, m[man[i].SID] = false;
tot++; n--;
for(int j = i; j < n; j++)
man[j] = man[j + 1];
i--;
}
}
// man = (Student*)realloc(man, n * sizeof(Student));
printf("%d student(s) removed.\n", tot);
}
}

void quer(){
sort(man, man + n);
int rankk = 1;
man[n - 1].rk = rankk++;
for(int i = n - 2; i >= 0; i--){
if(man[i + 1].zf == man[i].zf)man[i].rk = man[i + 1].rk;
else man[i].rk = rankk;
rankk++;
}
sort(man, man + n, cmpp);
while(1){
puts("Please enter SID or name. Enter 0 to finish.");
string tem;
cin>> tem;
if(tem == "0")return;
if(m.find(tem) == m.end() && nm.find(tem) == m.end())continue;
for(int i = 0; i < n; i++){
if(man[i].SID == tem || man[i].Name == tem){
cout<<man[i].rk<<' '<< man[i].SID << ' ' << man[i].CID << ' ' << man[i].Name << ' ' << man[i].sx << ' ' << man[i].yy << ' ' << man[i].jj << ' ' << man[i].dd <<' '<< man[i].dd+man[i].jj+man[i].sx+man[i].yy;
printf(" %.2f\n", man[i].pjf);
}
}
}
}
void sta(){
puts("Please enter class ID, 0 for the whole statistics.");
int tem, aver[5], pass[5], num[5];
memset(aver, 0, sizeof(aver));
memset(pass, 0, sizeof(pass));
memset(num, 0, sizeof(num));
int tot = 0;
cin>> tem;
if(tem != 0)
for(int i = 0; i < n; i++){
if(man[i].CID == tem){
tot++;
int pa = 0;
aver[0] += man[i].sx, aver[1] += man[i].yy, aver[2] += man[i].jj, aver[3] += man[i].dd;
if(man[i].sx >= 60)pass[0]++, pa++;
if(man[i].yy >= 60)pass[1]++, pa++;
if(man[i].jj >= 60)pass[2]++, pa++;
if(man[i].dd >= 60)pass[3]++, pa++;
num[pa]++;
}
}
else
for(int i = 0; i < n; i++){
tot++;
int pa = 0;
aver[0] += man[i].sx, aver[1] += man[i].yy, aver[2] += man[i].jj, aver[3] += man[i].dd;
if(man[i].sx >= 60)pass[0]++, pa++;
if(man[i].yy >= 60)pass[1]++, pa++;
if(man[i].jj >= 60)pass[2]++, pa++;
if(man[i].dd >= 60)pass[3]++, pa++;
num[pa]++;
}
// cout<< num[0] <<' ' <<num[1] << ' ' << num[2] <<' '<< num[3] <<' ' << num[4] << endl;
printf("Chinese\nAverage Score: %.2f\nNumber of passed students: %d\nNumber of failed students: %d\n\n", 1.0*aver[0]/tot + eps, pass[0], tot - pass[0]);
printf("Mathematics\nAverage Score: %.2f\nNumber of passed students: %d\nNumber of failed students: %d\n\n", 1.0*aver[1]/tot + eps, pass[1], tot - pass[1]);
printf("English\nAverage Score: %.2f\nNumber of passed students: %d\nNumber of failed students: %d\n\n", 1.0*aver[2]/tot + eps, pass[2], tot - pass[2]);
printf("Programming\nAverage Score: %.2f\nNumber of passed students: %d\nNumber of failed students: %d\n\n", 1.0*aver[3]/tot + eps, pass[3], tot - pass[3]);
printf("Overall:\nNumber of students who passed all subjects: %d\nNumber of students who passed 3 or more subjects: %d\nNumber of students who passed 2 or more subjects: %d\nNumber of students who passed 1 or more subjects: %d\nNumber of students who failed all subjects: %d\n\n", num[4], num[3] + num[4], num[2] + num[3] + num[4], num[1] + num[2] + num[3] + num[4], num[0]);
}
};

int main(){
SPMS tt;
int con;
do{
meau;
scanf("%d", &con);
switch(con){
case 1:
tt.add();
break;
case 2:
tt.remo();
break;
case 3:
tt.quer();
break;
case 4:
puts("Showing the ranklist hurts students' self-esteem. Don't do that.");
break;
case 5:
tt.sta();
}
}while(con);

return 0;
}

Comments

⬆︎TOP