[关闭]
@Dmaxiya 2018-08-17T10:26:49.000000Z 字数 6355 阅读 978

Codeforces Round #385 (Div. 2)

Codeforces


Contests 链接:Codeforces Round #385 (Div. 2)
过题数:4
排名:27/8581

A. Hongcow Learns the Cyclic Shift

题意

正在学习英语单词,他想要将一个单词通过循环右移得到新的单词,循环右移的方法是:将这个单词的最后一个字符移动到这个单词的第一个字符之前,现在他想要知道,一个单词经过无限次的循环右移,能够得到多少个不同的单词。

输入

一个字符串 ,其中 ,字符串中只有小写字符 'a'-'z'。

输出

输出一个数字,表示将单词 经过任意多次循环右移后得到的不同的单词数量。

样例

输入 输出
abcd 4
bbb 1
yzyz 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 <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. string str, tmp;
  21. set<string> st;
  22. int main() {
  23. #ifdef LOCAL
  24. freopen("test.txt", "r", stdin);
  25. // freopen("out.txt", "w", stdout);
  26. #endif // LOCAL
  27. ios::sync_with_stdio(false);
  28. while(cin >> str) {
  29. st.clear();
  30. int len = str.length();
  31. for(int i = 0; i < len; ++i) {
  32. st.insert(str);
  33. str = str.substr(1, len - 1) + str[0];
  34. }
  35. cout << st.size() << endl;
  36. }
  37. return 0;
  38. }

B. Hongcow Solves A Puzzle

题意

很喜欢拼图,现在他有一块长方形的拼图,这块拼图可以用一个 的字符串矩阵来描述,'X' 表示这块地方有图片, '.' 表示这块地方是空的,由于这块拼图太重了,所以 不能旋转、翻转这块拼图。现在给定一块拼图,问能否只通过平移,使得这块拼图的复制品能与原拼图不重叠地拼成一个实心矩形。

输入

第一行包含 ,接下来的 行每行有 个字符,所有字符只包含 '.''X',含义如题,数据保证所有的 'X' 在四个方向上是连通的,且至少含有一个 'X'

输出

如果可以拼成一个矩形,则输出 "YES",否则输出 "NO"。

样例

输入 输出
2 3
XXX
XXX
YES
2 2
.X
XX
NO
5 5
.....
..X..
.....
.....
.....
YES

题解

多画几组样例就可以发现,在 全连通的情况下,只有 为一个实心矩形时,才可能将两块拼图不旋转不翻转地拼成一个实心矩形,所以只要找到上下左右最边上的坐标,判断是否实心就可以了。

过题代码

  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 <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 600;
  21. int n, m;
  22. int minx, miny, maxx, maxy;
  23. char str[maxn][maxn];
  24. int main() {
  25. #ifdef LOCAL
  26. freopen("test.txt", "r", stdin);
  27. // freopen("out.txt", "w", stdout);
  28. #endif // LOCAL
  29. ios::sync_with_stdio(false);
  30. while(scanf("%d%d", &n, &m) != EOF) {
  31. int cnt = 0;
  32. minx = miny = INT_MAX;
  33. maxx = maxy = INT_MIN;
  34. for(int i = 0; i < n; ++i) {
  35. scanf("%s", str[i]);
  36. for(int j = 0; j < m; ++j) {
  37. if(str[i][j] == 'X') {
  38. ++cnt;
  39. minx = min(minx, i);
  40. miny = min(miny, j);
  41. maxx = max(maxx, i);
  42. maxy = max(maxy, j);
  43. }
  44. }
  45. }
  46. if(cnt == 0) {
  47. printf("NO\n");
  48. continue;
  49. }
  50. bool flag = true;
  51. for(int i = minx; i <= maxx; ++i) {
  52. for(int j = miny; j <= maxy; ++j) {
  53. if(str[i][j] == '.') {
  54. flag = false;
  55. break;
  56. }
  57. }
  58. if(!flag) {
  59. break;
  60. }
  61. }
  62. if(flag) {
  63. printf("YES\n");
  64. } else {
  65. printf("NO\n");
  66. }
  67. }
  68. return 0;
  69. }

C. Hongcow Builds A Nation

题意

是世界的统治者,这个世界上有 个城市和 条道路,这些道路连接任意两个不相同的城市,且任意两个城市之间最多只有一条道路。在这 个城市中有 个城市是首都,为了让这个世界稳定,任意一个两个非首都的城市,如果它们能够到达的首都不相同,那么它们之间就不能有能够互相到达的路径。现在 想要在保证世界稳定的前提下,修建尽可能多的路,问他最多能修建多少条道路。

输入

第一行三个整数 ,第二行有 个不同的整数 ,表示 个首都,接下去 行每行两个整数 ,表示城市 之间有一条道路。数据保证世界是稳定的。

输出

输出 在保证世界稳定的前提下,能够修建的最多的道路数。

样例

输入 输出
4 1 2
1 3
1 2
2
3 3 1
2
1 2
1 3
2 3
0

题解

在一个 个节点的连通块内,能修建的最多的道路数为 ,所以可以用并查集判断连通块并统计连通块内的边的数量,对于无法到达首都的那些节点,由于连通块内能连边的道路数是 增长的,所以应尽量使这些节点往有首都的、节点数多的连通块连通,这样才能让可以修建的道路最多。

过题代码

  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 <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 100000 + 100;
  21. int n, m, k, ans;
  22. int u[maxn], v[maxn];
  23. int line[maxn];
  24. int sum[maxn];
  25. int cap[maxn];
  26. int fa[maxn];
  27. bool iscap[maxn];
  28. void Init() {
  29. for(int i = 1; i <= n; ++i) {
  30. fa[i] = i;
  31. sum[i] = 1;
  32. iscap[i] = false;
  33. line[i] = 0;
  34. }
  35. }
  36. int Find(int x) {
  37. return (x == fa[x]? x: fa[x] = Find(fa[x]));
  38. }
  39. void unit(int x, int y) {
  40. int xx = Find(x);
  41. int yy = Find(y);
  42. if(xx != yy) {
  43. fa[xx] = yy;
  44. sum[yy] += sum[xx];
  45. }
  46. }
  47. int main() {
  48. #ifdef LOCAL
  49. freopen("test.txt", "r", stdin);
  50. // freopen("out.txt", "w", stdout);
  51. #endif // LOCAL
  52. ios::sync_with_stdio(false);
  53. while(scanf("%d%d%d", &n, &m, &k) != EOF) {
  54. Init();
  55. for(int i = 0; i < k; ++i) {
  56. scanf("%d", &cap[i]);
  57. }
  58. for(int i = 0; i < m; ++i) {
  59. scanf("%d%d", &u[i], &v[i]);
  60. unit(u[i], v[i]);
  61. }
  62. int Index = 0;
  63. for(int i = 0; i < k; ++i) {
  64. cap[i] = Find(cap[i]);
  65. iscap[cap[i]] = true;
  66. if(sum[cap[i]] > sum[cap[Index]]) {
  67. Index = i;
  68. }
  69. }
  70. Index = cap[Index];
  71. for(int i = 1; i <= n; ++i) {
  72. int f = Find(i);
  73. if(!iscap[f]) {
  74. unit(f, Index);
  75. }
  76. }
  77. for(int i = 0; i < m; ++i) {
  78. int uu = Find(u[i]);
  79. ++line[uu];
  80. }
  81. ans = 0;
  82. for(int i = 0; i < k; ++i) {
  83. ans += (sum[cap[i]] * (sum[cap[i]] - 1)) / 2 - line[cap[i]];
  84. }
  85. printf("%d\n", ans);
  86. }
  87. return 0;
  88. }

D. Hongcow's Game

题意

你和 玩一个游戏,首先有一个 的矩阵,如果用 表示这个矩阵中的第 行第 列的数字,则这个矩阵满足


现在你可以问 最多 个问题,每个问题包含 个整数 ,表示要询问的列数, 将会回复你 个整数,第 个整数表示从第 行的所有数字中,选出所有被询问的列的数字中的最小值,即 ,你要通过 的回答来得到每一行除对角线外的最小值,即

输入

初始输入只包含一个数字 ,表示矩阵的大小,后面的输入根据你的提问进行回复,每次输入 个数字。

输出

如果你要询问 ,则先输出一个 ,第二行为 个整数,表示要询问的列数,如果你要回答 的问题,则先输出单独的一行 ,第二行输出 个整数,第 个整数表示 。注意在每段输出后清空输出缓冲区。
如果出现下面的情况,你的输出将会返回

  1. 你的输入格式与题目描述不符;
  2. 你的提问超过了 个;
  3. 你的问题包含了重复的下标;
  4. 你的 不在区间 之间;
  5. 你最后的回答不正确。

样例

输入 输出
3


0 0 0


2 7 0


0 0 4


3 0 8


0 5 4

3
1 2 3

1
3

2
1 2

1
2

1
1

-1
2 5 4
2


0 0


0 0

1
2

1
1

-1
0 0

题解

首先从下标的二进制最低位到最高位枚举(最多只要 次),第 次枚举第 位为 的所有下标,这样就能得到每一行所有下标组合的最小值,由题意可以知道,如果询问的列下标包含 ,则关于 行的回答总是 ,这个回答是不正确的,所以只要将这样的回答筛掉,就可以得到正确的答案。

过题代码

  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 <functional>
  17. #include <iomanip>
  18. using namespace std;
  19. #define LL long long
  20. const int maxn = 1000 + 100;
  21. int n, dig;
  22. int Min[maxn], ret[maxn];
  23. int ask[maxn], cnt;
  24. void get_ask(int d, int x) {
  25. cnt = 0;
  26. for(int i = 1; i <= n; ++i) {
  27. if(((i >> d) & 1) == x) {
  28. ask[cnt++] = i;
  29. }
  30. }
  31. }
  32. int main() {
  33. #ifdef LOCAL
  34. // freopen("test.txt", "r", stdin);
  35. // freopen("out.txt", "w", stdout);
  36. #endif // LOCAL
  37. ios::sync_with_stdio(false);
  38. scanf("%d", &n);
  39. for(int i = 1; i <= n; ++i) {
  40. Min[i] = INT_MAX;
  41. }
  42. int nn = n;
  43. while(nn != 0) {
  44. ++dig;
  45. nn >>= 1;
  46. }
  47. for(int i = 0; i < dig; ++i) {
  48. get_ask(i, 0);
  49. printf("%d\n", cnt);
  50. for(int j = 0; j < cnt; ++j) {
  51. if(j != 0) {
  52. printf(" ");
  53. }
  54. printf("%d", ask[j]);
  55. }
  56. printf("\n");
  57. fflush(stdout);
  58. for(int j = 1; j <= n; ++j) {
  59. scanf("%d", &ret[j]);
  60. if(((j >> i) & 1) != 0) {
  61. Min[j] = min(Min[j], ret[j]);
  62. }
  63. }
  64. get_ask(i, 1);
  65. printf("%d\n", cnt);
  66. for(int j = 0; j < cnt; ++j) {
  67. if(j != 0) {
  68. printf(" ");
  69. }
  70. printf("%d", ask[j]);
  71. }
  72. printf("\n");
  73. fflush(stdout);
  74. for(int j = 1; j <= n; ++j) {
  75. scanf("%d", &ret[j]);
  76. if(((j >> i) & 1) != 1) {
  77. Min[j] = min(Min[j], ret[j]);
  78. }
  79. }
  80. }
  81. printf("-1\n");
  82. for(int i = 1; i <= n; ++i) {
  83. if(i != 1) {
  84. printf(" ");
  85. }
  86. printf("%d", Min[i]);
  87. }
  88. printf("\n");
  89. fflush(stdout);
  90. return 0;
  91. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注