2021牛客暑期多校训练营2

比赛
字数统计: 2.7k   |   阅读时长≈ 14 分钟

C-Draw Grids

题目大意

给你一个$n\times m$的点阵，两个人轮流进行，可以横着连或者竖着连相邻两点，不能构成回路，问先手赢还是后手赢。

解题思路

因为不能构成回路，所以连接的图展开就是一棵树。

很明显的按照边数来确定谁赢，如果边数为奇则先手赢。

完整代码

1
2
3
4
5
int main(){
    int n,m; cin>>n>>m;
    if(((n*m - 1)&1)==0)    cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}

D-Er Ba Game

题目大意

每个人摸两张牌，告诉你比较规则，比两个人的牌谁大。

解题思路

模拟。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int a1, b1, a2, b2;
		cin >> a1 >> b1 >> a2 >> b2;
		if (a1 > b1)	swap(a1, b1);
		if (a2 > b2)	swap(a2, b2);
		if (a1 == a2 && b1 == b2)	cout << "tie" << endl;
		else if (a1 == 2 && b1 == 8)	cout << "first" << endl;
		else if (a2 == 2 && b2 == 8)	cout << "second" << endl;
		else if (a1 == b1 && a2 == b2) {
			if (a1 > a2)	cout << "first" << endl;
			else cout << "second" << endl;
		}
		else if (a1 == b1)	cout << "first" << endl;
		else if (a2 == b2)	cout << "second" << endl;
		else if ((a1 + b1) % 10 == (a2 + b2) % 10) {
			if (b1 > b2)	cout << "first" << endl;
			else cout << "second" << endl;
		}
		else {
			if ((a1 + b1) % 10 > (a2 + b2) % 10)	cout << "first" << endl;
			else cout << "second" << endl;
		}
	}
	return 0;
}

F-Girlfriend

题目大意

给你四个点$a,b,c,d$，设两个点$p_1,p_2$以及两个参数$k_1,k_2$，满足方程$|ap_1|\ge k_1|bp_1|$以及$|cp_2|\ge k_2|dp_2|$，求$p_1$与$p_2$之间相交的体积。

解题思路

以第一个不等式为例，设$a(x_1,y_1,z_1),b(x_2,y_2,z_2)$，带入不等式，得到$(k_1^2-1)(x^2+y^2+z^2)+(2x_1-2k_1^2x_2)x+(2y_1-2k_1^2y_2)y+(2z_1-2z_1^2z_2)z+k_1^2(x_2^2+y_2^2+z_2^2)-(x_1^2+y_1^2+z_1^2)\le 0$，可以得出轨迹是球以及球的内部空间，由圆的一般方程$x^2+y^2+z^2+Ax+By+Cz+D=0$得球心坐标为$(-\frac{A}{2},-\frac{B}{2},-\frac{C}{2})$，半径为$\frac{\sqrt {A^2+B^2+C^2-4D}}{2}$。

对于两个球的情况，存在相离，相切，相交，包含几种关系，相离和相切答案为0，包含答案为半径小的球的体积。

对于相交的情况，我们可以拆成两个球冠的体积之和，由球冠体积公式$V=\frac{π}{3}h^2(r-h)$可以求出相交体积。

球冠如下图：

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const double PI = acos(-1);

void solve(double x1, double y1, double z1, double r1, double x2, double y2, double z2, double r2) {
	double dis = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2));
	double ans = 0;
	if (dis >= r1 + r2)	ans = 0;
	else if (dis + r1 <= r2)	ans = 4 * PI * r1 * r1 * r1 / 3;
	else if (dis + r2 <= r1)	ans = 4 * PI * r2 * r2 * r2 / 3;
	else {
		double c = (r1 * r1 + dis * dis - r2 * r2) / (2 * r1 * dis);
		double d1 = r1 * c, d2 = dis - d1;
		double h1 = r1 - d1, h2 = r2 - d2;
		ans += PI * h1 * h1 * (3 * r1 - h1) / 3;
		ans += PI * h2 * h2 * (3 * r2 - h2) / 3;
	}
	printf("%.3lf\n", ans);
}

int main() {
	int t; cin >> t;
	while (t--) {
		double x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4;
		cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2 >> x3 >> y3 >> z3 >> x4 >> y4 >> z4;
		double k1, k2; cin >> k1 >> k2;
		double cx1, cx2, cy1, cy2, cz1, cz2, r1, r2;
		double t1 = k1 * k1 - 1, t2 = k2 * k2 - 1;
		double ca1, ca2, cb1, cb2, cc1, cc2, cd1, cd2;
		ca1 = 2 * (x1 - k1 * k1 * x2) / t1;
		cb1 = 2 * (y1 - k1 * k1 * y2) / t1;
		cc1 = 2 * (z1 - k1 * k1 * z2) / t1;
		cd1 = k1 * k1 * (x2 * x2 + y2 * y2 + z2 * z2) - (x1 * x1 + y1 * y1 + z1 * z1);
		cd1 /= t1;
		cx1 = -ca1 / 2;
		cy1 = -cb1 / 2;
		cz1 = -cc1 / 2;
		r1 = sqrt(ca1 * ca1 + cb1 * cb1 + cc1 * cc1 - 4 * cd1) / 2;
		ca2 = 2 * (x3 - k2 * k2 * x4) / t2;
		cb2 = 2 * (y3 - k2 * k2 * y4) / t2;
		cc2 = 2 * (z3 - k2 * k2 * z4) / t2;
		cd2 = k2 * k2 * (x4 * x4 + y4 * y4 + z4 * z4) - (x3 * x3 + y3 * y3 + z3 * z3);
		cd2 /= t2;
		cx2 = -ca2 / 2;
		cy2 = -cb2 / 2;
		cz2 = -cc2 / 2;
		r2 = sqrt(ca2 * ca2 + cb2 * cb2 + cc2 * cc2 - 4 * cd2) / 2;
        solve(cx1, cy1, cz1, r1, cx2, cy2, cz2, r2);
	}
	return 0;
}

G-League of Legends

题目大意

有n个人，每个人有一个游玩时间$[a_i,b_i)$，你需要将这n个人分为k组，每组的游玩时间为每个人的游玩时间的共同时间，每组的游玩时间必须超过1分钟，问每组的游玩时间的最大和是多少。

解题思路

首先，我们先把包含有其他区间的区间定义为大区间，其他的为小区间。对于大区间，他的最优情况要么是单独一组，要么是和他包含的区间一组，如果他与其他的区间一组，肯定会使自身的贡献减少。

对于小区间，我们把这些区间按照左端点从小到大来排序，因为我们把大区间去掉了，所以这些区间的右端点肯定是单调不降的。对于这个性质，我们假设将两个区间i和j分为一组，那么对于这两个区间中间的区间k，他与i和j的贡献$R[k]-L[j]$和$R[i]-L[k]$，都是包含在i和j的贡献$R[i]-L[j]$当中的。

我们设$dp[i][j]$为用前j个区间分i组的最大和，我们可以写出转移方程$dp[i][j]=max \lbrace dp[i-1][k]+R[k+1]-L[j] \rbrace (k<j\text{&&}R [k]>L[j])$。

变形得$dp[i][j]=max \lbrace dp[i-1][k]+R[k+1]\rbrace -L[j](k<j\text{&&}R [k]>L[j])$。

对于k来说，我们如果用枚举的形式肯定会超时，所以我们用单调队列来优化，对于每一个i，维护一个单调队列，储存$max\lbrace dp[i-1][k]+R[k+1]\rbrace $，这样能保证时间复杂度为$O(n^2)$。

最后枚举一下最优解，把小区间分了剩余的组数给大区间单独一组。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const int N = 5050;
struct node {
	int l, r;
	bool operator < (const node& t) const {
		return l < t.l || (l == t.l && r > t.r);
	}
}area[N], s[N];
int b[N], dp[N][N], q[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, k; cin >> n >> k;
	rep(i, 1, n)	cin >> area[i].l >> area[i].r;
	sort(area + 1, area + 1 + n);
	int maxr = 1e9, cnts, cntb;
	cnts = cntb = 0;
	per(i, n, 1) {
		if (area[i].r >= maxr) b[++cntb] = area[i].r - area[i].l;
		else maxr = area[i].r, s[++cnts] = area[i];
	}
	sort(s + 1, s + 1 + cnts);
	sort(b + 1, b + 1 + cntb, greater<int>());
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	rep(i, 1, k) {
		int l = 1, r = 0;
		rep(j, 1, cnts) {
			if (dp[i - 1][j - 1] != -1) {
				while (l <= r && dp[i - 1][q[r]] + s[q[r] + 1].r <= dp[i - 1][j - 1] + s[j].r)	r--;
				q[++r] = j - 1;
			}
			while (l <= r && s[q[l] + 1].r <= s[j].l)	l++;
			if (l <= r)	dp[i][j] = dp[i - 1][q[l]] + s[q[l] + 1].r - s[j].l;
		}
	}
	int ans = 0, t = 0;
	rep(i, 0, k) {
		t += b[i];
		if (dp[k - i][cnts] != -1)	ans = max(ans, t + dp[k - i][cnts]);
	}
	cout << ans << endl;
	return 0;
}

I-Penguins

题目大意

企鹅游戏

解题思路

广搜+记录路径

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
struct node{
	int x1, y1, x2, y2;
}pre[25][25][25][25];
char Map1[25][25], Map2[25][25], ch[] = { 'D','L','R','U' };
int dx1[] = { 0,-1,1,0 }, dx2[] = { 0,1,-1,0 };
int dy [] = { 1,0,0,-1 };
int vis[25][25][25][25];

void bfs(int x1, int y1, int x2, int y2) {
	queue<node> q;
	q.push({ x1,y1,x2,y2 });
	vis[x1][y1][x2][y2] = 1;
	while(!q.empty()){
		node t = q.front(); q.pop();
		if (t.x1 == 20 && t.y1 == 1 && t.x2 == 1 && t.y2 == 1) 	return;
		rep(i, 0, 3) {
			int X1 = t.x1 + dx1[i], X2 = t.x2 + dx2[i];
			int Y1 = t.y1 + dy [i], Y2 = t.y2 + dy [i];
			if (X1 > 20 || X1 < 1 || Y1 > 20 || Y1 < 1 || Map1[Y1][X1] == '#')
				X1 = t.x1, Y1 = t.y1;
			if (X2 > 20 || X2 < 1 || Y2 > 20 || Y2 < 1 || Map2[Y2][X2] == '#')
				X2 = t.x2, Y2 = t.y2;
			if (!vis[X1][Y1][X2][Y2]) {
				vis[X1][Y1][X2][Y2] = 1;
				q.push({ X1,Y1,X2,Y2 });
				pre[X1][Y1][X2][Y2] = t;

			}
		}
	}
}

void print(int x1,int y1,int x2,int y2) {
	string ans; int cnt = 0;
	Map1[y1][x1] = Map2[y2][x2] = 'A';
	while (x1 != 20 || y1 != 20 || x2 != 1 || y2 != 20) {
		node p = pre[x1][y1][x2][y2];
		Map1[p.y1][p.x1] = Map2[p.y2][p.x2] = 'A';
		rep(i, 0, 3) {
			int X1 = p.x1 + dx1[i], X2 = p.x2 + dx2[i];
			int Y1 = p.y1 + dy [i], Y2 = p.y2 + dy [i];
			if (X1 > 20 || X1 < 1 || Y1 > 20 || Y1 < 1 || Map1[Y1][X1] == '#')
				X1 = p.x1, Y1 = p.y1;
			if (X2 > 20 || X2 < 1 || Y2 > 20 || Y2 < 1 || Map2[Y2][X2] == '#')
				X2 = p.x2, Y2 = p.y2;
			if (X1 == x1 && Y1 == y1 && X2 == x2 && Y2 == y2) {
				ans += ch[i]; break;
			}
		}
		cnt++;
		x1 = p.x1, y1 = p.y1, x2 = p.x2, y2 = p.y2;
	}
	reverse(ans.begin(), ans.end());
	cout << cnt << endl;
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	rep(i, 1, 20) {
		rep(j, 1, 20)	cin >> Map1[i][j];
		rep(j, 1, 20)	cin >> Map2[i][j];
	}
	bfs(20, 20, 1, 20);
	print(20, 1, 1, 1);
	rep(i, 1, 20) {
		rep(j, 1, 20)	cout << Map1[i][j];
		cout << " ";
		rep(j, 1, 20)	cout << Map2[i][j];
		cout << endl;
	}
	return 0;
}

K-Stack

题目大意

有一个序列a，对于a构造一个单调栈，$b[i]$为构造到$a[i]$时，单调栈的大小，现给你某些b数列的值，问你能否构造出一个合法的序列a。

解题思路

首先我们需要把b数组给补全，对于已经标记过了的我们没办法更改，对于那些没有标记的考虑，我们位于i点时，要么就是向单调栈中push一个数，要么就是push的数比较小，导致单调栈的大小减小，我们贪心的想，我增大栈容量一次只能加一，但是我排空栈倒是可以一次减少许多，所以我们选择对于没标记过的点，他的容量为前一个值加一，即$b[i]=b[i-1]+1$，如果前后两个容量差大于1，那么肯定没有合法解。

补全完b数组之后，我们可以倒着来构造，如果栈的容量比该点的要求小，就需要往里面push值，从1开始，每次push到刚好满足该点要求的容量，那么这点的a，就是栈顶元素。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int N = 1e6 + 5;
int a[N], b[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	rep(i, 1, m) {
		int p, x; cin >> p >> x;
		b[p] = x;
	}
	int flag = 1;
	rep(i, 1, n) {
		if (!b[i])	b[i] = b[i - 1] + 1;
		if (b[i] - b[i - 1] > 1)	flag = 0;
	}
	if (!flag) {
		cout << -1 << endl;
		return 0;
	}
	stack<int> s;
	int t = 1;
	per(i, n, 1) {
		while (s.size() < b[i])	s.push(t++);
		a[i] = s.top(), s.pop();
	}
	rep(i, 1, n)	cout << a[i] << ' ';
	return 0;
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

扫一扫，分享到微信

微信分享二维码
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信