正題

---

題目大意

一個理想城市有$n$個塊構成，有以下性質

任意兩個塊之間可以通過其他塊到達

任意兩個塊之間可以不通過其他塊(通過空位)到達

然后求每個塊之間的距離之和。

---

解題思路

我們將橫豎的距離分開計算。

假設現在我們考慮計算豎向的邊的距離，我們將橫向的連續的塊縮成一個點(如下圖)

然后將相鄰的兩個塊連邊，這樣，因為上面的性質那么就能夠保證這樣是一個樹形結構。然后計算每條邊對應這些數對來說總共被走了多少次。也就是對于每條$x?>y$的邊，那么有$(n?siz{e}_y)?siz{e}_y$這么多個點對走過這條邊

然后橫著計算一次豎著計算一次將答案加和即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<map> #define p(x,y) ((x)*n+(y)) #define ll long long using namespace std; const ll N=100100,XJQ=1e9,M=3123656; struct node{ll x,y; }w[N]; struct edge_node{ll to,next; }a[M*2]; map<int,int> bz; ll n,bx,mx,cnt,size[M],ls[M],tot,by,be[M]; long long ans; bool cmp(node x,node y) {return x.x==y.x?x.y>y.y:x.x<y.x;} void adde(ll x,ll y) {if(a[ls[x]].to==y) return;a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dp(ll x,ll fa) {for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa) continue;dp(y,x);size[x]+=size[y];}for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa) continue;ans=(ans+(long long)(size[y]*(n-size[y]))%XJQ)%XJQ;} } void Reset() {sort(w+1,w+1+n,cmp);for(ll i=1;i<=n;i++)bz[p(w[i].x,w[i].y)]=i;for(ll i=n;i>=1;i--){ll x=w[i].x,y=w[i].y;if(be[i]==0){be[i]=i;size[i]=1;for(ll j=i-1;j>=1;j--)if(w[j].y==w[j+1].y+1) be[j]=i,size[i]++;else break;}ll k=bz[p(x+1,y)];if(k)adde(be[k],be[i]),adde(be[i],be[k]);} } int main() {freopen("city.in","r",stdin);freopen("city.out","w",stdout);scanf("%lld",&n);bx=2147483647;by=2147483647;for(ll i=1;i<=n;i++)scanf("%lld%lld",&w[i].x,&w[i].y),bx=min(bx,w[i].x),by=min(by,w[i].y);for(ll i=1;i<=n;i++)w[i].x-=bx-1,w[i].y-=by-1;Reset();dp(be[1],0);swap(bx,by);for(ll i=1;i<=n;i++)swap(w[i].x,w[i].y);tot=0;memset(ls,0,sizeof(ls));memset(be,0,sizeof(be));memset(size,0,sizeof(size));bz.clear();Reset();dp(be[1],0);printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的jzoj3738-[NOI2014模拟7.11]理想城市(city)【树,模型转换】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。