算法竞赛入门经典 第三章例题

发表于 | 更新于 | 分类于 | 阅读次数：

算法竞赛入门经典第三章例题部分

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';
    }
}