[关闭]
@Dmaxiya 2018-08-17T10:18:30.000000Z 字数 4089 阅读 906

Codeforces Round #462 (Div. 2)

Codeforces


Contests 链接:Codeforces Round #462 (Div. 2)
过题数:3
排名:462/9658

A. A Compatible Pair

题意

有一个长度为 的序列 有一个长度为 的序列 从自己的序列中除掉一个数字, 个数字的 序列中选择一个数字,再从自己序列中选择一个数字,将这两个数字相乘,就是得到的结果。现在 想让最终结果最小,而 想让最终结果最大,问如果两人都采取最优策略,最终的结果会是多少。

输入

第一行为两个整数 ,第二行为 个整数 ,第三行为 个整数 ,其中

输出

输出最终结果。

样例

输入 输出 提示
2 2
20 18
2 14
252 将会删去 ,而 将会选择
5 3
-1 0 1 2 3
-1 0 1
2 将会删去 将会选择

题解

暴力枚举所有情况,对于 删除的每一个数字,枚举 所有可能的选择中的最大值,输出这些最大值中的最小值。

过题代码

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

B. A Prosperous Lot

题意

给定数字 ,构造一个不超过 的正整数 ,使得所有数位中的圈的个数和等于

输入

一个整数

输出

输出满足条件的整数 ,如果不存在满足条件的正整数,则输出

样例

输入 输出
2 462
6 8080

题解

如果 大于 ,输出 ,否则输出 后,再输出 个一个环的数字()。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cfloat>
  7. #include <cstring>
  8. #include <string>
  9. #include <vector>
  10. #include <list>
  11. #include <queue>
  12. #include <stack>
  13. #include <map>
  14. #include <set>
  15. #include <algorithm>
  16. using namespace std;
  17. #define LL long long
  18. int k;
  19. int main() {
  20. #ifdef Dmaxiya
  21. freopen("test.txt", "r", stdin);
  22. #endif // Dmaxiya
  23. ios::sync_with_stdio(false);
  24. while(scanf("%d", &k) != EOF) {
  25. if(k > 36) {
  26. printf("-1\n");
  27. continue;
  28. }
  29. while(k - 2 >= 0) {
  30. printf("8");
  31. k -= 2;
  32. }
  33. if(k != 0) {
  34. printf("6");
  35. }
  36. printf("\n");
  37. }
  38. return 0;
  39. }

C. A Twisty Movement

题意

给定一个长度为 的序列 ,序列中所有的数字只可能是 或者 ,现在可以从序列中选取连续的一段数字,将这段数字左右镜像颠倒,求这样颠倒之后最大的最长非递减子序列长度。

输入

第一行为一个整数 ,第二行为 个整数

输出

输出所求答案。

样例

输入 输出 提示
4
1 2 1 2
4 将区间 内所有的数字颠倒之后,新的序列为 ,最长非递减子序列的
长度为
10
1 1 2 2 2 1 1 2 2 1
9 将区间 内所有的数字颠倒之后,新的序列为
最长非递减子序列的长度为

题解

先预处理从第 个数字到第 个数字最大值为 的最长非递减子序列长度 ,以及从第 个数字到第 个数字最小值为 的最长非递减子序列长度 ,以及 的前缀和 ,接着 枚举所有区间,对于每个区间求出区间内以 开头以 结尾最小值为 的最长非递增子序列的长度 ,对每一个区间

就是答案。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cfloat>
  7. #include <cstring>
  8. #include <string>
  9. #include <vector>
  10. #include <list>
  11. #include <queue>
  12. #include <stack>
  13. #include <map>
  14. #include <set>
  15. #include <algorithm>
  16. using namespace std;
  17. #define LL long long
  18. const int maxn = 2000 + 100;
  19. int n, ans;
  20. int num[maxn];
  21. int dpL[maxn][3], dpR[maxn][3];
  22. int dp[maxn][3], sum[maxn][3];
  23. int main() {
  24. #ifdef Dmaxiya
  25. freopen("test.txt", "r", stdin);
  26. #endif // Dmaxiya
  27. ios::sync_with_stdio(false);
  28. while(scanf("%d", &n) != EOF) {
  29. ans = 0;
  30. for(int i = 1; i <= n; ++i) {
  31. scanf("%d", &num[i]);
  32. sum[i][1] = sum[i - 1][1];
  33. sum[i][2] = sum[i - 1][2];
  34. ++sum[i][num[i]];
  35. }
  36. for(int i = 1; i <= n; ++i) {
  37. if(num[i] == 1) {
  38. dpL[i][1] = dpL[i - 1][1] + 1;
  39. dpL[i][2] = max(dpL[i][1], dpL[i - 1][2]);
  40. } else {
  41. dpL[i][1] = dpL[i - 1][1];
  42. dpL[i][2] = max(dpL[i - 1][1], dpL[i - 1][2]) + 1;
  43. }
  44. }
  45. dpR[n + 1][1] = dp[n + 1][2] = 0;
  46. for(int i = n; i > 0; --i) {
  47. if(num[i] == 1) {
  48. dpR[i][1] = max(dpR[i + 1][1], dpR[i + 1][2]) + 1;
  49. dpR[i][2] = dpR[i + 1][2];
  50. } else {
  51. dpR[i][2] = dpR[i + 1][2] + 1;
  52. dpR[i][1] = max(dpR[i + 1][1], dpR[i][2]);
  53. }
  54. }
  55. for(int i = 1; i <= n; ++i) {
  56. dp[i - 1][1] = dp[i - 1][2] = 0;
  57. for(int j = i; j <= n; ++j) {
  58. if(num[j] == 1) {
  59. dp[j][1] = max(dp[j - 1][1], dp[j - 1][2]) + 1;
  60. dp[j][2] = dp[j - 1][2];
  61. } else {
  62. dp[j][2] = dp[j - 1][2] + 1;
  63. dp[j][1] = max(dp[j - 1][1], dp[j][2]);
  64. }
  65. ans = max(ans, dpL[i - 1][1] + dpR[j + 1][1] + sum[j][1] - sum[i - 1][1]);
  66. ans = max(ans, dpL[i - 1][2] + dpR[j + 1][2] + sum[j][2] - sum[i - 1][2]);
  67. ans = max(ans, dpL[i - 1][1] + dpR[j + 1][2] + dp[j][1]);
  68. }
  69. }
  70. printf("%d\n", ans);
  71. }
  72. return 0;
  73. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注