[关闭]
@Dmaxiya 2020-12-12T15:28:10.000000Z 字数 5229 阅读 1108

Codeforces Round #423 (Div. 2)

Codeforces


Contests 链接:Codeforces Round #423 (Div. 2)
过题数:2
排名:1611/9405

A. Restaurant Tables

题意

一个餐馆里有 个单人座和 个双人座,如果来了一位顾客,如果还有单人座就让他坐单人座,否则如果有空着的双人座,就让他坐双人座,否则如果有已经坐了一位顾客的双人座,就让他坐那个双人座,否则餐馆就无法接待这位顾客;如果来了两位顾客,如果有空着的双人座,就让他们坐双人座,否则餐馆就无法接待他们。问这个餐馆最后拒绝了多少位顾客。

输入

第一行包含三个整数 ,分别表示来的顾客的组数、单人座的数量和双人座的数量,第二行包含 个整数 ,表示 组按顺序来的顾客里每一组的人数。

输出

输出这个餐馆最后拒绝的顾客数量。

样例

输入 输出 提示
4 1 2
1 2 1 1
0 第一组顾客坐在一个单人座上,第二组顾客坐在第一个双人座上,第三组顾客只能坐在
剩下的第二个双人座上,第四组顾客只能和第三组顾客一起坐在第二个双人座上,这个
餐馆可以接待所有顾客。
4 1 1
1 1 2 1
2 第一组顾客坐在单人座上,第二组顾客坐在剩下的双人座上,第三组顾客由于没有空着
的双人座,所以餐馆无法接待他们,第四组顾客要和第二组顾客一起坐在双人座上,最
终餐馆拒绝了两位顾客。

题解

用一个变量 记录被占用了一个位置的双人座的数量,按题意模拟就能得到答案。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <sstream>
  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 <algorithm>
  15. using namespace std;
  16. #define LL long long
  17. int n, a, b, c, t, ans;
  18. int main() {
  19. #ifdef Dmaxiya
  20. freopen("test.txt", "r", stdin);
  21. #endif // Dmaxiya
  22. ios::sync_with_stdio(false);
  23. while(scanf("%d%d%d", &n, &a, &b) != EOF) {
  24. ans = 0;
  25. c = 0;
  26. for(int i = 0; i < n; ++i) {
  27. scanf("%d", &t);
  28. if(t == 1) {
  29. if(a > 0) {
  30. --a;
  31. } else if(b > 0) {
  32. --b;
  33. ++c;
  34. } else if(c > 0) {
  35. --c;
  36. } else {
  37. ++ans;
  38. }
  39. } else {
  40. if(b > 0) {
  41. --b;
  42. } else {
  43. ans += 2;
  44. }
  45. }
  46. }
  47. printf("%d\n", ans);
  48. }
  49. return 0;
  50. }

B. Black Square

题意

在一个 的方格上,只有黑和白两种颜色,现在要在这个方格纸上涂出一块正方形的黑色区域,在涂的过程中只能将白色涂成黑色,不能将黑色涂成白色,且在正方形之外的所有颜色都是白色,问最少需要把多少块白色方格涂成黑色?如果无法办到则输出

输入

第一行包含两个整数 ,接下去 行每行一个长度为 的字符串,字符串内只有 'B''W' 两种字符,分别表示黑色和白色。

输出

输出要涂出一个边长为正整数的正方形黑色方块,且正方形之外的所有颜色都是白色,最少需要涂的白色方块数,如果无法办到则输出

样例

输入 输出 提示
5 4
WWWW
WWWB
WWWB
WWBB
WWWW
5 需要填充的五个白色方格的坐标为 ,该正方形的边长为
1 2
BB
-1 所有的方格都是黑色,且形状是一个矩形,所以无法涂成一个正方形。
3 3
WWW
WWW
WWW
1 所有的方格都是白色的,所以最少只要涂一个方格就能得到一个边长为 的正方形。

题解

找到最左上和最右下的黑色方格,在水平和竖直方向的距离最大的,就是最终的正方形的边长 ,边长应该满足 ,否则无法形成黑色正方形,然后计算需要涂色的白色方格数即可。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <sstream>
  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 <algorithm>
  15. using namespace std;
  16. #define LL long long
  17. const int maxn = 100 + 100;
  18. int n, m, maxx, maxy, minx, miny, a, cnt;
  19. char str[maxn];
  20. int main() {
  21. #ifdef Dmaxiya
  22. freopen("test.txt", "r", stdin);
  23. #endif // Dmaxiya
  24. ios::sync_with_stdio(false);
  25. while(scanf("%d%d", &n, &m) != EOF) {
  26. cnt = 0;
  27. maxx = maxy = -1;
  28. minx = miny = INT_MAX;
  29. for(int i = 0; i < n; ++i) {
  30. scanf("%s", str);
  31. for(int j = 0; j < m; ++j) {
  32. if(str[j] == 'B') {
  33. minx = min(minx, i);
  34. miny = min(miny, j);
  35. maxx = max(maxx, i);
  36. maxy = max(maxy, j);
  37. ++cnt;
  38. }
  39. }
  40. }
  41. if(maxx == -1) {
  42. printf("1\n");
  43. continue;
  44. }
  45. a = max(maxx - minx, maxy - miny) + 1;
  46. if(a > min(n, m)) {
  47. printf("-1\n");
  48. continue;
  49. }
  50. printf("%d\n", a * a - cnt);
  51. }
  52. return 0;
  53. }

C. String Reconstruction

题意

本来有一个只包含小写字母的字符串 ,但是他忘了这个字符串是什么,只记得这个字符串的一部分特征,他记得字符串 个子串 以及第 个子串出现的 个位置 ,他现在想要根据这些信息构造出一个新的字符串,要使这个新字符串的字典序最小,求满足条件的新字符串。

输入

第一行为一个整数 ,接下去 行,每行的开头为一个只包含小写字母的非空字符串 ,接下去为一个整数 ,表示子串 出现在 中的 个位置,后面跟着 个整数 。被描述的每个子串 出现的位置可能是重合的,数据保证不自相矛盾,一定能构造出一个合法的字符串

输出

输出满足条件的字典序最小的字符串

样例

输入 输出
3
a 4 1 3 5 7
ab 2 1 5
ca 1 4
abacaba
1
a 1 3
aaa
3
ab 1 1
aba 1 3
ab 2 3 5
ababab

题解

由数据范围可知,可能的最长的字符串的长度为 ,可以先将 都放入集合 ,表示还未确定字符的下标,根据每个子串以及出现的位置,每次都从 中二分查找出起始位置和终止位置,跑遍所有没有确定字符的下标,将这些字符按照题给规则确定,并从 中删除这些下标,时间复杂度为

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <sstream>
  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 <algorithm>
  15. using namespace std;
  16. #define LL long long
  17. const int maxn = 2000000 + 100;
  18. int n, k, x, len, Size;
  19. char ans[maxn], str[maxn];
  20. set<int> st;
  21. set<int>::iterator Begin, End, it;
  22. vector<set<int>::iterator> vct;
  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. st.clear();
  30. memset(ans, 0, sizeof(ans));
  31. for(int i = 1; i < maxn; ++i) {
  32. st.insert(i);
  33. }
  34. while(n--) {
  35. scanf("%s%d", str, &k);
  36. len = strlen(str);
  37. while(k--) {
  38. scanf("%d", &x);
  39. vct.clear();
  40. Begin = st.lower_bound(x);
  41. End = st.upper_bound(x + len - 1);
  42. for(it = Begin; it != End; ++it) {
  43. vct.push_back(it);
  44. ans[*it] = str[*it - x];
  45. }
  46. Size = vct.size();
  47. for(int i = 0; i < Size; ++i) {
  48. st.erase(vct[i]);
  49. }
  50. }
  51. }
  52. for(int i = maxn - 1; i >= 0; --i) {
  53. if(ans[i] != '\0') {
  54. len = i + 1;
  55. break;
  56. }
  57. }
  58. for(int i = 1; i < len; ++i) {
  59. if(ans[i] == '\0') {
  60. ans[i] = 'a';
  61. }
  62. }
  63. printf("%s\n", ans + 1);
  64. }
  65. return 0;
  66. }

D. High Load

题意

个节点,在其中添加 条边,每条边连接两个不同的节点,使所有节点连通,且在树上总共有 个节点的度为 ,找到一种最优的连接方案,使得树的直径最小。

输入

输入只有两个整数

输出

第一行输出最小的树的直径,接下去 行为树上的所有边,边的顺序和节点的顺序任意,且每条边不能重复出现。

样例

输入 输出 提示
3 2 2
1 2
2 3
输出所表示的树如图:

rV2Qd1.png

其中黄色为度为 的节点。
5 3 3
1 2
2 3
3 4
3 5
输出所表示的树如图:

rV2rJf.png

其中黄色为度为 的节点。

题解

构造一个叶子节点数量为 的菊花树。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <sstream>
  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 <algorithm>
  15. using namespace std;
  16. #define LL long long
  17. const int maxn = 200000 + 100;
  18. int n, k, cnt;
  19. int depth[maxn], fa[maxn];
  20. int main() {
  21. #ifdef Dmaxiya
  22. freopen("test.txt", "r", stdin);
  23. #endif // Dmaxiya
  24. ios::sync_with_stdio(false);
  25. while(scanf("%d%d", &n, &k) != EOF) {
  26. depth[1] = 0;
  27. for(int i = 2; i <= n; ++i) {
  28. int f = i - k;
  29. if(f < 1) {
  30. f = 1;
  31. }
  32. depth[i] = depth[f] + 1;
  33. fa[i] = f;
  34. }
  35. sort(depth + 1, depth + 1 + n);
  36. printf("%d\n", depth[n] + depth[n - 1]);
  37. for(int i = 2; i <= n; ++i) {
  38. printf("%d %d\n", fa[i], i);
  39. }
  40. }
  41. return 0;
  42. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注