BUPT 2022 Summer Training #2(2018-2019 ACM-ICPC, Asia Seoul Regional Contest)

  A B C D E F G H I J K L
考场过题 O O   O   O         O O
赛后补题         O         O    

A - Circuits

题目大意：平面中有N个矩形，找出两条横线使其穿过的矩形尽可能多，其中即使横线和刚好贴着矩阵边也算穿过（两条横线穿过同一个矩形只算1次）。

数据范围：3<=N<=1e5,-1e7<=ux,uy,vx,vy<=1e7   左上角：（ux,uy）,右下角：（vx,vy）

解题思路：矩形的横坐标其实是没有用的，因此把问题转化为一条直线上有若干[vy,uy]的线段，找出两条横线穿过尽可能多的线段。

还可以发现横线一定穿过某一个线段的端点（没穿过端点也可平移到穿过端点），故进行离散化。

因此，先枚举第一个点，然后通过线段树找出最优的第二个点，每次移动第一个点a->b时，恢复a穿过的线段，删除b穿过的线段即可。

罚时情况：1次。在最终记录答案的时候还是一次处理完所有相同坐标端点后才行，否则如果一个坐标是很多线段的终点+1，同时是很多线段的起点，那么和新的第一个点不穿过的应该被删掉的线段会被计入答案，导致答案偏大。即：不要偷懒，要模拟真实情况，一个坐标一个坐标枚举而非一个线段一个线段枚举，或者在排序时把是起点/终点算入第二关键字。

参考代码：

查看代码 
#include
#include
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N=1e5+1000;
struct Point
{
	int pos,npos,id,flag;
}P[2*N];
int left[N],right[N];
int cmp(const Point&a,const Point&b)
{
	return a.pos>1;
	if (b<=mid) update(root<<1,l,mid,a,b,x);
	else
	{
		if (a>mid) update(root<<1|1,mid+1,r,a,b,x);
		else update(root<<1,l,mid,a,mid,x),update(root<<1|1,mid+1,r,mid+1,b,x);
	}
	max[root]=std::max(max[root<<1],max[root<<1|1]);
}
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int ux,uy,vx,vy;
		scanf("%d%d%d%d",&ux,&uy,&vx,&vy);
		//[vy,uy]   [vy,uy+1)
		P[(i-1)*2+1]=(Point){vy,0,i,1};//left
		P[(i-1)*2+2]=(Point){uy+1,0,i,-1};//right
	}
	std::sort(P+1,P+1+2*n,cmp);P[0].npos =0;
	for(int i=1;i<=2*n;i++)
	{
		P[i].npos = P[i-1].npos +(P[i-1].pos!=P[i].pos||i==1);
		if (P[i].flag==1) left[P[i].id]=P[i].npos;
		else right[P[i].id]=P[i].npos;
	}
//	For(i,1,2*n) printf("!! %d %d %d\n",P[i].npos ,P[i].flag,P[i].id);
//	For(i,1,n) printf("?? %d %d\n",left[i],right[i]);
	for(int i=1;i<=n;i++) update(1,1,P[2*n].npos,left[i],right[i]-1,1);
	int tmp=0,ans=0;
	for(int i=1;i<=2*n;i++)
	{
		tmp+=P[i].flag;
		update(1,1,P[2*n].npos,left[P[i].id],right[P[i].id]-1,-P[i].flag);
//		printf("?? %d %d %d %d\n",i,P[i].npos,tmp,max[1]);
		if (i==2*n||P[i].npos!=P[i+1].npos) ans=std::max(ans,tmp+max[1]);
	}
	printf("%d\n",ans);
	return 0;
}

B - Cosmetic Survey

题目背景：m个化妆品，n个评委。每个评委会对所有化妆品打分，数字越低越喜欢，但是数字为0是最不喜欢。

d(X,Y)表示比起Y更喜欢X的评委数。从X到Y有一条C1,C2,...,Ck (C1=X,Ck=Y)的路径当且仅当d(Ci,Ci+1)>d(Ci+1,Ci) (1<=i

一条路径的偏好指标(preference index)为路径上最小的d(Ci,Ci+1)

一对化妆品的偏好强度(preference strength)  S(X,Y)为所有X->Y路径的最大偏好指标 （不可达则S(X,Y)=0）

判断有哪些化妆品X满足：任意其他化妆品Y(X!=Y) S(X,Y)>=S(Y,X)

数据范围：1

解题思路：d(X,Y)>d(Y,X)则建一条X->Y的权值为d(X,Y)的边

题目实际上是要问任意两点X,Y间的路径，路径上的最小边最大为多少

由于问任意两点，数据范围为500，考虑floyed变形。基于floyed的动态规划基本思想，一个点一个点加进来更新，把最终求的dis(X,Y)从X->Y的最短路径长度变为X->Y的最小边最大值

即：dis[i][j]=std::max(dis[i][j],std::min(dis[i][k],dis[k][j]))

罚时情况：2次。两次罚时都是队友罚的，不清楚具体情况

赛后总结：一开始还在想二分，后来想到一条边一条边地加进来搞dp，最后想干脆就一个点一个点加进来搞dp，最后发现，这不就是floyed模板嘛！

参考代码：

查看代码 
 #include
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N=510; 
int m,n,val[N],d[N][N],dis[N][N];
int main()
{
	scanf("%d%d",&m,&n);
	For(i,1,n)
	{
		For(j,1,m) scanf("%d",&val[j]);
		For(j,1,m) For(k,1,m) 
		{
			if (val[j]&&(val[j]d[j][i]) dis[i][j]=d[i][j];
	For(k,1,m) For(i,1,m) For(j,1,m) if (k!=i&&k!=j&&i!=j) 
		dis[i][j]=std::max(dis[i][j],std::min(dis[i][k],dis[k][j])); 
	For(i,1,m)
	{
		int flag=1;
		For(j,1,m) if (j!=i&&dis[i][j]

D - Go Latin

题目大意：签到题，字符串模拟。

罚时情况：无罚时。

赛后总结：好智障的签到题，但是也还是有一点繁琐...

参考代码：

查看代码 
 #include
#include
#include
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		char s[100];scanf("%s",s);
		int len=strlen(s);
		if (s[len-1]=='a') s[len++]='s',s[len]=0;
		else if (s[len-1]=='i'||s[len-1]=='y') s[len-1]='i',s[len++]='o',s[len++]='s',s[len]=0;
		else if (s[len-1]=='l') s[len++]='e',s[len++]='s',s[len]=0;
		else if (s[len-1]=='n') s[len-1]='a',s[len++]='n',s[len++]='e',s[len++]='s',s[len]=0;
		else if (s[len-2]=='n'&&s[len-1]=='e') s[len-2]='a',s[len-1]='n',s[len++]='e',s[len++]='s',s[len]=0;
		else if (s[len-1]=='o') s[len++]='s',s[len]=0;
		else if (s[len-1]=='r') s[len++]='e',s[len++]='s',s[len]=0;
		else if (s[len-1]=='t') s[len++]='a',s[len++]='s',s[len]=0;
		else if (s[len-1]=='u') s[len++]='s',s[len]=0;
		else if (s[len-1]=='v') s[len++]='e',s[len++]='s',s[len]=0;
		else if (s[len-1]=='w') s[len++]='a',s[len++]='s',s[len]=0;
		else s[len++]='u',s[len++]='s',s[len]=0;;
		printf("%s\n",s);
	}
	return 0;
}

E - LED

题目大意：给定N个二元组(vi,li)，求一个分段函数使得分段函数尽可能拟合这些二元组。

通过确定4个参数V1,V2,L1,L2(012,0<=L1<=L2)确定该分段函数:

F(v)= 0 ,0<=v1

??   L1 ,V1<=v2

??   L2 ,V2<=v?

尽可能拟合：即让error(F)=max|li-F(vi)|尽可能小。

数据范围：1<=n<=3e5, 0<=vi,li<=1e9, 相同vi只会有一个li

解题思路：由于n=3e5，最多支持O(nlogn)的复杂度

由于低误差可满足可则高误差必定满足，故二分error(F)的值X，然后再O(n)检验X

可以发现如果V1,V2确定，那么最优的L1,L2的取法就是取对应区间内的(最大值+最小值)/2

1、还可以发现由于函数一开始必为0，V1被限制了最大值

由于V1~V2和V2~+∞的总长度越小，则最大值越小，最小值越大，肯定越容易满足条件

所以就让V1取能取的最大值

2、可以发现如果V1确定，那么可以发现从V1之后每加入一个数，L1的范围都会被更新的更窄(最大值-X~最小值+X)

3、还可以发现从后面往前加，每加入一个数L2的范围也会被更新地更窄(最大值-X~最小值+X)

4、题目要求L1<=L2，则要求V1~V2这一段区间的最大值-X  <=  V2~+∞这一段区间的最小值+X

综上，先确定V1，预处理V1~V2和V2~+∞的最大最小值，然后然后枚举V2逐一判断

[注]有的做法是把V2取得越大越好，但是可能导致L1本来有机会<=L2，但是V2太大导致L1不得不变大，从而导致L1>L2，不过那些做法居然都AC了emmm

赛后总结：考试的时候我没看这题，太可惜了，不过这题的做法确实没那么好想，而且要特别注意012,0<=L1<=L2。

不过我在补题的时候一发就过了哈哈哈。以后比赛一定要多开题，多看题，千万不要卡在某一题。

罚时记录：比赛时没做出来，可惜了。

参考代码：

查看代码 
 #include
#include
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Frd(i,a,b) for(int i=a;i>=b;i--)
const int N=3e5+1000;
int n;
struct DATA
{
	int v,l;
}s[N];
int cmp(const DATA&a,const DATA&b)
{
	return a.vX) return 0;
		l++;
	}
	while (l<=n&&s[l].l<=X) l++;if (l>n) return 1;
	min[l-1][0]=1e18;max[l-1][0]=-1e18;
	For(i,l,r) 
	{
		min[i][0]=std::min(min[i-1][0],(double)s[i].l);
		max[i][0]=std::max(max[i-1][0],(double)s[i].l);
	}
	if (max[r][0]-X<=min[r][0]-X) return 1;
	
	min[r+1][1]=1e18;max[r+1][1]=-1e18;
	Frd(i,r,l)
	{
		min[i][1]=std::min(min[i+1][1],(double)s[i].l);
		max[i][1]=std::max(max[i+1][1],(double)s[i].l);
	}
	For(i,l,r-1)
	{
		if (max[i][0]-X<=min[i][0]+X&&max[i+1][1]-X<=min[i+1][1]+X&&max[i][0]-X<=min[i+1][1]+X)
			return 1;
	}
	return 0;
}
int main()
{
	scanf("%d",&n);
	For(i,1,n) scanf("%d%d",&s[i].v,&s[i].l);
	std::sort(s+1,s+1+n,cmp);
	double l=0,r=1e18;
	while ((r-l)>0.001)
	{
		double mid=(l+r)/2;
		if (check(mid)) r=mid;
		else l=mid;
//		printf("?? %lf %lf\n",l,r);
	}
	printf("%.1lf\n",l);
	return 0;
}

F - Parentheses

题目大意：给定一个表达式，先判断这个表达式是否符合C语言语法，再判断这个表达式是否完美（可能有歧义（即括号不够）/括号冗余）

解题思路：使用递归，每次遇到一个括号就进入一次递归。递归函数用于判断当前这组括号内的表达式是否合法&完美

ans用来存括号内部表达式是 不合法/合法但不完美/合法且完美。

最终结合当前表达式内操作数的数量return 当前整个括号的表达式 是不合法/合法但不完美/合法且完美。

罚时情况：一发入魂，哈哈哈哈哈哈哈

参考代码：

查看代码 
 #include
#include
int is_operator(char c)
{
	return c=='+'||c=='-'||c=='*'||c=='/'||c=='%';
}
char s[2000];int now;
int judge(char end)
{
	int ans=2,cnt=0,OK=1;//返回的答案，已经几个操作数，是否准备好分析新的操作数（前面有操作符，或是第一个操作数） ，
	while (1)//一轮循环一个操作数 
	{
		while (s[now]==' ') now++; 
		char ch=s[now];now++; 
		if (ch=='(')
		{
			if (!OK) return 0;
			ans=std::min(ans,judge(')'));
			if (!ans) return 0;
			else OK=0,cnt++; 
		}
		else if (ch==')'||ch=='\0')
		{
			if (ch==end&&!OK) //至少一个操作数 
			{
//				printf("?? %d %d\n",ans,cnt);
				if (cnt==2) return std::min(ans,2);
				else return std::min(ans,1);
			} 
			else return 0;
		}
		else if(is_operator(ch))
		{
			if (OK) return 0;
			OK=1;
		}
		else
		{
			if (!OK) return 0;
			OK=0,cnt++; 
		}
	}
	return 0;
}
int main()
{
	scanf("%[^\r\n]",s);now=0;
	int ans=judge('\0');
	printf("%s\n",ans==0?"error":ans==1?"improper":"proper");
	return 0;
}

J - Starwars

题目大意：太空中有N个星系（序号为0~N-1），星系分为两类：人类控制（H个）/非人类控制，人类在一些人类控制/非人类控制星系上建立了军事基地（M个）。

星系之间通过虫洞连接，虫洞是单向的，有重边和自环。

W个虫洞，每个虫洞从s通向t（0<=s,t<=N-1），有一个证书c（1<=c<=C），虫洞对应的证书与两端星系或其他边无关。

人类飞船从人类控制星系->军事基地时，每经过一个虫洞要收集该虫洞对应的证书，到达军事基地时通过证书序列证明自己是从人类控制星系来的。

外星间谍尝试从某非人类控制星系->某个军事基地Bi（中途可经过人类控制星系），要求证书序列和某人类控制星系->某个军事基地Bj的证书序列相同。(Bi可不等于Bj)

数据范围：1<=N<=1000,1<=W<=8000，1<=C<=20，1<=H<=N，1<=M<=N

解题思路：注意到可以用一个点对表示当前人类飞船的位置和外星间谍的位置，由于1<=N<=1000，点对最多只有1e6个。

对于(a,b)和(c,d)，如果a->c和b->d的证书相同，则连边。枚举a->c和b->d，则新图中最多有M2=6.4e7条边。

起点可以说所有(a,b)，其中a是人类控制星系，b是非人类控制星系。

终点为任意(a,b)，其中a,b都是军事基地。

罚时情况：考试时时间不够了，没想出做法也来不及做，害

参考代码：

查看代码 
 #include
#include
#include
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N=1100;
const int M=8100;
int n,w,c,h,m,humen_control[N],military[N];
struct Edge
{
	int s,t,c;
}e[M];
std::vector To[N*N];
int vis[N*N];
std::queue Q;
int id(int x,int y)
{
	return (x-1)*n+y;
}
int check(int id)
{
	int a=(id+n-1)/n;
	int b=id-(a-1)*n;
//	printf("?? %d %d %d\n",id,a,b);
	return military[a]&&military[b];
}
int BFS()
{
	while (!Q.empty()) Q.pop();
	For(i,1,n) For(j,1,n) if (humen_control[i]&&!humen_control[j]) 
		Q.push(id(i,j)),vis[id(i,j)]=1;
	while (!Q.empty())
	{
		int u=Q.front();Q.pop();
		if (check(u)) return 1;
		For(i,0,(int)To[u].size()-1) if (!vis[To[u][i]])
			Q.push(To[u][i]),vis[To[u][i]]=1;
	}
	return 0;
}
int main()
{
	scanf("%d%d%d%d%d",&n,&w,&c,&h,&m);
	For(i,1,h) 
	{
		int x;scanf("%d",&x);x++;
		humen_control[x]=1;
	}
	For(i,1,m) 
	{
		int x;scanf("%d",&x);x++;
		military[x]=1;
	}
	For(i,1,w) scanf("%d%d%d",&e[i].s,&e[i].c,&e[i].t),e[i].s++,e[i].t++;
	For(i,1,w) For(j,1,w) if (e[i].c==e[j].c)
		To[id(e[i].s,e[j].s)].push_back(id(e[i].t,e[j].t));
	printf("%s\n",BFS()?"YES":"NO");
	return 0;
 }
ACM系列

相关

标签