[NOIP2018模拟赛10.25]瞎搞报告

闲扯

最近有点颓,都修到好晚,早上起来和吔shi一样难受

忍着困意把题面看完,发现啥也不会,又是一场写暴力的模拟赛

T1发现似乎可以DP,顺手码了个

T2像个最小瓶颈路板子,但是只做过N^2算法的...

T3我是真的傻,估计全场就我一人以为只能往前跳于是写了个DP

结果30+35+0

然后发现T1爆了,后面都输出负数，全部用long long 后交了发,居然95?!wtf

后面发现最naiive的贪心都有90,这数据比联赛还水啊,后面发现只有一个点的一次询问答案不一样,打个表就A了

T1 colour

T2 graph

一看就发现这种边就是最小瓶颈路(边),根据最小生成树也是最小瓶颈生成树的性质,我们可以在最小生成树上DFS求到所有点对的最小瓶颈路.

但怎么找符合条件的点对?对于L=0的子任务,我们可以在Kruskal过程中每新加入一条边就计算两个联通块大小的乘积,由于我们的边是从小到大排序的,这条新加入的边一定是这两个联通块点对之间的最小瓶颈路

正解使用了Kruskal重构树,不了解的先去学习一下(我也是做这题才学的)

容易发现,两个原树上的点在重构树上的LCA的点权就是两点间的最小瓶颈路长度,这样只需要求一个LCA的时间复杂度就可以得到两点之间的最小瓶颈路

然后运用启发式合并的思路,我们可以枚举原树上的每一条边计算它的贡献,然后进入重构树上对应点相邻的两棵子树中较小的那一棵枚举点,这样就能得到了两个约束条件:一个是DFS序的约束(因为另一个点必须在另一棵较大的子树中),一个是颜色范围的约束

又转化成并不喜闻乐见的二维数点问题,离线+树状数组+二维前缀和即可

然后发现WA了,xxzh大佬说要注意l=0的情况,改后又RE了,交了几发终于A了...不过跑得好慢

其实这题一开始想线段树合并的,但是没有想到启发式合并,晚上有大佬提供线段树合并的思路就是每个联通块维护权值线段树,Kruskal连一条边的时候,进入较小的块枚举然后在另一棵树上线段树查询

这样的话也是两个log

/*

  code by RyeCatcher

*/

inline char gc(){

    static char buf[SIZE],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;

}

template <class T>inline void read(T &x){

    x=0;int ne=0;char c;

    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;

    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;

}

const int maxn=600005;

const int inf=0x7fffffff-10;

int n,m,l,c[maxn],mx_c=0;

struct Nico{

	int x,y,dis;

	bool operator <(const Nico &rhs)const{

		return dis<rhs.dis;

	}

}nico[maxn];

int pa[maxn];

int get(int x){return (pa[x]==x)?(pa[x]):(pa[x]=get(pa[x]));}

int cnt=0,w[maxn<<1],fa[maxn<<1],ch[maxn<<1][2],size[maxn<<1];

int dfn[maxn<<1],tot=0,ed[maxn<<1];

ll sum[maxn<<3],qry[maxn];

inline void add(int x,int d){for(;x<=2*n-1;x+=x&(-x))sum[x]+=d;}

inline ll query(int x){ll tmp=0;for(;x>=1;x-=x&(-x))tmp+=sum[x];return tmp;}

struct QAQ{

	int x,y,d,id;

	bool operator <(const QAQ & rhs)const{

		return (x==rhs.x)?id<rhs.id:x<rhs.x;

	}

}qwq[maxn*25];int num=0;

void pre_dfs(int now){

	int v;

	dfn[now]=++tot,size[now]=1;

	//printf("--%d %d--\n",now,fa[now]);

	if(ch[now][0])pre_dfs(ch[now][0]);

	if(ch[now][1])pre_dfs(ch[now][1]);

	size[now]+=(size[ch[now][0]]+size[ch[now][1]]);

	ed[now]=tot;

	if(now>=1&&now<=n){

		qwq[++num]=(QAQ){c[now],dfn[now],1,0};

		//printf("%d %d\n",dfn[now],c[now]);

	}

	return ;

}

int L,R,LL,RR;

void dfs(int now,int id){

	int v;

	if(ch[now][0])dfs(ch[now][0],id);

	if(ch[now][1])dfs(ch[now][1],id);

	//LL=max(0,c[now]-l),RR=min(c[now]+l,mx_c);

	if(now>n||now<1)return ;

	LL=c[now]-l,RR=c[now]+l;if (!l) RR++;

	qwq[++num]=(QAQ){-inf-1,L-1,1,id};

	qwq[++num]=(QAQ){-inf-1,R,-1,id};

	qwq[++num]=(QAQ){LL,L-1,-1,id};

	qwq[++num]=(QAQ){LL,R,1,id};

	qwq[++num]=(QAQ){RR-1,L-1,1,id};

	qwq[++num]=(QAQ){RR-1,R,-1,id};

	qwq[++num]=(QAQ){inf,L-1,-1,id};

	qwq[++num]=(QAQ){inf,R,1,id};

	//printf("%d %d %d %d %d %d\n",now,L,R,LL,RR,id);

	return ;

}

int main(){

	//freopen("graph19.in","r",stdin);

	FO(graph);

	int x,y,z;

	read(n),read(m),read(l);

	for(ri i=1;i<=n;i++)pa[i]=i,read(c[i]),mx_c=max(mx_c,c[i]);

	for(ri i=n+1;i<=n*2+2;i++)pa[i]=i;

	for(ri i=1;i<=m;i++){

		read(x),read(y),read(z);

		nico[i]=(Nico){x,y,z};

	}

	std::sort(nico+1,nico+1+m);

	cnt=n;

	for(ri i=1;i<=m;i++){

		x=nico[i].x,y=nico[i].y;

		x=get(x),y=get(y);

		if(x==y)continue;

		pa[x]=++cnt,pa[y]=cnt;

		fa[x]=cnt,fa[y]=cnt,ch[cnt][0]=x,ch[cnt][1]=y;

		w[cnt]=nico[i].dis;

		//printf("%d %d()()()\n",cnt,w[cnt]);

		if(cnt==2*n-1)break;

	}

	fa[cnt]=0;

	pre_dfs(cnt);

	//for(ri i=1;i<=cnt;i++)printf("--%d %d %d %d %d %d--\n",i,fa[i],ch[i][0],ch[i][1],dfn[i],ed[i]);

	for(ri i=n+1;i<=cnt;i++){

		x=ch[i][0],y=ch[i][1];

		if(size[x]>size[y])std::swap(x,y);

		L=dfn[y],R=ed[y];

		//printf("**%d %d %d %d\n",i,L,R,w[i]);

		dfs(x,i);

	}

	std::sort(qwq+1,qwq+1+num);

	for(ri i=1;i<=num;i++){

		if(qwq[i].id==0){

			//printf("%d %d\n",qwq[i].y,qwq[i].d);

			add(qwq[i].y,1);

		}

		else{

			//printf("%d %d %lld %d %d\n",qwq[i].id,qwq[i].d,query(qwq[i].y),qwq[i].x,qwq[i].y);

			qry[qwq[i].id]+=qwq[i].d*query(qwq[i].y);

		}

	}//return 0;

	ll ans=0;

	//for(ri i=n+1;i<=cnt;i++)printf("&&&%d %d\n",i,w[i]);

	for(ri i=n+1;i<=cnt;i++){

		//printf("%d %d %d\n",i,qry[i],w[i]);

		ans+=qry[i]*w[i];

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

[NOIP2018模拟赛10.25]瞎搞报告

闲扯

T1 colour

T2 graph

最新文章

热门文章