紫书第3章部分题解

2020-08-15

UVa340[Master-Mind Hints]

题意略

例题，书中讲解详细。

思路简单，直接暴力搞一搞，需要注意一下B的计算方法：对每个数字（1~9）统计其在两个串中出现的次数c1,c2， min{c1，c2}就是该数字对B的贡献，加起来最后减去A即为所求。

UVa1583[Digit Generator]

题意求某数的最小生成元（若x加上x的各个数字之和为y，则x为y的生成元）

例题，书中讲解详细。

考虑到直接暴力不大行，所以采用的了打表的方法。

for(int i=1;i<max;i++){
    int x=i,y=i;
    while(x>0){y+=(x%10);x/=10;}
    if(ans[y]==0||i<ans[y]) ans[y]=i;
  }

UVa1584[Circular Sequence]

题意略

书中例题，讲解详细。

出现了字典序，要额外写一个判断两点字典序的函数，如下：

int less(char* s,int a,int b){ //验证以a为起点的字典序是否小于以b为起点的！
  int n=strlen(s);
  for(int i=0;i<n;i++){
    if(s[(a+i)%n]!=s[(b+i)%n]) return s[(a+i)%n]<s[(b+i)%n];
  }
  return 0;
}

剩下的就是枚举一下啦。

UVa1586[Molar mass]

题意计算相对分子质量

暴力搞一下就行，判断数字时记得用isdigit函数，要加上头文件

UVa455[Periodic Strings]

题意求某一字符串的周期

因为数据不大，所以直接枚举周期。

记得最后一定要验证一下，串长是否为枚举周期的倍数!

UVa1368[DNA Consensus String]

题意暂略

仔细读题，我们需要造的字符串即字符矩阵里每一列出现次数最多的字典序小的那一个。

又因为只有4个字母，直接统计比较一下就好了。（感觉好多同学写的都好长）

UVa1587[Box]

题意给出六个矩形的长宽，判断是否能组成一个长方体

这题可以找规律利用好数组的下标。

显然十二个长度之中只能有三个不同的数据，则有

总共出现一个长度，满足情况
总共出现两个长度，则其中一个长度在12个数里出现4次，并在四个矩形中出现
总共出现三个长度，则必须每个长度都出现4次，并在四个矩形中出现

故初始化3个数组abc，a表示该长度的种类，b表示该种类的长度出现了几次，c表示该种类的长度出现在了几个矩形中

跟随书中章节的内容，这题个人还是想要用C写，所以想了好久，最后还是看了一位大佬的博客才明白的。。。

参考博客：https://blog.csdn.net/qq_43702096/article/details/97003716?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.channel_param

UVa1588

题意略

直接枚举，判断是否符合条件即可。（用的是s[i]==’2’&&s[j]==’2’)

结果还是WA了几次，最后的原因是枚举链时没有及时跳出。

 for(i=0;i<l1;i++){
      flag =1;
      for(j=0;j<l2;j++){
        if(i+j>l1) break; //一定要及时跳出！！
        if(s1[i+j]=='2'&&s2[j]=='2'){flag =0;break;}
      }
      if(flag) break;
    }

UVa11809

题意略

读完题之后有点懵，后来才明白这是到数学题。。。

题干的知识背景是浮点数储存的方式，浮点数在计算机里是分三部分表示的，最前面一位表示符号，后面一部分是尾数，最后一部分是阶码，表示方法类似于科学记数法，不过是二进制的，尾数是M阶码是E的话那么表示起来就是M × 2^E了。然后对于M还有一个要求，就是1/2 ≤ M < 1，所以用二进制表示M的话就应该是0.1XX……，用计算机表示的时候就把最前面的“0.1”这个永远不变的部分给省略掉，只表示可能变化的部分。阶码部分则是只用二进制表示E。

上面的图就给出了一个例子，前面的0表示是正数。后面8位表示尾数m，这里是0.111111111（注意后面是9个1，因为头一个省略了）。之后那个0表示分割，最后面6位表示e的二进制为111111。所以这个数就是，用十进制表示就是。

不过数据较小，所以可以直接打表，找到关系就好了。

令尾数为 m，阶码为 e，输入中有AeB，则他们有如下关系：

$m×2^e=A×10^B$

这里的 e 最大为 2^30 - 1，会超范围，所以我们可以对等式两边取对数：

$log10(m×2^e)=log10(A×10^B)$

等价于：

$log10m+e×log102=log10A+B$

题目中还提到 0 < A < 10，所以 log10A<1,是一个小数，因为B一定是一个整数，所以 B=(int)(log10m+e×log102)，即直接取整即可。所以此时有：

$B=(int)(lgm+e×lg2)$ $A=10^(lgm+e×lg2−B)$

所以，我们只要保存M和E对应的A和B，然后查表就行啦，

参考博客：https://blog.csdn.net/Artprog/article/details/69676946
https://blog.csdn.net/crazysillynerd/article/details/43339157?a=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param

Amazing