算法竞赛入门经典第三章例题部分
TEX Quotes
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 <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <cstring>
using namespace std;
int main()
{
string s;
int cnt = 1;
while(getline(cin, s))
{
for(int i = 0; i < s.size(); ++i)
{
if(s[i] == '"')
{
if(cnt % 2)
{
cout << "``" ;
}
else
cout << "''";
cnt++;
}
else
cout << s[i];
}
cout << '\n';
}
}
|
WERTYU
学会了用常量数组，确实方便，一开始做用map，很麻烦。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <iostream>
#include <map>
using namespace std;
main()
{
char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
char c;
while((c = getchar()) != EOF)
{
int flag = 1;
for(int i = 1; s[i] ; ++i)
{
if(s[i] == c)
{
flag = 0;
putchar(s[i - 1]);
}
}
if(flag)
putchar(c);
}
}
|
Palindromes
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
| #include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
string s1 = "AEHIJLMOSTUVWXYZ12358";
string s2 = "A3HILJMO2TUVWXY51SEZ8";
bool is_palin(string s)
{
int sz = s.size() - 1;
for(int i = 0; i <= s.size() / 2; ++i)
{
if(s[i] != s[sz - i])
return 0;
}
return 1;
}
bool is_mirror(string s)
{
int sz = s.size() - 1;
for(int i = 0; i <= s.size() / 2; ++i)
{
int flag = 0;
for(int j = 0; j < s1.size(); ++j)
{
if(s1[j] == s[i])
{
flag = 1;
if(s2[j] != s[sz - i])
return 0;
}
}
if(flag == 0)
return 0;
}
return 1;
}
int main()
{
string s;
int num,num1;
while(cin >> s)
{
int num1 = is_palin(s);
int num2 = is_mirror(s);
if(num1 && num2)
cout << s << " -- is a mirrored palindrome." << '\n';
if(!num1 && !num2)
cout << s << " -- is not a palindrome." << '\n';
if(!num1 && num2)
cout << s << " -- is a mirrored string." << '\n';
if(num1 && !num2)
cout << s << " -- is a regular palindrome." << '\n';
cout << '\n';
}
}
|
Master-Mind Hints
代码1：自己写的算是比较暴力了
代码2： 参考的书，更简便一些。
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
| % 代码1
#include <bits/stdc++.h>
using namespace std;
int a[3005],b[3005];
int main()
{
int vis[1010];
int caser = 1, n;
while(cin >> n && n)
{
printf("Game %d:\n",caser++);
multiset<int>S;
for(int i = 0; i < n; ++i)
{
scanf("%d",&a[i]);
}
while(1){
for(int i = 0; i < n; ++i)
{
S.insert(a[i]);
}
for(int i = 0; i < n; ++i)
vis[i] = 0;
int cnt = 0;
for(int i = 0; i < n; ++i)
{
scanf("%d",&b[i]);
if(b[i] == 0)
cnt++;
}
if(cnt == n)
break;
int cnt1 = 0;
for(int i = 0; i < n; ++i)
{
if(!vis[i] && a[i] == b[i])
{
S.erase(S.find(a[i]));
vis[i] = 1;
cnt1++;
}
}
int cnt2 = 0;
for(int i = 0; i < n; ++i)
{
if(!vis[i] && S.count(b[i]) > 0)
{
S.erase(S.find(b[i]));
vis[i] = 1;
cnt2++;
}
}
printf(" (%d,%d)\n",cnt1, cnt2);
S.clear();
}
}
}
|
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
| % 代码二
#include <bits/stdc++.h>
using namespace std;
int a[3005],b[3005];
int main()
{
int vis[1005];
int n, caser = 1;
while(cin >> n && n)
{
printf("Game %d:\n",caser++);
for(int i = 0; i < n; ++i)
{
scanf("%d",&a[i]);
}
while(1)
{
int cnt = 0;
for(int i = 0; i < n; ++i)
{
scanf("%d",&b[i]);
if(b[i] == a[i])
cnt++;
}
if(b[0] == 0)
break;
int cnt3 = 0;
for(int i = 1; i <= 9; ++i)
{
int cnt1 ,cnt2;
cnt1 = 0, cnt2 = 0;
for(int j = 0; j < n; ++j)
{
if(a[j] == i) cnt1++;
if(b[j] == i) cnt2++;
}
cnt3 += min(cnt1,cnt2);
}
printf(" (%d,%d)\n",cnt,cnt3 - cnt);
}
}
}
|
Digit Generator
觉得数据范围也不大啊，枚举就行啊，还是超时了，毕竟我开始的算法每次都需要遍历N-1次，现在这个算法直接打表。
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
| #include <bits/stdc++.h>
using namespace std;
int f(int x)
{
int sum = 0;
while(x)
{
sum += x % 10;
x /= 10;
}
return sum;
}
int vis[200001];
int main()
{
int t, n, ans[200001];
memset(ans,0, sizeof(ans));
memset(vis,0, sizeof(vis));
for(int i = 1; i <= 100001; ++i)
{
int num = i + f(i);
if(ans[num] == 0 && !vis[num])
{
vis[num] = 1;
ans[num] = i;
}
}
cin >> t;
while(t--)
{
scanf("%d",&n);
if(ans[n] == 0)
cout << "0" << '\n';
else
cout << ans[n] << '\n';
}
}
|
Circular Sequence
开始不太会判断两个字符串的字典序大小，也是参考的书籍，而且我对这种循环的题目，不怎么喜欢求余，再补充一个序列感觉更简单一些。我们用ans记录当前最小字典序字符串的开始字符的下标，每次都不断更新。
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
| #include <iostream>
#include <string>
#include <algorithm>
#include <stdio.h>
using namespace std;
int Less(string s, int pos, int ans)
{
for(int i = 0; i < s.size() / 2; ++i)
{
if(s[pos + i] != s[ans + i])
return s[pos + i] < s[ans + i];
}
return 0;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
string s, s1, s3;
cin >> s;
s1 += s;
s1 += s;
int ans = 0;
for(int i = 0; i < s.size(); ++i)
{
if(Less(s1, i, ans)) ans = i;
}
for(int i = ans; i < ans + s.size() ; ++i)
{
cout << s1[i];
}
cout << '\n';
}
}
|