POI2018

orz hhw posted @ 2017年11月28日 19:35 in 做题记录 with tags 解题报告 POI , 1908 阅读

T1 Pionek

极角排序，把每个向量都当做x轴正方向，取第一、第二象限的点加起来，判断最大值即可

#include<bits/stdc++.h>
#define N 402020
#define pi acos(-1)
using namespace std;
int n,nn,i,j,x,y;long long sx,sy,an;
struct P{int x,y;double z;}p[N];
bool cmp(P a,P b){return a.z<b.z;}
int main(){
	scanf("%d",&nn);
	for(i=1;i<=nn;i++){
		scanf("%d%d",&x,&y);
		if(x||y)p[++n]=P{x,y,atan2(y,x)};
	}
	sort(p+1,p+n+1,cmp);
	for(i=j=1;i<=n;i++){
		for(p[n+i]=p[i],p[n+i].z+=pi*2;j<i+n&&p[j].z<p[i].z+pi;j++){
			sx+=p[j].x;sy+=p[j].y;
			an=max(an,sx*sx+sy*sy);
		}
		sx-=p[i].x;sy-=p[i].y;
		an=max(an,sx*sx+sy*sy);
	}
	printf("%lld",an);
}

T2 Plan metra

给定$d_{1,i}$和$d_{n,i}$，让你还原一颗$n$个点的树，$n\leq500000$。

可以先把$1$到$n$路径上的点找出，剩下的点搭在这些路径上的点上

具体做法就是找到$a_i+b_i$最小的一些点，按照$a_i$的顺序串起来，剩下的点按$a_i-b_i$找到对应的父亲即可。

注意可能路径上没有点，那么判断一下所有的$|a_i-b_i|$是否相同，并且$|a_i-b_i|>0$即可

#include<bits/stdc++.h>
#define N 505050
using namespace std;
int n,i,u,t,ff,la,a[N],b[N],c[N],vs[N*8];
bool cmp(int x,int y){return a[x]-b[x]<a[y]-b[y]||a[x]-b[x]==a[y]-b[y]&&a[x]<a[y];}
int main(){
	scanf("%d",&n);
	if(n==2)return puts("TAK\n1 2 1"),0;
	for(i=2;i<n;i++)scanf("%d",&a[i]);
	for(i=2;i<n;i++)scanf("%d",&b[i]),c[i]=i;c[n]=n;
	for(i=2;i<n;i++)if(abs(a[i]-b[i])!=abs(a[2]-b[2]))ff=1;
	if(!ff&&a[2]!=b[2]){
		puts("TAK");
		for(i=2;i<n;i++)if(a[i]<b[i])printf("1 %d %d\n",i,a[i]);else printf("%d %d %d\n",i,n,b[i]);
		printf("1 %d %d\n",n,abs(a[2]-b[2]));
		return 0;
	}
	for(u=1e9,i=2;i<n;i++)u=min(u,a[i]+b[i]);
	vs[2000000-u]++;vs[u+2000000]++;b[1]=u;a[n]=u;
	for(i=2;i<n;i++)if(u==a[i]+b[i])if(vs[a[i]-b[i]+2000000]++)return puts("NIE"),0;
	for(i=2;i<n;i++)if(!vs[a[i]-b[i]+2000000])return puts("NIE"),0;
	puts("TAK");la=1;
	sort(c+2,c+n+1,cmp);
	for(i=2;i<=n;i++){
		printf("%d %d %d\n",la,c[i],a[c[i]]-a[la]);
		if(a[c[i]]+b[c[i]]==u)la=c[i];
	}
}

T3 Powod

用最小生成树完成，每个联通块记录最大高度$mx$方案数$an$

考虑连接两个联通块$x$和$y$，高度为$z$时，如果两个联通块不联通，则对于新的联通块来说，方案数为$(an_x+z-mx_x)(an_y+z-mx_y)$，不断合并即可

#include<bits/stdc++.h>
#define N 1001000
#define M 1000000007
#define fr(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n,m,H,x,y,z,t,F[N],an[N],mx[N];
struct P{int z,x,y;}q[N];
bool cmp(P a,P b){return a.z<b.z;}
int G(int x,int y){return x*m-m+y;}
int cal(int z,int x){return ((z-mx[x]+M)%M+an[x])%M;}
int gf(int x){return F[x]==x?x:F[x]=gf(F[x]);}
int main(){
	scanf("%d%d%d",&n,&m,&H);
	fr(i,n)fr(j,m-1)scanf("%d",&x),q[++t]=P{x,G(i,j),G(i,j+1)};
	fr(i,n-1)fr(j,m)scanf("%d",&x),q[++t]=P{x,G(i,j),G(i+1,j)};
	fr(i,n*m)F[i]=i,mx[i]=-1;
	sort(q+1,q+t+1,cmp);
	fr(i,t){
		x=gf(q[i].x);y=gf(q[i].y);z=q[i].z;
		if(x!=y)F[y]=x,an[x]=1ll*cal(z,x)*cal(z,y)%M,mx[x]=z;
	}
	printf("%d",cal(H,gf(1)));
}

T4 Prawnicy

即找$k$个数，使得他们$Y$的最小值减去$X$最大值最大。则将$X$排序，用堆来维护$Y$的值即可。

#include<bits/stdc++.h>
#define N 1001000
using namespace std;
int n,k,i,al,ar,an;
struct P{int x,y,id;}p[N];
bool cmp(P a,P b){return a.x<b.x;}
priority_queue<int,vector<int>,greater<int> >Q;
void cg(int l,int r){if(r-l>an)an=r-l,ar=r,al=l;}
int main(){
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y),p[i].id=i;
	sort(p+1,p+n+1,cmp);
	for(i=1;i<=k;i++)Q.push(p[i].y);
	cg(p[k].x,Q.top());
	for(i=k+1;i<=n;i++){
		if(p[i].y>Q.top())Q.pop(),Q.push(p[i].y);
		cg(p[i].x,Q.top());
	}
	printf("%d\n",an);
	for(i=1;i<=n&&k;i++)if(p[i].x<=al&&p[i].y>=ar)printf("%d ",p[i].id),k--;
}

T5 Ro?norodno

一个$n$行$m$列的矩阵，对于每个$k*k$的子矩阵，求出现颜色的最大个数和总个数。$n,m\leq3000,k\leq min(n,m),a_{i,j}\leq300000$.

每个颜色都是一个矩形，求和就是矩形覆盖，最大个数要差分一下，感觉要大力线段树。。

Small_feed 评论 (0)