update log:
- 2020-08-30 练习1题解
- 2020-09-14 练习2题解
- 2020-09-15 练习3题解
- 2020-09-28 练习4题解
练习1
本练习题目以枚举、执行为主，属于考试中容易类型的题目。
| 题号 | 题目 | 类型 |
|---|---|---|
| 1127 | 数列 | 枚举 |
| 1251 | Colombian Number | 枚举 |
| 1252 | Matrix Word | 枚举 |
| 1253 | Robot | 执行 |
| 1263 | 矩形面积的并 | 执行 |
| 1272 | Robot | 执行、找规律 |
| 1280 | String Hash | 进制转换 |
| 1281 | Cute String | 查找 |
| 1292 | Co-string | 枚举 |
| 1294 | Enquiry | 前缀和 |
1127 数列
先枚举所有a和b的组合（一共100种），找数列的循环节。
所有的数列都是 $s_0,s_1,\cdots,s_i,s_{i+1}\cdots,s_j,s_{j+1},\cdots$ 的形式，其中$s_i = s_j , s_{i+1} = s{j+1}$。
所以，得到每种情况下的$i$和循环节长度$k = j-i$，将其存入数组。
对于每次的查询$a,b,n$，根据上面得到结果，直接计算即可。
1251 Colombian Number
因为$n$最大为$10^9$,如果从小到大枚举的话，肯定会超时。
可以看到数码和最大也就$9$个$9$，所以从$n-1$开始向小的枚举，最多只要枚举$81$次，如果没找发现其不为哥伦比亚数，那么则一定为哥伦比亚数。
1252 Matrix Word
- 使用
row[n][26]和col[m][26]两个数组记录对应行和列字符出现的次数； - 按行列枚举所有字符，统计其在行和列的出现次数。
- 再按行列枚举所有字符，如果其对应行列对应字符只出现1次，那么输出该字符即可。
1253 Robot
可以用链表(list)或者两个数组（一个记录任务$i$的可做条件$a_i$，一个记录任务$i$是否已经被完成了）。
模拟整个过程，从左到右，再从右到左，每次转向时计数器加一，直到所有任务已经被完成。
1263 矩形面积的并
这题如果想把所有情况列举出来的话，比较容易漏掉情况，最容易出错的一种是，两个矩阵呈一个十字。
首先对于两个矩形而言，面积并 = 面积和 - 面积交， 所以我们只要求其面积交即可。
对此，我们可以将矩形分别投影到$X$和$Y$轴，这样矩形就变成两个一维的区间，分别两个矩形在$X$和$Y$轴投影的区间交，然后相乘即为面积交
1272 Robot
第一种做法是枚举，模拟：
- 对于某一个指令序列，机器人初始位置为(0,0),我们通过枚举指令，UD分别对应x的自减一和自加一;LR对应y的自减一和自加一。如果枚举完后，机器人的位置依然是(0,0)，那么其回到原点。
- 对于任意一种替换组合(一共$4\times 3 = 12$ 种)，对应替换掉原来指令序列，得到一个新的指令序列，使用第一步的方式验证即可。
第二种做法是找规律：
我们分别用UDLR表示四种指令的数量，由第一种的第一步可知，要回到原点必然U=D且L=R。由于题目要求必须换掉一种，所以无论怎么换，必然有一种没有对应的抵消指令，所以要回到原点的话，必然有一种指令的数量为0，否则必不能回到原点。对于存在某种指令数为0的情况下，则抵消指令的差值必须相等，才能回到原点。
1280 String Hash
进制转换的裸题。注意：
1. 使用64位整数来防止溢出；
2. 每计算一位都需要取模，否则会溢出。
1281 Cute String
根据题目输入，直接统计空格数，单词数为空格数+1；
再用一个int c[26]的字符计数器数组来统计对应的字母是否出现，遍历字符计数器数组计算一共出现了多少个字母。
1292 Co-string
字符串长度为len,从大到小枚举子串长度n(从len/2 到 1), 枚举子串起始位置i，枚举判断其是否为Co-String。
1294 Enquiry
- 从字符串数组下标1开始枚举所有字符，判断其是否与之前的字符不同，不同为1，否则为0，记录到前缀和数组中。
- 递推计算前缀和S
- 对于每次查询[a,b]，计算 s[b-1] - s[a-1] 即可。
练习2
本练习题目以数学和思维题为主，属于考试中中等类型的题目。
| 题号 | 题目 | 类型 |
|---|---|---|
| 1241 | Permutation | 枚举，GCD |
| 1266 | RGB | 思维 |
| 1271 | Color | 统计，容斥 |
| 1273 | Set | 思维 |
| 1295 | Flawless Prime | 枚举，素数判定 |
| 1123 | duoxida的数字游戏 | 思维 |
| 1172 | 因子和 | 数学，因式分解 |
| 1279 | Dual Prime | 素数筛 |
| 1348 | 数字 | 思维 |
1241 Permutation
很多同学好像看不懂数学语言，建议去复习（预习）一下离散数学的相关内容。
比如$P=\Big( \begin{array}\, 1&2&3&4&5&6\\2&1&4&5&6&3 \end{array} \Big)$，其由两个子置换组成
$P=\Big( \begin{array}\, 1&2\\2&1 \end{array} \Big)\Big( \begin{array}\, 3&4&5&6\\4&5&6&3 \end{array} \Big)$，
所以置换$P$的周期是子置换周期的乘积, $2\times 4 = 8$。
类似于dfs（不过这个直接写循环就可以了），枚举置换的每个位置，如果这个位置不在已经查找过的子置换中，就不停寻找子置换的下一个位置，直到回到这个位置，这样求得这个子置换的周期，然后将这个子周期乘进去即可。
1266 RGB
- 先统计RGB各有多少个，来确定R,G,B三个区域的大小
- 再统计R区有多少个G和B球，G区有多少个R和B，B区有多少个R和G
- 显然RG和GR，RB和BR，GB和BG 先进行交换，每种都取小的，记入结果。
- 剩下的必然只能进行轮换，对结果的贡献为剩余的某一种球的数量*2。
1271 Color
- 枚举黑色的格子，统计行和列，找出有多少行c和列r不存在黑色格子
- 利用容斥可得，$ ans = c \cdot n + r \cdot m - c \cdot r $
1273 Set
- 显然，如果不超过4种数，必然有解。
- 对于一个数$n$来说， 通过两步操作，可以得到 $n,n+x,n-y,n+x-y$ ,最多四种不同的情况。所以如果超过5种数，那么必然无解。
- 不妨设四种数依次为$a<b<c<d$, 显然我们只能变成中间的数，所以不妨设都变成b化简可得$b+c = a + d$。所以如果满足这个条件，则有解，否则无解。
1295 Flawless Prime
依次枚举判断素数即可。对于每次移除最高位，只要先求一个$m=10^k，且m>n$即可很容易每次去掉n的最高位了。
也可以按位枚举出所有的无瑕素数，然后打表进行二分查找。
1123 duoxida的数字游戏
- 从k到n的球必须同色，否则无解。因为如果存在不同色的球，那么这个球必然在移动的过程中无法被去除。
- 从k往前，如果连续同色的球的不需要被去除，所以步数就是比k小的连续与k同色的球的位置-1。
1172 因子和
根据唯一因式分解定理 $n = p_1 ^{k_1} \times p_2^{k_2} \times \ldots \times p_m^{k_m}$。
根据生成函数可知
$\prod_{i=1}^m{\sum_{j=0}^{k_i}{p_i^j}}$ 可以生成所有的因子的和，所以
因子和
1279 Dual Prime
- 暴力枚举会TLE
- 考虑朴素埃筛中，所有的双素数都会被标记2次，但是被标记两次的数中，还有一部分是素因子平方倍数的数，所以，把这些数再标记出来就可以筛出所有的双素数。
- 剩下的和素数个数的做法相同了。
1348 数字
- 枚举所有数码的倍数的个位集合$S_i$。
- 如果对于n的个位和k的个位$k_0$, $n_0 \notin S_{k_0}）$，那么必然不可能出现尾部为0的情况，此时的步数为 $\lfloor n / k \rfloor$ ， 结果为 $n\mod k $。
- 否则，则取对应的倍数t， t+1为步数， $n - kt$ ，再去掉尾部的0 ，为新的 n 继续迭代。
练习3
本练习题目为模拟题，题目难度为中等,个别属于容易类型
| 题号 | 题目 | 类型 |
|---|---|---|
| 1163 | ASCII | 模拟 |
| 1170 | ICPC | 模拟 |
| 1248 | Alice and Bob | 模拟 |
| 1239 | 2048 | 模拟 |
| 1243 | Bob’s Password | 模拟 |
| 1267 | Matrix | 模拟 |
| 1275 | Exam Schedule | 模拟 |
| 1287 | 银行 | 模拟 |
| 1297 | Homework | 模拟 |
| 1326 | Diagram | 模拟 |
1163 ASCII
一个字符一个字符读入，输出%02X
1170 ICPC
- 按位统计最高级别，得到答案的第一行
- 对第一行的字符串进行统计，得到第二行
1248 Alice and Bob
将骰子的影射成整数进行比较即可。比如下面的一种影射方案：
将骰子影射成一个三位数，百位为类型，后两位为优先级。
- 点数优先级1,6,5,4,3,2 ，影射为7,6,5,4,3,2
- 豹子百位为3，个位为点数优先级
- 对子百位为2，十位为对子的点数优先级，个位为剩余骰子的点数优先级
- 点子直接把三个骰子的点数加起来
1239 2048
- 先考虑向左这个操作
- 先考虑一行的情况，可以发现一次移动包含3步操作：
a. 从左到右压缩，去掉左边的0;
b. 将相邻相等的格子，把左边的翻倍，右边的清零；
c. 再从左到右压缩，将左边的0去掉。 - 那么所有的四行都按操作进行即可。
- 对于向右，向上，向下，只要按方向先拷贝到一个数组进行向左的移动，然后再按对应顺序拷回去就可以了。比如向上：，则按从上到下的顺序拷贝到数组执行第2步的操作，然后再将结果按从上到下的顺序拷贝回来即可。
1243 Bob’s Password
构造一个$9\times 9$的矩阵,其元素$a_{ij} = -1$ 表示从$i+1$到$j+1$ 可以直达; $a_{ij} = k$，表示 从$i+1$到$j+1$ ，之前必须已经经过$k+1$。
对于某一个密码字符串，按位进行判断，记录所有经过的点，即可。
1267 Matrix
每个操作写个对应函数就好了，需要注意的是，转置的时候，最后需要将行列的值进行互换；镜像函数可以利用之前的交换行、列的函数来进行。
1275 Exam Schedule
用一个bool[5][7]来存储时间的占用情况，对于2,3,4这三种不同的时长，枚举每天对应的可能区间，看是否是空的，空的就记下来，最后输出即可。
1287 银行
分两个队列分别存储普通用户和VIP用户，然后按时间进行处理，每次都优先处理VIP用户，除非当前时刻没有VIP客户，就处理普通客户，
直到处理完所有顾客。然后把普通用户和VIP用户的队列按取号时间进行归并，输出即可。
1297 Homework
- 根据输入的题目和排名，统计每个人的积分
- 求最高积分，枚举所有人，根据成绩公式，计算每个人的成绩
- 最后按成绩逆序，学号排名，输出即可。
1326 Diagram
- 统计每个字符的出现频度，并求频度的最大公约数，频度除最大公约数，得到字符的柱状图高度。
- 求得最大高度和出现的字符种类数，用二维数组做画布（画布初始为全空格），按列从左到右，从下到上画柱状图。
- 然后按行，把尾部的空格改成串结束符，最后按行输出即可。
练习4
本练习主要是递推，属于中档，偏难的类型。
| 题号 | 题目 | 类型 |
|---|---|---|
| 1249 | Alice’s Prime | 递推 |
| 1274 | Matrix | 找规律 |
| 1274 | Good Number | 推公式 |
| 1283 | Beautiful Number | 递推 |
| 1307 | 填颜色 | 推公式 |
| 1168 | Coins | 推公式 |
| 1171 | LOVE | 递推 |
| 1224 | Unique Digit Number | 递推 |
| 1270 | 比赛 | 推公式 |
| 1286 | Wave | 推公式 |
1249 Alice’s Prime
首先，${2,3,5,7}$是属于解集$S$的，从小到大枚举$S$, 对于$x \in S$, 那么枚举${10x+1,10x+3,10x+7,10x+9}$是否是素数，是的话，加入$S$，直到枚举完$S$。
1274 Matrix
观察可知，偶数行为$4,16,36$，是$2^2,4^2,6^2$，而奇数行为$0^2+1,2^2+1,4^2+1$。
所以当$n=2m$时，和$S_{2m} = \sum_{i=1}^m{(2i)^2} + \sum_{i=0}^{m-1}{((2i)^2 + 1)} = 8\sum_{i=1}^{m-1}{i^2} + m + 4m^2 = 4 \frac{(m-1)m(2m-1)}{3} + m + 4m^2$;
当$n=2m+1$时，$S_{2m+1} = S_{2m} + 4m^2 + 1 $。
由于有除$3$，这个时候可以讨论$m/mod 3$的值，先除掉$3$再进行取余计算；当然也可以乘$3$对于$10^9+7$的逆元$333333336$，这样会更方便些。
1283 Good Number
由于无前导$0$，所以第一位肯定为$1$,后面的$n-1$位中，至少需要$\lfloor\frac{n}{2}\rfloor$位$1$。
所以$n$位好数的数量为
考虑$2$次项系数的对称性
1307 Beautiful Number
先枚举出所有美丽数，对于查询，二分查找（暴力找也可以）就可以了。
枚举美丽数，可以从$3$到$63$位$1$中，去枚举中间那个$0$得到所有的美丽数。
1168 填颜色
先考虑一些特殊的情况，$m=1$时,$f(1) = 1$ 其他 $f(n) = 0$。 $m=2$时,$f(1) = 2$ , $n$是偶数时，$f(n) = 2$，其他$f(n) = 0 $。
当$m>2$时， $f(1) = m , f(2) = m(m-1)，f(3) = m(m-1)(m-2) $ 。 当$n>3$时，我们考虑第$n$格子，假设它的颜色是$1$，那么第$1$个和第$n-1$格与其不同色，而这两个格子有两种情况:
- 相等，此时 前$n-2$格必然是原问题，所以此时的前$n-2$格的方案数为$f(n-2)$,第$n-1$格与第$1$格相同，方案数为$1$，第$n$格的方案数为$m-1$，所以方案数为$(m-1)f(n-2)$。
- 不相等，那么此时前$n-1$格必然是原问题，所以此时的方案数为$(m-2)f(n-1)$。
所以，方案数$f(n)=(m-2)f(n-1)+(m-1)f(n-2)$。
1171 Coins
等价于斐波那契数列
1224 LOVE
dp[n][4] 表示前n个字符中，“L”,”LO”,”LOV”,”LOVE”子序列的个数。
当第i个字符是‘L’时，dp[i][0] = dp[i-1][0] + 1;
当第i个字符是‘O’时，dp[i][1] = dp[i-1][1] + dp[i-1][0];
当第i个字符是‘V’时，dp[i][2] = dp[i-1][2] + dp[i-1][1];
当第i个字符是‘E’时，dp[i][3] = dp[i-1][3] + dp[i-1][2];
由于递推时，只和之前的一行有关，可以用一维数组来减少内存使用。
当第i个字符是‘L’时，dp[0]++;
当第i个字符是‘O’时，dp[1]+= dp[0];
当第i个字符是‘V’时，dp[2]+= dp[1];
当第i个字符是‘E’时，dp[3]+= dp[2];
dp[3]为所求。
1270 Unique Digit Number
如果$x$是UDN，并记录下它使用了哪些数码（二进制状态表示），枚举数码$d$，如果$d$没有被使用，那么$10x+d$也是UDN。
这样，我们可以用一个队列来产生所有的UDN，最开始队列中有$0到9$,然后从$1$开始枚举，直到枚举完整个队列。
题目已经告诉你，这样的数一共有$8877691$个。
1286 比赛
我们将比赛可以描述成一棵二叉树，其叶子节点为选手的数量。根据题目要求，这颗树必然是AVL平衡树。题目相当于说，$n$个叶子节点AVL树最高是多少？
我们不妨设对于每个根节点，其左子树高度都不小于右子树高度。
最少叶子节点的AVL树假设高度是$h$，那么最少节点数$f(h) = f(h-1) + f(h-2) + 1$。
由于不存在度为1的点，叶子节点即参赛队员数$n$，所以$f(h) = 2n - 1$。
我们假设$g(h) = n$,那么$f(h) = 2g(h)-1$，所以$g(h) = g(h-1) + g(h-2)$。
显然$g(1) = 1, g(2) = 2$。
1340 Wave
假设不考虑平波，那么$n$为奇数时无解，$n$为偶数时相当于$2k$位有$k$位为$1$的二进制数有多少个？ $\binom{2k}{k}$
考虑平波，那么枚举平波的个数$i$，
To be continue …
