算法竞赛入门经典第三章习题(12/12)

这时候的代码水平极为低下，写出的代码仍然不好看，不过和习题一样，也作为警示自己别写出难看代码放上来吧（懒得改了

Score

UVA - 1585

题意：给你一个序列，每个O得分为连续出现的O的数量，X不得分

题解：直接模拟

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<math.h>
#include<string.h>
using namespace std;
char s[100];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s",s);
        int a,b=0,c=0;
        a=strlen(s);
        for(int k=0;k<a;k++){
            if(s[k]=='O')c+=++b;
            else b=0;
        }
        printf("%d\n",c);
    }
    return 0;
}

Molar mass

UVA-1586

题意：给你一个分子式，问你他的摩尔质量

题解: 直接模拟(写得好傻，看着想笑，这居然是我的代码.jpg😆）

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
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<iostream>
#include<math.h>
#include<string.h>
#define C 12.01
#define H 1.008
#define O 16.00
#define N 14.01
using namespace std;
char s[100];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%s",s);
        int a;
        double b,c=0;
        a=strlen(s);
        for(int k=0; k<a; k++){
            if(s[k+1]>'0'&&s[k+1]<='9'&&s[k+2]>'0'&&s[k+2]<='9'){
                switch(s[k]){
                case 'C':
                    c+=C*((s[k+1]-'0')*10+s[k+2]-'0');
                    break;
                case 'H':
                    c+=H*((s[k+1]-'0')*10+s[k+2]-'0');
                    break;
                case 'O':
                    c+=O*((s[k+1]-'0')*10+s[k+2]-'0');
                    break;
                case 'N':
                    c+=N*((s[k+1]-'0')*10+s[k+2]-'0');
                }
                k+=2;
            }
            if(s[k+1]>'0'&&s[k+1]<='9'){
                switch(s[k]){
                case 'C':
                    c+=C*(s[k+1]-'0');
                    break;
                case 'H':
                    c+=H*(s[k+1]-'0');
                    break;
                case 'O':
                    c+=O*(s[k+1]-'0');
                    break;
                case 'N':
                    c+=N*(s[k+1]-'0');
                }
                k+=1;
            }
            else
                switch(s[k]){
                case 'C':
                    c+=C;
                    break;
                case 'H':
                    c+=H;
                    break;
                case 'O':
                    c+=O;
                    break;
                case 'N':
                    c+=N;
                }
        }
        printf("%.3lf\n",c);
        c=0;
    }
    return 0;
}

Digit Counting

UVA - 1225

题意：给你一个n，问你从一到n的数字各位上出现多少个0， 1， 2， 3， 4 .. . 9，输出10个数字，代表这些数字出现过多少次

题解：从低位开始考虑，当前位所有数字出现了高位代表数字的次数，后面值影响当前位的出现次数，特殊考虑0，当当前位为0时，当前位0出现了高位次数减一加上后面的量。具体看代码（为现在才发现数据范围巨小无比，直接暴力解决，，，对当年的我感到绝望，，，我当时是把0出现考虑在1出现之前，如果考虑在9出现之后就无需特判0了，感兴趣的读者可自行一试。）

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
#include<iostream>
#include<cstdio>
using namespace std;
#include<math.h>
int xc(int a){
    int z=1,i;
    for (i=0; i<a; i++)
        z*=10;
    return z;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int l=0; l<n; l++){
        int a,b,c[11]= {0},i,d,t,f,k,q,o;
        scanf("%d",&b);
        i = log10(b);//0~i-1
        for(t=0; t<=i; t++){
            a = b/xc(t)%10;//当前
            q = b/xc(t+1);//高
            f = b%xc(t);//后面值
            if (a>0)
                c[0]+=q*xc(t);
            else if(a==0 && i>0)
                c[0]+=(q-1)*xc(t)+f+1;
            for(o=1; o<10; o++){
                if(a>o)
                    c[o]+=(q+1)*xc(t);
                else if(a==o)
                    c[o]+=f+1+q*xc(t);
                else
                    c[o]+=q*xc(t);
            }
        }
        for (k=0; k<10; k++){
            printf("%d",c[k]);
            if(k!=9)
                printf(" ");
        }
        printf("\n");
    }
    return 0;
}

Cube painting

UVA-253

题意：给你一个周期串，问你周期是多少

题解：枚举周期

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

int main(){
    char s[80];
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int a,b,c=0,d=0,q=0;
        scanf("%s",s);
        a=strlen(s);
        for(int k=1;k<=a;k++){
            q=0;
            if(a%k==0){
                for(q=0;q+k<a;q++)
                if(s[q]!=s[k+q])break;
            }
            if(q+k==a){printf("%d\n",k);if(i!=n-1)printf("\n");break;
            }
        }
    }
    return 0;
}

Puzzle

UVA - 227

题意： 给你一个5*5的方格， 再给你一串命令，如果非法输出非法，反之输出执行命令后的方格

题解：直接模拟（代码好丑, 注意输出

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
string s[10];
int kbh,kbl,k=0;

void yidong(char a){
    switch(a){
    case 'A':
        if(kbh-1<0||kbh-1>=5){
            k=1;
            break;
        }
        s[kbh][kbl]=s[kbh-1][kbl];
        s[kbh-1][kbl]=' ';
        kbh-=1;
        break;
    case 'B':
        if(kbh+1<0||kbh+1>=5){
            k=1;
            break;
        }
        s[kbh][kbl]=s[kbh+1][kbl];
        s[kbh+1][kbl]=' ';
        kbh+=1;
        break;
    case 'R':
        if(kbl+1<0||kbl+1>=5){
            k=1;
            break;
        }
        s[kbh][kbl]=s[kbh][kbl+1];
        s[kbh][kbl+1]=' ';
        kbl+=1;
        break;
    case 'L':
        if(kbl-1<0||kbl-1>=5){
            k=1;
            break;
        }
        s[kbh][kbl]=s[kbh][kbl-1];
        s[kbh][kbl-1]=' ';
        kbl-=1;
        break;
    }
}

int main(){
    int n=0;
    while(1){
        k=0;
        for(int i=0; i<5; i++){
            getline(cin,s[i]);
            if(s[i]=="Z")
                goto js;
        }
        for(int hang=0; hang<5; hang++)
            for(int lie=0; lie<5; lie++){
                if(s[hang][lie]==' '){
                    kbh=hang;
                    kbl=lie;
                    goto CL;
                }
            }
CL:
        char c;
        while((c=getchar())!='0'){
            yidong(c);
        }
        getchar();
        if(n!=0)printf("\n");
        printf("Puzzle #%d:\n",++n);
        if(k==0){
            for(int k=0; k<5; k++)
                for(int i=0; i<5; i++){
                    cout<<s[k][i];
                    if(i!=4)
                        printf(" ");
                    else
                        printf("\n");
                }
        }
        else
            printf("This puzzle has no final configuration.\n");
    }
js:
    return 0;
}

Crossword Answers

UVA-232

题意：纵横向字谜，就是让你横向输出所有单词，注意排序，从左到右从上到下的顺序

题解： 直接模拟(好丑好丑，，看不下去了😂)

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

int main(){
    int r,c,n=0;
    while(~scanf("%d",&r)&&r!=0&&scanf("%d",&c)){
        int cx=0;
        for(int i=0; i<r; i++)
            cin>>s[i];
        for(int i=0; i<r; i++)
            for(int k=0; k<c; k++){
                if(s[i][k]!='*'&&(i-1<0||k-1<0||s[i-1][k]=='*'||s[i][k-1]=='*')){
                    wz[i][k]=++cx;
                }
            }
        if(n!=0)printf("\n");
        printf("puzzle #%d:\n",++n);
        printf("Across\n");
        for(int i=0; i<r; i++){
            for(int k=0; k<c; k++){
                if(s[i][k]=='*')continue;
                else{
                        printf("%3d.",wz[i][k]);
                        for(int q=k;q<c&&s[i][q]!='*';q++){
                            cout<<s[i][q];
                            k=q;
                        }
                        printf("\n");
                    }
            }
        }
        printf("Down\n");
            for(int i=0; i<r; i++){
                for(int k=0;k<c;k++){
                    if(s[i][k]=='*')continue;
                    else{
                        printf("%3d.",wz[i][k]);
                        for(int q=i;q<r;q++){
                            if(s[q][k]=='*')break;
                            cout<<s[q][k];
                            s[q][k]='*';
                        }
                        printf("\n");
                    }
                }
            }
    }
    return 0;
}

DNA Consensus String

UVA-1368

题意：给你几个DNA序列，让你输出它们hamming距离最小的DNA序列；

题解：取位置上出现次数最少的输出(我到底写了些什么！！！太混乱了吧😓)

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
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
#include<string>
#include<stdlib.h>
#include<iomanip>
using namespace std;
int main()
{
    int h;
    scanf("%d",&h);
    while(h--)
    {
        int n,m,hmm=0;
        scanf("%d%d",&n,&m);
        string s[100];
        char l[2000];
        int c[2000][6];
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++)
        {
            cin>>s[i];
        }
        for(int i=0;i<m;i++)
            for(int k=0;k<n;k++)
        {
            if(s[k][i]=='A')c[i][0]+=1;
            else if(s[k][i]=='C')c[i][1]+=1;
            else if(s[k][i]=='G')c[i][2]+=1;
            else if(s[k][i]=='T')c[i][3]+=1;
        }
        for(int i=0;i<m;i++)
        {
            int a,c1,g,t;
            a=c[i][0];
            c1=c[i][1];
            g=c[i][2];
            t=c[i][3];
            l[i]=(a>=c1&&a>=g&&a>=t)?(hmm+=(c1+g+t),'A'):((c1>=g&&c1>=t)?(hmm+=(a+g+t),'C'):(g>=t?(hmm+=(a+c1+t),'G'):(hmm+=(a+c1+g),'T')));
        }
        for(int k=0;k<m;k++)
        cout<<l[k];
        cout<<"\n";
        cout<<hmm<<"\n";
    }
    return 0;
}

Repeating Decimals

UVA-202

题意：给你两个数，问你相除是不是循环小数

题解：模拟除法获取下一位数字，当循环时退出

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#define Maxx 3050
using namespace std;

int xs[Maxx];
int ys[Maxx];

int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        int yss = 0, xss = 0;
        memset(xs, 0, sizeof(xs));
        memset(ys, 0, sizeof(ys));
        printf("%d/%d = %d.", n, m, n/m);

        int t = n, i;
        while(1)
        {
            t = t % m * 10;
            xs[xss++] = t / m;
            for(i = 0; i < yss; i++)
                if(ys[i] == t) break;
            if(i != yss) break;
            ys[yss++] = t;
        }

        for(int k=0; k<i; k++)
            cout<<xs[k];
        cout<<'(';
        if(xss-1>50){
            for(int k=i; k<50; k++)
            cout<<xs[k];
            cout<<"...";
        }
        else
            for(int k=i; k<xss-1; k++)
            cout<<xs[k];
        cout<<')'<<'\n';

        printf("   %d = number of digits in repeating cycle\n\n", xss-i-1);
    }
    return 0;
}

All in All

UVA-10340

题意：给你两个字符串s, t，问你能否通过删减得到t得到s

题解：直接做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;

int main(){
    string mb,sc;
    while(cin>>mb>>sc){
        int k=0;
        for(int i=0;i<sc.length();i++){
            if(mb[k]==sc[i])++k;
        }
        if(k==mb.length())printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

Box

UVA - 1587

题意：给你三个面，问你能不能组成一个长方体

题解： 直接判断

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;

struct fu
{
    int f, s;
}fw[6];

bool cmpp(fu a, fu b)
{
    if(a.f != b.f)return a.f < b.f;
    else return a.s < b.s;
}

int main()
{
    while(~scanf("%d%d", &fw[0].f, &fw[0].s)){
        if(fw[0].f > fw[0].s) swap(fw[0].f, fw[0].s);
        for(int i = 1; i < 6; i++){
            scanf("%d%d", &fw[i].f, &fw[i].s);
            if(fw[i].f > fw[i].s)swap(fw[i].f, fw[i].s);
        }

        sort(fw, fw + 6, cmpp);

        bool n = true;
        for(int i = 0; i < 6; i += 2){
            if(fw[i].f != fw[i + 1].f || fw[i].s != fw[i + 1].s){n = false; break;}
        }

//        cout<< fw[0].f <<' '<< fw[2].f <<' '<< fw[0].s <<' ' <<fw[4].f <<' '<< fw[2].s <<' '<< fw[4].s<<'\n';
        if(n && fw[0].f == fw[2].f && fw[0].s == fw[4].f && fw[2].s == fw[4].s)printf("POSSIBLE\n");
        else printf("IMPOSSIBLE\n");
    }

    return 0;
}

Kickdown

UVA - 1588

题意：给你两个凹凸块，让你把他们接在一起，高度不超过三；

题解：直接匹配，因为不能转向，很可能出现退一步就能达成连接的情况，所以要正向反向都匹配下，（我代码中没直接记录，，至于原因，，，我对我当时感到绝望，，

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<bits/stdc++.h>
using namespace std;

int cmp(string a, string b, int n, int m)
{
    int i = 0, j = 0, t = 0;
    while(i < n && j < m)
        if(a[i] + b[j] - '0' > '3') i = 0, j = ++t;
        else ++i, ++j;

    return n + m - i;
}

int main()
{
    string bot, top;

    while(cin>> bot >> top){
        int le, l;
        le = bot.length();
        l = top.length();
        cout<< ((cmp(bot, top, le, l) < cmp(top, bot, l, le)) ? cmp(bot, top, le, l) : cmp(top, bot, l, le)) <<'\n';
    }

    return 0;
}

Floating-Point Numbers

UVA-11809

这题我专门为他写过题解

Comments

⬆︎TOP