mlger
0%

Codeforces Round 880(Div. 2)

发表于 更新于 分类于

挂个传送门：Dashboard - Codeforces Round 880 (Div. 2) - Codeforces

评价是，切完ABC蹲大牢

B. Astrophysicists

题意：

$k*g$ 银币分配给 $n$ 人，设一个人分到 $x$ 银币，$r=x \mod g$ 对每人有补正如下：

  • 若 $r\geq \lceil \frac{g}{2} \rceil$，则向上修正至 $x+(g-r)$；
  • 否则，向下修正至 $x-r$ .

求分配完后，剩下的银币数目之和最小值。

题解：

​ 什么黑心资本家出的题。

​ 考虑一个人分配到的银币，从 $0$ 增加至 $g$ 。增加至 $\lceil \frac{g}{2}\rceil$ 前，经补正他所获得银币为 $0$ ，原先分配银币即剩下；增加至 $\lceil \frac{g}{2}\rceil$ 后，我们需要额外的银币为其补正。 故对一个人来说，我们的收益和他分配的银币呈一个由两直线构成的分段函数，从 $0$ 开始并且回到 $0$ 。我们的最大收益点在 $p=\lceil \frac{g}{2}\rceil-1$ 。

​ 此时可以分成两种情况讨论：

  • 若 $np \geq kg $ ，那所有人贪心分配（至多 $p$ ），最后每个人分配到 $0$ ，方案显然最优，结果为 $ k*g $ 。

  • 若$np< kg$， 最优分配结果为$g\lfloor \frac{p*n}{g} \rfloor$ 。

​ 讨论下第二种情况，为什么是这个式子。

​ 易知，最优方案不存在向上修正。设第 $i$ 个人分配到 $x_i$ 银币，则有$\sum x_i = k*g$，因此我们的收益 $income$ 满足 $income=\sum (x_i\% g)\equiv (\sum x_i)\% g\equiv 0 $ 。这是一个比较重要的性质，答案必定是 $g$ 的倍数。

​ 设 $income=kg$ ，则必有 $kg \leq pn $ （答案上限就是 $pn$ ），故 $income = kg = g \lfloor \frac { p*n } { g } \rfloor $

code：

1
2
3
4
5
6
7
8
9
10
11
void solve() {
    long long n, k, g;
    cin >> n >> k >> g;
    long long p = ((g + 1) >> 1) - 1;
    if (p * n >= k * g) {
        cout << k * g << endl;
    } else {
        cout << p * n / g * g << endl;
    }

}
C. K-th equality

题意：

​ 构造第 $k$ 大字典序字符串，其中字符串形如 $A$ 位数 $+B$ 位数 $=C$ 位数。

题解：

​ 体感很简单的一道题。

​ 设 $x$ 位数的范围为 $[L_x, R_x)$

​ 由于 $A\leq 6$，因此枚举 $x+y=z$ 中的 $x$ 。

​ 接下来寻找对 $y$ 的限制条件。

  • $L_B\leq y<R_B$
  • $L_C\leq z< R_C$ ，即 $L_C\leq x+y <R_C$

​ 由此可得限制条件 $max\{L_B,L_C-x\}\leq y<min\{R_B,R_C+x\}$

​ 然后边统计边算即可。复杂度 $O (10^A)$

code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int mn[8] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000};

void solve() {
    int A, B, C;
    long long k;
    cin >> A >> B >> C >> k;
    for (int mx = mn[A + 1], i = mn[A]; i < mx; i++) {
        int l = max(mn[C] - i, mn[B]);
        int r = min(mn[C + 1] - i, mn[B + 1]);
        if (l >= r) continue;
        if (k <= r - l) {
            cout << i << " + " << l + k - 1 << " = " << i + l + k - 1 << endl;
            return;
        } else k -= r - l;
    }
    cout << -1 << endl;
    return;
}
E. Twin Clusters

题意：

​ 给定长为 $2^{k+1}$ 的一序列，值域为 $[0,4^k)$ 。求原序列两不相交子区间，使得两子区间中数字的异或和相同。

题解：

​ 瞄了眼 Tutorial ，不太好想。一开始想过类似于分块的思路，实际解法也差不多，不过只取一个块。

​ 先关注二进制下低 $k$ 位。算上空串，共有 $2^{k+1}+1$ 个值，但实际上低 $k$ 位值域 $[0,2^k-1]$ 共 $2^k$ 个值，因此根据鸽巢原理，我们可以匹配出 $2^k+1$ 个区间 $(l_i, r_i]$，使得这每个区间 $S_{r_i} \ xor\ S_{l_i}$ 的低$k$ 位均为 $0$ 。

​ 接下来关注这些线段的高 $k$ 位。采取同样的方法，根据鸽巢原理，必定存在两个子区间高 $k$ 位的异或和相同，取这两子区间的交即为结果。

code：

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
void solve() {
#define mp(x, y) make_pair(x, y)
    int k, n;
    cin >> k;
    n = (1 << (k + 1));
    vector<long long> g(n + 1), s(n + 1);
    vector<pair<long long, long long> > Line;
    unordered_map<long long, long long> mp;
    mp[0] = 0;
    g[0] = s[0] = 0;
    long long lbit = (1ll << k) - 1;
    long long hbit = (((1ll << (k << 1)) - 1) ^ lbit);
    for (int i = 1; i <= n; i++) {
        cin >> g[i];
        s[i] = s[i - 1] ^ g[i];
        long long p = (s[i] & lbit);
        if (mp[p] || p == 0) Line.push_back(mp(mp[p], i));
        mp[p] = i;
    }
    unordered_map<long long, int> pos;
    int i = 0;
    for (auto line: Line) {
        ++i;
        long long p = ((s[line.second] ^ s[line.first]) & hbit);
        if (pos[p] != 0) {
            auto l1 = Line[pos[p] - 1], l2 = line;
            if (l1.second <= l2.first) {
                cout << l1.first + 1 << ' ' << l1.second << ' ' << l2.first + 1 << ' ' << l2.second << endl;
            } else {
                cout << min(l1.first, l2.first) + 1 << ' ' << max(l1.first, l2.first) << ' ' << l1.second + 1 << ' '
                     << l2.second << endl;
            }
            return;
        } else pos[p] = i;
    }

}
D. Lottery

题意：

​ 给定 $n$ 个人，每人买一张彩票，票号在 $[0,m]$ 范围内。设开奖号为 $x$ ，则票号距离 $x$ 最近的 $k$ 人中奖，平局情况则编号小的获胜。作为第 $n+1$ 人，你编号最大，求最小位置，使得能够使你中奖的编号尽可能多。

题解：

​ 非常繁琐的一道题。先来看这幅图（截自 tutorials ）：

image-20230702173756179

​ 假设当前选择编号为 $c$ ，$c$ 的前 $k$ 名为 $a$ ，后 $k$ 名为 $b$ 。则中奖区间为 $(\lfloor \frac{a+c}{2} \rfloor, \lceil \frac{b+c}{2} \rceil)$ 。由此计算结果。

​ 接下来讨论需要枚举哪些 $c$ 。由上面图可知，处在 $(d,e)$ 区间内时，中奖区间虽然改变，但实际中奖区间长度不变（$a$ 和 $b$ 没有变化）。故我们只需讨论 $n$ 个人所选号码的前后两三个数即可。 当然，特别考虑边界情况。

​ 输入量较大，需要注意 $IO$ 效率。

code：

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
#include<bits/stdc++.h>

using namespace std;

vector<long long> v;
int nowl, nowr;
int n, k;
long long m;

long long calc(long long now_pos) {
    while (nowl < n && v[nowl] < now_pos) ++nowl;
    while (nowr < n && v[nowr] <= now_pos) ++nowr;
    long long posl = nowr - k < 0 ? 0 : (now_pos + v[nowr - k]) / 2 + 1;
    long long posr = nowl + k - 1 >= n ? m : (now_pos + v[nowl + k - 1] - 1) / 2;
    return max(0ll, posr - posl + 1);
}

void solve() {
    v.clear();
    cin >> n >> m >> k;
    long long c;
    for (int i = 0; i < n; i++) {
        cin >> c;
        v.push_back(c);
    }
    v.push_back(m + 1);
    sort(v.begin(), v.end());
    nowl = nowr = 0;
    long long res_pos = 0, ans = calc(0);
    for (int i = 0; i < n; i++) {
        long long bl = i == 0 ? max(0ll, v[i] - 2) : max(v[i] - 2, v[i - 1] + 3);
        long long br = min(v[i] + 2, m);
        for (long long now_pos = bl; now_pos <= br; now_pos++) {
            long long p = calc(now_pos);
            if (p > ans) {
                ans = p;
                res_pos = now_pos;
            }
        }
    }
    cout << ans << ' ' << res_pos << endl;
    return;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}
F. Doctor’s Brown Hypothesis

题意：

​ 给定一有向图，求无序点对 $(u, v)$ 的数目，使得 $u$ 和 $v$ 相互之间存在着长度为 $k$ 的路径，其中 $u=v$ 也被允许。

题解：

​ 不会。稍微翻译下 tutorial 。

​ 突破口在 $k\geq n^3$ 。显然对于所有满足答案的点对，两点都在同一个强连通分量内。于是讨论范围缩减到同一个 $SCC$ 。对强连通分量内的所有环的大小，存在一个最大公约数 $g$ 。将所有的边 $$ 按照 $t=(s+1)mod\ g$ 进行染色。由于 $k$ 比较大，所以可以认为颜色相同的点都是等价的。

​ 对于一个连通分量内，满足条件的点对有以下两种：

  • $g|k$ ，则所有颜色相同点对满足条件。
  • $2|g$ 且 $k\equiv g/2\ mod \ g$ ，则所有颜色差值为 $g/2$ 的点对满足条件

code：

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
125
126
127
128
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, m;
long long k;
vector<int> v[N];
vector<int> vec[N];
int col[N], cnt_col;
int _stack[N], _t, dfn[N], low[N], cnt, siz[N];
bool book[N];

inline void tarjan(int x) {
    //强连通分量
    dfn[x] = low[x] = ++cnt;
    _stack[++_t] = x;
    book[x] = true;
    for (auto ver: v[x]) {
        if (!dfn[ver]) {
            tarjan(ver);
            low[x] = min(low[x], low[ver]);
        } else if (book[ver]) low[x] = min(low[x], dfn[ver]);
    }
    if (dfn[x] == low[x]) {
        ++cnt_col;
        int p;
        do {
            p = _stack[_t];
            col[p] = cnt_col;
            ++siz[cnt_col];
            book[p] = false;
            --_t;
        } while (p != x);
    }
}

int flag[N], dis[N];
bool solved[N];

inline void dfs(int x, int d, int des) {
    dis[x] = d;
    flag[x] = des;
    for (auto ver: vec[x]) {
        if (flag[ver] != des) dfs(ver, d + 1, des);
    }
}

int num[N];

int tag[N];

inline bool draw_col(int x, int now, int base_num, int des) {
    //尝试染色
    num[x] = now;
    tag[x] = des;
    bool Flag = true;
    for (auto ver: vec[x]) {
        if (!Flag) return false;
        if (tag[ver] != des) Flag &= draw_col(ver, (now + 1) % base_num, base_num, des);
        else Flag &= (num[ver] == ((num[x] + 1) % base_num));
    }
    return Flag;
}

int cnt_num[N];

inline void Draw_col(int x, int now, int base_num, int des) {
    //染色，统计数目
    num[x] = now;
    tag[x] = des;
    ++cnt_num[now];
    for (auto ver: vec[x]) {
        if (tag[ver] != des) Draw_col(ver, (now + 1) % base_num, base_num, des);
    }
}


int main() {
    cin >> n >> m >> k;
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        v[x].push_back(y);
    }
    for (int i = 1; i <= n; i++) {
        if (!col[i]) tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        for (auto y: v[i]) {
            if (col[i] == col[y]) vec[i].push_back(y);
        }
    }
    int search_num = 0;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (solved[col[i]]) continue;
        solved[col[i]] = true;
        if (siz[col[i]] == 1) continue;
        int x = i, y = vec[x][0];
        int d = 0;
        dfs(y, 0, y);
        d += dis[x] + 1;
        int g = 1;
        for (int j = 2; j * j <= d; j++) {
            if (d % j != 0) continue;
            int p = j, rem_num = 1;
            bool now_flag = true;
            while (d % p == 0) {
                ++search_num;
                if (now_flag && draw_col(x, 0, p, search_num)) rem_num = p;
                else now_flag = false;
                p *= j;
            }
            d /= (p / j);
            g *= rem_num;
        }
        if (d > 1 && (++search_num) && draw_col(x, 0, d, search_num)) g *= d;
        for (int j = 0; j < g; j++) cnt_num[j] = 0;
        ++search_num;
        Draw_col(x, 0, g, search_num);
        if (k % g == 0) {
            for (int j = 0; j < g; j++) ans += 1ll * cnt_num[j] * (cnt_num[j]+1) / 2;
        } else if (g % 2 == 0 && k % g == g / 2) {
            for (int j = 0; j < g / 2; j++) ans += 1ll * cnt_num[j] * cnt_num[j + g / 2];
        }
    }
    cout << ans << endl;
}