刘汝佳紫书3章选题题解


本来想放题目的,但是太懒了

UVa340 Master-Mind Hints

直接统计可得A, 为了求B, 对于每个数字(1~9),统计二者出现的次数cntb1, cntb2.则min(cntb1, cntb2)就是该数字对B的贡献。最后要减去A的部分。


#include 
//#define LOCAL
//accepted
int main(void)
{
#ifdef LOCAL
    freopen("datain.txt", "r", stdin);
    freopen("dataout.txt", "w", stdout);
#endif
    int n;
    int count = 1;
    while(scanf("%d", &n) != EOF && n)
    {
        printf("Game %d:\n", count);
        int secret[1005];
        for(int i = 0; i < n; i++)  scanf("%d", secret + i);
        int guess[1005];
        while(1)
        {
            for(int i = 0; i < n; i++)  scanf("%d", guess + i);
            if(guess[0] == 0)   break;
            int cnta = 0;
            for(int i = 0; i < n; i++)
            {
                if(guess[i] == secret[i])   cnta++;
            }
            
            int cntb = 0;
            for(int i = 0; i <= 9; i++)
            {
                int cntb1 = 0, cntb2 = 0;
                for(int j = 0; j < n; j++)
                {
                    if(secret[j] == i)   cntb1++;
                    if(guess[j] == i)   cntb2++;   
                }
                cntb += (cntb1 < cntb2 ? cntb1 : cntb2);
            }
            
            printf("    (%d,%d)\n", cnta, cntb - cnta);
        }
        count++;
    }
    return 0;
}

UVa1583 Digit Generator

测试样例n(1 <= n <= 100000), 易知最小生成元肯定是比n小的数。又因为n最大为100000,故它的最小生成元肯定是小于100000的。由此我们先预处理1到100000的生成元,与它们的样例对应。于是就可以做到想要什么就给什么了。


#include 
//accepted
int result[100050];
int main(void)
{
    for(int i = 0; i < 100000; i++)
    {
        int temp = i + 1, s = temp;
        while(temp)
        {
            s += temp % 10;s
            temp /= 10;
        }
        if(!result[s])
            result[s] = i + 1;
    }
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        printf("%d\n", result[n]);
    }
    return 0;
}

UVa1584 Circular Sequence

这里要找最小字典序的环状串,首先是声明一个int类型变量用来当作指针去遍历数组,最后也是这个变量存储最小字典序环状串的第一个元素。
将下一个元素与该变量指针对应的字符比较,如果下一个元素的字典序小于该指针变量所指向的字符,则刷新该指针变量指向的值将其指向下一个元素。
如果下一个元素的字典序与该指针变量所指向的字符相等,则通过for循环从以上两个元素位置开始依次比较字典序,从而确定该不该刷新指针指向。
如果下一个元素的字典序大于该指针所指向的字符,则再进行下一个元素的比较。


#include 
#include 
//accepted
char str[105];
int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%s", str);
        int len = strlen(str);
        char ch = str[0];
        int p = 0;
        for(int i = 0; i < len; i++)
        {
            if(ch > str[i])
            {
                ch = str[i];
                p = i;
            }
            else if(ch == str[i])
            {
                for(int j = 0; j < len; j++)
                {
                    if(str[(p + j) % len] < str[(i + j) % len])
                       break;
                    else if(str[(p + j) %len] > str[(i + j) % len])
                    {
                        ch = str[i];
                        p = i;
                    }
                }
            }
        }
        for(int i = 0; i < len; i++)
            printf("%c", str[(p + i) % len]);
        putchar('\n');
    }
    return 0;
}

UVa1586 Molar mass

读入化学表达式后,我从右向左开始计算。首先遇到的可能是元素下标也有可能是元素符号,如果开始就是元素符号则直接计算这个元素的质量。如果开始读入的是数字那么将数字乘以1加到变量j上,如果下一个还是数字则该数字乘以10加到变量j上。依次直到遇到一个元素符号,则将j乘以该元素的原子质量。


#include 
#include 
//accepted
char str[85];
char s[4] = {'C', 'H', 'O', 'N'};
double value[4] = {12.01, 1.008, 16, 14.01};
int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%s", str);
        int len = strlen(str);
        double result = 0;
        int num = 1;
        int j = 1;
        while(len--)
        {
            if(str[len] <= 'O' && str[len] >= 'C')
            {
                for(int i = 0; i < 4; i++)
                    if(str[len] == s[i])
                    {
                        if(j != 1)  num--;
                        result += value[i] * num;
                    }
                j = num = 1;
            }
            else// if(str[len] <= '9' && str[len] >= '0')
            {
                num += (str[len] - '0') * j;
                j *= 10;
            }
        }
        printf("%.3lf\n", result);
    }
    return 0;
}

UVa455 Periodic Strings

首先假设周期为1,然后将第一个周期作为标准,与后面周期进行比对。如果不符,则周期加1,再把第一个周期作为标准与后面周期进行比对。直到比对均一致时,得到周期大小,如果字符串长度大小对周期大小取模不为0,则表示
该周期大小不对,直接让字符串长度作为周期大小。


#include 
#include 
//accepted
//UVa455
int main(void)
{
    int n;
    scanf("%d", &n);
    char str[100];
    
    while(n--)
    {
        scanf("%s", str);
        int i = 0, j = 1;
        while(str[i] != '\0')
        {
            for(int m = 0; m < j && str[i + m] != '\0'; m++)
                if(str[(i + m) % j] != str[i + m])  j = i + 1;
            i++;
        }
        int len = strlen(str);
        if(len % j != 0)    j = len;
        printf("%d\n", j);
        if(n > 0)   printf("\n");
    }
    return 0;
}

UVa1368 DNA Consensus String

声明一个二维字符数组,char str51.将输入读入该数组。
然后是一个两层的嵌套循环,用于一列一列的遍历这个字符矩阵。
例如第一列,统计4种字符出现的次数,找到出现次数最高的字符,这个字符就是最优字符。(当然若出现相等次数的字符,则字典序小的为最优字符)然后n - (最高次数)即为该列的 Hamming 距离,把每列的 Hamming 距离累加起来即可。


#include 
/*accepted*/
char str[51][1005];
char s[4] = {'A', 'C', 'G', 'T'};
int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int m, n;
        scanf("%d%d", &m, &n);
        for(int i = 0; i < m; i++)
            scanf("%s", str[i]);
        int max, index, value = 0;
        for(int i = 0; i < n; i++)
        {
            int num[4] = {0};
            for(int j = 0; j < m; j++)
            {
                for(int k = 0; k < 4; k++)
                    if(str[j][i] == s[k])
                        num[k]++;
            }
            max = num[0];
            index = 0;
            for(int j = 0; j < 4; j++)
                if(num[j] > max)
                {
                    max = num[j];
                    index = j;
                }
            putchar(s[index]);
            value += m - max;
        }
        putchar('\n');
        printf("%d\n", value);
    }
    return 0;
}

UVa1587 Box

首先构建一个结构体用来存木板的高和宽。
然后声明一个结构体数组大小为6,
在读取输入时判断大小,使得木板宽小于等于它的高。
然后对它进行排序,按照宽从小到大排列,当遇到宽相等时按照高进行排列。
最后得到这种


图是有点简陋啊,表达的意思就是你要是能把这六个木板组成一个箱子,相同颜色处数值要相等。


#include 
#include 
/*accepted*/
typedef struct
{
    int w;
    int h;
}wood;
wood box[6];
int cmp(const void *a, const void *b)
{
    int x = ((wood *)a)->w - ((wood *)b)->w;
    if(x)
        return x;
    else
        return ((wood *)a)->h - ((wood *)b)->h;
}
int main(void)
{
    while(1)
    {
        int i;
        for(i = 0; i < 6; i++)
        {
            if(scanf("%d%d", &(box[i].w), &(box[i].h)) == EOF)  break;
            if(box[i].w > box[i].h)
            {
                int temp = box[i].w;
                box[i].w = box[i].h;
                box[i].h = temp;
            }
        }
        if(i != 6)  break;
        qsort(box, 6, sizeof(box[0]), cmp);
        if(box[0].w == box[1].w && box[1].w == box[2].w && box[2].w == box[3].w && box[2].h == box[3].h && box[3].h == box[4].h && box[4].h == box[5].h && box[0].h == box[1].h && box[1].h == box[4].w && box[4].w == box[5].w)
            printf("POSSIBLE\n");
        else
            printf("IMPOSSIBLE\n");
    }
    return 0;
}

UVa1588 Kickdown

两个齿轮要想对上,当1对1时,即凹对凹,没事。当1对2或者2对1时,正好凹凸契合。只有当2对2时会出现问题。
代码注释中写得还算清楚,我就不多赘述了。


#include 
#include 
//accepted
char str1[105], str2[105];
int main(void)
{
    while(scanf("%s%s", str1, str2) != EOF)
    {
        int len1 = strlen(str1);
        int len2 = strlen(str2);
        int i, j;
        /*初始状态为两个齿轮左对齐*/
        /*该循环为下齿轮len1向右匹配上齿轮len2*/
        for(i = 0; i < len1; i++)
        {
            for(j = 0; j < len2 && (i + j) < len1; j++)
                if(str1[i + j] == str2[j] && str2[j] == '2')
                    break;
            if(j == len2 || i + j == len1)  break;
        }
        int min = len1 + len2 - j;  /*得到的最小长度*/
        /*该循环为上齿轮len2向左匹配下齿轮len1*/
        for(i = 0; i < len2; i++)
        {
            for(j = 0; j < len1 && (i + j) < len2; j++)
                if(str2[i + j] == str1[j] && str1[j] == '2')
                    break;
            if(j == len1 || i + j == len2)  break;
        }
        int temp = len1 + len2 - j; /*得到的最小长度*/
        min = min < temp ? min : temp;  /*最后在两个最小中取最小的*/
        printf("%d\n", min);
    }
    return 0;
}

UVa11809 Floating-Point Numbers

这题题意理解上有点难,对我这种菜菜来说。
最后在csdn上找到了一个大佬的文章,大致看懂了题目。首先我开始不知道二进制小数怎么转换十进制,后来百度了一下,搞懂了操作过程,但是还不知道是什么道理。。。
然后我把他的c++代码用c实现了一下。就是先打表,然后就照着输出了。
发一下大佬的博客地址。


#include 
#include 
#include 
double M[20][40];
long long E[20][40];
/*accepted*/
int main(void)
{
    for(int i = 0; i <= 9; i++)
        for(int j = 1; j <= 30; j++)
        {
            /*1 - pow(2, -1 - i)为等比数列求和结果,此时的m,e表示当M为i位E为就位时所表示的最大浮点数(m * 2^e)*/
            double m = 1 - pow(2, -1 - i), e = pow(2, j) - 1;
            double t = log10(m) + e * log10(2);
            E[i][j] = t;    /*double 赋值给 long long 发生截断, E[i][j]表示B*/
            M[i][j] = pow(10, t - E[i][j]); /*M[i][j]表示A*/
        }
    char str[25];
    while(scanf("%s", str) != EOF && strcmp(str, "0e0") != 0)
    {
        double A;
        int B;
        sscanf(str, "%17lfe%d", &A, &B);
        while(A < 1)
        {
            A *= 10;
            B -= 1;
        }
        int i, j;
        for(i = 0; i <= 9; i++)
        {
            for(j = 1; j <= 30; j++)
                if(B == E[i][j] && fabs(A - M[i][j]) < 1e-4)
                {
                    printf("%d %d\n", i, j);
                    break;
                }
            if(j != 31) break;
        }
    }
    return 0;
}
好了,睡觉。

声明:Trikker的小破站|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 刘汝佳紫书3章选题题解


分享一些学习成果