Codeforces Round #609 (Div. 2)

        Codeforces Round #609 (Div. 2)题解。

A. Equation

        输出$9n$和$8n$不就行了。。

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
printf("%d %d", 9 * n, 8 * n);
return 0;
}

B. Modulo Equality

        枚举$b$的每一个数,使得$a$的第一个数可以等于这个数,求出对应的$x$,然后暴力判断是否可行。

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
#include <bits/stdc++.h>
using namespace std;
int n, m, a[5000], b[5000], ans = 0x3f3f3f3f, tmp[5000];
int check(int x)
{
for (int i = 1; i <= n; i++) tmp[i] = (a[i] + x) % m;
sort(tmp + 1, tmp + n + 1);
for (int i = 1; i <= n; i++) {
if (tmp[i] != b[i]) return 0;
}
return 1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1; i <= n; i++) scanf("%d", b + i);
sort(b + 1, b + n + 1);
for (int i = 1, x; i <= n; i++) {
x = b[1] - a[i], x = (x % m + m) % m;
if (check(x)) ans = min(ans, x);
}
printf("%d", ans);
// PAUSE;
return 0;
}

C. Long Beautiful Integer

        容易发现答案长度一定与给定数相同(因为有$9999$这样的数存在)。
        复制前$k$个数,后面根据周期性推出来。
        判断这样得到的数是否可行,如果可行直接输出,否则进行调整。调整的方法是从$k$遍历到$1$,找第一个不是$9$的数,将其加一,然后将后面的$9$变成$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
#include <bits/stdc++.h>
using namespace std;
char s1[500005], s2[500005];
int n, k;
int cmp()
{
for (int i = 1; i <= n; i++) {
if (s2[i] > s1[i]) return 0;
if (s1[i] > s2[i]) return i;
}
return 0;
}
int main()
{
scanf("%d%d", &n, &k);
scanf("%s", s1 + 1);
for (int i = 1; i <= k; i++) s2[i] = s1[i];
for (int i = k + 1; i <= n; i++) s2[i] = s2[i - k];
int d = cmp();
if (d == 0) {
printf("%d\n", n);
for (int i = 1; i <= n; i++) printf("%c", s2[i]);
} else {
int ans = 0;
for (int i = k; i >= 1; i--) {
if (s2[i] != '9') {
ans = i;
break;
}
}
for (int i = ans; i <= n; i += k) ++s2[i];
for (int i = ans + 1; i <= k; i++) {
for (int j = i; j <= n; j += k) s2[j] = '0';
}
printf("%d\n", n);
for (int i = 1; i <= n; i++) printf("%c", s2[i]);
}
// PAUSE;
return 0;
}

D. Domino for Young

        利用二分图的思想,将其黑白染色,答案就是两色点数量较少的一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int op[300005], n;
long long ans, s;
vector<int> vec;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i), s += op[i];
for (int i = 1; i <= n; i++) {
if (i & 1)
ans += (op[i] + 1) >> 1;
else
ans += op[i] - ((op[i] + 1) >> 1);
}
printf("%lld", min(ans, s - ans));
// PAUSE;
return 0;
}

E. K Integers

        先将$1$到$k$放到一起(不修改相对次序),然后再调整。
        考虑放到一起的最小代价。假设排名为$i$的数的位置为$pos(i)$,最后调整的位置中最左侧的位置的左侧为$x$。那么调整的代价就是:

        为了最小化这个式子,我们将$pos(i)-i$看成一个整体,这样$x$在取这些数的中位数时可以使上述答案最小。为了$O(logn)$地求这个数,可以开平衡树来维护,需要注意的是插入一个数后,排名会发生变化,需要打懒标记。
        调整相对次序的代价就是逆序数,这个很好维护。

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
#include <bits/stdc++.h>
#define N 300005
using namespace std;
int n, op[N], to[N], tr[N], nx[N], cnt = 1, root;
struct Node
{
int l, r, v, k, num, lz;
long long sum;
} nd[N];
inline int newNode(int v)
{
nd[cnt].k = rand(), nd[cnt].v = v, nd[cnt].sum = v, nd[cnt].num = 1;
return cnt++;
}
inline void upd(int x)
{
nd[x].sum = nd[x].v + nd[nd[x].l].sum + nd[nd[x].r].sum;
nd[x].num = 1 + nd[nd[x].l].num + nd[nd[x].r].num;
}
inline void pud(int x)
{
if (x == 0 || nd[x].lz == 0) return;
if (nd[x].l) {
nd[nd[x].l].v += nd[x].lz, nd[nd[x].l].sum += 1ll * nd[x].lz * nd[nd[x].l].num;
nd[nd[x].l].lz += nd[x].lz;
}
if (nd[x].r) {
nd[nd[x].r].v += nd[x].lz, nd[nd[x].r].sum += 1ll * nd[x].lz * nd[nd[x].r].num;
nd[nd[x].r].lz += nd[x].lz;
}
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 - nd[nd[rt].l].num - 1);
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[rt].l);
upd(rt);
}
inline void add(int x, int v)
{
for (; x <= n; 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;
}
inline void addNode(int at, int v)
{
int a, b;
split(root, a, b, at - 1);
if (b) --nd[b].v, nd[b].sum -= nd[b].num, --nd[b].lz;
merge(a, a, newNode(v)), merge(root, a, b);
}
inline long long get(int s)
{
int mid = (s + 1) >> 1, a, b, c;
long long ans = 0;
split(root, a, c, mid);
split(a, a, b, mid - 1);
if (a != 0) ans += 1ll * (mid - 1) * nd[b].v - nd[a].sum;
if (c != 0) ans += nd[c].sum - 1ll * (s - mid) * nd[b].v;
merge(a, a, b), merge(root, a, c);
return ans;
}
int main()
{
srand(time(0)), scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i), to[op[i]] = i;
for (int i = n; i >= 1; i--) nx[op[i]] = sum(op[i] - 1), add(op[i], 1);
long long ss = 0;
for (int i = 1; i <= n; i++) {
ss += nx[i], addNode(i - nx[i], to[i] - (i - nx[i]));
printf("%lld ", ss + get(i));
}
// PAUSE;
return 0;
}

0%