codeforces 423 A. Restaurant Tables 【水题】
//注意，一个人选座位的顺序，先去单人桌，没有则去空的双人桌，再没有则去有一个人坐着的双人桌。读清题意。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, a, b, bb, x;
int main()
{
int ans = ;
scanf("%d%d%d", &n, &a, &b);
while(n--) {
scanf("%d", &x);
if(x==) {
if(a) a--;
else if(b) b--, bb++;
else if(bb) bb--;
else ans++;
}
else {
if(b) b--;
else ans += ;
}
}
printf("%d\n", ans);
return ;
}
codeforces 423 B. Black Square 【模拟】
题意：求需要将几块W涂成B能使所有B组成方形
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = ;
char s[N][N];
int n, m, ans;
int main()
{
int i, j, cnt = ;
scanf("%d%d", &n, &m);
int l1=m-, l2=n-, r1=, r2=;
for(i = ; i < n; ++i) scanf("%s", s[i]);
for(i = ; i < n; ++i) {
for(j = ; j < m; ++j) {
if(s[i][j] == 'B') {
cnt++;
l1 = min(l1, j); l2 = min(l2, i);
r1 = max(r1, j); r2 = max(r2, i);
}
}
}
int len = max(r1-l1+, r2-l2+);
if(len > min(n, m)) ans = -;
else if(!cnt) ans = ;
else { ans = len*len - cnt; }
printf("%d\n", ans);
return ;
}
codeforces 423 C. String Reconstruction 【字符串】
题意：给你n个子串的出现次数和出现位置，构造原字符串，要求字典序最小。
//对每个子串出现位置判断有没有和前一个位置的区间重复，从没有重复的部分继续构造，避免超时。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e6+;
char s[N], t[N];
int n, k, x, ans;
int main()
{
memset(s, 'a', sizeof(s));
int i, j, r = ;
scanf("%d", &n);
while(n--) {
scanf("%s %d", t, &k);
int len = strlen(t);
int pre = -len;
for(i = ; i < k; ++i) {
scanf("%d", &x);
for(j = max(, len-(x-pre)); j < len; ++j)
s[j+x-] = t[j];
pre = x;
r = max(r, x+len-);
}
}
for(i = ; i < r; ++i)
printf("%c", s[i]);
puts("");
return ;
}
codeforces 423 D. High Load 【构造】
题意：给出结点总数n和出口结点数k，（出口结点度数为1，其他结点度数至少为2， 结点编号为1~n）构造网络，使得两个最远的出口节点之间的距离最小的。（两节点之间的距离是这两个节点之间的线数）。输出最远结点之间的最小距离 和 构造出的网络。
题解：就是构造一棵深度最小的树，先将k个结点都与根结点相连，然后依次将剩余结点与这k个结点相连，层次性加深树的深度即可。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, k, m, h, d;
int main()
{
int i, ans;
scanf("%d%d", &n, &k);
h = (n-) / k;
d = (n-) % k;
if(!d) ans = * h;
else if(d == ) ans = * h + ;
else ans = * h + ;
printf("%d\n", ans);
for(i = ; i <= k+; ++i) printf("1 %d\n", i);
for(i = k+; i <= n; ++i) printf("%d %d\n", i, i-k);
return ;
}