@Dmaxiya 2018-08-17T10:18:52.000000Z 字数 5331 阅读 1060

Educational Codeforces Round 37

Codeforces

Contests 链接：Educational Codeforces Round 37
过题数：3
排名：763/9623

A. Water The Garden

题意

有 $n$ 个花圃排成一排，从 $1$ 到 $n$ 编号，有 $k$ 个喷头放在这 $n$ 个花圃中的 $x_i$ 处，这个喷头开启后第 $1$ 秒会将 $x_i$ 处的花圃淋湿，第 $j$ 秒会将区间 $[x_i-(j-1),x_i+(j-1)]$ 内的所有花圃淋湿，且只有整数秒时才会淋湿一个花圃，问所有喷头同时开启，最少多少秒可以将所有花圃淋湿。

输入

第一行为一个整数 $T~(1\leq T\leq200)$ ，接下来有 $T$ 组数据，每组数据的第一行为两个整数 $n,k~(1\leq n\leq200,1\leq k\leq n)$ ，第二行有 $k$ 个整数 $x_1,x_2,\cdots,x_k~(1\leq x_i\leq n)$ ，表示第 $i$ 个喷头的位置为 $x_i$ 。

输出

输出最少让所有花圃淋湿的时间。

样例

输入	输出	提示
3 5 1 3 3 3 1 2 3 4 1 1	3 1 4	1.在第一组数据中，第 $1$ 秒的时候第 $3$ 个花圃会被淋湿，第 $2$ 秒的时候区间 $[2,4]$ 内的花圃会被淋湿，第 $3$ 秒的时候所有的花圃都会被淋湿； 2.在第二组数据中，每一个花圃上都有一个喷头，因此在第 $1$ 秒的时候所有的花圃就都会被淋湿； 3.在第三组数据中，只有第 $1$ 个花圃有喷头，所以需要 $4$ 秒时间将所有花圃淋湿。

题解

计算所有相邻喷头中间位置的花圃被淋到的时间，以及边缘的花圃会被淋到的时间，取最大值。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 200 + 100;
int T, n, k, ans;
int num[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        ans = 0;
        for(int i = 1; i <= k; ++i) {
            scanf("%d", &num[i]);
        }
        for(int i = 2; i <= k; ++i) {
            ans = max(ans, (num[i] - num[i - 1]) / 2 + 1);
        }
        ans = max(ans, num[1]);
        ans = max(ans, n - num[k] + 1);
        printf("%d\n", ans);
    }
    return 0;
}

B. Tea Queue

题意

有 $n$ 个学生，第 $i$ 个学生将会在第 $l_i$ 秒来等待接茶水，每个人接茶水消耗的时间为 $1s$ ，如果两个学生同时到达，则编号小的同学排在队伍的前面，如果某个同学到达时前面有同学在等待，他也会排队等待，如果超过 $r_i$ 秒仍然没有轮到他接茶水，他就会马上离开，求每个同学接到茶水的时间。

输入

第一行为一个整数 $T~(1\leq T\leq1000)$ ，接下去有 $T$ 组数据，每组数据第一行为一个整数 $n~(1\leq n\leq1000)$ ，接下去有 $n$ 行，每一行有两个整数 $l_i,r_i~(1\leq l_i\leq r_i\leq5000)$ ，对于所有的 $i\in[2,n]$ ，都有 $l_{i-1}\leq l_i$ 。且所有数据的 $n$ 的和不超过 $1000$ 。

输出

每一组数据输出一行 $n$ 个整数，第 $i$ 个整数代表第 $i$ 个学生接到茶水的时间，如果某个学生没有接到茶水直接离开，则输出 $0$ 。

样例

输入	输出	提示
2 2 1 3 1 4 3 1 5 1 1 2 3	1 2 1 0 2	1.对于第 $1$ 组数据， $2$ 个学生同时到达，第 $1$ 个学生在第 $1$ 秒接到茶水，第 $2$ 个学生在第 $2$ 秒接到茶水。 2.对于第 $2$ 组数据，第 $1$ 个和第 $2$ 个学生同时到达，第 $1$ 个学生在第 $1$ 秒接到茶水，第 $1$ 秒结束第二个学生没有接到茶水就离开了，第 $2$ 秒时第 $3$ 个学生到达，并接到茶水。

题解

按照题意模拟。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
int T, n, l, r;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        int now = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &l, &r);
            now = max(now, l);
            if(i != 0) {
                printf(" ");
            }
            if(now > r) {
                printf("0");
            } else {
                printf("%d", now);
                ++now;
            }
        }
        printf("\n");
    }
    return 0;
}

C. Swap Adjacent Elements

题意

给定一个长度为 $n$ 的序列，在这个序列中的某些位置 $i$ 可以和第 $i+1$ 个位置的数字进行交换，问能否通过任意次合法的交换，使得这个数列成为一个递增数列。

输入

第一行为一个整数 $n~(2\leq n\leq2\times10^5)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq2\times10^5)$ ，第三行为一个字符串 $s~(|s|=n-1)$ ，字符串的第 $i$ 位为 $1$ 表示序列中的第 $i$ 个数字可以和第 $i+1$ 个数字交换位置。

输出

如果可以在给定的条件下，通过任意次交换得到一个递增的数列，则输出 $YES$ ，否则输出 $NO$ 。

样例

输入	输出	提示
6 1 2 5 3 4 6 01110	YES	可以通过交换 $a_3,a_4$ 和 $a_4,a_5$ ，使数列成为一个递增的数列。
6 1 2 5 3 4 6 01010	NO

题解

能否通过交换使数列有序，即询问所有数字能否通过交换从排序前的下标移动到排序后的下标，即排序前后所有数字的下标都必须由 $1$ 连通，就可以用并查集来判了。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n;
int num[maxn], Index1[maxn], Index2[maxn];
int fa[maxn];
char str[maxn];
int Find(int x) {
    return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    fa[xx] = yy;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
            fa[i] = i;
            Index1[num[i]] = i;
        }
        sort(num + 1, num + 1 + n);
        for(int i = 1; i <= n; ++i) {
            Index2[num[i]] = i;
        }
        scanf("%s", str + 1);
        for(int i = 1; i < n; ++i) {
            if(str[i] == '1') {
                unit(i, i + 1);
            }
        }
        bool flag = true;
        for(int i = 1; i <= n; ++i) {
            if(Find(Index1[num[i]]) != Find(Index2[num[i]])) {
                flag = false;
                break;
            }
        }
        if(flag) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

D. Connected Components?

题意

一个 $n$ 个节点的无向图的补图上有 $m$ 条边，输出原图上所有连通块中节点的数量。

输入

第一行为两个整数 $n,m~(1\leq n\leq2\times10^5,0\leq m\leq\min(\frac{n(n-1)}{2},2\times10^5))$ ，接下去 $m$ 行每行两个整数 $x,y~(1\leq x,y\leq n,x\neq y)$ ，表示原图上 $x$ 与 $y$ 之间没有连边。

输出

第一行输出一个整数 $k$ ，表示连通块的个数，第二行按照非递减的顺序输出每个连通块内的节点数量。

样例

输入	输出
5 5 1 2 3 4 3 2 4 2 2 5	2 1 4

题解

用一个 $set$ 来存所有没有被访问过的节点，每访问一个节点就从 $set$ 中删去，直到所有节点都被访问（ $set$ 为空），就可以得到所有连通块的信息，用 $bfs$ 判连通块。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n, m, u, v, cnt;
set<int> st;
set<int> G[maxn];
int ans[maxn];
queue<int> que;
set<int>::iterator it;
vector<set<int>::iterator> vct;
int bfs(int x) {
    int ret = 1;
    while(!que.empty()) {
        que.pop();
    }
    que.push(x);
    st.erase(x);
    while(!que.empty()) {
        if(st.empty()) {
            return ret;
        }
        vct.clear();
        int tmp = que.front();
        que.pop();
        for(it = st.begin(); it != st.end(); ++it) {
            if(G[tmp].find(*it) == G[tmp].end()) {
                que.push(*it);
                vct.push_back(it);
                ++ret;
            }
        }
        int len = vct.size();
        for(int i = 0; i < len; ++i) {
            st.erase(vct[i]);
        }
    }
    return ret;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        cnt = 0;
        st.clear();
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
            st.insert(i);
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d%d", &u, &v);
            G[u].insert(v);
            G[v].insert(u);
        }
        while(!st.empty()) {
            ans[cnt++] = bfs(*(st.begin()));
        }
        sort(ans, ans + cnt);
        printf("%d\n", cnt);
        for(int i = 0; i < cnt; ++i) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

Educational Codeforces Round 37

A. Water The Garden

题意

输入

输出

样例

题解

过题代码

B. Tea Queue

题意

输入

输出

样例

题解

过题代码

C. Swap Adjacent Elements

题意

输入

输出

样例

题解

过题代码

D. Connected Components?

题意

输入

输出

样例

题解

过题代码

内容目录