kakaの博客

你所热爱的，就是你的生活

0%

Codeforces Round 615 (Div. 3)

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 5.8k 阅读时长 ≈ 5 分钟

比赛链接：https://codeforces.com/contest/1294

A. Collecting Coins

先将所有数补成相等，然后看剩下的是否是3的倍数即可

1
2
3
4
5
6
7
8
9
void solve() {
    int a, b, c, n; cin >> a >> b >> c >> n;
    if (a < b) swap(a, b);
    if (a < c) swap(a, c);
    int ans = a - b + a - c;
    if (ans > n) cout << "NO" << endl;
    else if ((ans-n)%3==0) cout << "YES" << endl;
    else cout << "NO" << endl;
}

B. Collecting Packages

简单的模拟题，按x轴排序，再按y排序

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
struct node {
    int x, y;
    bool operator < (const node &rhs) const{
        if (x == rhs.x) return y < rhs.y;
        return x < rhs.x;
    }
}p[N];
void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    sort(p+1, p+n+1);
    int f = 0;
    for (int i = 2; i <= n; i++) {
        if (p[i].y < p[i-1].y) f = 1;
    }
    if (f) cout << "NO" << endl;
    else {
        cout << "YES" << endl;
        for (int i = 1; i <= n; i++) {
            int x = p[i].x - p[i-1].x;
            int y = p[i].y - p[i-1].y;
            for (int j = 1; j <= x; j++) cout << "R";
            for (int j = 1; j <= y; j++) cout << "U";
        }
        cout << endl;
    }
}

C. Product of Three Numbers

我的想法是先质因数分解，然后讨论质因子的个数，如果质因子的种类>=3，那么一定是可以的，如果是2，那么先各取一个，然后判断剩下的是否和其中两个相等，如果只有一个质因子，那么数量至少为6。

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() {
    map<int, int> mp;
    int n; cin >> n;
    int tmp = n;
    for (int i = 2; i * i <= tmp; i++) {
        if (tmp % i == 0) {
            while (tmp % i == 0) tmp /= i, mp[i]++;
        }
    }
    if (tmp != 1) mp[tmp]++;
    if (mp.size() >= 3) {
        cout << "YES" << endl;
        auto it = mp.begin();
        int a = (*it).first;
        int b = (*++it).first;
        cout << a << ' ' << b << ' ' << n / a / b << endl;
    } else if (mp.size() == 2) {
        auto it = mp.begin();
        int a = (*it).first;
        int b = (*++it).first;
        if (a != n / a / b && n / a / b != b && n / a / b > 2) {
            cout << "YES" << endl;
            cout << a << ' ' << b << ' ' << n / a / b << endl;
        } else {
            cout << "NO" << endl;
        }
    } else if (mp.size() == 1) {
        auto it = mp.begin();
        //cout << (*it).second << endl;
        if ((*it).second >= 6) {
            cout << "YES" << endl;
            cout << (*it).first << ' ' << (*it).first*(*it).first << ' ' << n/(*it).first/(*it).first/(*it).first << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

D. MEX maximizing

因为一个数可以+或-任意个x，因此这些数如果%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
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
struct node {
    int l, r;
    int mi, pos;
}t[N<<2];
void push_up(int u) {
    if (t[u<<1].mi <= t[u<<1|1].mi) {
        t[u].mi = t[u<<1].mi;
        t[u].pos = t[u<<1].pos;
    } else {
        t[u].mi = t[u<<1|1].mi;
        t[u].pos = t[u<<1|1].pos;
    }
}
void build(int u, int l, int r) {
    t[u].l = l, t[u].r = r;
    if (l == r) {
        t[u].pos = l;
        t[u].mi = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(u<<1, l, mid);
    build(u<<1|1, mid+1, r);
    push_up(u);
}
void modify(int u, int pos) {
    if (t[u].l == t[u].r) {
        t[u].mi++;
        return;
    }
    int mid = (t[u].l + t[u].r) >> 1;
    if (pos <= mid) modify(u<<1, pos);
    else modify(u<<1|1, pos);
    push_up(u);
}
pii query(int u, int ql, int qr) {
    if (ql <= t[u].l && qr >= t[u].r) return {t[u].mi, t[u].pos};
    int mid = (t[u].l + t[u].r) >> 1;
    pii ans = {inf, inf};
    if (ql <= mid) ans = min(ans, query(u<<1, ql, qr));
    if (qr > mid) ans = min(ans, query(u<<1|1, ql, qr));
    return ans;
}
void solve() {
    int q, x; cin >> q >> x;
    build(1, 0, x);
    for (int i = 1; i <= q; i++) {
        int val; cin >> val;
        val %= x;
        modify(1, val);
        pii ans = query(1, 0, x-1);
        cout << ans.first * x + ans.second << endl;
    }
}

E. Obtain a Permutation

很明显如果是变换，那么一定是同一列的在变，因此对于每一列来说都是独立考虑的，我们需要计算每一列重新排列的最小花费，其实就是计算在当前有多少个数不在顺序上再加上偏移量就是花费，最后对花费和n取一个min。

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
vector<int> a[N];
void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        a[i].push_back(0);
        for (int j = 1; j <= m; j++) {
            int x; cin >> x;
            a[i].push_back(x);
        }
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        vector<int> ve;
        for (int j = 1; j <= n; j++) ve.push_back(a[j][i]);
        map<int, int> mp, cnt;
        cnt[0] = 0;
        for (int j = 1; j <= n; j++) mp[i+(j-1)*m] = j;
        for (int j = 0; j < n; j++) {
            if (mp[ve[j]]) {
                cnt[(j+1-mp[ve[j]]+n)%n]++;
            }
        }
        int mi = 1e9;
        for (auto it : cnt) {
//            cout << i << ' ' << it.first << ' ' << it.second << endl;
            mi = min(mi, n - it.second + it.first);
        }
        ans += mi;
//        cout << mi << endl;
    }
    cout << ans << endl;
}

F. Three Paths on a Tree

首选从贪心的角度想，肯定有两个点是直径的两端，然后再选择一个点到直径上最长的距离，这里用多源的bfs就可以，记住三个点不可以相同，特判一下。

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
vector<int> g[N];
int dis1[N], p, pre[N], vis[N], dis3[N], pp, q, dis2[N];
 
void dfs1(int x, int fa) {
    for (auto v : g[x]) {
        if (v == fa) continue;
        dis1[v] = dis1[x] + 1;
        if (dis1[v] > dis1[p]) p = v;
        pre[v] = x;
        dfs1(v, x);
    }
}
void dfs2(int x, int fa) {
    for (auto v : g[x]) {
        if (v == fa) continue;
        dis2[v] = dis2[x] + 1;
        if (dis2[v] > dis2[pp]) pp = v;
        pre[v] = x;
        dfs2(v, x);
    }
}
void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(p, 0);
    vector<int> tmp;
    int now = pp;
    vis[now] = 1;
    while (now != p) {
        tmp.push_back(now);
        now = pre[now];
        vis[now] = 1;
    }
    tmp.push_back(now);
    queue<int> que;
    for (auto it : tmp) que.push(it);
    while (que.size()) {
        int x = que.front();
        que.pop();
        if (dis3[x] > dis3[q]) q = x;
        else if (dis3[x] == dis3[q] && x != pp && x != p) q = x;
        for (auto v : g[x]) {
            if (!vis[v]) {
                dis3[v] = dis3[x] + 1;
                que.push(v);
                vis[v] = 1;
            }
        }
    }
    cout << dis2[pp] + dis3[q] << endl;
    cout << pp << ' ' << p << ' ' << q << endl;
}
相关文章推荐