2021牛客暑期多校训练营2(部分补题)

2021牛客暑期多校训练营2

D题
简单模拟,按照题目要求判断就行

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

int main() {
	int t;
	cin >> t;
	int a1, b1, a2, b2;
	while (t--) {
		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)cout << "first" << endl;
		else if (a1 != b1 && a2 == b2)cout << "second" << endl;
		else if (a1 == b1 && a2 == b2) {
			if (a1 > a2)cout << "first" << endl;
			else if (a1 < a2)cout << "second" << endl;
		}
		else if (a1 != b1 && a2 != b2) {
			if ((a1 + b1) % 10 > (a2 + b2) % 10)cout << "first" << endl;
			else if ((a1 + b1) % 10 < (a2 + b2) % 10)cout << "second" << endl;
			else if ((a1 + b1) % 10 == (a2 + b2) % 10) {
				if (b1 > b2)cout << "first" << endl;
				else if (b1 < b2)cout << "second" << endl;
			}
		}
	}
	return 0;
}

C题
一开始一直没有看到题目呜呜呜呜呜呜呜
就是对点连线,不能重复也不能形成闭合图形,那么有k个点,就有k-1个可以连接的点,奇数先手赢,偶数后手。

#include<algorithm>
#include<iostream>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 7;

int main() {
	int n, m;
	cin >> n >> m;
	int ans = n * m;
	ans -= 1;
	if (ans % 2 == 1)cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

F题

题意,给了四个点,求满足题目不等式的p1,p2的活动范围的相交的区域的体积,推导过程如下,可得为两个球的相交的体积。
2021牛客暑期多校训练营2(部分补题)
无白色草稿纸了,将就着看
这时候只需要求两个球相交的体积
参考博客
2021牛客暑期多校训练营2(部分补题)
按照公式写就行
(参考了牛客题解区)

#include<algorithm>
#include<iostream>
#include<map>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N = 1e6 + 7;
//pai 3.1415.....
const double pi = acos(-1);

int t;
double x[5], y[5], z[5];
double k1, k2;

int main() {
	cin >> t;
	while (t--) {
		for (int i = 1; i <= 4; i++) {
			cin >> x[i] >> y[i] >> z[i];
		}
		cin >> k1 >> k2;

		//球一
		double xs1 = k1 * k1 - 1;
		double a1, b1, c1, r1, d1;
		a1 = (k1 * k1 * x[2] - x[1]) / xs1;
		b1 = (k1 * k1 * y[2] - y[1]) / xs1;
		c1 = (k1 * k1 * z[2] - z[1]) / xs1;
		d1 = k1 * k1 * (x[2] * x[2] + y[2] * y[2] + z[2] * z[2]) - x[1] * x[1] - y[1] * y[1] - z[1] * z[1];
		d1 /= xs1;
		r1 = sqrt(a1 * a1 + b1 * b1 + c1 * c1 - d1);

		//球二
		double xs2 = k2 * k2 - 1;
		double a2, b2, c2, r2, d2;
		a2 = (k2 * k2 * x[4] - x[3]) / xs2;
		b2 = (k2 * k2 * y[4] - y[3]) / xs2;
		c2 = (k2 * k2 * z[4] - z[3]) / xs2;
		d2 = k2 * k2 * (x[4] * x[4] + y[4] * y[4] + z[4] * z[4]) - x[3] * x[3] - y[3] * y[3] - z[3] * z[3];
		d2 /= xs2;
		r2 = sqrt(a2 * a2 + b2 * b2 + c2 * c2 - d2);

		//计算两球相交的体积  球1球心(a1,b1,c1)半径r1 球2球心(a2,b2,c2)半径r2
		double ans = 0;
		//两个圆心的距离
		double d3 = sqrt((a1 - a2) * (a1 - a2) + (b1 - b2) * (b1 - b2) + (c1 - c2) * (c1 - c2));
		//判断,1.相离相切,ans为0. 2.内切内含,ans为里面那个球的体积
		//3.相交
		if (d3 >= r1 + r2) {
			ans = 0;
		}
		else if (d3 + r1 <= r2) {
			ans = (4.0 / 3.0) * pi * r1 * r1 * r1;
		}
		else if (d3 + r2 <= r1) {
			ans = (4.0 / 3.0) * pi * r2 * r2 * r2;
		}
		else {
			double co1 = (r1 * r1 + d3 * d3 - r2 * r2) / (2 * r1 * d3);
			double h1 = r1 * (1 - co1);
			double co2 = (r2 * r2 + d3 * d3 - r1 * r1) / (2 * r2 * d3);
			double h2 = r2 * (1 - co2);
			ans = pi * (3 * r1 - h1) * h1 * h1 / 3.0 + pi * (3 * r2 - h2) * h2 * h2 / 3.0;
		}
		printf("%.3lf\n", ans);
	}
	return 0;
}

K题
呜呜呜呜呜呜呜呜呜呜又又又无法理解题目
题意的话大概就是求ai数组的可能值,需要用1~n来填充
是一个单调栈,刚开始栈为零,将ai数组一个一个放入,如果栈里有比放入大的数,弹出,bi数组为每次操作栈里数的个数
由题目给出条件可求出bi数组的一种可满足的值(bi数组即ai数组中每一个位置的size) 刚开始一直没有看懂
如果b[i]!=b[j],就把较小的数放到较小的下标里
如果b[i]==b[j],将小的数放到较大的下标里
还是参考了题解区大佬的代码

#include<algorithm>
#include<iostream>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N = 1e6 + 10;

struct p
{
    int num, w;
}po[N];

//进行排序
bool cmp(struct p a, struct p b)
{
    if (a.w != b.w)return a.w < b.w;
    else return a.num > b.num;
}

int b[N], book[N], ans[N];

int main()
{
    int n, k, f = 1;
    cin >> n >> k;
    for (int i = 0; i < k; i++){
        int t, w;
        cin >> t >> w;
        b[t] = w;
        book[t] = 1;
        if (w > t || t > n || w > n)  f = 0; 
    }
    //当下标小于需要长度或者两者大于n时输出-1
    if (f == 0) {
        puts("-1");
        return 0;
    }
    for (int i = 1; i <= n; i++){
        if (book[i]){
            for (int j = i - 1; j >= 1 && !book[j]; j--){
                b[j] = max(b[j + 1] - 1, 1);//构造一个满足条件的b数组
                book[j] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i++){
        if (book[i] == 0)b[i] = b[i - 1];
        po[i].num = i;
        po[i].w = b[i];
    }

    sort(po + 1, po + 1 + n, cmp);
    for (int i = 1; i <= n; i++){
        ans[po[i].num] = i;
    }

    for (int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

I题
题意,两只小企鹅在两个地图镜像移动,求移动到终点的移动方向的字典序最小。
按照顺序“D,L,R,U”的移动顺序,用bfs求出他的最短路径,分别储存两边地图,可以移动并且没有到过这个点入队列,用q储存路径,然后递归求,具体的看代码注释
代码实现真的好神奇,呜呜呜呜呜呜呜呜呜呜巨菜

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;

const int N = 0x3f3f3f3f;
char a[25][25], b[25][25];
int dp[25][25][25][25];
int d[4][4] = { 1,0,1,0,0,-1,0,1,0,1,0,-1,-1,0,-1,0 };
struct node {
	int x1, y1, x2, y2;
};
char dd[4] = { 'D','L','R','U' };
node q[25][25][25][25];
char f[25][25][25][25];
char z[1000];
queue <node> p;

void bfs() {
	while (!p.empty()) {
		node u = p.front();
		p.pop();
		int k = dp[u.x1][u.y1][u.x2][u.y2];
		for (int i = 0; i < 4; i++) {
			//控制的小企鹅为左边的
			//i==0: D; i==1: L; i==2: R; i==3: U;
			//镜像同步
			int x1 = u.x1 + d[i][0];
			int y1 = u.y1 + d[i][1];
			int x2 = u.x2 + d[i][2];
			int y2 = u.y2 + d[i][3];

			if (a[x1][y1] != '.')
				x1 = u.x1, y1 = u.y1;
			if (b[x2][y2] != '.')
				x2 = u.x2, y2 = u.y2;
			//dp是走到每个点的最小步数
			//q是路径,从一个点到下一个点
			//求出最短路径
			if (dp[x1][y1][x2][y2] > k + 1) {
				dp[x1][y1][x2][y2] = k + 1;
				q[x1][y1][x2][y2] = node{ u.x1,u.y1,u.x2,u.y2 };
				f[x1][y1][x2][y2] = i;
				p.push(node{ x1,y1,x2,y2 });
			}
		}
	}
}

int ans = 0;
void aa(node u) {
	int x1 = u.x1;
	int y1 = u.y1;
	int x2 = u.x2;
	int y2 = u.y2;
	//将经过的地方做标记
	a[x1][y1] = 'A'; b[x2][y2] = 'A';
	//如果到达起点就返回
	if (x1 == 20 && y1 == 20 && x2 == 20 && y2 == 1)
		return;
	//继续遍历
	aa(q[x1][y1][x2][y2]);
	//递归,ans为步数,z储存的为移动方向
	z[++ans] = dd[f[x1][y1][x2][y2]];
}

int main() {
	/*for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cout << d[i][j] << ' ';
		}
		cout << endl;
	}*/
	for (int i = 1; i <= 20; i++) {
		cin >> a[i] + 1 >> b[i] + 1;
	}
	//A从(20,20)开始搜B从(20,1)开始
	p.push(node{ 20,20,20,1 });
	memset(dp, N, sizeof(dp));
	dp[20][20][20][1] = 0;
	bfs();
	//终点 A为(1,20) B为(1,1),从终点到起点
	aa(node{ 1,20,1,1 });

	cout << ans << endl << z + 1 << endl;
	for (int i = 1; i <= 20; i++) {
		cout << a[i] + 1 << " " << b[i] + 1 << endl;
	}
	return 0;
}
上一篇:BZOJ5027: 数学题


下一篇:2021年ECNU计科考研复试机试 B. 矩形个数(二维前缀和+二分或者尺取)