2021牛客高校暑假训练赛二

本文最后更新于：2021年8月19日 晚上

昨天在忙江苏省赛. . .一不小心做到了很晚，第二天醒来就是一点多了. . .（悲

比赛过程

由于起来的很晚. . .醒来后外卖都没定就立马进入比赛，悲伤的是唯一的队友也忘了（据说他们有800行的大作业，奇了怪了为啥会有老师要求代码行数的？）。只能先迅速签到，先看了C题（我看的时候过的人就已经过k了QAQ），题目大意好像是在网点图里面走点，同时还有限制条件。输入数据是nm反馈一个答案类型，输入简单并且还是个签到题，结合数据大但猜测一波是判断n*m的奇偶性，结果竟然真的过了。再看另一道签到题，是一道小模拟，没啥技术含量，全在读题，也快速过了。之后去看K题，钻研了许久钻研出了一个自以为对的结论，码完后Wa了. . .最后发现自己题意搞错了。没办法，重新读题再搞 . . 中间还T了好多发。看正解说是拓扑排序. . .还是需要学习。题写到一半被室友叫去吃饭了. . .搞的虎头蛇尾

总结

由于自己的原因这场比赛有效时间很短，需要正视自己的态度，现在是练习就要减少骗分抖机灵尽量学习新东西，以及需要加强补题（updating 2021.7.22:郑州暴雨，虽然我们不是受灾最严重的地方，但是宿舍楼停水停电，极大降低补题效率. . .上次的题还没补完就有新比赛，节奏好快啊）

题目详情

补题不补签到(c,d,I)了，费时间又没啥用

F

题意，给你 $A,B,C,D$ 四个点的坐标及系数.点p满足,问你合法的p的所占空间的大小
需要手推一波公式，设 ,呢么不等式为

这明显是球的表达式，然后通过化简就可以得出球的球心及半径，由于P是由两个球确定的范围，呢么P的空间就是两个球的体积并。
关于球的体积并，需要拓展一些计算几何的知识，我已经更新到了这里.

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
#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1);//学到的一种pi的定义
int T;
double x[20],y[20],z[20],k1,k2,k_1,k_2;
double Circle1_x,Circle1_y,Circle1_z,Circle1_r;
double Circle2_x,Circle2_y,Circle2_z,Circle2_r;
inline double solve(double x1,double y1,double z1,double r1,double x2,double y2,double z2,double r2)
{//求球的体积并
    double num=0;
    double dis=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
    if(dis>=r1+r2)return 0.0;
    if(dis+r1<=r2){num=(4.00/3.00)*pi*r1*r1*r1;return num;}
    if(dis+r2<=r1){num=(4.00/3.00)*pi*r2*r2*r2;return num;}
    double kl=(r1*r1+dis*dis-r2*r2)/(2.00*dis*r1);
    double h=r1*(1-kl);
    num+=(pi/3.00)*(3.00*r1-h)*h*h;
    kl=(r2*r2+dis*dis-r1*r1)/(2.00*dis*r2);
    h=r2*(1.00-kl);
    num+=(pi/3.00)*(3.00*r2-h)*h*h;
    return num;
}
int main()
{
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	cin>>T;
	while(T--)
	{
		for(int i=0;i<4;i++)scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
		scanf("%lf%lf",&k1,&k2);
		//cout<<k1<<' '<<k2<<endl;
		K_1=k1*k1-1;

		Circle1_x=(k1*k1*x[1]-x[0])/K_1;
		Circle1_y=(k1*k1*y[1]-y[0])/K_1;
		Circle1_z=(k1*k1*z[1]-z[0])/K_1;
		t=k1*k1*((x[1]*x[1])+(y[1]*y[1])+(z[1]*z[1]))-x[0]*x[0]-y[0]*y[0]-z[0]*z[0];
		double t/=K_1;
		Circle1_r=sqrt(Circle1_x*Circle1_x+Circle1_y*Circle1_y+Circle1_z*Circle1_z-t);
		////////////////////////////////////////////////
		K_2=k2*k2-1;
		Circle2_x=(k2*k2*x[3]-x[2])/K_2;
		Circle2_y=(k2*k2*y[3]-y[2])/K_2;
		Circle2_z=(k2*k2*z[3]-z[2])/K_2;
		t=k2*k2*((x[3]*x[3])+(y[3]*y[3])+(z[3]*z[3]))-x[2]*x[2]-y[2]*y[2]-z[2]*z[2];
		t/=K_2;
		Circle2_r=sqrt(Circle2_x*Circle2_x+Circle2_y*Circle2_y+Circle2_z*Circle2_z-t);
		//cout<<Circle1_x<<' '<<Circle1_y<<' '<<Circle1_z<<' '<<Circle1_r<<endl;
		//cout<<Circle2_x<<' '<<Circle2_y<<' '<<Circle2_z<<' '<<Circle2_r<<endl;
		printf("%.6f\n",solve(Circle1_x,Circle1_y,Circle1_z,Circle1_r,Circle2_x,Circle2_y,Circle2_z,Circle2_r));	
	}
	return 0;
}

I

给两个20*20的点阵图，同一个操作在两个图中互为镜像，问你如何操作使两个图中的人达到目的地，同时要求操作长度最小及字典序最小。
以两个图中的坐标为参照进行广搜。（其实我最开始想的是两个图各进行一次路径查询然后融合，但是明显不对。搞不出来）。注意剪枝，就没了。

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
75
76
77
#include<bits/stdc++.h>
using namespace std;
struct ss
{
	int x1,y1;
	int x2,y2;
	int num;
	string s1; 
	ss(int a1=0,int a2=0,int a3=0,int a4=0,int a5=0,string a7="\0"){x1=a1;y1=a2;x2=a3;y2=a4;num=a5;s1=a7;}
	inline void out(){printf("%d %d %d %d %d ",x1,y1,x2,y2,num);cout<<s1<<endl;}
}ans;
queue<ss> Q;
char ch1[25][25],ch2[25][25],ch3[5]={'D','L','R','U'};
int a[22][22][22][22];
int fx1[5]={1,0,0,-1},fy1[5]={0,-1,1,0};
int fx2[5]={1,0,0,-1},fy2[5]={0,1,-1,0};
inline bool check1(int xx,int yy){return (xx>0&&xx<=20&&yy>0&&yy<=20&&ch1[xx][yy]!='#')?1:0;}
inline bool check2(int xx,int yy){return (xx>0&&xx<=20&&yy>0&&yy<=20&&ch2[xx][yy]!='#')?1:0;}
int main()
{
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	memset(a,10,sizeof(a));
	for(int i=1;i<=20;i++)scanf("%s %s",ch1[i]+1,ch2[i]+1);
	//for(int i=1;i<=20;i++)printf("%s\n",ch1[i]);
	Q.push(ss(20,20,20,1,0));a[20][20][20][1]=0;
	while(!Q.empty())
	{
		ss a1=Q.front();
		if(a1.x1==1&&a1.y1==20&&a1.x2==1&&a1.y2==1)
		{
			//a1.out();
			cout<<a1.num<<'\n'<<a1.s1<<endl;
			ans=a1;
			break;
		}
		Q.pop();
		for(int i=0,xx1,yy1,xx2,yy2;i<=3;i++)
		{
			xx1=a1.x1+fx1[i];xx2=a1.x2+fx2[i];
			yy1=a1.y1+fy1[i];yy2=a1.y2+fy2[i];
			if(!check1(xx1,yy1)&&!check2(xx2,yy2))continue;
			if(!check1(xx1,yy1)){xx1=a1.x1;yy1=a1.y1;}
			if(!check2(xx2,yy2)){xx2=a1.x2;yy2=a1.y2;}
			if(a[xx1][yy1][xx2][yy2]!=a[0][0][0][0])continue;
			
			if(a[xx1][yy1][xx2][yy2]<a1.num)continue;
			a[xx1][yy1][xx2][yy2]=a1.num;
			Q.push(ss(xx1,yy1,xx2,yy2,a1.num+1,(a1.s1+ch3[i])));
		}
	}
	int xx1=20,xx2=20,yy1=20,yy2=1;
	ch1[xx1][yy1]='A';
	for(int i=0,xxx1,yyy1;i<ans.s1.size();i++)
	{
		xxx1=xx1;yyy1=yy1;
		if(ans.s1[i]=='L')yy1--;
		if(ans.s1[i]=='R')yy1++;
		if(ans.s1[i]=='U')xx1--;
		if(ans.s1[i]=='D')xx1++;
		if(!check1(xx1,yy1)){xx1=xxx1;yy1=yyy1;}
		ch1[xx1][yy1]='A';
	}
	ch2[xx2][yy2]='A';
	for(int i=0,xxx2,yyy2;i<ans.s1.size();i++)
	{
		xxx2=xx2;yyy2=yy2;
		if(ans.s1[i]=='L')yy2++;
		if(ans.s1[i]=='R')yy2--;
		if(ans.s1[i]=='U')xx2--;
		if(ans.s1[i]=='D')xx2++;
		if(!check2(xx2,yy2)){xx2=xxx2;yy2=yyy2;}
		ch2[xx2][yy2]='A';
	}
	for(int i=1;i<=20;i++)printf("%s %s \n",ch1[i]+1,ch2[i]+1);
	return 0;
}

K

往一个单调栈里填入一个数组，保证单调递增。现给你栈在各个时刻的情况（站内元素个数），让你输出数组可能的一种情况。
根据栈的关系建立拓扑序，然后把1~n个数填到拓扑序内。
比较麻烦的点在于拓扑序的建立处理，我在这儿卡了一会。

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
75
76
77
#include<bits/stdc++.h>
using namespace std;
inline void Read(int &r)
{
	static char c;
	for(c=0;c<'0' || c>'9';c=getchar());
	for(r=0;c>='0' && c<='9';c=getchar())r=r*10+(c^'0');
}
struct ss
{
	int id,num;
}b[1100000];
struct s1
{
	int x,y,next;
}e[2100000];
int n,k;
int Stack[1100000],Link[1100000],jkl=0;
int Q[1100000],l=0,r=0,vis[1100000],dis[1100000],N;
bool mycmp(ss a1,ss a2){return a1.id<a2.id;}
inline void insert(int xx,int yy)
{
	vis[yy]++;
	e[++jkl].next=Link[xx];
	e[jkl].x=xx;
	e[jkl].y=yy;
	Link[xx]=jkl;
}
int main()
{
	//freopen("a.out","w",stdout);
	Read(n),Read(k);
	for(int i=1;i<=k;i++)Read(b[i].id),Read(b[i].num);
	sort(b+1,b+k+1,mycmp);
	for(int i=1;i<=k;i++)
	{
		if(b[i].id<b[i].num){cout<<-1<<endl;return 0;}
		if(b[i].id==b[i+1].id&&b[i].num!=b[i+1].num&&i!=k){cout<<-1<<endl;return 0;}
		if(b[i+1].id-b[i].id<b[i+1].num-b[i].num&&i!=k){cout<<-1<<endl;return 0;}
	}
	for(int i=1,j=1,flag=0;i<=n;i++)
	{
		if(i==b[j].id) 
		{
			//cout<<Stack[0]<<' '<<b[j].num<<endl;
			flag=0;
			while(Stack[0]+1>b[j].num)insert(Stack[Stack[0]],i),Stack[0]--;
			j++;
		}
		insert(i,Stack[Stack[0]]);
		Stack[++Stack[0]]=i;
	}
	for(int i=1;i<=n;i++)if(vis[i]==0)Q[++r]=i;
	N=n;
	int jkll=0;
	while(l<r)
	{
		l++;
		dis[Q[l]]=N--;
		for(int i=Link[Q[l]];i;i=e[i].next)
		{
			vis[e[i].y]--;
			if(!vis[e[i].y])Q[++r]=e[i].y;
		}
	}
	for(int i=1;i<=n;i++)printf("%d ",dis[i]);cout<<endl;
	/*for(int i=1;i<=n;i++)
	{
		cout<<i<<':';
		for(int j=Link[i];j;j=e[j].next)
		{
			cout<<e[j].y<<' ';
		}cout<<endl;
	}*/

	return 0;
}
2021 比赛 暑期牛客高校训练赛
大学 牛客 icpc

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！