Educational Codeforces Round 80
/ / 阅读耗时 20 分钟 Educational Codeforces Round 80题解。
A. Deadline
考虑下面的式子：
双对勾函数在$(x+1)^2=d$时取最小值，在$\sqrt d-1$附近找一下最小值即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
int main()
{
int t;
scanf("%d", &t);
while (t--) {
int n, d;
scanf("%d%d", &n, &d);
double ans = 1e100;
int p = sqrt(d) - 1;
for (int i = max(0, p - 3); i <= p + 3; i++) {
ans = min(ans, i + 1.0 * d / (i + 1));
}
int ps = ceil(ans);
if (ps <= n)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
B. Yet Another Meme Problem
假设$b$的十进制位数为$x$，那么$conc(a,b)=a10^x+b$。于是原式化成：
就是：
满足这个条件的$b$只有$9$、$99$、$999$这样的数，从$B$的范围中找找有多少满足的数，然后乘上$A$就是答案。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
int bin[20];
int main()
{
bin[0] = 1;
for (int i = 1; i <= 10; i++) bin[i] = bin[i - 1] * 10;
int t;
scanf("%d", &t);
while (t--) {
int a, b;
scanf("%d%d", &a, &b);
int at = 1;
while (bin[at] - 1 <= b) ++at;
printf("%lld\n", 1ll * a * (at - 1));
}
// PAUSE;
return 0;
}
C. Two Arrays
$DP$大水题。只要让末端满足不小于的条件即可，然后$DP$，没什么可说的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
int n, m, dp1[1005][11], ans, dp2[1005][11], s1[1005][11], s2[1005][11];
int main()
{
scanf("%d%d", &n, &m);
for (int i = n; i >= 1; i--) dp1[i][1] = 1;
for (int i = n; i >= 1; i--) s1[i][1] = (s1[i + 1][1] + dp1[i][1]) % MOD;
for (int i = 2; i <= m; i++) {
for (int j = 1; j <= n; j++) dp1[j][i] = s1[j][i - 1];
for (int j = n; j >= 1; j--) s1[j][i] = (s1[j + 1][i] + dp1[j][i]) % MOD;
}
for (int i = 1; i <= n; i++) dp2[i][1] = 1;
for (int i = 1; i <= n; i++) s2[i][1] = (s2[i - 1][1] + dp2[i][1]) % MOD;
for (int i = 2; i <= m; i++) {
for (int j = 1; j <= n; j++) dp2[j][i] = s2[j][i - 1];
for (int j = 1; j <= n; j++) s2[j][i] = (s2[j - 1][i] + dp2[j][i]) % MOD;
}
for (int i = 1; i <= n; i++) ans = (ans + 1ll * dp1[i][m] * s2[i][m] % MOD) % MOD;
printf("%d", ans);
return 0;
}
D. Minimax Problem
上来就能想到二分答案，关键是怎么判定。
二分出一个答案$p$，我们每一个数列中不小于$p$的数变成$1$，否则变成$0$，然后将数列变成一个二进制数。问题转化为从一堆数中找出两个数的按位或为$2^m-1$。
由于$m$很小，可以开一个大小为$256$左右的数组强行记忆，从而求解。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
int op[500005][10], n, m, hs[500005], vis[500], to[500], ll, rr;
int check(int mid)
{
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++) {
hs[i] = 0;
for (int j = 1; j <= m; j++) {
if (op[i][j] >= mid) hs[i] |= 1 << (j - 1);
}
for (int j = 0; j < (1 << m); j++) {
if ((j | hs[i]) == (1 << m) - 1) vis[j] = 1, to[j] = i;
}
if (vis[hs[i]]) {
ll = to[hs[i]], rr = i;
return 1;
}
}
return 0;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) scanf("%d", &op[i][j]);
}
int l = 0, r = 1000000001, mid;
while (l < r) {
if (r == l + 1) break;
mid = (l + r) >> 1;
if (check(mid))
l = mid;
else
r = mid;
}
check(l);
// cout << l << endl;
printf("%d %d", ll, rr);
// PAUSE;
return 0;
}
E. Messenger Simulator
先说说我的无脑做法，$O((n+m)log(n))$。
平衡树维护队列次序。将某一个数提到前方就进行序列之间的拼接，实现转移。找某一个数的位置时，从上到下依次下方懒标记，从而求解。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
using namespace std;
struct Node
{
int l, r, lz, v, num, k, by, minans, maxans, fa;
} nd[N];
int cnt = 1, root, n, m, sta[N], la[N], ra[N];
inline int newNode(int x)
{
nd[cnt].by = x, nd[cnt].v = x, nd[cnt].num = 1;
nd[cnt].maxans = nd[x].minans = x;
nd[cnt].lz = 0, nd[cnt].k = rand();
return cnt++;
}
inline void upd(int x)
{
if (x == 0) return;
nd[x].num = 1 + nd[nd[x].l].num + nd[nd[x].r].num;
nd[x].minans = min(nd[x].minans, nd[x].v);
nd[x].maxans = max(nd[x].maxans, nd[x].v);
if (nd[x].l) nd[nd[x].l].fa = x;
if (nd[x].r) nd[nd[x].r].fa = x;
nd[x].fa = 0;
}
inline void pud(int x)
{
if (nd[x].lz == 0 || x == 0) return;
int l = nd[x].l, r = nd[x].r;
if (l) {
nd[l].v += nd[x].lz, nd[l].lz += nd[x].lz;
nd[l].minans = min(nd[l].minans, nd[l].v);
nd[l].maxans = max(nd[l].maxans, nd[l].v);
}
if (r) {
nd[r].v += nd[x].lz, nd[r].lz += nd[x].lz;
nd[r].minans = min(nd[r].minans, nd[r].v);
nd[r].maxans = max(nd[r].maxans, nd[r].v);
}
nd[x].lz = 0;
}
void split(int rt, int& a, int& b, int v)
{
pud(rt);
if (rt == 0) {
a = b = 0;
return;
}
if (nd[nd[rt].l].num + 1 <= v)
a = rt, split(nd[rt].r, nd[a].r, b, v - 1 - nd[nd[rt].l].num);
else
b = rt, split(nd[rt].l, a, nd[b].l, v);
upd(rt);
}
void merge(int& rt, int a, int b)
{
pud(a), pud(b);
if (a == 0 || b == 0) {
rt = a + b;
return;
}
if (nd[a].k > nd[b].k)
rt = a, merge(nd[rt].r, nd[a].r, b);
else
rt = b, merge(nd[rt].l, a, nd[b].l);
upd(rt);
}
inline void solve(int x)
{
int i = 0;
sta[i++] = x;
while (nd[x].fa) sta[i++] = nd[x].fa, x = nd[x].fa;
while (i >= 1) pud(sta[i - 1]), --i;
}
void DFS(int x)
{
if (x == 0) return;
pud(x), la[nd[x].by] = nd[x].minans, ra[nd[x].by] = nd[x].maxans;
DFS(nd[x].l), DFS(nd[x].r);
}
int main()
{
srand(time(nullptr)), scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) merge(root, root, newNode(i));
for (int i = 1, x; i <= m; i++) {
scanf("%d", &x), solve(x);
int a, b, c, np = nd[x].v;
split(root, a, c, np), split(a, a, b, np - 1);
nd[b].v = 1, upd(b), nd[b].lz = 0;
if (a) ++nd[a].lz, ++nd[a].v, upd(a);
merge(b, b, a), merge(root, b, c);
}
DFS(root);
for (int i = 1; i <= n; i++) printf("%d %d\n", la[i], ra[i]);
// PAUSE;
return 0;
}
更好的做法是这样。
注意到如果不把数提到前面，则它的最小位置就是本身，否则就是1。现在问题就是如何求最大位置。
我们开一个长度为$n+m$的树状数组，将序列逆序，变成$n$到$1$，它们的位置分别为$1$到$n$，即记$pos_i=n-i+1$，这样提到前面就是放到最后。然后将对应的位置记为$1$，其余记为$0$。对于某一个操作，将$x$提到前方，我们将更新$x$的最大位置（通过树状数组前缀和差实现），然后将它的位置放到$n+i$上（$i$是询问的序号），将原位置变为$0$，新位置变为$1$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using namespace std;
int minn[N], maxn[N], pos[N], n, m, tr[N << 1], x;
inline void add(int x, int v)
{
for (; x <= n + m; x += x & -x) tr[x] += v;
}
inline int sum(int x)
{
int s = 0;
for (; x >= 1; x -= x & -x) s += tr[x];
return s;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) pos[i] = n - i + 1, add(pos[i], 1), minn[i] = maxn[i] = i;
for (int i = 1; i <= m; i++) {
scanf("%d", &x), minn[x] = 1, maxn[x] = max(sum(n + m) - sum(pos[x] - 1), maxn[x]);
add(pos[x], -1), pos[x] = n + i, add(pos[x], 1);
}
for (int i = 1; i <= n; i++) maxn[i] = max(maxn[i], sum(n + m) - sum(pos[i] - 1));
for (int i = 1; i <= n; i++) printf("%d %d\n", minn[i], maxn[i]);
return 0;
}
F. Red-Blue Graph
看起来像一个网络流，主要问题是如何描述严格大于的关系。
我们将每一条边变成方向相反的两条，其中从左向右的一条代表红边，从右向左的代表蓝边，它们的流量限制为1，费用分别为$r$和$b$。
如何描述严格大于的关系？对于左边的红点，它流出的流量多于流入的流量，这意味着它需要更多的流入来平衡，于是建一个源点$S$，指向该点，容量下限为1，上限无穷大。其余的都可以类似建图。对于无色点，需要同时连向源点和汇点，容量下限为0，上限无穷大，表示对于流入流出的多少没有限制。
容易发现原图上的一条边拆出的两条边是不可能同时走的，原因自行思考。
问题转化为求有源汇最小费用可行流问题。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
using namespace std;
struct Edge
{
int next, to, v, p;
} edge[N << 4];
int head[N], n1, n2, m, r, b, S, T, h[N], heap[N], dis[N], sz, ID[N], cnt, s, t, H, ep;
int flow[N], pre[N], ans, minCost, d[N];
char s1[N], s2[N];
inline void addE(int x, int y, int v, int p)
{
edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].p = p, head[x] = cnt++;
edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].p = -p, head[y] = cnt++;
}
void down(int x)
{
int x1 = x << 1, x2 = x << 1 | 1, minn = x;
if (x1 <= sz && dis[heap[x1]] < dis[heap[minn]]) minn = x1;
if (x2 <= sz && dis[heap[x2]] < dis[heap[minn]]) minn = x2;
if (x != minn) swap(heap[x], heap[minn]), swap(ID[heap[x]], ID[heap[minn]]), down(minn);
}
void up(int x)
{
if (x == 1) return;
if (dis[heap[x >> 1]] > dis[heap[x]]) swap(heap[x >> 1], heap[x]), swap(ID[heap[x >> 1]], ID[heap[x]]), up(x >> 1);
}
inline void add(int x)
{
ID[x] = ++sz, heap[sz] = x, up(sz);
}
inline int top()
{
int t = heap[1];
ID[heap[1]] = 0;
if (sz != 1)
ID[heap[sz]] = 1, heap[1] = heap[sz--], down(1);
else
sz = 0;
return t;
}
inline int dijkstra()
{
memset(pre, -1, sizeof(pre)), memset(dis, 0x3f, sizeof(dis));
dis[S] = 0, add(S), flow[S] = inf;
while (sz) {
int f = top();
for (int i = head[f]; ~i; i = edge[i].next) {
if (edge[i].v > 0 && dis[edge[i].to] > dis[f] + edge[i].p + h[f] - h[edge[i].to]) {
dis[edge[i].to] = dis[f] + edge[i].p + h[f] - h[edge[i].to];
flow[edge[i].to] = min(flow[f], edge[i].v);
pre[edge[i].to] = i;
if (ID[edge[i].to])
up(ID[edge[i].to]);
else
add(edge[i].to);
}
}
}
return pre[T] != -1;
}
inline void add(int x, int y, int l, int r, int p)
{
d[x] -= l, d[y] += l, addE(x, y, r - l, p);
}
int main()
{
cnt = 0, memset(head, -1, sizeof(head));
scanf("%d%d%d%d%d", &n1, &n2, &m, &r, &b), scanf("%s%s", s1, s2);
S = 0, T = n1 + n2 + 1;
for (int i = 0; i < n1; i++) {
if (s1[i] == 'R')
add(S, i + 1, 1, inf, 0);
else if (s1[i] == 'B')
add(i + 1, T, 1, inf, 0);
else
addE(S, i + 1, inf, 0), addE(i + 1, T, inf, 0);
}
for (int i = 0; i < n2; i++) {
if (s2[i] == 'B')
add(S, i + 1 + n1, 1, inf, 0);
else if (s2[i] == 'R')
add(i + 1 + n1, T, 1, inf, 0);
else
addE(S, n1 + i + 1, inf, 0), addE(n1 + i + 1, T, inf, 0);
}
addE(T, S, inf, 0), ep = cnt;
for (int i = 1, x, y; i <= m; i++) scanf("%d%d", &x, &y), addE(x, y + n1, 1, r), addE(y + n1, x, 1, b);
s = n1 + n2 + 2, t = n1 + n2 + 3;
for (int i = 0; i <= T; i++) {
if (d[i] > 0) addE(s, i, d[i], 0), H += d[i];
if (d[i] < 0) addE(i, t, -d[i], 0);
}
S = s, T = t;
while (dijkstra()) {
int to = T;
while (to != S) edge[pre[to]].v -= flow[T], edge[pre[to] ^ 1].v += flow[T], to = edge[pre[to] ^ 1].to;
ans += flow[T], minCost += flow[T] * (dis[T] - h[S] + h[T]);
for (int i = 0; i <= n1 + n2 + 3; i++) h[i] += dis[i];
}
if (ans != H) minCost = -1;
printf("%d\n", minCost);
if (minCost != -1) {
for (int i = 0; i < m; i++) {
int e = ep + (i << 2);
if (edge[e].v == 0)
printf("R");
else if (edge[e + 2].v == 0)
printf("B");
else
printf("U");
}
}
// PAUSE;
return 0;
}