2018_9_23 模拟賽

今日比賽

• 前言：
• JZOJ 5775 農夫約的假期
• • 題目
• 分析
• 代碼
• JZOJ 5776 小x遊世界樹
• • 題目
  • 分析
  • 代碼
• JZOJ 5786 觀察
• • 題目
  • 分析
  • 代碼
• 後續

前言：

感覺自己越來越渺小了

JZOJ 5775 農夫約的假期

題目

在一個平面，有 n n n個點，找出一個點使 n n n個點到該點的曼哈頓距離 ( ∑ a b s ( x i − x j ) + a b s ( y i + y j ) ) (\sum abs(x_i-x_j)+abs(y_i+y_j)) (∑abs(xi​−xj​)+abs(yi​+yj​))和最短

分析

顯然，這道題講到這裡，那麼可以發現中位數就是最優的

。All in all，就講完了

代碼

#include <cstdio>
    #include <algorithm>
    #define rr register
    using namespace std;
    int m,x[100001],y[100001];long long ans;
    inline int in(){
    	rr int ans=0; rr char c=getchar();
    	while (c<48||c>57) c=getchar();
    	while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
    	return ans;
    }
    int main(){
    	in(); m=in(); in(); rr int mid=m+1>>1;
    	for (rr int i=1;i<=m;i++) x[i]=in(),y[i]=in(),ans+=in();
    	nth_element(x+1,x+mid,x+1+m);//求第mid大
    	nth_element(y+1,y+mid,y+1+m);	
        for (rr int i=1;i<=m;i++) ans+=abs(x[i]-x[mid])+abs(y[i]-y[mid]);//計算曼哈頓距離
    	return !printf("%lld\n%d %d",ans,x[mid],y[mid]);
    }
           

JZOJ 5776 小x遊世界樹

題目

在一棵樹上重新找一個根，使根到各點的距離最短

分析

其實這道題可以說是近乎暴力，但是關于找根可以用二次掃描換根法，感性了解，代碼才是最有力的解釋工具

代碼

#include <cstdio>
    #define rr register
    struct node{int y,w,next;}e[1400011];
    int n,son[700001],ls[700001],k=1,ans1=1;long long ans;
    inline int in(){
    	rr int ans=0; rr char c=getchar();
    	while (c<48||c>57) c=getchar();
    	while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
    	return ans;
    }
    inline void add(int x,int y){
    	rr int w=in();
    	e[++k]=(node){y,w-son[x],ls[x]}; ls[x]=k;
    	e[++k]=(node){x,w-son[y],ls[y]}; ls[y]=k;
    }
    inline void dp(int x,int fa,long long sum){
    	for (rr int i=ls[x];i;i=e[i].next)
    	if (e[i].y!=fa)	dp(e[i].y,x,sum+e[i].w),son[x]+=son[e[i].y];
    	ans+=sum; son[x]++;
    }
    inline void dfs(int x,int fa,long long sum){
    	for (rr int i=ls[x];i;i=e[i].next)
    	if (e[i].y!=fa) dfs(e[i].y,x,sum+(n-son[e[i].y])*e[i^1].w-son[e[i].y]*e[i].w);
    	if (sum<ans||sum==ans&&ans1>x) ans1=x,ans=sum;
    }
    int main(){
    	n=in();
    	for (rr int i=1;i<=n;i++) son[i]=in();
    	for (rr int i=1;i<n;i++) add(in(),in());
    	for (rr int i=1;i<=n;i++) son[i]=0;
    	dp(1,0,0); dfs(1,0,ans);
    	return !printf("%d\n%lld",ans1,ans);
    }
           

JZOJ 5786 觀察

題目

求離目前點LCA最深的編号（可能會被修改）

分析

這道題也就是求歐拉序的前驅和該點，和後繼，可以用線段樹維護，然後求深度更大的點的編号

代碼

#include <cstdio>
    #include <cstring>
    #define rr register
    #define f(i,a,b) for (rr int i=a;i<=b;++i)
    #define min(a,b) ((a)<(b)?(a):(b))
    #define max(a,b) ((a)>(b)?(a):(b))
    #define N 800005
    bool v[N],op; int top,dep[N],ne[N],ls[N],sta[N],ola[N],rk[N],st[N],dfn[N],son[N];
    int n,q,bas=1,tot,father[N],minx[2100001],maxx[2100001]; char buf[1<<13],*p1,*p2;
    inline int in(bool &op){
    	rr int ans=0; rr char c=getchar();
    	while ((c<48||c>57)&&c!='-') c=getchar();
    	if (c=='-') op=1,c=getchar();
    	while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
    	return ans;
    }
    inline void print(int ans){
    	if (ans>9) print(ans/10);
    	putchar(ans%10+48);
    }
    inline int lca(int x,int y){
    	while (son[x]!=son[y]) if (dep[son[x]]>dep[son[y]]) x=father[son[x]]; else y=father[son[y]];
    	return dep[x]<dep[y]?x:y;
    }
    signed main(){
    	n=in(op); q=in(op); while ((bas<<=1)<n+2); bas--;
    	f(i,2,n) father[i]=in(op); dep[1]=1;
    	f(i,2,n) ne[i]=ls[father[i]],ls[father[i]]=i;
    	f(i,1,n) sta[i]=ls[i]; st[top=1]=1;
    	while (top){//第一次深搜求深度和子樹大小以及通過子樹大小求歐拉序
    		rr int x=st[top];
    		if (!dfn[x]) son[rk[dfn[x]=++tot]=x]=1;
    		if (sta[x]){
    			st[++top]=sta[x];
    			dep[sta[x]]=dep[x]+1;
    			sta[x]=ne[sta[x]];
    			continue;
    		}
    		son[st[--top]]+=son[x];
    		if (son[ola[st[top]]]<son[x]) ola[st[top]]=x,v[st[top]]=1;
    	}
    	f(i,1,n) sta[i]=ls[i],son[i]=0;
    	st[top=1]=1; rr int ST=1;
    	while (top){//現在的son表示的已經是倍增的祖先了
    		rr int x=st[top];
    		if (!son[x]) son[x]=ST;
    		if (v[x]){
    			v[x]=0,st[++top]=ola[x];
    			continue;
    		}
    		if (sta[x]==ola[x]) sta[x]=ne[sta[x]];
    		if (sta[x]){
    			ST=st[++top]=sta[x];
    			sta[x]=ne[sta[x]];
    			continue;
    		}
    		top--;
    	}
    	f(i,1,(bas<<1|1)) minx[i]=n+1,maxx[i]=0;//zkw線段樹初始化
    	while (q--){
    		rr int x=in(op=0),y=dfn[x]+bas;//跳到葉子節點
    		if (op){
    			rr int ans;
    			if (minx[y]==y-bas) ans=x;//直接找到答案
    			else{
    				rr int l=0,r=n+1;
    				for (rr int i=y>>1;i;y=i,i>>=1) if (i<<1==y) r=min(r,minx[y^1]); else l=max(l,maxx[y^1]);//查找前驅和後繼
    				if (l) l=lca(rk[l],x);
    				if (r<=n) r=lca(x,rk[r]);
    				ans=dep[l]<dep[r]?r:l;//深度更深
    			}
    			if (ans) print(ans); else putchar(48); putchar(10);
    		}
    		else{
    			if (minx[y]==y-bas) minx[y]=n+1,maxx[y]=0; else minx[y]=maxx[y]=y-bas;//修改該點的最小值和最大值
    			for (rr int i=y>>1;i;y=i,i>>=1) minx[i]=min(minx[y],minx[y^1]),maxx[i]=max(maxx[y],maxx[y^1]); //單點修改
    		}
    	}
    	return 0;
    }
           

後續