A.约数个数(签到题)

1200000 有多少个约数（只计算正约数）。

分析: 我们可以优化一下求因子的过程, 让i只循环到sqrt(num), 为了防止重复计数放入 set 即可:

时间复杂度: O(n ^ 1/2):

B: 门牌制作(模拟)

【问题描述】

小蓝要为一条街的住户制作门牌号。

这条街一共有 2020 位住户，门牌号从 1 到 2020 编号。

小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，最后根据需要将字

符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、 0、 1、 7，即需要 1 个

字符 0， 2 个字符 1， 1 个字符 7。

请问要制作所有的 1 到 2020 号门牌，总共需要多少个字符 2？

分析: 模拟即可，时间复杂度为 O(nlgn):

C: 跑步锻炼(模拟)

【问题描述】

小蓝每天都锻炼身体。

正常情况下，小蓝每天跑 1 千米。如果某天是周一或者月初（1 日），为了

激励自己，小蓝要跑 2 千米。如果同时是周一或月初，小蓝也是跑 2 千米。

小蓝跑步已经坚持了很长时间，从 2000 年 1 月 1 日周六（含）到 2020 年

10 月 1 日周四（含）。请问这段时间小蓝总共跑步多少千米？

分析: 从2000年开始一天一天算即可, 要依次更新天数，星期数，年数 (还要判断日期是否合法(闰年)):

D: 平面分割(几何 + 递推)

【问题描述】
20条直线和20个圆最多能把一个平面分割成多少部分？

分析: 这种题一般都是规律题，要用数学推出关系式

设 a[i][j] 为 i 条直线, j 个圆时的分割平面的数量

假设只有直线: 要使得平面尽可能被分割, 我们要让第 i 条直线与之前的直线相交, 通过作图可以发现每次会新增 i 个平面.

当我们添加圆时, 如果要使平面尽可能被分割, 我们要使第 i 个圆尽可能与之前的直线和园相交， 通过作图发现会增加  2 * i + 2 * (j - 1) 个平面.

E: 蛇形填数(模拟)

如下图所示，小明用从 1 开始的正整数“蛇形”填充无限大的矩阵。

1 2 6 7 15 :::

3 5 8 14 :::

4 9 13 :::

10 12 :::

11 :::

:::

容易看出矩阵第二行第二列中的数是 5。请你计算矩阵中第 20 行第 20 列

的数是多少 ?

分析: 通过观察可以发现每次填数 row, col 都会加一，起点或终点是 a[row][1] (第奇数次) 或 a[1][col] (第偶数次),于是开始模拟"对角循环":

F: 成绩统计(模拟)

时间限制: 1.0s 内存限制: 512.0MB

本题总分：15 分

【问题描述】

小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。

如果得分至少是 60 分，则称为及格。如果得分至少为 85 分，则称为优秀。

请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整数。

分析: c++中可以用 %.0f 四舍五入保留整数

G: 单词分析(模拟 || 优先队列)

时间限制: 1.0s 内存限制: 512.0MB

本题总分：20 分

【问题描述】

小蓝正在学习一门神奇的语言，这门语言中的单词都是由小写英文字母组成，有些单词很长，远远超过正常英文单词的长度。小蓝学了很长时间也记不住一些单词，他准备不再完全记忆这些单词，而是根据单词中哪个字母出现得最多来分辨单词。

现在，请你帮助小蓝，给了一个单词后，帮助他找到出现最多的字母和这个字母出现的次数。

当然，求优先级问题也可以用优先队列，效率会更高:

 I: 作物杂交(dp超时，寄)

时间限制: 1.0s 内存限制: 512.0MB

本题总分：25 分

作物杂交是作物栽培中重要的一步。已知有 N 种作物 (编号 1 至 N )，第i 种作物从播种到成熟的时间为 Ti。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天，作物 B 种植时间为 7 天，则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物，新产生的作物仍然属于 N 种作物中的一种。

初始时，拥有其中 M 种作物的种子 (数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。

如存在 4 种作物 ABCD，各自的成熟时间为 5 天、7 天、3 天、8 天。初始拥有 AB 两种作物的种子，目标种子为 D，已知杂交情况为 A × B → C，

A × C → D。则最短的杂交过程为：

第 1 天到第 7 天 (作物 B 的时间)，A × B → C。

第 8 天到第 12 天 (作物 A 的时间)，A × C → D。

花费 12 天得到作物 D 的种子。

有大佬看一下这里 dp 有什么问题吗，这里调试了很久题目的测试过了但结果还是 WA 。。。

H: 数字三角形(dfs || 动态规划)

时间限制: 1.0s 内存限制: 512.0MB

本题总分：20 分

【问题描述】

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。

对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

分析: 挺经典的 dp, 注意相差不能超过 1，所以最大一定落再最后一行的中位数:

写了个暴力写法，顺便练一下dfs骗分技巧(比赛并不容易想出 dp...):

J: 字串分值和(数学 || 暴力)

暴力写法(能拿一半分):

时间复杂度: O(n ^ 2):

那么拿满分的方法是什么呢? 首先我们计算出如果所有字符都不相同的答案, 那么此时问题就转化为求一个字符串的所有子串, 对于一个字符串，我们截取出长度为 i 的字符串, 此时的子串数量与长度 i - 1的关系为:

dp[i] = dp[i - 1] + i;

那么我们对 dp[i] 求和就可以得到最大的答案(就是字符串中全部字符都不同)

接下来我们要看有相同字符对我们答案的影响:

a b a b c

^    ^

通过枚举我们发现a对答案的贡献为 -3, 也就是有 3 个字串会受到影响, 所以要减去 3

再来看看 b

a b a b c

   ^     ^

通过枚举我们会发现b对答案的贡献为 -4, 也就是有 4 个字串会受到影响, 所以要减去 4

我们再继续深入地想一想， 实际上受到影响的字串的个数与与两边字符串的个数有关:

我们记第一次出现的下标为 last[i]: 那么所有受到影响的个数为:

last[i] * (n - i)

于是我们将最理想的情况减去受到影响的个数就是答案了: