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;
}