@Dmaxiya 2018-08-17T02:27:23.000000Z 字数 5095 阅读 1243

Codeforces Round #363 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #363 (Div. 2)
过题数：4
排名：158/11417

A. Launch of Collider

题意

一个很大的原子对撞机，有 $n$ 个原子同时发射，所有原子都被排列在一条直线上，它们的位置用一个 $x$ 轴上的坐标 $x_i$ 表示，每个原子所在的坐标都是一个偶数，每个原子都有一个初始的运动方向，它们的速度都是 $1m/\mu s$ ，问对撞机启动后，最早相互碰撞的原子的碰撞时间，如果所有原子都无法碰撞，则输出 $-1$ 。

数据范围

$1\leq n\leq2\times10^5\\0\leq x_i\leq10^9$

题解

根据给定的方向，如果相邻的两个原子运动方向相对，计算它们的撞击时间，对所有满足条件的原子计算时间取最小。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n, ans;
char str[maxn];
int num[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        ans = INT_MAX;
        scanf("%s", str);
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
        }
        for(int i = 0; i < n - 1; ++i) {
            if(str[i] == 'R' && str[i + 1] == 'L') {
                ans = min(ans, (num[i + 1] - num[i]) / 2);
            }
        }
        if(ans == INT_MAX) {
            printf("-1\n");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}

B. One Bomb

题意

给定一个 $n\times m$ 的仓库，用一个字符串表示，"." 表示空地，"*" 表示墙，问能不能在仓库中的某个位置放置一个炸弹，使得这个炸弹能够炸掉所有的墙，炸弹可以放在空地上也可以放在墙上，且炸弹在炸毁一堵墙后不会停止，它会直接炸掉所有与其同一行与同一列的墙。

数据范围

$1\leq n,m\leq1000$

题解

$O(nm)$ 枚举放炸药的位置，然后 $O(n+m)$ 判断能否炸掉所有墙，总的时间复杂度是 $O(n^3)$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
struct Node {
    int x, y;
};
int n, m, ansx, ansy;
bool f;
char str[maxn][maxn];
Node node[maxn * maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        int cnt = 0;
        f = false;
        for(int i = 0; i < n; ++i) {
            scanf("%s", str[i]);
            for(int j = 0; j < m; ++j) {
                if(str[i][j] == '*') {
                    node[cnt].x = i;
                    node[cnt].y = j;
                    ++cnt;
                }
            }
        }
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                bool flag = true;
                for(int k = 0; k < cnt; ++k) {
                    if(node[k].x != i && node[k].y != j) {
                        flag = false;
                        break;
                    }
                }
                if(flag) {
                    f = true;
                    ansx = i;
                    ansy = j;
                    break;
                }
            }
            if(f) {
                break;
            }
        }
        if(f) {
            printf("YES\n%d %d\n", ansx + 1, ansy + 1);
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

C. Vacations

题意

$Vasya$ 想要在 $n$ 天内提高自己的 $IT$ 技能和体能，他每天进行一项活动，或者休息，如果某天体育馆是开着的，他就可以休息或者进行体育运动，如果某天有比赛，他就可以休息或者参加比赛，他在连续的两天内不会做同样的活动（运动/写代码），问他在 $n$ 天内，最少休息多少天。

数据范围

$1\leq n\leq100$

题解

定义状态 $dp(i,j)$ ，表示从第 $1$ 天到第 $i$ 天，在第 $i$ 天进行某项活动的情况下，他能休息的最少天数， $j=0$ 表示休息， $j=1$ 表示写代码， $j=2$ 表示做运动。就有下面的递推式：

$dp(i,0)=\min(dp(i-1,0),dp(i-1,1),dp(i-1,2))+1\\ dp(i,1)=\begin{cases} \min(dp(i-1,0),dp(i-1,2))&(a_i\&1=1)\\ \infty&(a_i\&1\neq1) \end{cases}\\ dp(i,2)=\begin{cases} \min(dp(i-1,0),dp(i-1,1))&(a_i\&2=2)\\ \infty&(a_i\&2\neq2) \end{cases}$

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long
const int INF = INT_MAX;
const int maxn = 100 + 100;
int n, x;
int dp[maxn][3];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &x);
            dp[i][0] = min(dp[i - 1][0], min(dp[i - 1][1], dp[i - 1][2])) + 1;
            if((x & 1) == 1) {
                dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]);
            } else {
                dp[i][1] = INF;
            }
            if((x & 2) == 2) {
                dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]);
            } else {
                dp[i][2] = INF;
            }
        }
        printf("%d\n", min(dp[n][0], min(dp[n][1], dp[n][2])));
    }
    return 0;
}

D. Fix a Tree

题意

给定一个长度为 $n$ 的序列，其中的每个数字 $1\leq a_i\leq n$ ，如果只有一个数字满足条件 $a_i=i$ ，则这个数列可以表示成一棵合法的树，表示的方法是：将满足 $a_i=i$ 的数字作为根，其他的数字表示 $a_j$ 与 $j$ 之间有一条连边。现在给出任意一个序列，更改这个数列中的一些数字，使得这个序列成为可以表示成一棵合法的树的序列，问最少需要改动的数字的个数，并输出改动后的序列。

数据范围

$2\leq n\leq2\times10^5\\1\leq a_i\leq n$

题解

任意 $n$ 个数字 $a_i$ ，将 $a_i$ 与 $i$ 进行连边的话，一定有 $x$ 条边，相当于在 $x$ 个节点的图上有 $x$ 条边，而 $x$ 个节点的树只有 $x-1$ 条边，所以这个图在每个连通块内一定存在一个环，且最多只有一个环。题目给出的用树构造序列的方式，就是让整个图连通，且把这个环作为根的自环，因此除自环以外，所有点之间就只有 $n-1$ 条连边。
这道题就是一个贪心，如果原序列中有某个数字满足 $a_i=i$ ，就把这个点作为根，如果没有任何数字满足 $a_i=i$ ，就任取一条环上的边，将这条边作为自环，自环对应的点为根，再将其他的连通块（如果有的话）环上的一条边指向这个根，使得整张图连通。判环用并查集。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long
const int maxn = 200000 + 100;
int n, root, cnt;
int fa[maxn], num[maxn];
void Init() {
    for(int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
}
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);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        root = cnt = 0;
        Init();
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
            if(num[i] == i) {
                root = i;
            }
            if(root == 0 && Find(num[i]) == Find(i)) {
                root = i;
            }
            unit(num[i], i);
        }
        Init();
        for(int i = 1; i <= n; ++i) {
            if(Find(num[i]) == Find(i)) {
                if(num[i] != root) {
                    ++cnt;
                    num[i] = root;
                }
            }
            unit(i, num[i]);
        }
        printf("%d\n", cnt);
        for(int i = 1; i <= n; ++i) {
            if(i != 1) {
                printf(" ");
            }
            printf("%d", num[i]);
        }
        printf("\n");
    }
    return 0;
}

Codeforces Round #363 (Div. 2)

A. Launch of Collider

题意

数据范围

题解

过题代码

B. One Bomb

题意

数据范围

题解

过题代码

C. Vacations

题意

数据范围

题解

过题代码

D. Fix a Tree

题意

数据范围

题解

过题代码

内容目录