CF #575 Div3

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

// CF 2019.7.24

// 本想Div3手速场上分，结果卡在C题，掉了不少分。

// 自闭了这么久，今天补题，吸取教训。

A - Three Piles of Candies

题意：

比赛时候看了半天也没看明白，真是sb了。

Alice与Bob要把三堆糖果尽可能地平分，两人轮流拿，最后一个拿的要保证两人一样多。否则的话如果最后谁多了就要扔掉，直到两人拿的糖果数量相等。

给定三堆糖果初始数量，求他们能平分到的最多糖果数量。

题解：

三个数求和 / 2 就是答案。（奇数相当于向下取整了）

AC代码：

略。

B - Odd Sum Segments

题意：

有 n 个数字 a1，a2，…… an，要把他们分割成 k 段，每段和都为奇数。若能实现，输出YES和划分情况，否则输出NO。

题解：

显然 ai 为偶数对每段的和没有贡献，只要统计奇数个数不少于 k 且多余的奇数和为偶数就能完成划分。

从前往后扫一遍即可。（注意格式，我都服气WA了五次。。。心态炸裂）

AC代码：（补题时候头脑怎么如此清醒2min就写好1A？？？）

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

ll a[];

int main() {

    int q; cin>>q;

    while(q--) {

        int n, k;

        int cnt = ;   // 奇数个数

        scanf("%d %d", &n, &k);

        for(int i=;i<=n;i++) {

            scanf("%lld", &a[i]);

            if(a[i]%) ++cnt;

        }

        if(cnt<k || (cnt-k)%==) {

            printf("NO\n");

            continue;

        }

        printf("YES\n");

        for(int i=;i<=n && k>;i++) {

            if(a[i]%==) {

                printf("%d ", i);

                --k;

            }

        }

        printf("%d\n", n);  // 最后一段 n 结尾

    }

    return ;

}

C - Robot Breakout

题意：

平面上有 n 个机器人，机器人可以上下左右四个方向移动，但机器人出了问题，只具备其中某些方向移动的能力。给出 n 个机器人的坐标及可以移动的方向，求出 n 个机器人都可以抵达的一点(X, Y)。

题解：

分析一下可知，机器人能向上移动时，(x, y+n)都能抵达；机器人能向下移动时，(x, y-n)都能抵达；对 x 方向同理。

所以比赛时候我sb地把能到的区域求交（而忽略了不能到的区域）。

反过来想：

用不能走到的区域更新能到的区域。（默认能到达平面上全部点）

初始时，取down = left = -INF，up = right = INF，全部平面上的点(x, y) 满足 down <= x <= up，left <= y <= right，用四个边界来表示。

加入一个机器人，某个方向不能移动则与边界值求交（同小取小，同大取大）。

AC代码：

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

int main() {

    int q; cin>>q;

    while(q--) {

        int n;

        int x, y, left, right, up, down;

        int minX = -;

        int maxX = ;

        int minY = -;

        int maxY = ;  // 题目规定了平面大小，就不要设更大的值

        scanf("%d", &n);

        while(n--) {

            scanf("%d %d %d %d %d %d", &x, &y, &left, &up, &right, &down);

            if(!left)

                minX = max(minX, x);

            if(!right)

                maxX = min(maxX, x);

            if(!up)

                maxY = min(maxY, y);

            if(!down)

                minY = max(minY, y);

        }

        if(minX<=maxX && minY<=maxY)

            printf("1 %d %d\n", minX, minY);

        else

            printf("0\n");

    }

    return ;

}

D1 - RGB Substring (easy version)

题意：

将一个含有RGB字母的字符串改变最少的字符使其包含字符串“RGBRGB..."的长度为 k 的子串，求改动的字符数量最小值。

题解：

easy版本字符串的长度不超过3000，暴力就能解决。（枚举 s 串起点终点记录改变数量）

AC代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

char s[];

char p[] = "RGBRG";

int main() {

    int q; cin>>q;

    while(q--) {

        int n, k;

        scanf("%d %d", &n, &k);

        scanf("%s", s);

        int len = strlen(s);

        int ans = 0x3f3f3f3f;

        for(int i=;i+k<=len;i++) {

            for(int st=;st<;st++) {

                int now = ;

                for(int kk=;kk<k;kk++) {

                    if(s[i+kk]!=p[st+kk%]) ++now;

                }

                ans = min(ans, now);

            }

        }

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

    }

    return ;

}

D2 - RGB Substring (hard version)

题意：

同上一题，长度更新为 n<= 2e5。

题解：

简单dp。

记录每一位不同后，只需要滑动长度为 k 的串，改动数量由 dp[i+1]，dp[i-k]处的变化更新。

AC代码：（RE一次忘记开大内存了）

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

char s[];

char p[] = "RGBRG";

int dp[][];

int main() {

    int q; cin>>q;

    while(q--) {

        int n, k;

        scanf("%d %d", &n, &k);

        scanf("%s", s);

        int len = strlen(s);

        for(int st=;st<;st++) {

            for(int i=;i<len;i++) {

                dp[st][i] = (s[i]!=p[st+i%]);

            }

        }

        int ans = 0x3f3f3f3f;

        for(int st=;st<;st++) {

            int now = ;

            for(int i=;i<k;i++) {

                now += dp[st][i];

            }

            ans = min(ans, now);

            for(int i=k;i<len;i++) {

                now += dp[st][i];

                now -= dp[st][i-k];

                ans = min(ans, now);

            }

        }

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

    }

    return ;

}

// 补题不超过20分钟能A，比赛能保持这速度就好了 O.O

E - Connected Component on a Chessboard

题意：

文化差异方面的原因吗？看半天也看不懂题。

看了别人博客的题目说明，原来是要在国际象棋上选 b个黑色格子，w 个白色格子（满足全部格子连通的条件）。给出b + w 个格子的坐标。

题解：

一个白色格子有4个黑色相邻，两个白色格子有4+3个相邻，n 个白色格子有 3*n + 1 个黑色格子相邻。

所以只要 b <= 3*w + 1 或者 w <= 3*b + 1 就能构造出解。

AC代码：

#include<cstdio>

#include<iostream>

using namespace std;

// 原题 b == black w == white

// 潜意识里b当做白块了，读取交换了w，b的含义

int main() {

    int q; cin>>q;

    while(q--) {

        int add = ;

        int b, w;

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

        if(b>w) {

            swap(b, w);

            add = ;

        }

        if(w>*b+) {

            printf("NO\n");

            continue;

        }

        printf("YES\n");

        for(int i=;i<=b;i++) { // 白块

            printf("%d %d\n", +add, i*);

        }

        for(int i=;i<=b && w;i++) { // 黑块>=白块，放左右两边

            printf("%d %d\n", +add, i*+);

            --w;

        }

        for(int i=;i<=b && w;i++) { // 黑块放白块上面

            printf("%d %d\n", +add, i*);

            --w;

        }

        for(int i=;i<=b && w;i++) { // 黑块放白块下面

            printf("%d %d\n", +add, i*);

            --w;

        }

    }

    return ;

}

F - K-th Path

题意：

给出一个无向图，求图上所有路径中第 k 长的长度。

题解：

突破口是 k 的范围，k = min(n*(n+1)/2, 400)，k 不超过400。

可以想到，第 k 短路至少在边权第 k 大的边上，所有边权排在400以后的对图上两点最短路没有任何贡献。

只需要记录前 k 条边的节点，利用Floyd算法跑两点间的最短路即可。

AC代码：

#include<cstdio>

#include<iostream>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

ll dis[][];

int n, m, k;

struct Edge {

    int u, v;

    ll w;

    bool operator<(const Edge& a)const {

        return w<a.w;

    }

}edge[];

vector<int> node;

int main() {

    cin>>n>>m>>k;

    for(int i=;i<m;i++) {

        scanf("%d %d %lld", &edge[i].u, &edge[i].v, &edge[i].w);

    }

    sort(edge, edge+m);

    for(int i=;i<min(m, k);i++) {

        node.push_back(edge[i].u);

        node.push_back(edge[i].v);

    }

    // 离散化

    sort(node.begin(), node.end());

    node.resize(unique(node.begin(), node.end())-node.begin());

    memset(dis, 0x3f, sizeof(dis));

    for(int i=;i<min(m, k);i++) {

        int x = lower_bound(node.begin(), node.end(), edge[i].u)-node.begin();

        int y = lower_bound(node.begin(), node.end(), edge[i].v)-node.begin();

        dis[x][y] = dis[y][x] = min(dis[x][y], edge[i].w);

    }

    // Floyd

    for(int l=;l<node.size();l++) {

        for(int i=;i<node.size();i++) {

            for(int j=;j<node.size();j++) {

                dis[i][j] = min(dis[i][j], dis[i][l]+dis[l][j]);

            }

        }

    }

    // 注意 i,j 不能重复, j = i + 1

    vector<ll> ans;

    for(int i=;i<node.size();i++) {

        for(int j=i+;j<node.size();j++) {

            ans.push_back(dis[i][j]);

        }

    }

    sort(ans.begin(), ans.end());

    printf("%lld\n", ans[k-]);

    return ;

}

（End）

巴特西

CF #575 Div3

A - Three Piles of Candies

B - Odd Sum Segments

C - Robot Breakout

D1 - RGB Substring (easy version)

D2 - RGB Substring (hard version)

E - Connected Component on a Chessboard

F - K-th Path

最新文章

热门文章