首页 > 代码库 > Codeforces Round #423 (Div. 2)
Codeforces Round #423 (Div. 2)
codeforces 423 A. Restaurant Tables 【水题】
//注意，一个人选座位的顺序，先去单人桌，没有则去空的双人桌，再没有则去有一个人坐着的双人桌。读清题意。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 int n, a, b, bb, x; 6 int main() 7 { 8 int ans = 0; 9 scanf("%d%d%d", &n, &a, &b);10 while(n--) {11 scanf("%d", &x);12 if(x==1) {13 if(a) a--;14 else if(b) b--, bb++;15 else if(bb) bb--;16 else ans++;17 }18 else {19 if(b) b--;20 else ans += 2;21 }22 }23 printf("%d\n", ans);24 return 0;25 }
codeforces 423 B. Black Square 【模拟】
题意：求需要将几块W涂成B能使所有B组成方形
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 const int N = 105; 6 char s[N][N]; 7 int n, m, ans; 8 int main() 9 {10 int i, j, cnt = 0;11 scanf("%d%d", &n, &m);12 int l1=m-1, l2=n-1, r1=0, r2=0;13 for(i = 0; i < n; ++i) scanf("%s", s[i]);14 for(i = 0; i < n; ++i) {15 for(j = 0; j < m; ++j) {16 if(s[i][j] == ‘B‘) {17 cnt++;18 l1 = min(l1, j); l2 = min(l2, i);19 r1 = max(r1, j); r2 = max(r2, i);20 }21 }22 }23 int len = max(r1-l1+1, r2-l2+1);24 if(len > min(n, m)) ans = -1;25 else if(!cnt) ans = 1;26 else { ans = len*len - cnt; }27 printf("%d\n", ans);28 return 0;29 }
codeforces 423 C. String Reconstruction 【字符串】
题意：给你n个子串的出现次数和出现位置，构造原字符串，要求字典序最小。
//对每个子串出现位置判断有没有和前一个位置的区间重复，从没有重复的部分继续构造，避免超时。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 const int N = 2e6+10; 6 char s[N], t[N]; 7 int n, k, x, ans; 8 int main() 9 {10 memset(s, ‘a‘, sizeof(s));11 int i, j, r = 0;12 scanf("%d", &n);13 while(n--) {14 scanf("%s %d", t, &k);15 int len = strlen(t);16 int pre = -len;17 for(i = 0; i < k; ++i) {18 scanf("%d", &x);19 for(j = max(0, len-(x-pre)); j < len; ++j)20 s[j+x-1] = t[j];21 pre = x;22 r = max(r, x+len-1);23 }24 }25 for(i = 0; i < r; ++i)26 printf("%c", s[i]);27 puts("");28 return 0;29 }
codeforces 423 D. High Load 【构造】
题意：给出结点总数n和出口结点数k，（出口结点度数为1，其他结点度数至少为2， 结点编号为1~n）构造网络，使得两个最远的出口节点之间的距离最小的。（两节点之间的距离是这两个节点之间的线数）。输出最远结点之间的最小距离 和 构造出的网络。
题解：就是构造一棵深度最小的树，先将k个结点都与根结点相连，然后依次将剩余结点与这k个结点相连，层次性加深树的深度即可。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 int n, k, m, h, d; 6 int main() 7 { 8 int i, ans; 9 scanf("%d%d", &n, &k);10 h = (n-1) / k;11 d = (n-1) % k;12 if(!d) ans = 2 * h;13 else if(d == 1) ans = 2 * h + 1;14 else ans = 2 * h + 2;15 printf("%d\n", ans);16 for(i = 2; i <= k+1; ++i) printf("1 %d\n", i);17 for(i = k+2; i <= n; ++i) printf("%d %d\n", i, i-k);18 return 0;19 }
Codeforces Round #423 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。