中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當前位置: 首頁 > news >正文

訪問網(wǎng)站人多的時候很慢是服務(wù)器問題還是帶寬pageadmin建站系統(tǒng)

訪問網(wǎng)站人多的時候很慢是服務(wù)器問題還是帶寬,pageadmin建站系統(tǒng),小店怎么做網(wǎng)站,運維管理平臺LCA(Lowest Common Ancestor) 定義 在樹上取兩點 x,yx,y,他們的 LCA 為距離他們最近的公共祖先。 本章主要講的是倍增求 LCA。 暴力求取 從 xx 開始向上移動到根結(jié)點,并標記沿途結(jié)點。從 yy 開始向上移動到根結(jié)點&#xff0c…

LCA(Lowest Common Ancestor)

定義

在樹上取兩點?x,yx,y,他們的 LCA 為距離他們最近的公共祖先。

本章主要講的是倍增求 LCA。

暴力求取

  1. 從?xx?開始向上移動到根結(jié)點,并標記沿途結(jié)點。
  2. 從?yy?開始向上移動到根結(jié)點,第一個被標記的就是?xx?和?yy?的 LCA。

倍增求 LCA

從任意點對?(x,y)(x,y)?移到?xx?和?yy?的 LCA 的距離可拆分為?22?的冪的和。

若預(yù)處理任意點?xx?移動?22?的冪步所到達的結(jié)點編號,則不超過?\log_2{n}log2?n?次即可找到 LCA。

具體實現(xiàn)

first:預(yù)處理倍增 DP

定義狀態(tài)?dp_{i,j}dpi,j??表示點?ii?向上移動?2^j2j?步到達的結(jié)點編號。

狀態(tài)轉(zhuǎn)移方程:枚舉?jj?從?11?到?\log_2 nlog2?n,dp_{i,j}=dp_{dp_{i,j-1},j-1}dpi,j?=dpdpi,j?1?,j?1?。

初始狀態(tài):dp_{i,0}=fa_idpi,0?=fai?。

代碼片段
void pre_lca(int cur, int fa)
{dep[cur]=dep[fa]+1;dp[cur][0]=fa;for(int i=1;(1<<i)<=dep[cur];i++){dp[cur][i]=dp[dp[cur][i-1]][i-1];}for(int nxt:nbr[cur]){if(nxt!=fa)pre_lca(nxt,cur);}
}
second:處理單次詢問

第一步:約定深度較大的點,若?dep_x>dep_ydepx?>depy?,交換?xx?和?yy。

第二步:將深度較大的結(jié)點?yy?倍增向上跳至深度等于?xx。

第三步:判斷?xx?是否等于?yy。若已經(jīng)相等則?xx?為 LCA,停止尋找。

第四步:xx?和?yy?一起倍增向上跳,只要?xx?和?yy?不重合。

第五步:xx?向上一步即為 LCA。

代碼片段
int lca(int x, int y)
{if(dep[y]<dep[x])swap(x,y);for(int i=20;i>-1;i--){if(dep[dp[y][i]]>=dep[x]){y=dp[y][i];}}if(x==y)return x;for(int i=20;i>-1;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}return dp[x][0];
}

時間復(fù)雜度

預(yù)處理是?O(n \log_2 n)O(nlog2?n)?的,中間單次求取僅為?O(n)O(n)

模板代碼

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[500005][21],dep[500005], n, m, s;
vector<int> nbr[500005];
void pre_lca(int cur, int fa)
{dep[cur]=dep[fa]+1;dp[cur][0]=fa;for(int i=1;(1<<i)<=dep[cur];i++){dp[cur][i]=dp[dp[cur][i-1]][i-1];}for(int nxt:nbr[cur]){if(nxt!=fa)pre_lca(nxt,cur);}
}
int lca(int x, int y)
{if(dep[y]<dep[x])swap(x,y);for(int i=20;i>-1;i--){if(dep[dp[y][i]]>=dep[x]){y=dp[y][i];}}if(x==y)return x;for(int i=20;i>-1;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}return dp[x][0];
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m>>s;for(int i=1;i<n;i++){int x, y;cin>>x>>y;nbr[x].push_back(y);nbr[y].push_back(x);}pre_lca(s,0);for(int i=1;i<=m;i++){int x, y;cin>>x>>y;cout<<lca(x,y)<<"\n";}
}

LCA 應(yīng)用

  1. 求樹上兩點之間距離。
  2. 樹上差分。

LCA 求樹上兩點之間距離

維護?dis_xdisx??表示根結(jié)點到?xx?的距離。

xx?到?yy?的簡單路徑的長度為?dis_x+dis_y-2\times dis_{\texttt{lca}(x,y)}disx?+disy??2×dislca(x,y)?。

LCA 例題

first:P5836

方法 1

點權(quán)可以轉(zhuǎn)為?00?或?11,維護?dis_idisi??表示由根結(jié)點到?ii?的距離。

維護深度?dep_idepi?,對于每次詢問,若?(dis[a]+dis[b]-2*dis[lcad]+w[lcad]==dep[a]+dep[b]-2*dep[lcad]+1)&&c!='H'?或?dis[a]+dis[b]-2*dis[lcad]+w[lcad]==0&&c=='H'?則輸出?00,否則輸出?11。

方法 2

若一條邊的兩個端點的?ww?相同,則?unionn?這兩個端點。

若一條路徑上點權(quán)相同,則兩個端點一定在同一集合。若該集合的權(quán)值不等于詢問,輸出?00,否則輸出?11。

while(m--)
{int x, y;char c;cin>>x>>y>>c;if(c=='H'){cout<<!(find(x)==find(y)&&w[x]==0);}else{cout<<!(find(x)==find(y)&&w[x]==1);}
}
方法 3

維護?dp_{i,j}dpi,j??表示?ii?向上動?2^j2j?步到達的結(jié)點編號,維護?yes_{i,j,0/1}yesi,j,0/1??表示?ii?向上跳?2^j2j?步是否有?ww?為?0/10/1?的點。

yes[cur][i][0]=yes[cur][i-1][0]|yes[dp[cur][i-1]][i-1][0],yes[cur][i][1]=yes[cur][i-1][1]|yes[dp[cur][i-1]][i-1][1];。

初始狀態(tài):dp_{i,0}=fa_idpi,0?=fai?,yes_{i,0,w_{fa}}=1yesi,0,wfa??=1。

second:CF519E

若?AA?到?BB?的距離為奇數(shù),則答案直接為?00。

否則分情況討論:

  1. 中間位置的點?x=lcax=lca

    xx?兒子結(jié)點中包含?AA?和?BB?的子樹剔除,其余為答案。

  2. 中間位置的點?xx?不是?lcalca

    約定深度較大的點為?BB,找到?BB?向上距離?xx?一步的點?pp,則答案為?size_x-size_psizex??sizep?。

注意特殊情況:A==BA==B?時,答案為?nn。

從?lcalca?到?xx?的距離為?\frac{dep_B-dep_A}{2}2depB??depA??。

void work(int x,int y)
{if(x==y){cout<<n<<"\n";return ;}if(dep[x]==dep[y]){for(int i=14;i>=0;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}cout<<size[1]-size[x]-size[y]<<"\n";return  ;}if(dep[x]<dep[y]) swap(x,y);if((dep[x]-dep[y])%2==1){cout<<"0\n";return ;}int x2=x,len=(dep[x]-dep[y])/2;for(int i=14;i>=0;i--){if(dep[dp[x][i]]>=dep[y]){x=dp[x][i];}}if(x==y){len+=dep[x];for(int i=14;i>=0;i--){if(dep[dp[x2][i]]>len){x2=dp[x2][i];}}cout<<size[dp[x2][0]]-size[x2]<<"\n";return ;}for(int i=14;i>=0;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}len+=dep[x]-1;for(int i=14;i>=0;i--){if(dep[dp[x2][i]]>len){x2=dp[x2][i];}}cout<<size[dp[x2][0]]-size[x2]<<"\n";
}

Third:P8972 一切都已過去

見?題解:P8972 『GROI-R1』 一切都已過去 - 洛谷專欄

方便閱讀搬過來。

從數(shù)據(jù)范圍很容易發(fā)現(xiàn),如果我們把邊權(quán)累乘再判整數(shù),炸掉是必然的,這時候,我們來發(fā)現(xiàn)一個性質(zhì):只有小數(shù)部分有?22?和?55?相乘的時候,才可能變成整數(shù)。當然,這并不是絕對的,例如?2.02 \times 52.02×5?就不是整數(shù)。從上面舉的例子很容易發(fā)現(xiàn)一個性質(zhì):兩個實數(shù)的乘積是否為整數(shù)與小數(shù)點數(shù)位也有關(guān)系。一對?22?和?55?可以抵消掉一個小數(shù)點數(shù)位(22?和?55?可以在任意且不同數(shù)位上,并且?22?和?55?的倍數(shù)也有用)。這時,我們可以將邊權(quán)通過不斷?\times 10×10?變成整數(shù),并分解質(zhì)因數(shù)分別求因數(shù)中?22?和?55?的個數(shù)(點權(quán)也要處理)。22?和?55?的個數(shù)求出來了,小數(shù)點數(shù)位也很好處理。最終的小數(shù)點位數(shù)應(yīng)該是所有路徑上的邊權(quán)小數(shù)點位數(shù)之和,所以我們在將邊權(quán)化整數(shù)時再維護一個變量統(tǒng)計小數(shù)點位數(shù)并記錄到鄰接矩陣里。若路徑?xx?到?yy?的總邊權(quán)乘上?xx?的點權(quán)得到的結(jié)果中?22?的個數(shù)和?55?的個數(shù)大于或等于總小數(shù)點位數(shù),則其為整數(shù)。分別維護即可。

注意:若邊權(quán)或點權(quán)為?00?則對應(yīng)維護的當前點權(quán)或點權(quán)的?22?和?55?賦予極大值。

Latex有雙倍問題,完整版請在安全訪問中心 - 洛谷查看

http://www.risenshineclean.com/news/53845.html

相關(guān)文章:

  • 襄陽做網(wǎng)站公司電話簡單的html網(wǎng)頁制作
  • 新鄉(xiāng)谷雨網(wǎng)絡(luò)公司做的網(wǎng)站怎么樣seo外鏈要做些什么
  • Wordpress做APP后端徐州關(guān)鍵詞優(yōu)化排名
  • 武漢通官網(wǎng)網(wǎng)站建設(shè)如何用手機免費創(chuàng)建網(wǎng)站
  • oa系統(tǒng)品牌seo效果檢測步驟
  • 紅色企業(yè)網(wǎng)站源碼整站優(yōu)化系統(tǒng)
  • 許昌建設(shè)網(wǎng)站哪家好關(guān)鍵詞提取工具app
  • 什么做網(wǎng)站開發(fā)漣源網(wǎng)站seo
  • 越秀移動網(wǎng)站建設(shè)怎么在百度上發(fā)布廣告
  • 做免費推廣的網(wǎng)站有哪些如何出售自己的域名
  • 買CAD設(shè)計圖做的網(wǎng)站怎么投稿各大媒體網(wǎng)站
  • 裝修素材的網(wǎng)站大全搜索引擎營銷的6種方式
  • 北京新站優(yōu)化國內(nèi)永久免費建站
  • 網(wǎng)站建設(shè)屬于前端還是后臺今日小說百度搜索風(fēng)云榜
  • 自己做淘客網(wǎng)站成本大嗎廣告公司怎么找客戶資源
  • 網(wǎng)站頂部小圖標怎么做品牌推廣與傳播方案
  • 網(wǎng)站建設(shè)管理 優(yōu)幫云東莞建設(shè)企業(yè)網(wǎng)站
  • 給別人做的網(wǎng)站涉及到詐騙投稿網(wǎng)站
  • 大良做網(wǎng)站網(wǎng)頁制作作業(yè)100例
  • 北京西站到八達嶺長城最快路線上海優(yōu)化關(guān)鍵詞的公司
  • a做爰網(wǎng)站網(wǎng)店運營基礎(chǔ)知識
  • 廊坊哪里能夠做網(wǎng)站正規(guī)seo排名多少錢
  • 網(wǎng)站開發(fā)語言查詢 蔡學(xué)鏞網(wǎng)絡(luò)營銷方法和手段
  • 網(wǎng)站更新seo看seo
  • 建設(shè)河南分行網(wǎng)站網(wǎng)站seo快速
  • 網(wǎng)站制作主題如何檢測網(wǎng)站是否安全
  • 做網(wǎng)站要求高嗎百度手機版
  • wordpress縮略圖thumb貴州seo技術(shù)查詢
  • 貿(mào)易公司寮步網(wǎng)站建設(shè)哪家好友情鏈接出售平臺
  • 貴陽網(wǎng)站制作策劃無錫網(wǎng)站seo