1. 好数
题目描述
如果一个正整数 x在十进制下的各位数字是严格单调递增的，则称 x为“好数”。给出 k，请回答第 k个“好数”是多少。注意，一位数都是“好数”。
输入格式
一个整数 k。
输出格式
输出一个整数表示第 k个好数。
数据范围
1≤k≤10^9，且保证好数至少有 k个。
样例输入1
10样例输出1
12样例输入2
100样例输出2
356解题思路
好数的各位数字严格递增，因此好数等价于从数字1~9中选择若干个数字（至少一个）按升序排列组成的数。好数总数是 29−1=511个（非空子集）。生成所有好数后排序，输出第 k个数。
2. 数字游戏
题目描述
对于所有 1≤i≤n的 i，每一轮操作可以选择将 ai变为 2×ai或 ai/3，但每次操作后必须保证 ai仍然是正整数。对于每一轮操作，至少有一个 i的选择是将 ai变成 ai/3。问最多可以进行几轮操作？
输入格式
第一行一个整数 n。
第二行 n个整数 a1,a2,…,an。
输出格式
输出一个非负整数，表示最多可以进行几轮操作。
数据范围
1≤n≤10^5
样例输入1
2 6 3 2样例输出1
2样例输入2
10 181008513 139202550 701506895 200648502 630613512 301523877 332060958 209571615 387697401 539492967样例输出2
52解题思路
每轮操作至少有一个数除以3，因此总操作轮数不超过所有数的3的因子个数之和。而通过乘以2可以调整顺序使得每轮都能找到一个数除以3，因此最大操作轮数就是所有数的3的因子个数之和。
3. 排列
题目描述
小A在玩一个游戏，有 n个数 1,2,3,…,n和一个正整数 k。
小A可以进行任意次以下操作：选择一个 i(1≤i≤n−k)，交换序列中的第 i个数和第 i+k个数。
小A吃完饭以后回来，怀疑有人打乱了他的顺序，他只记得游戏开始时的 n和 k，想知道对于目前的数列有可能是通过上述若干次操作（包括0次操作）得到的。
输入格式
第一行两个整数 n,k。
第二行 n个整数 a1,a2,…,an，表示小A吃完饭后看到的数列。
输出格式
输出 "Yes" 或 "No"。
数据范围
1≤n≤10^5，1≤k<n
样例输入1
4 2 2 3 1 4样例输出1
No样例输入2
4 2 3 4 1 2样例输出2
Yes样例输入3
10 7 6 4 10 5 3 7 1 9 2 8样例输出3
No样例输入4
10 8 6 3 10 7 8 5 4 2 9 1样例输出4
Yes解题思路
操作相当于可以交换距离为 k的两个位置，因此位置模 k同余的数之间可以任意交换。将数组按位置模 k分成 k组，每组内部元素可以任意排列。因此，只需检查每组中的元素是否与目标集合（即 1∼n中该组位置上的数）相同。具体来说，对于每组，将当前位置上的数和应该出现在这些位置上的数分别排序，比较是否相同。
4. 序列
题目描述
现有若干个 1∼n中的整数：a1个 1，a2个 2，a3个 3，…，an个 n。从这些数里取若干个，形成一个非空序列 b1,b2,…,bk(k≥1)，问有几种取法使得这个序列先单调不降再单调不升。
输入格式
第一行一个整数 n。
第二行 n个整数 a1,a2,…,an。
输出格式
一个正整数，表示有几种取法符合条件，结果对 109+7取模。
数据范围
1≤n≤104，1≤ai≤104
样例输入1
2 1 2样例输出1
7解题思路
序列先单调不降再单调不升，即存在一个峰值，使得左边不降、右边不升。枚举峰值 v，则序列中所有数不超过 v，且至少包含一个 v。对于每个小于 v的数 i，可以选择不取，或取若干个放在左边，或取若干个放在右边。设从 ai个 i中取 t个放左边，s个放右边，需满足 t,s≥0且 t+s≤ai，方案数为 C(ai+2,2)。因此，以 v为峰值的方案数为 av×i<vC(ai+2,2)。对所有 v求和即可。
5. 礼物
题目描述
小A偶然发现一个旧的生日礼物。礼物是一个含有 n个元素的数组，每个元素都介于 1和 m之间。但是现在数组已经很旧了，有的数难以看清。他记得一个由 0,1构成的序列 b1,b2,…,bn，对于第 i个元素，如果 bi=0表示它的相邻元素中至少有一个不小于它，如果 bi=1表示它的相邻元素中至少有一个不大于它。小A想知道有几种方案能够还原数组。当然，还原后的数组要保证每个元素仍介于 1到 m之间。
输入格式
第一行两个整数 n,m。
第二行 n个整数 a1,a2,…,an，若 ai=−1表示这个数已经看不清了，否则表示这个数。
第三行 n个整数 b1,b2,…,bn。
输出格式
一个正整数，表示方案数，结果对 998244353取模。
数据范围
2≤n≤105，2≤m≤200
样例输入1
3 10 1 -1 2 0 0 0样例输出1
1样例输入2
2 200 -1 -1 0 0样例输出2
200解题思路
动态规划。设 dp[i][v]表示考虑前 i个元素，且第 i个元素为 v的方案数。转移时，根据 bi的约束，从 dp[i−1]中符合条件的值转移过来。由于 m较小，可以用前缀和优化。注意第一个和最后一个元素只有一侧相邻，需要特殊处理。
此文章同步发送于语雀，网址
四川省第四届青少年c++算法设计大赛小低组题目
