鹏鹏的算法博客

学习...学习..学习.



Codeforces Round #575 Div.3 解题报告

题目地址:https://codeforces.com/contest/1196
题解地址:https://codeforces.com/blog/entry/68655


A. Three Piles of Candies

有3堆糖果,第一个人先选一堆,第二个人再选一堆,剩下的一堆任意分配,之后如果两个人糖果不一样多,把多的人的多出来的糖果舍弃。问最后每个人最多有多少糖果。
一开始的做法是把最小的两堆先分掉,然后用最大的那堆来补齐两堆的差距,再平均分配到两堆。

#include <bits/stdc++.h>
using namespace std;

int main() {

    int T;
    scanf("%d", &T);
    
    while (T--) {
        
        long long c[3], a = 0, b = 0;
        for (int i = 0; i < 3; ++i) {
            scanf("%I64d", &c[i]);
        }

        sort(c, c + 3);

        a = c[0];
        b = c[1];

        if (c[2] >= b - a) {
            c[2] -= b - a;
            a = b;
        }
        else {
            a += c[2];
            c[2] = 0;
        }

        a += c[2] / 2;
        b += c[2] - c[2] / 2;

        printf("%I64d\n", min(a, b));


    }

    return 0;

}

这里,中间的if实际上是多余的,因为如果b和a的差值大于c的话,那么b就会比c大,显然是矛盾的。所以也就相当于两个人都分了一样的数量,然后剩下的第三堆平均分配。所以答案就是 \( \lfloor \frac{a+b+c}{2} \rfloor \) 。

#include <bits/stdc++.h>
using namespace std;

int main() {

    int T;
    long long a, b, c;

    scanf("%d", &T);
    
    while (T--) {
        
        scanf("%I64d%I64d%I64d", &a, &b, &c);

        printf("%I64d\n", (a + b + c) / 2);

    }

    return 0;

}

B. Odd Sum Segments

给n个数的序列,分成k个和为奇数的子串,如果可以则输出每个子串的右端点下标,如果不可以则输出NO。
一开始的做法是从左到右扫描这个序列,用一个t记录当前子串的奇偶,每读到一个数,t就加上这个数对2的余数。如果t变奇数了,就说明找到了一个奇数和子串,记录当前的位置。如果能找到大于等于k个子串并且总数的奇偶性和k相同,就说明合法,输出前k-1个以及最后一个n,就可以了。

#include <bits/stdc++.h>
using namespace std;

int T, n, m, a, cnt, t, p[200000 + 10];

int main() {

    scanf("%d", &T);
    
    while (T--) {
        cnt = t = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a);
            t += a % 2;
            if (t % 2) {
                cnt++;
                t = 0;
                p[cnt] = i;
            }
        }
        if (cnt % 2 == m % 2 && cnt >= m) {
            printf("YES\n");
            for (int i = 1; i < m; ++i) {
                printf("%d ", p[i]);
            }
            printf("%d\n", n);
        }
        else printf("NO\n");
    }

    return 0;

}

然而实际上,t在每次读到一个奇数的时候都会变成奇数,然后清零,也就是说每次读到一个奇数就会被记录,所以奇数的个数就是最大的奇数和子串的个数,只需要找奇数的位置输出就可以了。

#include <bits/stdc++.h>
using namespace std;

int T, n, m, a[200010], cnt;

int main() {

    scanf("%d", &T);
    
    while (T--) {
        cnt = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            cnt += a[i] % 2;
        }
        if (cnt < m || cnt % 2 != m % 2) { printf("NO\n"); continue; }
        printf("YES\n");
        for (int i = 1, j = 0; i <= n && j < m - 1; ++i) {
            if (a[i] % 2) {
                printf("%d ", i);
                j++;
            }
        }
        printf("%d\n", n);
    }

    return 0;

}

C. Robot Breakout

有n个机器人,第i个机器人初始位置为xi和yi,每个机器人只能四方向中的几个方向运动,问有没有一个位置能让所有机器人都运动到?
每个机器人只能限制某一些方向运动,所以某一个机器人的能运动到的位置的横纵左边分别是一个区间或者一个点。我们就把所有机器人的横纵坐标分别取交集,如果交集为空就说明找不到,不为空则输出交集中的任一位置。
有一个优化是,优先考虑方向少的机器人,因为方向少,说明限制多,可以更早地发现无解的情况。
用Range结构体类型的x和y来分别表示横纵坐标的区间,每次添加一个机器人,对横纵坐标取交集。这里细节比较多,需要特别小心。

#include <bits/stdc++.h>
using namespace std;

const int N = 100000 + 10;

struct Robot {
    int x, y, f[4], t;
    void read() {
        t = 0;
        scanf("%d%d", &x, &y);
        for (int i = 0; i < 4; ++i) {
            scanf("%d", &f[i]);
            t += f[i];
        }
    }
    bool operator < (const Robot &b) const {
        return t < b.t;
    }
} robot[N];

struct Range {
    int l, r;
    void init() {
        l = -N;
        r = N;
    }
    bool add(const int grtr, const int num) {
        if (grtr == 0) {
            if (num >= l && num <= r) {
                l = r = num;
                return true;
            }
            else {
                return false;
            }
        }
        else if (grtr == 1) {
            if (num <= r) {
                l = max(l, num);
                return true;
            }
            else {
                return false;
            }
        }
        else {
            if (num >= l) {
                r = min(r, num);
                return true;
            }
            else {
                return false;
            }
        }
    }
} x, y;

bool add_robot(const Robot &r) {
    if (r.t == 0) return x.add(0, r.x) && y.add(0, r.y);
    if (r.f[0] + r.f[2] == 0) {
        if (!x.add(0, r.x)) return false;
    }
    else if (r.f[0] != r.f[2]) {
        if (r.f[0]) {
            if (!x.add(-1, r.x)) return false;
        }
        else {
            if (!x.add(1, r.x)) return false;
        }
    }
    if (r.f[1] + r.f[3] == 0) {
        if (!y.add(0, r.y)) return false;
    }
    else if (r.f[1] != r.f[3]) {
        if (r.f[1]) {
            if (!y.add(1, r.y)) return false;
        }
        else {
            if (!y.add(-1, r.y)) return false;
        }
    }
    return true;
}

int n;

int main() {

    int T;
    scanf("%d", &T);

    while (T--) {

        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            robot[i].read();
        }

        sort(robot + 1, robot + n + 1);

        x.init();
        y.init();

        bool flag = 1;
        for (int i = 1; i <= n; ++i){
            if (add_robot(robot[i]) == false) {
                flag = 0;
                break;
            }
        }

        if (flag) printf("1 %d %d\n", max(x.l, -100000), max(y.l, -100000));
        else printf("0\n");
            
    }

    return 0;

}

这里实际上可以不必要自己去取交集,只需要计算区间的左右端点,如果最后左端点在右端点右边就说明无解。

#include <bits/stdc++.h>
using namespace std;

const int INF = 100000;

int main() {

    int T, n;
    scanf("%d", &T);

    while (T--) {

        scanf("%d", &n);

        int minx = -INF, miny = -INF, maxx = INF, maxy = INF;
        int x, y, f1, f2, f3, f4;

        while (n--) {
            scanf("%d%d%d%d%d%d", &x, &y, &f1, &f2, &f3, &f4);
            if (!f1) minx = max(minx, x);
            if (!f2) maxy = min(maxy, y);
            if (!f3) maxx = min(maxx, x);
            if (!f4) miny = max(miny, y);
        }

        if (minx > maxx || miny > maxy) printf("0\n");
        else printf("1 %d %d\n", minx, miny);
        
    }

    return 0;

}

D1. RGB Substring (easy version)

给整数n和k,和一个长度为n的只由"R""G""B"组成的字符串,问最少需要修改几个字符,才能使这个字符串和字符串“RGBRGBRGBRGB...”有长度为k的公共子串。
先简化字符串,把RGB分别设为012。在原串中枚举起点为i,长度为k的子串,比较这个子串和“012012012...”中的子串的不同字符个数。因为“012012012...”是循环的,分别可能是012为开头,也就是“012012...”“120120...”“201201...”,这些其实没有本质区别,每个字符串的字符就相当于是相差1再模3。因此在枚举原串的子串的时候,分别比较3种情况,每次都是加一模三就能得到另一种字符串,然后取3种情况的最小值。

#include <bits/stdc++.h>
using namespace std;

const int N = 2010;

int n, k, a[N];
char s[N];

int main() {

    int T;
    scanf("%d", &T);

    while (T--) {

        scanf("%d%d%s", &n, &k, s);
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'R') a[i + 1] = 0;
            else if (s[i] == 'G') a[i + 1] = 1;
            else a[i + 1] = 2;
        }

        int ans = k;
        for (int i = 1; i + k - 1 <= n; ++i) {
            int m[3] = {0, 0, 0};
            for (int j = 0; j < k; ++j) {
                for (int q = 0; q < 3; ++q) {
                    if (a[i + j] != (j + q) % 3) {
                        m[q]++;
                    }
                }
            }
            for (int q = 0; q < 3; ++q) {
                ans = min(ans, m[q]);
            }
        }

        printf("%d\n", ans);

    }

    return 0;

}

D2. RGB Substring (hard version)

这一题和上一题题面一样,唯一区别在于数据范围更大,之前的 \( O(nk) \) 算法不能胜任。
这里可以先把原串和“012012012..”按位相减,这样的结果中,不为0的位置的个数就是和目标串的差距,然后用一个长度为k的窗口,在结果中滑动,求出这个窗口中不为0的位置个数,取最小值。时间复杂度为 \( O(n) \) 。
然后在结果中每个加一模三,再用窗口求一次。这里就相当于原串和“120120..”相减。
然后再在结果中每个加一模三,再用窗口求一次。这里就相当于原串和“201201..”相减。
这样就能求出来最小的答案了。

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 10;

int n, k, a[N];
char s[N];

int get_min_cnt() {
    int cnt = 0, min_cnt = k;
    for (int i = 0; i < k; ++i) {
        if (a[i] != 0) cnt++;
    }
    min_cnt = cnt;
    for (int i = k; i < n; ++i) {
        if (a[i - k] != 0) cnt--;
        if (a[i] != 0) cnt++;
        min_cnt = min(min_cnt, cnt);
    }
    for (int i = 0; i < n; ++i) {
        a[i] = (a[i] + 1) % 3;
    }
    return min_cnt;
}

int main() {

    int T;
    scanf("%d", &T);

    while (T--) {

        scanf("%d%d%s", &n, &k, s);
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'R') a[i] = 0;
            else if (s[i] == 'G') a[i] = 1;
            else a[i] = 2;
            a[i] = (a[i] - i % 3 + 3) % 3;
        }

        int ans = k;
        for (int i = 0; i < 3; ++i) {
            ans = min(ans, get_min_cnt());
        }

        printf("%d\n", ans);

    }

    return 0;

}

E. Connected Component on a Chessboard

一个可以看作无穷大的国际象棋棋盘,左上角的位置为白色,问能否找到一个联通的块,由b个黑块w个白块组成,能则输出任一方案。
一开始是考虑用广度优先的方法去搜索,某一种方块不够就拓展另一种颜色的方块。这样做会WA,想了想也确实,因为这样做的话,有可能找到的联通块就是一个类似圆形的图案,因为是一圈一圈拓展的,所以就可能在黑白个数差距大的时候,圆形无法满足要求而输出无解。
换一种思维。因为方案是随意的,所以我们可以先取一条直线。比如当白块比黑块多时,可以从(2, 2)开始向右一直走,这样走直到黑块达到数量,这样的话只需要再处理白块,而取到的黑块上下都还是白块,可以取来,这样就可以把白块取满。如何判断无解呢,因为这样的取法,可以说是“表面积”最大的,所以这样的方案肯定是最优的,那么当白块的数量不超过多少的时候可以有解呢?白块为w,黑块为b,向右一横用掉了b块黑b块白,剩下w-b块白要取,而b块黑的上下还能提供2个白,还有横的后面还有一个白,总共还能提供2b+1块白,所以如果 \( w-b \le 2b+1 \) 也就是 \( w \le 3b+1 \) 就有解了。
如果黑块比白块多的话,就交换一下两个的数量,一样的做法,只需要在输出的时候行数或者列数加1就可以了,相当于把起点取为黑色了。

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 10;

int b, w, cntb, cntw;
struct Node {
    int x, y;
} ansb[N], answ[N];
bool flag;

void print_ans() {
    printf("YES\n");
    for (int i = 1; i <= w; ++i) {
        printf("%d %d\n", answ[i].x + flag, answ[i].y);
    }
    for (int i = 1; i <= b; ++i) {
        printf("%d %d\n", ansb[i].x + flag, ansb[i].y);
    }
}

int main() {

    int T;
    scanf("%d", &T);

    while (T--) {

        scanf("%d%d", &b, &w);

        flag = false;
        if (b > w) {
            swap(b, w);
            flag = true;
        }

        if (w > 3 * b + 1) { printf("NO\n"); continue; }

        cntb = cntw = 0;

        for (int i = 1; i <= b; ++i) {
            answ[++cntw] = Node{2, 2 + (i - 1) * 2};
            ansb[++cntb] = Node{2, 3 + (i - 1) * 2};
        }

        if (w == b) { print_ans(); continue; }

        for (int i = 1; i <= b && cntw < w; ++i) {
            answ[++cntw] = Node{1, 3 + (i - 1) * 2};
            answ[++cntw] = Node{3, 3 + (i - 1) * 2};
        }

        if (cntw < w) answ[++cntw] = Node{2, 2 + b * 2};

        print_ans();

    }

    return 0;

}

F. K-th Path

n个点m条边的联通加权无向图,在任意两点的最短距离集合中,找出第k大的。
这里n和m都是200000,所以给每个点跑一遍最短路是不现实的,而直接跑floyd更是不行。题目的突破口在k,最大为400,这也就限定了,我们只需要考虑不超过k条边,而要考虑的这k条边的权值是图中最小的k个。为什么?因为边数大于k的话,那么图中的最短距离的集合就绝对大于k了,因为每条边都能提供至少一个最短距离。所以让边数等于k就可以了,也就是取权值最小的k条。
取完k条后,在新图中跑一遍floyd就可以了,然后取出所有距离求第k个就可以了。

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 10, M = 800 + 10;
const long long INF = (long long)1 << 60;

int n, m, k, id[N], cnt, dis_cnt;
long long g[M][M], dis[M * M];

struct Edge {
    int u, v, w;
    bool operator < (const Edge &x) const {
        return w < x.w;
    }
} edge[N];

int main() {

    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < M; ++j) {
            if (i != j) g[i][j] = g[j][i] = INF;
        }
    }

    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    }

    sort(edge + 1, edge + m + 1);

    for (int i = 1; i <= k && i <= m; ++i) {
        if (!id[edge[i].u]) id[edge[i].u] = ++cnt;
        if (!id[edge[i].v]) id[edge[i].v] = ++cnt;
        g[id[edge[i].u]][id[edge[i].v]] = g[id[edge[i].v]][id[edge[i].u]] = edge[i].w;
    }

    for (int k = 1; k <= cnt; ++k) {
        for (int i = 1; i <= cnt; ++i) {
            for (int j = 1; j <= cnt; ++j) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }

    for (int i = 1; i <= cnt; ++i) {
        for (int j = i + 1; j <= cnt; ++j) {
            if (g[i][j] != INF) dis[++dis_cnt] = g[i][j];
        }
    }

    sort(dis + 1, dis + dis_cnt + 1);

    printf("%I64d", dis[k]);

    return 0;

}