@Dmaxiya
2018-08-17T10:27:23.000000Z
字数 5095
阅读 1042
Codeforces
Contests 链接:Codeforces Round #363 (Div. 2)
过题数:4
排名:158/11417
一个很大的原子对撞机,有 个原子同时发射,所有原子都被排列在一条直线上,它们的位置用一个 轴上的坐标 表示,每个原子所在的坐标都是一个偶数,每个原子都有一个初始的运动方向,它们的速度都是 ,问对撞机启动后,最早相互碰撞的原子的碰撞时间,如果所有原子都无法碰撞,则输出 。
根据给定的方向,如果相邻的两个原子运动方向相对,计算它们的撞击时间,对所有满足条件的原子计算时间取最小。
#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;
}
给定一个 的仓库,用一个字符串表示,"." 表示空地,"*" 表示墙,问能不能在仓库中的某个位置放置一个炸弹,使得这个炸弹能够炸掉所有的墙,炸弹可以放在空地上也可以放在墙上,且炸弹在炸毁一堵墙后不会停止,它会直接炸掉所有与其同一行与同一列的墙。
枚举放炸药的位置,然后 判断能否炸掉所有墙,总的时间复杂度是 。
#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;
}
想要在 天内提高自己的 技能和体能,他每天进行一项活动,或者休息,如果某天体育馆是开着的,他就可以休息或者进行体育运动,如果某天有比赛,他就可以休息或者参加比赛,他在连续的两天内不会做同样的活动(运动/写代码),问他在 天内,最少休息多少天。
定义状态 ,表示从第 天到第 天,在第 天进行某项活动的情况下,他能休息的最少天数, 表示休息, 表示写代码, 表示做运动。就有下面的递推式:
#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;
}
给定一个长度为 的序列,其中的每个数字 ,如果只有一个数字满足条件 ,则这个数列可以表示成一棵合法的树,表示的方法是:将满足 的数字作为根,其他的数字表示 与 之间有一条连边。现在给出任意一个序列,更改这个数列中的一些数字,使得这个序列成为可以表示成一棵合法的树的序列,问最少需要改动的数字的个数,并输出改动后的序列。
任意 个数字 ,将 与 进行连边的话,一定有 条边,相当于在 个节点的图上有 条边,而 个节点的树只有 条边,所以这个图在每个连通块内一定存在一个环,且最多只有一个环。题目给出的用树构造序列的方式,就是让整个图连通,且把这个环作为根的自环,因此除自环以外,所有点之间就只有 条连边。
这道题就是一个贪心,如果原序列中有某个数字满足 ,就把这个点作为根,如果没有任何数字满足 ,就任取一条环上的边,将这条边作为自环,自环对应的点为根,再将其他的连通块(如果有的话)环上的一条边指向这个根,使得整张图连通。判环用并查集。
#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;
}