2020.05.02【NOIP普及组】模拟赛C组31 总结

$2020.05.02$2020.05.02【$NOIP$NOIP普及组】模拟赛$C$C组$31$31 总结

这次比赛我$AK$AK了，拿了满分，题目简单很多（比上次）。

第一题：笨小猴

题目

题目描述
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。

输入
输入文件word.in只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。

输出
输出文件word.out共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；
第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。

样例输入
【输入样例1】
error

【输入样例2】
olympic
 

样例输出
【输出样例1】
Lucky Word
2

【输出样例1解释】
单词error中出现最多的字母r出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。


【输出样例2】
No Answer
0

【输出样例2解释】
单词olympic中出现最多的字母出现了1次，出现次数最少的字母出现了1次，1-1=0，0不是质数。

数据范围限制

解题方法

直接用桶暴力。
时间复杂度为$O(n)$O(n)。
注：$n$n为字符串的长度。

第二题：数列

题目

题目描述
给定一个正整数k(3≤k≤15)，把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：
 1，3，4，9，10，12，13，…
（该序列实际上就是：3^0，3^1，3^0+3^1，3^2，3^0+3^2，3^1+3^2，3^0+3^1+3^2，…）
请你求出这个序列的第N项的值（用10进制数表示）。
例如，对于k=3，N=100，正确答案应该是981。

输入
输入文件sequence.in 只有1行，为2个正整数，用一个空格隔开：
k N（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。

输出
输出文件sequence.out 为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*10^9）。（整数前不要有空格和其他符号）。

样例输入
3 100

样例输出
981

数据范围限制

解题方法

我们将这些十进制数转化为$k$k进制，得
$1\:10\:11\:100\:101\:110\:111\:...$11011100101110111...
我们发现这些数是$0$0或$1$1，也就是选或不选。
我们把这个数转化二进制。
从最低位开始，如果遇到一个$1$1，就加上位置编号的$k$k次方。
注意：一定要开$long\:long$longlong。

第三题：$Jam$Jam的计数法

题目

题目描述
Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。
在Jam数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam还指定使用字母的范围，例如，从2到10，表示只能使用{b,c,d,e,f,g,h,i,j}这些字母。如果再规定位数为5，那么，紧接在Jam数字“bdfij”之后的数字应该是“bdghi”。（如果我们用U、V依次表示Jam数字“bdfij”与“bdghi”，则U<V，且不存在Jam数字P，使U<P<V）。你的任务是：对于从文件读入的一个Jam数字，按顺序输出紧接在后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。

输入
输入文件count.in 有2行：
第1行为3个正整数，用一个空格隔开：s t w（其中s为所使用的最小的字母的序号，t为所使用的最大的字母的序号。w为数字的位数，这3个数满足：1≤s≤26, 2≤w≤t-s ）
第2行为具有w个小写字母的字符串，为一个符合要求的Jam数字。 所给的数据都是正确的，不必验证。

输出
输出文件count.out 最多为5行，为紧接在输入的Jam数字后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。每行只输出一个Jam数字，是由w个小写字母组成的字符串，不要有多余的空格。

样例输入
2 10 5
bdfij

样例输出
bdghi
bdghj
bdgij
bdhij
befgh
 

数据范围限制

解题方法

这道题我们直接模拟，注意：这个序列是严格递增的。
每一次我们按照高精度加法在这个位置上加一，然后进位就行了。

第四题：传纸条

题目

题目描述
小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。

输入
输入文件message.in的第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1<=m,n<=50）。

接下来的是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。

输出
输出文件message.out共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

样例输入
3 3
0 3 9
2 8 5
5 7 0

样例输出
34

数据范围限制
30%的数据满足：1<=m,n<=10
100%的数据满足：1<=m,n<=50

解题方法

方法$1$1

用$4$4维$dp$dp来做。
我们可以把两个人到达的位置一起考虑。
设$f_{i,j,k,l}$fi,j,k,l​表示第一个人走到了$(i,j)$(i,j)，第二个人走到了$(k,l)$(k,l)的答案。
我们知道$(i,j)$(i,j)从$(i-1,j)$(i−1,j)或$(i,j-1)$(i,j−1)转移过来。
我们又知道$(k,l)$(k,l)从$(k-1,l)$(k−1,l)或$(k,l-1)$(k,l−1)转移过来。
所以
$f_{i,j,k,l}=\max(f_{i-1,j,k-1,l},f_{i-1,j,k,l-1},f_{i,j-1,k-1,l},f_{i,j-1,k,l-1})+a_{i,j}+a_{k,l}$fi,j,k,l​=max(fi−1,j,k−1,l​,fi−1,j,k,l−1​,fi,j−1,k−1,l​,fi,j−1,k,l−1​)+ai,j​+ak,l​
注意：因为路径不能相同，所以$j<l$j<l。
答案是$f_{n,m-1,n-1,m}$fn,m−1,n−1,m​。
因为终点前一步就只有这两个点。
时间复杂度为$O(n^4)$O(n4)。
可以过。

方法$2$2

把上面的方法简化。
可以转化成$3$3维$dp$dp，因为步数都是一样的，没必要再枚举。
设$f_{p,i,j}$fp,i,j​表示走了$p$p步，一个人走到了$i$i行，另一个人走到了$j$j行的答案。
设$k$k表示第一个人的列坐标，$l$l表示第二个人的列坐标。
则可以发现$k-1+i-1=p$k−1+i−1=p，$l-1+j-1=p$l−1+j−1=p。
也就是$k=p-i+2$k=p−i+2，$l=p-j+2$l=p−j+2。
因为只有四个位置可以转移，$(i-1,k)$(i−1,k)，$(i,k-1)$(i,k−1)，$(j-1,l)$(j−1,l)，$(j,l-1)$(j,l−1)。
所以我们得到了状态转移方程。
$f_{p,i,j}=\max(f_{p-1,i,j},f_{p-1,i-1,j},f_{p-1,i,j-1},f_{p-1,i-1,j-1})+a_{i,k}+a_{l,j}$fp,i,j​=max(fp−1,i,j​,fp−1,i−1,j​,fp−1,i,j−1​,fp−1,i−1,j−1​)+ai,k​+al,j​
注意：位置不能相等。
时间复杂度为$O(n^3)$O(n3)

方法$3$3

把上面的状态转移方程用滚动数组。
时间复杂度不变。
空间复杂度为$O(n^2)$O(n2)。