算法竞赛入门刷题

算法竞赛入门刷题

按照书中的顺序刷题，太简单直接给答案。

第一章

第4题可以使用KMP算法，但是用暴力方法也能过；第8题提供了一种高精度浮点数除法的思路；第10题不要想太多，直接写if；

1、Score UVA-1585

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <cstring>
using namespace std;

char S[100];

int main() {

    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", S);
        int len = strlen(S);
        int k = 0;
        int ans = 0;
        for (int i = 0; i < len; ++i) {
            if (S[i] == 'O') ans += ++k;
            else k = 0;
        }
        printf("%d\n", ans);
    }
    return 0;
}

2、Molar mass UVA-1586

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <cstring>
using namespace std;

char S[100];
int M[256] = {0};
int main() {

    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", S);
        char ch = 'C';
        int len = strlen(S);
        int k = 0;
        int ans = 0;
        for (int i = 0; i <= len; ++i) {
            if (S[i] >= '0' && S[i] <= '9') {
                if (k == -1) k = S[i] - '0';
                else k = k * 10 + S[i] - '0';
            } else {
                M[ch] += (k == -1 ? 1 : k);
                ch = S[i], k = -1;
            }
        }
        printf("%.3lf\n", M['C'] * 12.01 + M['H'] * 1.008 + M['O'] * 16.00 + M['N'] * 14.01);
        memset(M,0,sizeof(M));
    }
    return 0;
}

3、Digit Counting UVA-1225

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <cstring>
using namespace std;

char S[100];
int M[10] = {0};
int main() {

    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            int k = i;
            while (k)++M[k % 10], k /= 10;
        }

        printf("%d %d %d %d %d %d %d %d %d %d\n", 
            M[0], M[1], M[2], M[3], M[4], M[5], M[6], M[7], M[8], M[9]);
        memset(M,0,sizeof(M));
    }
    return 0;
}

4、Periodic Strings UVA - 455

KMP 算法求最大周期: n-next[n], 非常简单证明其正确性。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <cstring>
using namespace std;

char S[100];
char N[100] = { -1,0 };
int main() {
    //freopen("out.txt","w+",stdout);
    int T, f = 0;
    scanf("%d", &T);
    while (T--) {
        scanf("\n%s",S);
        int n = strlen(S);
        int i = 1, j = 0;
        while (i < n) {
            if (S[i] == S[j]) N[++i] = ++j;
            else if (j == 0) N[++i] = 0;
            else j = N[j];
        }
        if (f) puts(""); f = true;
        if(n%(n-N[n]) == 0)printf("%d\n", n - N[n]);  
        else printf("%d\n", n);
    }
    return 0;
}

5、Puzzle UVA-227

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;

int kase=0;
char P[10][10];
char GetChar(){
    char ch = '\n';
    while(ch == '\n') ch = getchar();
    return ch; 
}

int main()
{
    char ch;
    int nx,ny;

    while((ch = GetChar())!= EOF){
        int x=0,y=0;
        bool f = false;
        if(ch == 'Z') break;
        P[0][0] = ch;
        for(int i = 0; i < 5; ++i){
            for(int j = i==0?1:0; j < 5; ++j) {

                P[i][j] = GetChar();
                if(P[i][j] == ' ') x=i,y=j;
            }
            ch = -1;
            while(ch!='\n') ch = getchar();
        }
        while((ch = GetChar())!= '0'){
            if(f) continue;
            nx = x,ny = y;
            if(ch == 'A') nx = nx - 1;
            else if(ch == 'B') nx = nx + 1;
            else if(ch == 'L') ny = ny - 1;
            else if(ch == 'R') ny = ny + 1;
            else f=true;
            if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) f = true; 
            if(f) continue;

            swap(P[x][y],P[nx][ny]);
            x = nx;
            y = ny; 
        }
        if(kase)puts("");
        printf("Puzzle #%d:\n",++kase);
        if(f) printf("This puzzle has no final configuration.\n");
        else{
            for(int i = 0; i < 5; ++i){
                for(int j = 0; j < 5; ++j) {
                    printf("%c", P[i][j]);
                    if(j!=4)printf(" ");
                }
                printf("\n");
            }    
        }
    }
    return 0;
}

6、Crossword Answers UVA-232

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
char S[15][15];
char B[15][15];
int N[15][15];
int kase = 0 ;
int main()
{
    int m,n;
    while(~scanf("%d",&m)){
        if(m==0) return 0;
        scanf("%d",&n);
        int no=0;
        for(int i = 0; i < m; ++i)scanf("%s",S[i]);

        for(int i = 0 ; i < m; ++i){
            for(int j = 0; j< n;++j){
                if(S[i][j] == '*') continue;
                if(i==0 || j == 0 || S[i-1][j]=='*' ||S[i][j-1]=='*' ) N[i][j] = ++no;
            }
        }

        memcpy(B,S,sizeof(S));
        if(kase)printf("\n");
        printf("puzzle #%d:\nAcross\n",++kase);
        for(int i = 0 ; i < m; ++i){
            for(int j = 0; j< n;++j){
                int x = j;
                if(S[i][x] == '*') continue;
                else printf("%3d.",N[i][j]); 
                while(S[i][x] != '*' && x < n) putchar(S[i][x]),S[i][x++]='*';
                printf("\n");
            } 
        }
        printf("Down\n");
        for(int i = 0 ; i < m; ++i){
            for(int j = 0; j< n;++j){
                int x = i;
                if(B[x][j] == '*') continue;
                else printf("%3d.",N[i][j]); 
                while(B[x][j] != '*' && x < m) putchar(B[x][j]),B[x++][j]='*';
                printf("\n");
            } 
        }

        //printf("\n");
    }

    return 0;
}

7、DNA Consensus String UVA-1368

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
char S[55][1005];
int M[255] ={0};
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int m,n,ans=0;
        scanf("%d%d",&m,&n);

        for(int i = 0; i < m; ++i)scanf("%s",S[i]);
        for(int i = 0 ; i < n; ++i){
            memset(M,0,sizeof(M));
            for(int j = 0; j< m;++j) ++M[S[j][i]];
            int t = M['A'];
            char ch = 'A';
            if(M['C'] > t) t=M[ch='C'];
            if(M['G'] > t) t=M[ch='G'];
            if(M['T'] > t) t=M[ch='T'];
            putchar(ch);
            ans += m - t;
        }
        printf("\n%d\n",ans);

    }

    return 0;
}

8、 ⭐Repeating Decimals UVA-202

本题方法值得借鉴

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
map<int,int> X;
int N[55000];

int main()
{
    int a,b,x;
    while(~scanf("%d%d",&a,&b)){
        X.clear();
        printf("%d",a);
        N[0] = a / b;
        int i = 1 ,j = 0, k = 1, f = 0, t;
        while(true){
            a = (a % b) * 10;
            if(t = X[a]) break;
            else X[a] = i;
            N[i++] = a / b;
        }
        printf("/%d = %d.",b,N[0]);
        while(true){
            if(k == t) printf("("), f = 1;
            printf("%d", N[k++]);
            if(f) ++j;
            if(k == i || j == 50) break;
        }
        if(k!=i)printf("...)\n");
        else printf(")\n");
        printf("   %d = number of digits in repeating cycle\n\n",i-t);
    }
    return 0;
}

9、 All in All UVA-10340

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
char A[100005];
char B[100005];

int main()
{
    while (~scanf("%s%s", A, B)) {
        int m = strlen(A);
        int n = strlen(B);
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (A[i] == B[j])++i;
            ++j;
        }
        if (i == m) puts("Yes");
        else puts("No");
    }

    return 0;
}

10、Box UVA-1587

长方体，只需要判断3个面

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
long long int F[6];
int H[3][2];

int main()
{
    int a, b;
    while (true) {
        bool f = false, ans = false;
        for (int i = 0; i < 6; ++i) {
            if (~scanf("%d%d", &a, &b)) {
                if (a > b)F[i] = a * 100005 + b;
                else F[i] = b * 100005 + a;
            }
            else return 0;
        }
        sort(F, F + 6);
        for (int i = 0; i < 3; ++i) {
            if (F[2 * i] != F[2 * i + 1]) {
                f = true;
                break;
            }
            H[i][0] = F[2 * i] / 100005;
            H[i][1] = F[2 * i] % 100005;
        }
        if (!f && H[0][0] == H[1][0]) {
            if (H[0][1] == H[2][0] && H[1][1] == H[2][1]) ans = true;
            else if (H[0][1] == H[2][1] && H[1][1] == H[2][0]) ans = true;
        }
        if (!f && H[0][0] == H[1][1]) {
            if (H[0][1] == H[2][0] && H[1][0] == H[2][1]) ans = true;
            else if (H[0][1] == H[2][1] && H[1][0] == H[2][0])ans = true;
        }
        if (!f && H[0][0] == H[2][0]) {
            if (H[0][1] == H[1][0] && H[2][1] == H[1][1])ans = true;
            else if (H[0][1] == H[1][1] && H[2][1] == H[1][0])ans = true;
        }
        if (!f && H[0][0] == H[2][1]) {
            if (H[0][1] == H[1][0] && H[2][0] == H[1][1])ans = true;
            else if (H[0][1] == H[1][1] && H[2][0] == H[1][0])ans = true;
        }

        if (f || !ans)puts("IMPOSSIBLE");
        else puts("POSSIBLE");
    }

    return 0;
}

11、Kickdown UVA-1588

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
char A[205];
char B[205];
int solve(char* a, char* b) {
    int m = strlen(a);
    int n = strlen(b);
    for (int i = 0; i < m; ++i) {
        int ans = 0;
        int j = 0;
        while (j < n) {
            int x = a[i + j] ? a[i + j] - '0' : 0;
            int y = b[j] ? b[j] - '0' : 0;
            if (x + y > 3)break;
            ++j;
        }
        if (j == n) return max(j + i, m);
    }
    return m + n;
}

int main()
{
//    freopen("in.txt","r",stdin);

    while (~scanf("%s%s",A,B)) {

        printf("%d\n", min(solve(A, B), solve(B, A)));
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));

    }

    return 0;
}

12、Floating-Point Numbers UVA-11809

根据题目得到公式，直接枚举

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
const double EPS = 1e-6;

int main()
{
//    freopen("in.txt","r",stdin);
    char S[256];
    while (~scanf("%s",S) && strcmp(S,"0e0") != 0) {
        double a, b;
        *strchr(S, 'e') = ' ';
        sscanf(S, "%lf%lf", &a, &b);
        for (int i = 0; i < 10; ++i) {
            for (int j = 1; j <= 30; ++j) {
                double x = log10(pow(2, i + 1) - 1) - (i + 1) * log10(2) + (pow(2, j) - 1) * log10(2);
                double y = log10(a) + b;
                if (fabs(x - y) < EPS) printf("%d %d\n", i, j), i = 100, j = 100;
            }
        }

    }

    return 0;
}