试题 A: 美丽的 2
本题总分：5 分
我的答案：563，水题暴力循环即可
【问题描述】
小蓝特别喜欢 2，今年是公元 2020 年，他特别高兴。
他很好奇，在公元 1 年到公元 2020 年（包含）中，有多少个年份的数位中 包含数字 2？
1. int fx(int x) { 2. int num = 0; 3. while (x > 0) { 4. if (x % 10 == 2) { 5. num++; 6. } 7. x /= 10; 8. } 9. return num; 10. } 11. int main() { 12. int ans = 0; 13. for (int i = 1; i <= 2020; i++) { 14. if (fx(i) > 0) ans++; 15. } 16. cout << ans << endl; 17. return 0; 18. }
试题 B: 扩散
本题总分：5 分
等待大神认领
【问题描述】
小蓝在一张无限大的特殊画布上作画。 这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。 小蓝在画布上首先点了一下几个点：(0, 0), (2020, 11), (11, 14), (2000, 2000)。 只有这几个格子上有黑色，其它位置都是白色的。
每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色 （如果原来就是黑色，则还是黑色）。
请问，经过 2020 分钟后，画布上有多少个格子是黑色的。
试题 C: 阶乘约数
我的答案：883423532389192164791648750371459257913741948437809479060803100646309888
我的思路是先求出1到100所有数的质因子，共239个，然后C(0,239)+C(1,239)+C(2,239)+...+C(238,239)+C(239,239) 就等于2的239次
本题总分：10 分
【问题描述】
定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100! （100 的阶乘）有多少个约数。
1. bool ssbiao[102]; 2. int num[102]; 3. bool ss(int x) { 4. if (x < 2) return false; 5. for (int i = 2; i < x; i++) { 6. if (x % i == 0) return false; 7. } 8. return true; 9. } 10. void init() { 11. int ansSum = 0; 12. for (int i = 2; i < 100; i++) { 13. if (ss(i)) ssbiao[i] = true; 14. } 15. for (int i = 2; i <= 100; i++) { 16. int j = i; 17. while (j > 1) { 18. for (int k = 2; k < 100; k++) { 19. if (ssbiao[k] && (j % k == 0)) { 20. j /= k; 21. num[k] ++; 22. ansSum++; 23. } 24. } 25. } 26. } 27. for (int i = 2; i <= 100; i++) { 28. cout << i << " : " << num[i] << endl; 29. } 30. cout << ansSum << endl; 31. } 32. int main() { 33. // init(); 34. double s = pow(2.0, 239.0); 35. printf("%lf\n", s); 36. cout << s << endl; 37. //883423532389192164791648750371459257913741948437809479060803100646309888 38. return 0; 39. }
试题 D: 本质上升序列
本题总分：10 分
等待大神认领
【问题描述】
小蓝特别喜欢单调递增的事物。在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺 序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。
例如，在字符串 lanqiao 中，如果取出字符 n 和 q，则 nq 组成一个单 调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。 小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第 二个字符和最后一个字符可以取到 ao，取最后两个字符也可以取到 ao。小蓝 认为他们并没有本质不同。
对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？
例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别 是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、 anq、lno、ano、aio。
请问对于以下字符串（共 200 个小写英文字母，分四行显示）
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
本质不同的递增子序列有多少个？
试题 E: 玩具蛇
我的答案：604，从每一个点开始深搜，搜到给标记，退回还原标记，16个点结果相加就是604
本题总分：15 分
【问题描述】
小蓝有一条玩具蛇，一共有 16 节，上面标着数字 1 至 16。每一节都是一 个正方形的形状。相邻的两节可以成直线或者成 90 度角。 小蓝还有一个 4 × 4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着 字母 A 到 P 共 16 个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将 玩具蛇放进去。
下图给出了两种方案：
请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩
具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。
1. int a[5][5]; 2. bool b[5][5]; 3. int ans = 0; 4. void init() { 5. for (int i = 0; i < 5; i++) { 6. for (int j = 0; j < 5; j++) { 7. a[i][j] = 0; 8. b[i][j] = false; 9. } 10. } 11. } 12. void dfs(int x, int y, int num) { 13. if (x < 0 || x >3 || y < 0 || y > 3) return; 14. if (b[x][y]) return; 15. if (num == 16) { 16. ans++; 17. return; 18. } 19. b[x][y] = true; 20. dfs(x, y + 1, num + 1); 21. dfs(x, y - 1, num + 1); 22. dfs(x + 1, y, num + 1); 23. dfs(x - 1, y, num + 1); 24. b[x][y] = false; 25. } 26. int main() { 27. ans = 0; 28. dfs(0, 0, 1); 29. for (int i = 0; i < 4; i++) { 30. for (int j = 0; j < 4; j++) { 31. init(); 32. dfs(i, j, 1); 33. } 34. } 35. cout << ans << endl;// 604 36. }
试题 F: 皮亚诺曲线距离
我的思路：
首先对于这样的图形，只有两个图案，我们认定最左下角的那块坐标为（0,0）
那么当x坐标加y坐标为偶数时，是第一种图形
当x坐标加y坐标为奇数时，是第二种图形
不管是第一种图形还是第二种图形，都有入口和出口
并且每一个点到入口的路径是确定的
第一种图形到入口的路径由fx1()求，第二种由fx2()求
求任意两个点，首先要确定在哪两个大块
比如阶数为3的样例，可以看做9个9*9的二阶大块构成，求出相距几个大块
接下来把一个大块平移到另外一个大块，注意平移的是到入口的路径
接下来求二阶，看做9个3*3的样例构成，一直递归下去......
【问题描述】
皮亚诺曲线是一条平面内的曲线。 下图给出了皮亚诺曲线的 1 阶情形，它是从左下角出发，经过一个 3 × 3 的 方格中的每一个格子，最终到达右上角的一条曲线。
下图给出了皮亚诺曲线的 2 阶情形，它是经过一个 32 × 32 的方格中的每一 个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。
下图给出了皮亚诺曲线的 3 阶情形，它是经过一个 33 × 33 的方格中的每一 个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。
皮亚诺曲线总是从左下角开始出发，最终到达右上角。 我们将这些格子放到坐标系中，对于 k 阶皮亚诺曲线，左下角的坐标是 (0, 0)，右上角坐标是 (3k - 1, 3k - 1)，右下角坐标是 (3k - 1, 0)，左上角坐标是 (0, 3k - 1)。
给定 k 阶皮亚诺曲线上的两个点的坐标，请问这两个点之间，如果沿着皮亚诺曲线走，距离是到少？
【输入格式】
输入的第一行包含一个正整数 k，皮亚诺曲线的阶数。
第二行包含两个整数 x1, y1，表示第一个点的坐标。
第三行包含两个整数 x2, y2，表示第二个点的坐标。
【输出格式】
输出一个整数，表示给定的两个点之间的距离。
【样例输入】
1
0 0
2 2
【样例输出】
8
【样例输入】
2
0 2
0 3
【样例输出】
13
【评测用例规模与约定】
对于 30% 的评测用例，0 ≤ k ≤ 10。
对于 50% 的评测用例，0 ≤ k ≤ 20。
对于所有评测用例，0 ≤ k ≤ 100, 0 ≤ x1, y1, x2, y2 < 3k, x1, y1, x2, y2 ≤ 1018。
数据保证答案不超过 1018。
1. int fx1(int x,int y) { 2. if (x == 0 && y == 0) return 1; 3. if (x == 0 && y == 1) return 2; 4. if (x == 0 && y == 2) return 3; 5. if (x == 1 && y == 2) return 4; 6. if (x == 1 && y == 1) return 5; 7. if (x == 1 && y == 0) return 6; 8. if (x == 2 && y == 0) return 7; 9. if (x == 2 && y == 1) return 8; 10. if (x == 2 && y == 2) return 9; 11. return 0; 12. } 13. int fx2(int x, int y) { 14. if (x == 2 && y == 0) return 9; 15. if (x == 2 && y == 1) return 8; 16. if (x == 2 && y == 2) return 7; 17. if (x == 1 && y == 2) return 6; 18. if (x == 1 && y == 1) return 5; 19. if (x == 1 && y == 0) return 4; 20. if (x == 0 && y == 0) return 3; 21. if (x == 0 && y == 1) return 2; 22. if (x == 0 && y == 2) return 1; 23. return 0; 24. } 25. int jl(int x, int y,int x1,int y1) { 26. if (x < 3 && y < 3 && x1 < 3 && y1 < 3) 27. return fx1(x, y) - fx1(x1, y1); 28. return jl(x / 3, y / 3, x1 / 3, y1 / 3); 29. } 30. int main() { 31. 32. int jie; 33. while (cin >> jie) { 34. int scanfJie = jie; 35. int x1, y1, x2, y2; 36. int xx1, yy1, xx2, yy2; 37. cin >> x1 >> y1; 38. cin >> x2 >> y2; 39. int scanfX1 = x1; 40. int scanfX2 = x2; 41. int scanfY1 = y1; 42. int scanfY2 = y2; 43. int da1, da2; 44. int ans = 0; 45. 46. while (jie > 1) { 47. int tempJie = (int)pow(3, jie - 1); 48. xx1 = scanfX1 / tempJie; 49. yy1 = scanfY1 / tempJie; 50. xx2 = scanfX2 / tempJie; 51. yy2 = scanfY2 / tempJie; 52. da1 = fx1(xx1, yy1); 53. da2 = fx1(xx2, yy2); 54. ans *= 9; 55. ans += da2 - da1; 56. scanfX1 %= tempJie; 57. scanfX2 %= tempJie; 58. scanfY1 %= tempJie; 59. scanfY2 %= tempJie; 60. jie--; 61. } 62. ans *= 9; 63. int xx = x1 / 3; 64. int yy = y1 / 3; 65. int type1, type2; 66. int num1, num2; 67. if ((xx + yy) % 2 == 0) { 68. type1 = 1; 69. num1 = fx1(x1 % 3, y1 % 3); 70. } 71. else { 72. type1 = 2; 73. num1 = fx2(x1 % 3, y1 % 3); 74. } 75. 76. xx = x2 / 3; 77. yy = y2 / 3; 78. if ((xx + yy) % 2 == 0) { 79. type2 = 1; 80. num2 = fx1(x2 % 3, y2 % 3); 81. } 82. else { 83. type2 = 2; 84. num2 = fx2(x2 % 3, y2 % 3); 85. } 86. ans += num2 - num1; 87. // cout << num1 << " " << num2 << endl; 88. cout << ans << endl; 89. } 90. return 0; 91. }
