AtCoder Beginner Contest 177

发表于2020-08-31更新于2023-09-15字数统计1.5k阅读时长16分

比赛链接

D Friends

Description

题目链接

Solution

并查集处理每个联通块大小。设最大联通块大小为 SS，那么属于这个联通块的人不能分在一组，所以至少分成 SS 组，而对于大小为 T<ST < S 的联通块，将块中 TT 个人分配到之前分好的 SS 组，且每组至多分配一人即可。故答案为最大联通块的大小。

Code

Friends
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
int n, m, a, b, fa[MAXN], sz[MAXN], ans;

inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

inline void unionn(int a, int b) {
    int r1 = find(a), r2 = find(b);
    if (r1 != r2) fa[r1] = r2, sz[r2] += sz[r1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
    for (int j = 1; j <= m; j++) cin >> a >> b, unionn(a, b);
    for (int i = 1; i <= n; i++)
        if (fa[i] == i) ans = max(ans, sz[i]);
    cout << ans;
    return 0;
}

E Coprime

Description

题目链接

Solution

aia_i 和 ∀aj(j>i)∀a_j(j>i) 互质当且仅当对 ∀j>i,aj∀j>i,a_j 和 aia_i 没有相同的质因数。可以 O(nlnn)O(nlnn) 处理出每个数的所有约数，或者线性筛素数并 O(n)O(n) 预处理出 [2,106][2, 10^6] 每个数的质因数后，对每个质因数的数目记录后缀和 O(n)O(n) 扫一遍即可。

Code

Coprime
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
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;

int n, a[MAXN], cnt[MAXN], gcdd;
vector<int> v[MAXN];

template <class T>
void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

bool isprime(int x) {
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0) return false;
    return true;
}

void init() {
    for (int i = 2; i <= MAXN - 5; i++)
        if (isprime(i))
            for (int k = 1; k * i <= MAXN - 5; k++) v[k * i].push_back(i);
}

int main() {
    init();
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);
    bool tag = 1;
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < v[a[i]].size(); j++)
            if (cnt[v[a[i]][j]]) {
                tag = 0;
                break;
            }
        for (int j = 0; j < v[a[i]].size(); j++) cnt[v[a[i]][j]]++;
    }
    gcdd = a[1];
    for (int i = 2; i <= n; i++) gcdd = __gcd(a[i], gcdd);
    if (tag)
        cout << "pairwise coprime";
    else if (gcdd == 1)
        cout << "setwise coprime";
    else
        cout << "not coprime";
    return 0;
}

F I hate Shortest Path Problem

Description

题目链接

Solution

设 a[i][j]a[i][j] 表示到第 ii 行第 jj 列需要往右移动的最少次数，由题意可知，a[1]=0a[1]=0。之后的状态转移分以下两种情况：

  • a[i][j]=a[i−1][j],j∈[1,Ai−1−1]∪[Bi−1+1,w]a[i][j]=a[i-1][j],j∈[1,A_{i-1}-1]∪[B_{i-1}+1,w]
  • a[i][j]=a[i−1][Ai−1−1]+j−Ai−1+1,j∈[Ai−1,Bi−1]a[i][j]=a[i-1][A_{i-1}-1]+j-A_{i-1}+1,j∈[A_{i-1},B_{i-1}]

需要注意的是，若 Ai−1=1A_{i-1}=1，那么对 j∈[Ai−1,Bi−1]j∈[A_{i-1},B_{i-1}] 是无法抵达的，这时需要把距离设为 INFINF。

设 dp[i]dp[i] 表示到第 ii 行所需要的最少移动次数。由于一定会往下移动 i−1i-1 次，所以只需要考虑至少要往右移动的次数。故 dp[i]=i−1+min⁡1≤j≤wa[i][j]dp[i]=i-1+\min \limits_{1 \le j \le w}a[i][j]。

显然，aa 的第一维可以滚掉，而维护 aa 的最小值和等差区间可以用线段树实现。

Code

I hate Shortest Path Problem
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
#include <bits/stdc++.h>
#define lid id << 1
#define rid id << 1 | 1

using namespace std;
const int MAXN = 2e5 + 5;
const int INF = 1e9;

int h, w, a[MAXN], L[MAXN], R[MAXN], ans[MAXN];

template <class T>
void read(T &x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct Node {
    int l, r, mi, lval;
    bool tag;
    Node() { mi = lval = 0, tag = 0; }
    // mi denotes the minimum value in array [l,r]
    // lval denotes the value of the left end point of array [l,r]
} tr[MAXN * 4];

void update(int id) {
    tr[id].mi = min(tr[lid].mi, tr[rid].mi);
    tr[id].lval = tr[lid].lval;
}

void pushdown(int id) {
    if (tr[id].tag) {
        tr[lid].tag = 1;
        tr[lid].lval = tr[lid].mi = tr[id].lval;
        tr[rid].tag = 1;
        tr[rid].lval = tr[rid].mi = tr[id].lval + tr[rid].l - tr[lid].l;
        tr[id].tag = 0;
    }
}

void build(int id, int l, int r) {
    tr[id].l = l, tr[id].r = r;
    if (l == r) return;
    int mid = l + r >> 1;
    build(lid, l, mid);
    build(rid, mid + 1, r);
}

void modify(int id, int l, int r, int val) {
    if (tr[id].l == l && tr[id].r == r) {
        tr[id].mi = tr[id].lval = val;
        tr[id].tag = 1;
        return;
    }
    pushdown(id);
    int mid = tr[id].l + tr[id].r >> 1;
    if (r <= mid)
        modify(lid, l, r, val);
    else if (l > mid)
        modify(rid, l, r, val);
    else {
        modify(lid, l, mid, val);
        modify(rid, mid + 1, r, val + mid + 1 - l);
    }
    update(id);
}

int query(int id, int l, int r) {
    if (r < 1) return INF;
    if (tr[id].l == l && tr[id].r == r) {
        return tr[id].mi;
    }
    pushdown(id);
    int mid = tr[id].l + tr[id].r >> 1;
    if (r <= mid)
        return query(lid, l, r);
    else if (l > mid)
        return query(rid, l, r);
    else
        return min(query(lid, l, mid), query(rid, mid + 1, r));
}

int main() {
    read(h), read(w);
    for (int i = 1; i <= h; i++) read(L[i]), read(R[i]);
    fill(ans + 1, ans + h + 2, -1);
    build(1, 1, w);
    for (int i = 2; i <= h + 1; i++) {
        int tmp = query(1, L[i - 1] - 1, L[i - 1] - 1);
        modify(1, L[i - 1], R[i - 1], tmp + 1);
        int mi = query(1, 1, w);
        if (mi >= INF) break;
        ans[i] = mi + i - 1;
    }
    for (int i = 2; i <= h + 1; i++) printf("%d\n", ans[i]);
    return 0;
}