紫书第三章课后习题

时间:2023-02-27 00:05:28

UVA - 1585

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<time.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t --)
    {
        char a[100];
        scanf("%s",a);
        int ans = 0;
        int tot = 0;
        for(int i = 0; i < strlen(a); i ++)
        {
            if(a[i] == 'O')
            {
                tot++;
                ans += tot;
            }
            else tot = 0;
        }
        printf("%d\n",ans);
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<time.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t --)
    {
        char a[100];
        scanf("%s",a);

        map<char, double>m;
        m['O'] = 16.00;
        m['C'] = 12.01;
        m['H'] = 1.008;
        m['N'] = 14.01;
        int n = strlen(a);
        double ans = 0;
        double num = 0;
        double cheng;
        for(int i = 0; i < n; i ++)
        {
            if(a[i] >= '0' && a[i] <= '9') continue;
            if(a[i] >= 'A' && a[i] <= 'Z'){
                cheng = m[a[i]];
               // cout<<cheng<<endl;
                int j = i + 1;
                if((a[j] >= 'A' && a[j] <= 'Z')||a[j] == '\0')
                {
                    ans += cheng;
                    continue;
                }
                num = (a[j] - '1') + 1;
                while((a[j+1]>='0'&&a[j+1]<='9') || a[j+1] == '\0')
                {
                    if(a[j+1] == '\0') break;
                    num = num * 10 + (a[j+1] - '1') + 1;
                    j ++;
                }
                ans += num * cheng;
            }
        }
        printf("%.3f\n",ans);
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<time.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t --)
    {
        int num[10] = {0};
        int n;
        scanf("%d",&n);
        for(int i = 1; i <= n; i ++){
            int j = i;
            while(j)
            {
                num[j%10]++;
                j/=10;
            }
        }
        for(int i = 0; i <= 8; i ++)
            printf("%d ",num[i]);
        printf("%d\n",num[9]);
    }
    return 0;
}

UVA - 455

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<time.h>
using namespace std;

int main()
{
    char a[100];
    int t;
    scanf("%d",&t);
    int cas = 0;
    while(t --)
    {
        scanf("%s",a);
        int n = strlen(a);
        int ans;
        int tot;
        for(int i = 1; i <= n; i ++)
        {
            tot = 0;
            int cnt = -1;
            if(n % i) continue;
            for(int j = i; j < n; j ++)
            {
                if(a[j] == a[++ cnt])
                    tot ++;
                if(cnt == i - 1)
                    cnt = -1;
            }
            if(tot == n - i)
            {
                ans = i;
                break;
            }
        }
        if(cas)printf("\n");
        cas ++;
        printf("%d\n",ans);
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<time.h>
using namespace std;

int main()
{
    char a[7][7];
    int cas = 1;
    while(1)
    {

        int p, q;
        char c;
        if(cas != 1)
            getchar();
        for(int i = 0; i < 5; i ++)
            for(int j = 0; j <= 5; j ++)
        {
            c = getchar();
            if(j == 5) continue;
            if(c == ' ')
            {
                p = i;
                q = j;
            }
            a[i][j] = c;
        }
       // getchar();

        if(a[0][0] == 'Z') break;
//        for(int i = 0; i < 5; i ++)
//        {
//            for(int j = 0; j < 5; j ++)
//            {
//                cout<<a[i][j];
//                if(j != 4)
//                    cout<<' ';
//            }
//            cout<<endl;
//        }
        char ss[1005];
        int cnt = 0;
        while(1)
        {
            c = getchar();
            if(c == '0') break;
            if(c == '\n')continue;
            if(c == ' ')continue;
            else ss[cnt ++] = c;
        }
        ss[cnt] = '\0';
//        for(int i = 0; i < strlen(ss); i ++)
//            cout<<ss[i];
//            cout<<endl;
//        cout<<p<<' '<<q<<endl;
        bool flag = 1;
        for(int i = 0; i < strlen(ss); i ++)
        {
            if(ss[i] == 'A')
            {
                if(p - 1 < 0) {
                    flag = 0;
                    break;
                }
                swap(a[p][q], a[p-1][q]);
//                a[p][q] = a[p-1][q];
//                a[p-1][q] = ' ';
                p--;
            }
            if(ss[i] == 'B')
            {
                if(p + 1 >= 5) {
                    flag = 0;
                    break;
                }
                swap(a[p][q], a[p+1][q]);
//                a[p][q] = a[p+1][q];
//                a[p+1][q] = ' ';
                p++;
            }
            if(ss[i] == 'L')
            {
                if(q - 1 < 0) {
                    flag = 0;
                    break;
                }
                swap(a[p][q], a[p][q-1]);
//                a[p][q] = a[p][q - 1];
//                a[p][q-1] = ' ';
                q--;
            }
            if(ss[i] == 'R')
            {
                if(q + 1 >= 5) {
                    flag = 0;
                    break;
                }
                swap(a[p][q], a[p][q+1]);
//                a[p][q] = a[p][q+1];
//                a[p][q+1] = ' ';
                q++;
            }
        }
        if(cas != 1)cout<<endl;
        printf("Puzzle #%d:\n",cas++);
        //cout<<flag<<endl;
        if(! flag)
        {
            printf("This puzzle has no final configuration.\n");
            continue;
        }
        for(int i = 0; i < 5; i ++)
        {
            for(int j = 0; j < 5; j ++)
            {
                cout<<a[i][j];
                if(j != 4)
                    cout<<' ';
            }
            cout<<endl;
        }
        //cout<<endl;
    }
    return 0;
}

    UVA - 1368
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<time.h>
using namespace std;
#define inf 0x3f3f3f3f
char a[52][1005];
int main()
{
    int n, m;
    int t;
    scanf("%d",&t);
    int num[4];
    while(t --)
    {
        scanf("%d%d",&n,&m);
        for(int i = 0; i < n; i ++)
            scanf("%s",a[i]);
        char ans[1005];
        char ans1;
        int ans2 = 0;
        int maxy = -1;
        for(int i = 0; i < m; i ++)
        {
            memset(num, 0, sizeof(num));
            maxy = -1;
            for(int j = 0; j < n; j ++)
            {
                if(a[j][i] == 'A')
                {
                    num[0] ++;
                    if(num[0] >= maxy)
                    {
                        maxy = num[0];
                        ans1 = 'A';
                    }
                }
                if(a[j][i] == 'C')
                {
                    num[1] ++;
                    if(num[1] == num[0]){}
                    else if(num[1] >= maxy)
                    {
                        maxy = num[1];
                        ans1 = 'C';
                    }
                }
                if(a[j][i] == 'G')
                {
                    num[2] ++;
                    if((num[2] == num[1]) || (num[2] == num[0])){}
                    else if(num[2] >= maxy)
                    {
                        maxy = num[2];
                        ans1 = 'G';
                    }
                }
                if(a[j][i] == 'T')
                {
                    num[3] ++;
                    if((num[3] == num[2]) || (num[3] == num[0]) || (num[3] == num[1])){}
                    else if(num[3] >= maxy)
                    {
                        maxy = num[3];
                        ans1 = 'T';
                    }
                }
            }
            ans2 += (n - maxy);
            ans[i] = ans1;
        }
        for(int i = 0; i < m; i ++)
            cout<<ans[i];
        cout<<endl;
        printf("%d\n",ans2);
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<time.h>
using namespace std;
char a[100005], b[100005];
int main()
{
    
    while(scanf("%s%s",a,b)!=EOF)
    {
        int pos = 0;
        for(int i = 0; i < strlen(b); i ++)
        {
            if(a[pos] == b[i])
            {
                pos ++;
                continue;
            }
        }
        if(pos == strlen(a)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<time.h>
using namespace std;

int main()
{
    char a[105], b[105];
    while(scanf("%s%s",a, b) != EOF)
    {
        int n = strlen(a);
        int m = strlen(b);
        int ans = m + n;
        int sum = 0;
        int maxy = 0;
        for(int i = 0; i < n; i ++)
        {
            int st = i;
            bool flag = 1;
            sum = 0;
            for(int j = 0; j < m && st < n; j ++, st ++)
            {
                //cout<<(int)(a[st]-'0')+(int)(b[j]-'0')<<endl;
                if((int)(a[st]-'0')+(int)(b[j]-'0')<=3)
                {
                    sum ++;
                }
                else
                {
                    flag = 0;
                    break;
                }
            }
            if(! flag) sum = 0;
            maxy = max(maxy, sum);
        }
        for(int i = 0; i < m; i ++)
        {
            int st = i;
            bool flag = 1;
            sum = 0;
            for(int j = 0; j < n && st < m; j ++, st ++)
            {
                //cout<<(int)(a[st]-'0')+(int)(b[j]-'0')<<endl;
                if((int)(b[st]-'0')+(int)(a[j]-'0')<=3)
                {
                    sum ++;
                }
                else
                {
                    flag = 0;
                    break;
                }
            }
            if(! flag) sum = 0;
            maxy = max(maxy, sum);
        }
        printf("%d\n",ans - maxy);
    }
    return 0;
}