[Codeforces Round #516 (Div. 2, by Moscow Team Olympiad) ](A~E)

A：

题目大意：给你$a,b,c$三条边，可以给任意的边加任意的长度，求最少共加多少长度使得可以构成三角形

题解：排个序，若可以组成，输出$0$，否则输出$c-a-b+1(设a\leqslant b\leqslant c)$

卡点：无

C++ Code：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

inline int min(int a, int b) {return a < b ? a : b;}

inline int max(int a, int b) {return a > b ? a : b;}

int n, m;

int a[5];

int main() {

	for (int i = 0; i < 3; i++) scanf("%d", a + i);

	std::sort(a, a + 3);

	if (a[0] + a[1] > a[2]) {

		puts("0");

	} else {

		printf("%d\n", a[2] - a[0] - a[1] + 1);

	}

	return 0;

}

B：

题目大意：给你一个数$a(0\leqslant a\leqslant2^{30}-1$，问有多少个数$x(0\leqslant x\leqslant2^{30}-1)$满足$a-(a\oplus x)-x=0$。多组询问

题解：发现满足若$a-(a\oplus x)-x=0$，则$a=(a\oplus x)+x$，即$((a\oplus x)|x)+((a\oplus x)\&x)=a$，若$a$的某一位为$0$，则$x$该位必须为$1$，若为$1$，$x$该位$1,0$均可。所以$ans=2^{\_\_builtin\_popcount(a)}$

卡点：无

C++ Code：

#include <cstdio>

#include <algorithm>

#include <cstring>

inline int min(int a, int b) {return a < b ? a : b;}

inline int max(int a, int b) {return a > b ? a : b;}

int n, m, Tim;

long long a, ans;

int main() {

	scanf("%d", &Tim);

	while (Tim --> 0) {

		scanf("%I64d", &a);

		ans = 1;

		for (long long i = 0; i < 31; i++) {

			if (a & (1ll << i)) {

				ans *= 2;

			}

		}

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

	}

	return 0;

}

C：

题目大意：给你一个字符串，要求你把它重排，使得重排后的字符串的回文字串最多

题解：把原字符串排序，发现这样每一段的回文字串个数是平方级别的，猜测这样最多，然后就过了

卡点：无

C++ Code：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

inline int min(int a, int b) {return a < b ? a : b;}

inline int max(int a, int b) {return a > b ? a : b;}

int n, m;

char s[100010];

int main() {

	scanf("%d", &n);

	scanf("%s", s + 1);

	std::sort(s + 1, s + n + 1);

	printf("%s\n", s + 1);

	return 0;

}

D：

题目大意：给你一个$n\times m$的矩阵，其中"*"表示墙，"."表示空地，你最多可以按$x$次左和$y$次右，上下没有限制，问最多可以到达几个点

题解：$bfs$，考虑对于到达一个点的不同状态，一定有一个$x,y$比其他的均优（因为要向左一定要向右），可以用优先队列保存（上下的优先级比较高）。

卡点：以为先到达的一定优，于是用普通队列，然后$FST$

C++ Code：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

const int z[2][4] = {{1, 0, -1, 0}, {0, 1, 0, -1}};

inline int min(int a, int b) {return a < b ? a : b;}

inline int max(int a, int b) {return a > b ? a : b;}

int n, m, r, c, a, b;

char s[2010][2010];

struct node {

	int x, y, a, b;

	inline bool operator < (const node &rhs) const {return a < rhs.a;}

	inline node(int __x = 0, int __y = 0, int __a = 0, int __b = 0) {x = __x, y = __y, a = __a, b = __b;}

};

std::priority_queue<node> q;

bool inq[2010][2010];

inline bool yj(int x, int y) {

	if (x < 1 || x > n || y < 1 || y > m) return true;

	if (s[x][y] != '.') return true;

	return false;

}

int ans;

void bfs(int __x, int __y) {

	q.push(node(__x, __y, a, b));

	while (!q.empty()) {

		node u = q.top(); q.pop();

		if (inq[u.x][u.y]) continue;

		ans++;

		inq[u.x][u.y] = true;

		for (int i = 0; i < 4; i++) {

			int x = u.x + z[0][i], y = u.y + z[1][i];

			if (yj(x, y)) continue;

			node tmp = node(x, y, u.a, u.b);

			if (i == 1) tmp.b--;

			if (i == 3) tmp.a--;

			if (tmp.a < 0 || tmp.b < 0) continue;

			q.push(tmp);

		}

	}

}

int main() {

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

	scanf("%d%d", &r, &c);

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

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

		scanf("%s", s[i] + 1);

	}

	bfs(r, c);

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

	return 0;

}

E：

题目大意：交互题。给定一个平面（横、纵坐标均在[0,10^9]之间）。有$n(n\leqslant 30)$个点，每个点都为黑色或白色。但你不知道点的颜色。

要你依次给出点的位置，你选择一个点的位置，交互库给你它的颜色。要求最后输出一条直线，将平面分成$2$部分，使得每部分的点的颜色相同（不能有点落在直线上）。

所有的点的坐标都是整数。

题解：二分答案，第一个点放在最左边，如果一个点和第一个点一样，下一个点就向右移，否则向左移。

卡点：被卡精度，直线经过一个点，$FST$

C++ Code：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

inline int min(int a, int b) {return a < b ? a : b;}

inline int max(int a, int b) {return a > b ? a : b;}

int n, m, l, r;

char s[10];

int get(char *s) {

	if (s[0] == 'b') return 1;

	return 0;

}

void put(int x, int y) {

	printf("%d %d\n", x, y);

	fflush(stdout);

	fflush(stdin);

}

int main() {

	scanf("%d", &n);

	l = 0, r = 1000000000;

	put(0, 0);

	scanf("%s", s);

	int op = get(s);

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

		int mid = (l + r + 1) >> 1;

		put(mid, mid);

		scanf("%s", s);

		if (op == get(s)) l = mid;

		else r = mid;

	}

	printf("%d %d %d %d\n", l, l + 1, l + 1, l);

	return 0;

}

巴特西

[Codeforces Round #516 (Div. 2, by Moscow Team Olympiad) ](A~E)

最新文章

热门文章