【2019CSPJ第一轮】试卷答案答案解析

　　2019CSPJ第一轮试卷
　　2019CSPJ第一轮答案
　　2019CSPJ第一轮答案解析
　　一：
　　。cn：中国的顶级域名是。cn，概念性知识，但大家注册的时候其实对这个后缀非常熟悉了，rg。noi。cn
　　01001010000011：与运算是有0就为0，都是1才是1，所以比较快速的做法是看有没有0。
　　4：1Byte8bits
　　sac：过去考过类似的，既然是做了c次1，自然等价于c。
　　7：1（50），2（25），3（13），4（7），5（4），6（2），7（1）
　　可随意访问任一元素：链表要访问到某个元素，必须一个个找过去。
　　18：我们保证放法升序就能没有遗漏枚举了，实际考场中采用此方法是最稳妥的，可以避免推错。8，17，26，35，44，116，125，134，224，233，1115。。。。当然从这里我们也能发现递推方程。
　　15：非常良心的考了原题，跟坐标是1，往右依次就是3、7、15
　　97：这个就没啥说的了。。
　　29：如果辗转相除啥的可能会比较麻烦，最简单的方式就是验证一下四个选项是否除得尽。
　　2400：阅读理解题，做法就按照说法来跑就好。
　　4：抽屉原理，最坏情况就是最平均的情况，123412341234，还有一张必然会构成4。
　　75：xyzyx模式，其中z必须是（0，1，8）中的一个，y必须是（0，1，8，6，9）中的一个，前面是6后面就是9，x同y，所以乘法原理后就是，35575
　　ABDEGHJCFI：经典的内容，在后序遍历找根然后在中序遍历划分左右子树即可。
　　图灵奖：果然有你
　　二（1）
　　x：输入的字符并没有什么限制。
　　：我们下面索引用到了i1
　　x：在sqrt（n）时也是存在因子的
　　：这个程序在做的就是特定位置小写转大写。
　　6：只有18的因子的位置会被判断是否需要转换，共6个
　　100000：验证每个选项，发现另外三个因子数明显没有36
　　二（2）
　　非常绕的一道题，也是让大家叫苦连天的题。到底在做什么呢？很快能发现a与b数组在做的是建立xy的链接，设置的时候也是对称设置的。
　　如果x原来对应的a〔x〕比新的y小，并且y原来对应的b〔y〕比新的x小，那么把原来的对应关系清空，建立新的关系。
　　：只要有关系来，不管会不会覆盖，至少不会关系全空。
　　x：看上去是对称的，但是因为有可能x1对应着y2，那么做到i1时a〔1〕2，b〔1〕0；
　　x：如果我们建立了23与32两组关系明显就可以了。
　　x：15行是在清楚原来x所对应的关系，和题目表述没啥联系。
　　2n2m：此时不会发生覆盖的情况，每组链接都被做了。
　　2n2：最后只会保留一组关系
　　二（3）
　　经验丰富的同学会看出来，这里就是在建立一颗树，每次找到当前区间最小值的位置作为根，然后划分左右做下一层。
　　最后的返回值非常重要，返回的是左边的值右边的值深度当前根权值，其实就是根节点权值为1，后续按照深度定权值
　　x：题目中找最小值有多个相等的话是随便选一个，不会有问题的
　　：b数组是每个点的value，a数组是每个点的key，最后计算是计算valuedepth，所以b数组全0结果就是全0
　　5000：每一层都要做一次，最坏情况下是一开始有序，每次都是第一个是根，所以要做100层，第一次100次，每层次数1，123。。。1005050
　　600：最好情况下就是每次都二分，层数应该是log2（100），也就是6左右。此时每层都差不多100个（后面随着有的点做了根会略少）。
　　385：最坏情况就是112233。。。。，手算一下，很快发现选择385。
　　580：最好情况就是刚好每次都二分，那么100个节点的每层节点数量就是（1，2，4，8，16，32，37）分别乘对应权值即可14123280192259
　　三（1）
　　这题很明显是利用递归填好每个的位置，从最大的开始递归往下做。
　　t：x，y指当前的矩阵左上角，n是多少阶，那么t自然就是当前是0还是1了。
　　x，y：左上角矩阵
　　xstep，ystep：第二个是右上，第三个是左下，那么剩下的自然是右下了。
　　n，0：一开始的时候是n阶，0为特征做下去。
　　1n：最终大小自然是2的n次幂，这边复合的就是位运算的方式的结果。
　　三（2）
　　题目其实提示的非常充分了，空还是很好填的
　　cnt〔b〔i〕〕：题目说了，先按照b排序，那么自然是用b数组做关键字。
　　ord〔cnt〔b〔i〕〕〕i：理解这里最重要的是搞懂1819行的内容，1819行在处理我们上限范围内的前缀和，而其实本质上就是每个人的排名了。所以这边我们的cnt〔b〔i〕〕就是排名了，后续就很好理解了。
　　cnt〔a〔i〕〕：现在做a，同样的方式即可。
　　res〔cnt〔a〔ord〔i〕〕〕〕ord〔i〕：同上，此时我们采用res数组来处理最终结果。
　　a〔res〔i〕〕，b〔res〔i〕〕：输出最终顺序的a与b。