[关闭]
@Dmaxiya 2018-08-17T10:23:55.000000Z 字数 5286 阅读 1094

Codeforces Round #441 (Div. 2)

Codeforces


Contests 链接:Codeforces Round #441 (Div. 2)
过题数:4
排名:840/9270

A. Trip For Meal

题意

小熊维尼一天要吃 次蜂蜜,而兔子、猫头鹰和屹耳的家里都有蜂蜜,最初他在兔子的家里,先吃一次蜂蜜,接着去另一个朋友的家里吃蜂蜜,假设当他离开某个朋友的家之后,这个朋友家里的蜂蜜就会恢复,给定三个朋友的家之间的距离,问小熊维尼想要吃 次蜂蜜,最少要走多少米。

输入

输入包括四行整数,分别为 ,表示小熊要吃蜂蜜的次数、兔子和猫头鹰家之间的距离、兔子和屹耳家之间的距离以及猫头鹰和屹耳家之间的距离。

输出

输出要吃 次蜂蜜,维尼至少要走的距离。

样例

输入 输出 提示
3
2
3
1
3 对于维尼来说最优的策略是:兔子猫头鹰屹耳。
1
2
3
5
0 维尼只要在兔子家吃一次蜂蜜,之后不需要移动任何距离。

题解

分别对 分情况按贪心策略讨论即可。

过题代码

  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 <bitset>
  16. #include <algorithm>
  17. #include <ctime>
  18. #include <functional>
  19. #include <iomanip>
  20. using namespace std;
  21. #define LL long long
  22. int n, a, b, c;
  23. int main() {
  24. #ifdef LOCAL
  25. freopen("test.txt", "r", stdin);
  26. // freopen("out.txt", "w", stdout);
  27. #endif
  28. ios::sync_with_stdio(false);
  29. while(scanf("%d%d%d%d", &n, &a, &b, &c) != EOF) {
  30. if(n == 1) {
  31. printf("0\n");
  32. } else {
  33. printf("%d\n", min(a, b) + (n - 2) * min(min(a, b), c));
  34. }
  35. }
  36. return 0;
  37. }

B. Divisiblity of Differences

题意

给出 个整数的序列 ,从中找出 个数字,使这 个数字两两之间的差能整除

输入

第一行包含三个整数 ,第二行包含 个整数

输出

如果无法找出 个满足要求的数字,就输出 ,否则在第一行输出 ,第二行输出 个满足条件的整数,如果有多解,则输出任意一组。

样例

输入 输出
3 2 3
1 8 4
Yes
1 4
3 3 3
1 8 4
No
4 3 5
2 7 7 7
Yes
2 7 7

题解

如果每个数字对 的模数相等,那么这几个数字任意两个数字之间的差一定是 的倍数。

过题代码

  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 <bitset>
  16. #include <algorithm>
  17. #include <ctime>
  18. #include <functional>
  19. #include <iomanip>
  20. using namespace std;
  21. #define LL long long
  22. const int maxn = 100000 + 100;
  23. int n, k, m, num, Index;
  24. vector<int> ans[maxn];
  25. int main() {
  26. #ifdef LOCAL
  27. freopen("test.txt", "r", stdin);
  28. // freopen("out.txt", "w", stdout);
  29. #endif
  30. ios::sync_with_stdio(false);
  31. while(scanf("%d%d%d", &n, &k, &m) != EOF) {
  32. Index = -1;
  33. for(int i = 0; i < n; ++i) {
  34. ans[i].clear();
  35. }
  36. for(int i = 0; i < n; ++i) {
  37. scanf("%d", &num);
  38. ans[num % m].push_back(num);
  39. if((int)ans[num % m].size() >= k) {
  40. Index = num % m;
  41. }
  42. }
  43. if(Index == -1) {
  44. printf("No\n");
  45. continue;
  46. }
  47. printf("Yes\n");
  48. for(int i = 0; i < k; ++i) {
  49. if(i != 0) {
  50. printf(" ");
  51. }
  52. printf("%d", ans[Index][i]);
  53. }
  54. printf("\n");
  55. }
  56. return 0;
  57. }

C. Classroom Watch

题意

给定一个数字 ,求有多少个数字 ,满足 ,其中 表示数字 的位数。

输入

输入只有一个整数

输出

第一行输出一个整数 ,表示有 个满足条件的数字,接下去 行每行一个整数,表示每个满足条件的整数,按照从小到大的顺序输出。

样例

输入 输出 提示
21 1
15
是唯一一个满足条件的数字:.
20 0 没有任何数字满足条件

题解

从数据范围可以知道,满足条件的数字一定在范围 内,因为 内的数字所有数位的和最大为 ,所以暴力枚举 个数字就能找到所有满足条件的答案。

过题代码

  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 <bitset>
  16. #include <algorithm>
  17. #include <ctime>
  18. #include <functional>
  19. #include <iomanip>
  20. using namespace std;
  21. #define LL long long
  22. const int maxn = 300;
  23. int n, cnt;
  24. int ans[maxn];
  25. int get_sum(int num) {
  26. int ret = num;
  27. while(num != 0) {
  28. ret += num % 10;
  29. num /= 10;
  30. }
  31. return ret;
  32. }
  33. int main() {
  34. #ifdef LOCAL
  35. freopen("test.txt", "r", stdin);
  36. // freopen("out.txt", "w", stdout);
  37. #endif
  38. ios::sync_with_stdio(false);
  39. while(scanf("%d", &n) != EOF) {
  40. cnt = 0;
  41. for(int i = 0; i <= 90; ++i) {
  42. if(n - i >= 0) {
  43. if(get_sum(n - i) == n) {
  44. ans[cnt++] = n - i;
  45. }
  46. }
  47. }
  48. printf("%d\n", cnt);
  49. for(int i = cnt - 1; i >= 0; --i) {
  50. if(i != cnt - 1) {
  51. printf(" ");
  52. }
  53. printf("%d", ans[i]);
  54. }
  55. printf("\n");
  56. }
  57. return 0;
  58. }

D. Sorting the Coins

题意

对一个长度为 的序列,进行下面的操作:

  1. 从左到右扫一遍整个序列;
  2. 如果第 个数字是被标记的,而第 个数字是没有被标记的,就将第 个数字和第 个数字交换。

重复以上步骤,直到无法再对这个序列的任意两个数字进行交换。
定义一个序列的“难度”,为一个序列能进行以上操作的次数,如果这个序列已经不能再交换数字,它的“难度”为
最初这个序列没有数字是被标记的,它的“难度”为 ,接着将这个序列每一位上的数字逐一标记,总共标记 次,对这个序列的每次标记,输出这个序列的“难度”。

输入

第一行为一个整数 ,第二行为 的排列 ,表示每次标记的数字为序列的第 项。

输出

输出 个数字 表示初始序列的“难度”, 表示第 个数字被标记后序列的难度。

样例

输入 输出 提示
4
1 3 4 2
1 2 3 2 1 表示没有被标记的数字, 表示被标记的数字,最初没有任何数字可以
被交换,序列的“难度”为 ,第 个数字被标记后,对序列的
操作为:

序列的“难度”为 ,第 个数字被标记后,对序列的操作为:

序列的“难度”为 ,第 个数字被标记后,序列的操作为:

序列的“难度”为 ,第 个数字被标记后,序列的操作为:

序列的“难度”为
8
6 8 3 4 7 2 1 5
1 2 2 3 4 3 4 5 1

题解

每次操作的时候,最右边的所有被标记的数字都无法移动,且不在最右边的所有数字中,只能移动一个最右边的数字到最右边,如:

一次操作之后变为

最右边的 个数字都无法移动,而前面的数字里,只有倒数第 个数字能够移动到最右边,所以每次操作只能移动一个数字到最右边,因此总的操作次数就是已经被标记的数字个数 最右边的数字个数,可以用并查集维护。

过题代码

  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 <bitset>
  16. #include <algorithm>
  17. #include <ctime>
  18. #include <functional>
  19. #include <iomanip>
  20. using namespace std;
  21. #define LL long long
  22. const int maxn = 300000 + 100;
  23. int n, x;
  24. int fa[maxn], num[maxn];
  25. bool vis[maxn];
  26. void Init() {
  27. for(int i = 1; i <= n; ++i) {
  28. fa[i] = i;
  29. vis[i] = false;
  30. num[i] = 1;
  31. }
  32. }
  33. int Find(int x) {
  34. return (fa[x] == x? x: fa[x] = Find(fa[x]));
  35. }
  36. void unit(int x, int y) {
  37. int xx = Find(x);
  38. int yy = Find(y);
  39. if(xx != yy) {
  40. fa[xx] = yy;
  41. num[yy] += num[xx];
  42. }
  43. }
  44. int main() {
  45. #ifdef LOCAL
  46. freopen("test.txt", "r", stdin);
  47. // freopen("out.txt", "w", stdout);
  48. #endif
  49. ios::sync_with_stdio(false);
  50. while(scanf("%d", &n) != EOF) {
  51. Init();
  52. printf("1");
  53. for(int i = 1; i <= n; ++i) {
  54. scanf("%d", &x);
  55. vis[x] = true;
  56. if(vis[x - 1]) {
  57. unit(x - 1, x);
  58. }
  59. if(vis[x + 1]) {
  60. unit(x, x + 1);
  61. }
  62. int ans;
  63. if(vis[n]) {
  64. int f = Find(n);
  65. ans = i - num[f] + 1;
  66. } else {
  67. ans = i + 1;
  68. }
  69. printf(" %d", ans);
  70. }
  71. printf("\n");
  72. }
  73. return 0;
  74. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注