【算法竞赛入门经典】第三章

题目链接：https://vjudge.net/contest/216712#overview

半年前写的了，现在再看的话，题目是挺水的，但是书上代码还是要看的。

书上有些方法比较巧妙，代码也比较好看吧。

有些题目比较烦，当时就没有做。

很好的小白练手题吧，这么多题每天做几个小时，三四天就能做完啦。

例题3-1 TeX中的引号

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

int main()
{
//    freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    char ch;
    int flag = -1;
    while(~scanf("%c", &ch))
    {
        if(ch == '"')
        {
            flag = -flag;
            if(flag == 1)
                printf("``");
            else
                printf("''");
        }
        else
            printf("%c", ch);
    }
    return 0;
}

例题3-2 WERTYU

'\'要转义，不要输出多余的换行！

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

int main()
{
//    freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
    char ch;
    int i, flag, l = strlen(s);
    while(~scanf("%c", &ch))
    {
        flag = 0;
        for(i = 0; i < l; i++)
            if(s[i] == ch)
            {
                flag = 1;
                break;
            }
        if(flag)
            printf("%c", s[i - 1]);
        else
            printf("%c", ch);
    }
    return 0;
}

例题3-3 回文词

注意输出格式，书上代码很巧妙。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

int main()
{
//    freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    char a[] = "AEHIJLMOSTUVWXYZ12358";
    char b[] = "A3HILJMO2TUVWXY51SEZ8";
    char s[1000];
    while(~scanf("%s", s))
    {
        int len = strlen(s);
        int p = 1, q = 1;
        for(int i = 0; i < (len + 1) / 2; i++)
        {
            if(s[i] != s[len - i - 1])                  //回文
                p = 0;
            int j, flag = 0;
            for(j = 0; j < strlen(a); j++)
                if(a[j] == s[i])
                {
                    flag = 1;
                    break;
                }
            if(flag && s[len - i - 1] != b[j] || !flag) //对称
                    q = 0;
            if(!p && !q)
                break;
        }
        if(!p && !q)
            printf("%s -- is not a palindrome.\n", s);
        else if(p && !q)
            printf("%s -- is a regular palindrome.\n", s);
        else if(!p && q)
            printf("%s -- is a mirrored string.\n", s);
        else
            printf("%s -- is a mirrored palindrome.\n", s);
        printf("\n");
    }
    return 0;
}

例题3-4 猜数字游戏的提示

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

int main()
{
//    freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int n, Case = 0, a[1010], b[1010], c[10], d[10];
    while(~scanf("%d", &n) && n)
    {
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        printf("Game %d:\n", ++Case);
        while(1)
        {
            int p = 0, q = 0;
            for(int i = 0; i < n; i++)
            {
                scanf("%d", &b[i]);
                if(a[i] == b[i])
                    p++;
            }
            if(b[0] == 0)
                break;
            memset(c, 0, sizeof(c));
            memset(d, 0, sizeof(d));
            for(int i = 0; i < n; i++)
            {
                c[a[i]]++;                  //a中各字母出现次数
                d[b[i]]++;                  //b中各字母出现次数
            }

            for(int i = 0; i < 10; i++)
                q = q + min(c[i], d[i]);
            q = q - p;
            printf("    (%d,%d)\n", p, q);
        }
    }
    return 0;
}

例题3-5 生成元

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

const int maxn = 100005;
int s[maxn];

void init()
{
    memset(s, 0, sizeof(s));
    for(int i = 0; i < maxn; i++)
    {
        int j = i;
        s[i] += i;
        while(j)
        {
            s[i] += j % 10;
            j /= 10;
        }
    }
}

int main()
{
//    freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    init();
    int T, n, i, flag;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        flag = 0;
        for(i = 0; i < n; i++)
        {
            if(n == s[i])
            {
                flag = 1;
                break;
            }
        }
        printf("%d\n", flag ? i : 0);
    }
    return 0;
}

例题3-6 环状序列

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

char s[110];
int len;

int judge(int a, int b)         //是否从a开始比从b开始小
{
    for(int i = 0; i < len; i++)
    {
        if(s[(a + i) % len] < s[(b + i) % len])
            return 1;
        else if(s[(a + i) % len] > s[(b + i) % len])
            return 0;
        else
            continue;
    }
}

int main()
{
//    freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", s);
        len = strlen(s);
        int ans = 0;
        for(int i = 1; i < len; i++)
        {
            if(judge(i, ans))
                ans = i;
        }
        for(int i = 0; i < len; i++)
            printf("%c", s[(ans + i) % len]);
        printf("\n");
    }
    return 0;
}

习题3-1 得分

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

char a[90];

int main()
{
//    freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T, n;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", a);
        int ans = 0, x = 0;
        for(int i = 0; i < strlen(a); i++)
        {
            if(a[i] == 'O')
                ans += ++x;
            else
                x = 0;
        }
        printf("%d\n", ans);
    }
    return 0;
}

习题3-2 分子量

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

char s[100];
map<char, int> M;

int main()
{
    //freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    M['C'] = 0;
    M['H'] = 1;
    M['O'] = 2;
    M['N'] = 3;
    int T;
    int fuck[4];
    double ans;
    scanf("%d", &T);
    while(T--)
    {
        memset(fuck, 0, sizeof(fuck));
        int i = 0;
        scanf("%s", s);
        int len = strlen(s);
        while(i < len)
        {
            int j;
            for(j = i + 1; j < len; j++)
                if(isalpha(s[j]))
                    break;
            if(j == i + 1)
                fuck[M[s[i]]] ++;
            else if(j == i + 2)
                fuck[M[s[i]]] += s[i + 1] - '0';
            else
                fuck[M[s[i]]] += (s[i + 1] - '0') * 10 + s[i + 2] - '0';
            i = j;
        }
        //for(int i = 0; i < 4; i++) cout << fuck[i] << endl;
        ans = 12.01 * fuck[0] + 1.008 * fuck[1] + 16 * fuck[2] + 14.01 * fuck[3];
        printf("%.3f\n", ans);
    }
    return 0;
}

习题3-3 数数字

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

int main()
{
//    freopen("output.txt", "w", stdout);
    int T, n;
    int s[10];
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        memset(s, 0, sizeof(s));
        for(int i = 0; i <= n; i++)
        {
            int p = i;
            while(p)
            {
                s[p % 10]++;
                p /= 10;
            }
        }
        for(int i = 0; i <= 9; i++)
            printf("%d%c", s[i], i == 9 ? '\n' : ' ');
    }
    return 0;
}

习题3-4 周期串

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

int main()
{
    //freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T, ans;
    char s[100];
    scanf("%d", &T);
    for(int kase = 1; kase <= T; kase++)
    {
        scanf("%s", s);
        int len = strlen(s);
        int ans;
        for(int i = 1; i <= len; i++)
        {
            if(len % i != 0)
            {
                continue;
            }
            else
            {
                bool flag = true;
                for(int j = 0; j < i; j++)
                {
                    for(int k = j; k < len; k = k + i)
                        if(s[k] != s[j])
                        {
                            flag = 0;
                            break;
                        }
                    if(!flag)
                        break;
                }
                if(flag)
                {
                    ans = i;
                    break;
                }
            }
        }
        if(kase == T)
            printf("%d\n", ans);
        else
            printf("%d\n\n", ans);
    }
    return 0;
}

习题3-5 谜题

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

char s[5][5];

int main()
{
    //freopen("input1.txt", "r", stdin);
   // freopen("output.txt", "w", stdout);
    int x, y, kase = 0;
    bool ok = true;
    while(scanf("%c", &s[0][0]) && s[0][0] != 'Z')
    {
        if(!ok)printf("\n");
        x = 0;
        y = 0;
        ok = false;
        for(int i = 1; i < 5; i++)
        {
            scanf("%c", &s[0][i]);
            if(s[0][i] == ' ') y = i;
        }
        getchar();
        for(int i = 1; i < 5; i++)
        {
            for(int j = 0; j < 5; j++)
            {
                scanf("%c", &s[i][j]);
                if(s[i][j] == ' ')
                {
                    x = i;
                    y = j;
                }
            }
            getchar();
        }
 /*
       for(int i = 0; i < 5; i++)
        {
            for(int j = 0; j < 5; j++)
                printf("%c", s[i][j]);
            cout << endl;
        }
        //*/
        char ch;
        bool flag = true;
        while((ch = getchar()) && ch != '0')
        {
            if(!flag) continue;
            if(ch == 'A')
            {
                if(x - 1 < 0)
                    flag = false;
                else
                {
                    s[x][y] = s[x - 1][y];
                    s[--x][y] = ' ';
                }
            }
            else if(ch == 'R')
            {
                if(y + 1 > 4)
                    flag = false;
                else
                {
                    s[x][y] = s[x][y + 1];
                    s[x][++y] = ' ';
                }
            }
            else if(ch == 'B')
            {
                if(x + 1 > 4)
                    flag = false;
                else
                {
                    s[x][y] = s[x + 1][y];
                    s[++x][y] = ' ';
                }
            }
            else if(ch == 'L')
            {
                if(y - 1 < 0)
                    flag = false;
                else
                {
                    s[x][y] = s[x][y - 1];
                    s[x][--y] = ' ';
                }
            }
        }
        getchar();
        printf("Puzzle #%d:\n", ++kase);
        if(flag)
        {
            for(int i = 0; i < 5; i++)
            {
                for(int j = 0; j < 5; j++)
                {
                    if(j)
                        printf(" %c", s[i][j]);
                    else
                        printf("%c", s[i][j]);
                }
                printf("\n");
            }
        }
        else
            printf("This puzzle has no final configuration.\n");
    }
    return 0;
}

习题3-6 纵横字谜的答案

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

char s[10][10];
int flag[10][10];
int r, c, p, kase = 0, ok = 1;

int main()
{
//    freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    while(~scanf("%d", &r) && r)
    {
        scanf("%d", &c);
        if(!ok)
            printf("\n");
        printf("puzzle #%d:\n", ++kase);
        ok = p = 0;
        getchar();
        memset(flag, 0, sizeof(flag));
        for(int i = 0; i < r; i++)
        {
            for(int j = 0; j < c; j++)
            {
                scanf("%c", &s[i][j]);
                if(s[i][j] != '*' && (i == 0 || j == 0) || (s[i - 1][j] == '*' || s[i][j - 1] == '*') && s[i][j] != '*')
                    flag[i][j] = ++p;
                else if(s[i][j] == '*')
                    flag[i][j] = -1;
            }
            getchar();
        }
        printf("Across\n");
        for(int i = 0; i < r; i++)
        {
            for(int j = 0; j < c; j++)
            {
                if(flag[i][j] != -1 && flag[i][j] != 0)
                {
                    printf("%3d.%c", flag[i][j], s[i][j]);
                    for(int k = j + 1; k <= c; k++)
                    {
                        if(flag[i][k] == -1 || k == c)
                        {
                            j = k;
                            printf("\n");
                            break;
                        }
                        else
                            printf("%c", s[i][k]);
                    }
                }
            }
        }
        printf("Down\n");
        for(int i = 0; i < r; i++)
        {
            for(int j = 0; j < c; j++)
            {
                if(flag[i][j] != -1 && flag[i][j] != 0 && (flag[i - 1][j] == -1 || i == 0))
                {
                    printf("%3d.%c", flag[i][j], s[i][j]);
                    for(int k = i + 1; k <= r; k++)
                    {
                        if(flag[k][j] == -1 || k == r)
                        {
                            printf("\n");
                            break;
                        }
                        else
                            printf("%c", s[k][j]);
                    }
                }
            }
        }
    }
    return 0;
}

习题3-7 DNA序列

注意输出字典序最小的

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

map<char, int> M;
char s[55][1005];
int a[4];

int main()
{
//    freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    M['A'] = 0;
    M['C'] = 1;
    M['G'] = 2;
    M['T'] = 3;
    int T, m, n, ans;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &m, &n);
        ans = 0;
        getchar();
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                scanf("%c", &s[i][j]);
            }
            getchar();
        }
/*        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
                cout << s[i][j];
            cout << endl;
        }*/
        for(int i = 0; i < n; i++)
        {
            memset(a, 0, sizeof(a));
            int x = 0;
            char c;
            for(int j = 0; j < m; j++)
            {
                a[M[s[j][i]]]++;
            }
            for(int j = 0; j < 4; j++)
                if(a[j] > a[x])
                    x = j;
            if(x == 0)
                c = 'A';
            else if(x == 1)
                c = 'C';
            else if(x == 2)
                c = 'G';
            else
                c = 'T';
            for(int j = 0; j < m; j++)
                if(s[j][i] != c)
                    ans++;
            printf("%c", c);
        }
        printf("\n%d\n", ans);
    }
    return 0;
}

习题3-9 子序列

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

int main()
{
//    freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    string s, t;
    while(cin >> s >> t)
    {
        int len1 = s.length();
        int len2 = t.length();
        int i = 0, j = 0;
        while(i < len1 && j < len2)
        {
            if(s[i] == t[j])
            {
                i++;
                j++;
            }
            else
                j++;
        }
        if(i == len1)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

习题3-10 盒子

关键是要知道如何判断

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<cctype>
#include<map>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

struct Node
{
    int x, y;
    bool operator ==(Node &t)
    {
        if(this->x == t.x && this->y == t.y)
            return true;
        return false;
    }
    bool operator !=(Node &t)
    {
        if(this->x != t.x || this->y != t.y)
            return true;
        return false;
    }
}node[6];

bool cmp(Node p, Node q)
{
    if(p.x != q.x)
        return p.x < q.x;
    else
        return p.y < q.y;
}

int main()
{
//    freopen("input1.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    while(~scanf("%d%d", &node[0].x, &node[0].y))
    {
        if(node[0].x > node[0].y)
            swap(node[0].x, node[0].y);
        for(int i = 1; i < 6; i++)
        {
            scanf("%d%d", &node[i].x, &node[i].y);
            if(node[i].x > node[i].y)
                swap(node[i].x, node[i].y);
        }
        sort(node, node + 6, cmp);
        bool ok = true;
        if(node[0] != node[1] || node[2] != node[3] || node[4] != node[5])
            ok = false;
        if(node[0].x != node[2].x)
            ok = false;
        if(node[0].y != node[4].x)
            ok = false;
        if(node[2].y != node[4].y)
            ok = false;
        if(ok)
            printf("POSSIBLE\n");
        else
            printf("IMPOSSIBLE\n");
    }
    return 0;
}