Codeforces Round #1002(Div.2)

B

题目大意：给定一个数组 $a$ 和一个偶整数 $k$ （ $2\le k\le n$ ）。需要将数组 $a$ 分割为恰好 $k$ 个非空子数组。使得数组 $a$ 的每一个元素恰好属于其中一个子数组。下一步，将所有具有偶数索引的子数组（第 $2$，$4$，…，$k$ 个）连接起来，成为一个新数组 $b$。之后，把 $0$ 添加到数组 $b$ 的末尾。数组 $b$ 的开销被定义为：最小的使 $b_i\ne i$ 的索引 $i$。请确定一种划分数组 $a$ 的最优方案，使得数组 $b$ 的开销最小。

数据范围：$1\le t\le10^4$，$2\le k\le n\le 2 \cdot 10^5$。

思路：

 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
using i128 = __int128_t;
void solve() {
    ll n, k;
    cin >> n >> k;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    if (k == n) {
        int ans = n / 2 + 1;
        for (int i = 1; i <= n - 1; i += 2) {
            if (a[i] != (i + 1) / 2) {
                ans = (i + 1) / 2;
                cout << ans << endl;
                return;
            }
        }
        cout << ans << endl;
        return;
    }
    int ans = k / 2 + 1;
    rep(i, 1, n - (k - 2) - 1) {
        if (a[i] != 1) {
            cout << 1 << endl;
            return;
        }
    }
    cout << 2 << endl;
    return;
}

C

题目大意：现在有共 $n$ 条队列，每条队列一开始都有 $0$ 个人。在接下来的 $n$ 个时刻，每个时刻会发生以下两件事（顺序发生）： 1. 在第 $j$ 个时刻，第 $i$ 个队伍的人数增加 $a_{i,j}$； 2. 你可以且必须选择 $n$ 条队列中的一条，并使该队列人数清零。最后，记第 $i$ 条队列的剩余人数为 $x_i$，需要确定集合 $\{x_1,x_2,\cdots,x_n\}$ 的 $\operatorname{MEX}^{\dagger}$ 可能的最大值。

数据范围：$1 \le t \le 2 \cdot 10^4$，$1 \le n \le 300$，$1 \le a_{i,j} \le 10^9$，$\sum n^2 \le 2 \times 10^5$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using i128 = __int128_t;
void solve() {
    ll n;
    cin >> n;
    vvl ma(n, vl(n));
    rep(i, 0, n - 1) { rep(j, 0, n - 1) cin >> ma[i][j]; }
    vl tem;
    rep(i, 0, n - 1) {
        int tem2 = 0;
        frep(j, n - 1, 0) {
            if (ma[i][j] != 1) break;
            tem2++;
        }
        tem.push_back(tem2);
    }
    int cnt = 0;
    ranges::sort(tem);
    rep(i, 0, n - 1) {
        if (tem[i] >= cnt) cnt++;
    }
    cout << cnt << endl;
    return;
}

D

题目大意：给定两个具有相同顶点数的连通无向图。在这两个图中，各有一个标记位于某个顶点处。在第一个图中，标记初始位于顶点 $s_1$；在第二个图中，标记初始位于顶点 $s_2$。以下操作将被无限次重复执行： - 假设当前第一个图中的标记位于顶点 $v_1$，第二个图中的标记位于顶点 $v_2$。- 在第一个图中选择一个与 $v_1$ 相邻的顶点 $u_1$。- 在第二个图中选择一个与 $v_2$ 相邻的顶点 $u_2$。- 将标记移动到选定的顶点：在第一个图中，标记从 $v_1$ 移动到 $u_1$；在第二个图中，标记从 $v_2$ 移动到 $u_2$。- 该操作的代价等于 $|u_1 - u_2|$。确定所有操作的最小可能总代价，或者报告该值将无限大。

数据范围：$1 \le t \le 500$，$2 \le n \le 1000$，$1 \le s_1, s_2 \le n$，$1 \le m_1 \le 1000$，$1 \le a_i, b_i \le n$，$1 \le m_2 \le 1000$，$1 \le c_j, d_j \le n$，$\sum n \le m_2$，$\sum m_1 \le m_2$。

思路：

 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
using i128 = __int128_t;
void solve() {
    ll n, s1, s2, m1, m2, x, y;
    cin >> n >> s1 >> s2;
    vvl ma1(n), ma2(n);
    s1--, s2--;
    cin >> m1;
    set<pll> s;
    vl vis(n);
    rep(i, 0, m1 - 1) {
        cin >> x >> y;
        ma1[x - 1].push_back(y - 1);
        ma1[y - 1].push_back(x - 1);
        s.insert(make_pair(min(x - 1, y - 1), max(x - 1, y - 1)));
    }
    cin >> m2;
    rep(i, 0, m2 - 1) {
        cin >> x >> y;
        ma2[x - 1].push_back(y - 1);
        ma2[y - 1].push_back(x - 1);
        if (s.count(make_pair(min(x - 1, y - 1), max(x - 1, y - 1)))) {
            vis[x - 1] = 1, vis[y - 1] = 1;
        }
    }
    priority_queue<trl, vector<trl>, greater<>> q;
    vvl dis(n + 1, vl(n + 1, LLONG_MAX / 3));
    dis[s1][s2] = 0;
    q.emplace(0, s1, s2);
    ll ans = LLONG_MAX / 3;
    while (!q.empty()) {
        auto [d, x, y] = q.top();
        q.pop();
        if (d > dis[x][y]) continue;
        if (x == y && vis[x]) ans = min(ans, d);
        for (auto& p : ma1[x]) {
            for (auto& q1 : ma2[y]) {
                ll tem = d + abs(p - q1);
                if (tem < dis[p][q1]) {
                    dis[p][q1] = tem;
                    q.emplace(tem, p, q1);
                }
            }
        }
    }
    cout << (ans == LLONG_MAX / 3 ? -1 : ans) << endl;
    return;
}