算法竞赛入门经典第三章例题(6/6)

第三章为笔者刚学习时所作，码风不大好看，代码习惯也不太好，对刘大爷代码借鉴严重； 在此放上以前写的代码，也是作为警示自己别写出难看代码（懒得改了

TEX Quotes

UVA-272

题意：给你一段话，让你将"..."变成``...''

题解：直接模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;

int main()
{
    int q = 1;
    char c;
    while((c = getchar())!=EOF){
        if(c == '"'){
            printf("%s", q ? "``" : "''");
            q = !q;
        }
        else
            printf("%c", c);
    }
    return 0;
}

WERTYU

UVA-10082

题意：键盘错位， 将键盘进行映射

题解： 直接模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
int main(){
    char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
    char b;
    while((b=getchar())!=EOF){
        int i;
        for(i=0;s[i]&&s[i]!=b;i++);
        if(s[i])putchar(s[i-1]);
        else putchar(b);
    }
    return 0;
}

Palindromes

UVA-401

题意： 给你一个字符串，问你他为何种字符串，如果为镜像串就输出"is a mirrored string.", 为回文串就输出" is a regular palindrome."， 即是回文串又是镜像串就输出"is a mirrored palindrome."，什么都不是就输出"is not a palindrome."

题解：直接模拟

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
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
const char* c="A   3  HIL JM O   2TUVWXY51SE Z  8 ";
const char* msg[]={" -- is not a palindrome."," -- is a regular palindrome."
," -- is a mirrored string."," -- is a mirrored palindrome."};
char hw(char a){
    if(a>64&&a<91)return c[a-'A'];
    return c[a-'0'+25];
}
int main(){
    string s;
    int a;
    while(cin>>s){
    a=s.length();
    int m=1,n=1;
    for(int i=0;i<(a+1)/2;i++){
        if(s[i]!=s[a-1-i])m=0;
        if(hw(s[i])!=s[a-1-i])n=0;
    }
    printf("%s%s\n\n",s.c_str(),msg[n*2+m]);
    }
    return 0;
}

Master-Mind Hints

UVA-340

题意：你有每个游戏包含n个数字，给你一个答案序列和一个猜测序列，让你统计位置正确的数字个数和在两个序列中出现过但是位置不同的数数量

题解：正确的直接统计，另一个先统计在俩个串中共同出现的字符个数，然后减去正确的字符个数即可

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
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
int c[1020]= {1},s[1020]= {1};

int main(){
    int n,q=1;
    while(~scanf("%d",&n)&&n!=0){
        printf("Game %d:\n",q++);
        for(int i=0; i<n; i++)
            scanf("%d",&c[i]);
        while(c[0]!=0){
            int a=0,b=0;
            for(int k=0; k<n; k++){
                scanf("%d",&s[k]);
                if(s[k]==c[k])
                    a+=1;
            }
            if(s[0]==0)
                break;
            for(int i=1; i<10; i++){
                int h=0,p=0;
                for(int k=0; k<n; k++){
                    if(c[k]==i)
                        h+=1;
                    if(s[k]==i)
                        p+=1;
                }
                if(h>p)
                    b+=p;
                else
                    b+=h;
            }
            printf("    (%d,%d)\n",a,b-a);
        }
    }
    return 0;
}

Digit Generator

UVA-1583

题意：介绍数字可能是由一个数字加上它每一位上的数字得来的，问你一个数字是否能由一个数字这么得来，有则输出那个数字，否则输出零

题意：因为数字范围很小，我们可以直接打表解决

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
#include<cstdio>
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
int s[100000];
int main(){
    memset(s,0,sizeof(s));
    for(int i=0;i<100000;i++){
        int c=0,b;
        b=i;
        while(b){
            c+=b%10;
            b/=10;
        }
        if(s[i+c]==0||s[i+c]>i)s[i+c]=i;
    }
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int m;
        scanf("%d",&m);
        printf("%d\n",s[m]);
    }
    return 0;
}

Circular Sequence

UVA-1584

题意：给你一个环状序列，问你以那个位置作为开头能使表达字典序最小

题解：枚举每个字母作为开头，取最小的表示法

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<cstdio>
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
char s[100];

int xl(char* s,int a,int b,int c){
    for(int i=0; i<c; i++)
        if(s[(i+a)%c]!=s[(i+b)%c])
                return s[(i+a)%c]<s[(i+b)%c];
    return 0;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%s",s);
        int m=0,a;
        a=strlen(s);
        for(int k=0; k<a; k++)
            if(xl(s,k,m,a))
                m=k;
        for(int k=0; k<a; k++){
            printf("%c",s[(m+k)%a]);
        }
        printf("\n");
    }
    return 0;
}

Comments

⬆︎TOP