欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-09 22:56:09
...

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;
}