[关闭]
@Dmaxiya 2020-12-15T23:27:27.000000Z 字数 10126 阅读 958

2018 Multi-University Training Contest 4

暑期集训


链接:2018 Multi-University Training Contest 4
过题数:3
排名:333/802
成员:官展鹏,冯彦博,孙昊哲

B. Harvest of Apples

题意

总共有 个苹果,编号分别为 ,问最多能摘到 个苹果的总方案数。

输入

第一行包含一个整数 ,接下去有 组数据,每组数据包含两个整数

输出

对每组数据,输出答案对 取模的结果。

样例

输入
2
5 2
1000 500
输出
16
924129523

题解

个苹果最多能摘到 个的方案数为 ,由于这个公式的计算是 的,所以 组数据显然超时,考虑离线莫队。
我们定义 ,设 ,则有:

于是将上标 设为左区间 ,下标 设为右区间 ,有以下转移方程:
方程中的每一项都可以 求得,因此总的时间复杂度为

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <sstream>
  17. using namespace std;
  18. #define LL long long
  19. const int maxn = 100000 + 100;
  20. const int MOD = 1000000007;
  21. struct Node {
  22. int l, r;
  23. int Index;
  24. };
  25. int sq;
  26. bool operator<(const Node &a, const Node &b) {
  27. return a.r / sq == b.r / sq? a.l < b.l: a.r < b.r;
  28. }
  29. int T, n, m, l, r, Max;
  30. int ans[maxn];
  31. Node node[maxn];
  32. int inv[maxn], pro[maxn], invpro[maxn];
  33. void Init() {
  34. inv[1] = 1;
  35. for(int i = 2; i < maxn; ++i) {
  36. inv[i] = (LL)(MOD - MOD / i) * inv[MOD % i] % MOD;
  37. }
  38. pro[0] = invpro[0] = 1;
  39. for(int i = 1; i < maxn; ++i) {
  40. pro[i] = (LL)pro[i - 1] * i % MOD;
  41. invpro[i] = (LL)invpro[i - 1] * inv[i] % MOD;
  42. }
  43. }
  44. int get_C(int n, int m) {
  45. if(n < m) {
  46. return 0;
  47. }
  48. return (LL)pro[n] * invpro[m] % MOD * invpro[n - m] % MOD;
  49. }
  50. int main() {
  51. #ifdef Dmaxiya
  52. freopen("test.txt", "r", stdin);
  53. // freopen("out.txt", "w", stdout);
  54. #endif // Dmaxiya
  55. ios::sync_with_stdio(false);
  56. Max = 0;
  57. Init();
  58. scanf("%d", &T);
  59. for(int i = 0; i < T; ++i) {
  60. scanf("%d%d", &node[i].r, &node[i].l);
  61. node[i].Index = i;
  62. Max = max(Max, node[i].r);
  63. }
  64. sq = sqrt(Max);
  65. sort(node, node + T);
  66. l = 1;
  67. r = 0;
  68. LL tmp = 1;
  69. LL ttmp;
  70. for(int i = 0; i < T; ++i) {
  71. while(r < node[i].r) {
  72. ttmp = tmp + tmp;
  73. if(ttmp >= MOD) {
  74. ttmp -= MOD;
  75. }
  76. tmp = ttmp - get_C(r, l);
  77. if(tmp < 0) {
  78. tmp += MOD;
  79. }
  80. ++r;
  81. }
  82. while(l > node[i].l) {
  83. tmp = tmp - get_C(r, l);
  84. if(tmp < 0) {
  85. tmp += MOD;
  86. }
  87. --l;
  88. }
  89. while(r > node[i].r) {
  90. ttmp = tmp + get_C(r - 1, l);
  91. if(ttmp >= MOD) {
  92. ttmp -= MOD;
  93. }
  94. tmp = (ttmp * inv[2]) % MOD;
  95. --r;
  96. }
  97. while(l < node[i].l) {
  98. tmp = tmp + get_C(r, l + 1);
  99. if(tmp >= MOD) {
  100. tmp -= MOD;
  101. }
  102. ++l;
  103. }
  104. ans[node[i].Index] = tmp;
  105. }
  106. for(int i = 0; i < T; ++i) {
  107. printf("%d\n", ans[i]);
  108. }
  109. return 0;
  110. }

D. Nothing is Impossible

题意

一个班上有 个学生参加考试,试卷上总共有 道题,每道题有 个正确选项和 个错误选项,每个学生每道题只能从 个选项中选择一个选项作为答案,每个学生都不知道正确答案,但是这个教室内的学生在考试期间可以相互讨论,且他们十分团结,他们想让班上的最高分的做对的题数最多,问他们在采取最优策略下,能够做对的最多的题数。

输入

第一行为一个整数 ,接下去有 组数据,每组数据第一行为两个整数 ,接下去 行每行两个整数

输出

输出最高分能够做对的最多的题数。

样例

输入
2
3 5
1 3
1 3
1 3
5 50
1 1
1 3
1 2
1 3
1 5
输出
1
3

题解

个人认为这题应该加一个“最高分至少能够做对的题数”,即在他们所有人运气都最坏的情况下,能够做对的题数的最大值,最优策略就是让所有人的答案填法按照 进制一个一个地填上去,如果能够达到第 位,则说明第 位以下的所有情况都已经填上去,也就至少能够保证做对 道题,为了让位数增长最快,应该让 值小的作为低位。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <sstream>
  17. using namespace std;
  18. #define LL long long
  19. const int maxn = 100 + 100;
  20. struct Node {
  21. int a, b;
  22. };
  23. bool operator<(const Node &a, const Node &b) {
  24. return a.b < b.b;
  25. }
  26. int T, n, m, ans;
  27. Node node[maxn];
  28. int num[maxn];
  29. int main() {
  30. #ifdef Dmaxiya
  31. freopen("test.txt", "r", stdin);
  32. // freopen("out.txt", "w", stdout);
  33. #endif // Dmaxiya
  34. ios::sync_with_stdio(false);
  35. scanf("%d", &T);
  36. while(T--) {
  37. ans = 0;
  38. scanf("%d%d", &n, &m);
  39. for(int i = 0; i < n; ++i) {
  40. scanf("%d%d", &node[i].a, &node[i].b);
  41. }
  42. sort(node, node + n);
  43. for(int i = 0; i < n; ++i) {
  44. if(m > node[i].b) {
  45. ++ans;
  46. }
  47. m /= (node[i].b + 1);
  48. }
  49. printf("%d\n", ans);
  50. }
  51. return 0;
  52. }

E. Matrix from Arrays

题意

给定一个长度为 的数组 ,用以下代码生成一个无穷大矩阵:

  1. int cursor = 0;
  2. for (int i = 0; ; ++i) {
  3. for (int j = 0; j <= i; ++j) {
  4. M[j][i - j] = A[cursor];
  5. cursor = (cursor + 1) % L;
  6. }
  7. }

次询问,每次询问为从第 列到第 列的子矩阵中数字的和。

输入

第一行为一个整数 ,接下有 组数据,每组数据第一行为一个整数 ,第二行为 个整数 ,第三行为一个整数 ,接下去 行每行四个整数

输出

对于每次询问,输出结果。

样例

输入
1
3
1 10 100
5
3 3 3 3
2 3 3 3
2 3 5 8
5 1 10 10
9 99 999 1000
输出
1
101
1068
2238
33076541

题解

打表可以发现矩阵的循环节为 ,因此可以只打出 的矩阵,就可以通过循环节求出所有矩阵的值,设 为无穷大矩阵前 列的和,则所求子矩阵的和为

注意 取得 的情况。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <sstream>
  17. using namespace std;
  18. #define LL long long
  19. const int maxn = 100 + 100;
  20. int T, n, q;
  21. int a[maxn];
  22. LL num[maxn][maxn];
  23. LL Sum(int x, int y) {
  24. if(x < 0 || y < 0) {
  25. return 0;
  26. }
  27. int nn = n << 1;
  28. LL ret = num[nn - 1][nn - 1] * ((x + 1) / nn) * ((y + 1) / nn);
  29. int xx = x % nn;
  30. int yy = y % nn;
  31. if(xx != nn - 1) {
  32. ret += num[xx][nn - 1] * ((y + 1) / nn);
  33. }
  34. if(yy != nn - 1) {
  35. ret += num[nn - 1][yy] * ((x + 1) / nn);
  36. }
  37. if(xx != nn - 1 && yy != nn - 1) {
  38. ret += num[xx][yy];
  39. }
  40. return ret;
  41. }
  42. int main() {
  43. #ifdef Dmaxiya
  44. freopen("test.txt", "r", stdin);
  45. // freopen("out.txt", "w", stdout);
  46. #endif // Dmaxiya
  47. ios::sync_with_stdio(false);
  48. scanf("%d", &T);
  49. while(T--) {
  50. scanf("%d", &n);
  51. for(int i = 0; i < n; ++i) {
  52. scanf("%d", &a[i]);
  53. }
  54. int Index = 0;
  55. for(int i = 0; i < maxn; ++i) {
  56. for(int j = 0; j <= i; ++j) {
  57. num[j][i - j] = a[Index];
  58. Index = (Index + 1) % n;
  59. }
  60. }
  61. for(int i = 0; i < maxn; ++i) {
  62. for(int j = 0; j < maxn; ++j) {
  63. if(i != 0) {
  64. num[i][j] += num[i - 1][j];
  65. }
  66. if(j != 0) {
  67. num[i][j] += num[i][j - 1];
  68. }
  69. if(i != 0 && j != 0) {
  70. num[i][j] -= num[i - 1][j - 1];
  71. }
  72. }
  73. }
  74. scanf("%d", &q);
  75. int x1, x2, y1, y2;
  76. while(q--) {
  77. scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  78. LL ans = Sum(x2, y2) + Sum(x1 - 1, y1 - 1);
  79. ans -= Sum(x2, y1 - 1) + Sum(x1 - 1, y2);
  80. printf("%I64d\n", ans);
  81. }
  82. }
  83. return 0;
  84. }

J. Let Sudoku Rotate

题意

有一个 的数独,其中的每一行、每一列、每一 的方格内都不重复地包含 的每一个十六进制数, 已经完成了一个数独,但是被 逆时针旋转了其中的某几个 的方格,给出旋转后的方格,问最少需要几步才能从原数独逆时针旋转到当前状态。

输入

第一行为一个整数 ,接下来有 组数据,每组数据为一个 的字符矩阵,矩阵中只包含 以及 种字符,表示最终的数独状态。

输出

输出一个非负整数,表示最少需要的操作次数。

样例

输入
1
681D5A0C9FDBB2F7
0A734B62E167D9E5
5C9B73EF3C208410
F24ED18948A5CA63
39FAED5616400B74
D120C4B7CA3DEF38
7EC829A085BE6D51
B56438F129F79C2A
5C7FBC4E3D08719F
AE8B1673BF42A58D
60D3AF25619C30BE
294190D8EA57264C
C7D1B35606835EAB
AF52A1E019BE4306
8B36DC78D425F7C9
E409492FC7FA18D2
输出
5
提示
原数独按照如下方式旋转可以得到所输入的数独:

题解

将每个 格子顺时针旋转,每次旋转检查是否与当前格子左上方的所有格子冲突,若冲突则剪枝,否则继续往下搜索,“由于数独限制较强,剪枝效果良好。”

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <sstream>
  17. using namespace std;
  18. #define LL long long
  19. const int maxn = 100;
  20. int T, cnt, ans;
  21. int num[maxn][maxn], Copy[maxn][maxn];
  22. char str[maxn][maxn];
  23. int vis[20];
  24. void Print() {
  25. for(int i = 0; i < 16; ++i) {
  26. for(int j = 0; j < 16; ++j) {
  27. printf("%3d", num[i][j]);
  28. }
  29. printf("\n");
  30. }
  31. }
  32. void rot(int x, int y) {
  33. for(int i = 0; i < 4; ++i) {
  34. for(int j = 0; j < 4; ++j) {
  35. Copy[x + j][y + 3 - i] = num[x + i][y + j];
  36. }
  37. }
  38. for(int i = 0; i < 4; ++i) {
  39. for(int j = 0; j < 4; ++j) {
  40. num[x + i][y + j] = Copy[x + i][y + j];
  41. }
  42. }
  43. }
  44. bool Check(int x, int y) {
  45. for(int i = x; i < x + 4; ++i) {
  46. ++cnt;
  47. for(int j = 0; j < y + 4; ++j) {
  48. if(vis[num[i][j]] == cnt) {
  49. return false;
  50. }
  51. vis[num[i][j]] = cnt;
  52. }
  53. }
  54. for(int j = y; j < y + 4; ++j) {
  55. ++cnt;
  56. for(int i = 0; i < x + 4; ++i) {
  57. if(vis[num[i][j]] == cnt) {
  58. return false;
  59. }
  60. vis[num[i][j]] = cnt;
  61. }
  62. }
  63. return true;
  64. }
  65. void dfs(int depth, int step) {
  66. if(depth == 16) {
  67. ans = min(ans, step);
  68. return ;
  69. }
  70. int x = depth / 4;
  71. int y = depth % 4;
  72. for(int i = 0; i < 4; ++i) {
  73. if(Check(x * 4, y * 4)) {
  74. dfs(depth + 1, step + i);
  75. }
  76. rot(x * 4, y * 4);
  77. }
  78. }
  79. int main() {
  80. #ifdef Dmaxiya
  81. freopen("test.txt", "r", stdin);
  82. // freopen("out.txt", "w", stdout);
  83. #endif // Dmaxiya
  84. ios::sync_with_stdio(false);
  85. scanf("%d", &T);
  86. while(T--) {
  87. for(int i = 0; i < 16; ++i) {
  88. scanf("%s", str[i]);
  89. for(int j = 0; j < 16; ++j) {
  90. if(str[i][j] <= '9') {
  91. num[i][j] = str[i][j] - '0';
  92. } else {
  93. num[i][j] = str[i][j] - 'A' + 10;
  94. }
  95. }
  96. }
  97. ans = INT_MAX;
  98. dfs(0, 0);
  99. printf("%d\n", ans);
  100. }
  101. return 0;
  102. }

K. Expression in Memories

题意

给定一个合法表达式的定义(即我们平时认为的合法表达式):表达式中每个数字除 以外其他数字不包含前导零,表达式中只包含加号和乘号,两个数字之间只能包含一个加号或乘号,加号和乘号必须包含在数字之间。给定一个字符串,字符串中只含有字符 09+*以及 ?,其中 ? 可以被替换成任意一个字符,如果可以将给出的字符串替换为合法的表达式,则输出替换后的表达式,否则输出

输入

第一行为一个整数 ,接下去有 组数据,每组数据为一行字符串 ,字符串中只包含字符 09+*?

输出

如果可以通过替换其中的所有 ? 成为一个合法的表达式,则输出最终的合法表达式,否则输出 ,若有多解输出任意一个。

样例

输入
5
?????
0+0+0
?+*??
?0+?0
?0+0?
输出
11111
0+0+0
IMPOSSIBLE
10+10
IMPOSSIBLE

题解

首先如果有 ? 在一个单独的零(零前无字符,或者是加号与乘号)后面,就将 ? 替换为 +,否则将 ? 替换为 1,替换结束后检查字符串格式是否为一个合法的表达式,如果是则输出字符串,否则输出

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <sstream>
  17. using namespace std;
  18. #define LL long long
  19. const int maxn = 500 + 100;
  20. int T;
  21. char str[maxn];
  22. bool single_zero(int Index) {
  23. if(str[Index] != '0') {
  24. return false;
  25. }
  26. if(Index == 0 || str[Index - 1] == '+' || str[Index - 1] == '*') {
  27. return true;
  28. }
  29. return false;
  30. }
  31. bool Check() {
  32. int len = strlen(str);
  33. if(!isdigit(str[0]) || !isdigit(str[len - 1])) {
  34. return false;
  35. }
  36. int Index = 0;
  37. while(Index < len) {
  38. if(str[Index] == '0' && isdigit(str[Index + 1])) {
  39. return false;
  40. }
  41. while(Index < len && str[Index] != '+' && str[Index] != '*') {
  42. ++Index;
  43. }
  44. ++Index;
  45. if(Index >= len) {
  46. return true;
  47. }
  48. if(!isdigit(str[Index])) {
  49. return false;
  50. }
  51. }
  52. return true;
  53. }
  54. int main() {
  55. #ifdef Dmaxiya
  56. freopen("test.txt", "r", stdin);
  57. // freopen("out.txt", "w", stdout);
  58. #endif // Dmaxiya
  59. ios::sync_with_stdio(false);
  60. scanf("%d", &T);
  61. while(T--) {
  62. scanf("%s", str);
  63. for(int i = 0; str[i]; ++i) {
  64. if(str[i] == '?') {
  65. if(i > 0 && single_zero(i - 1)) {
  66. str[i] = '+';
  67. } else {
  68. str[i] = '1';
  69. }
  70. }
  71. }
  72. if(Check()) {
  73. printf("%s\n", str);
  74. } else {
  75. printf("IMPOSSIBLE\n");
  76. }
  77. }
  78. return 0;
  79. }

L. Graph Theory Homework

题意

给定 个节点的完全图,每个节点都有一个权值 ,节点 和节点 之间的边权为 ,问从节点 到节点 的最短路径长度。

输入

第一行为一个整数 ,接下来有 组数据,每组数据第一行为一个整数 ,第二行有 个整数

输出

输出节点 到节点 的最短路径。

样例

输入
1
3
1 3 5
输出
2

题解

从节点 到节点 之间,经历的中间节点越多, 的距离越长,最短距离就是从节点 的边权。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <sstream>
  17. using namespace std;
  18. #define LL long long
  19. const int maxn = 100000 + 100;
  20. int T, n;
  21. int num[maxn];
  22. int main() {
  23. #ifdef Dmaxiya
  24. freopen("test.txt", "r", stdin);
  25. // freopen("out.txt", "w", stdout);
  26. #endif // Dmaxiya
  27. ios::sync_with_stdio(false);
  28. scanf("%d", &T);
  29. while(T--) {
  30. scanf("%d", &n);
  31. for(int i = 1; i <= n; ++i) {
  32. scanf("%d", &num[i]);
  33. }
  34. printf("%d\n", (int)sqrt(abs(num[n] - num[1])));
  35. }
  36. return 0;
  37. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注