zoj3747 鏈接更多此題參考可以看這個(gè)博客更多dp參考可以看這里題意: 給n個(gè)士兵排隊(duì),每個(gè)士兵三種G、R、P可選,求至少有m個(gè)連續(xù)G士兵,最多有k個(gè)連續(xù)R士兵的排列的種...
zoj3747 鏈接更多此題參考可以看這個(gè)博客更多dp參考可以看這里題意: 給n個(gè)士兵排隊(duì),每個(gè)士兵三種G、R、P可選,求至少有m個(gè)連續(xù)G士兵,最多有k個(gè)連續(xù)R士兵的排列的種...
題目鏈接戳這里 我們?nèi)稳」?jié)點(diǎn)1為樹根,分兩次dfs,第一次求節(jié)點(diǎn)i形成的子樹的距離之和。第二次dfs求節(jié)點(diǎn)i到其它所有節(jié)點(diǎn)的距離和。dfs1:根據(jù)子節(jié)點(diǎn)v的dp求父節(jié)點(diǎn)u的d...
學(xué)習(xí)樹鏈剖分我看過以下博客:樹鏈剖分原理和實(shí)現(xiàn)樹鏈剖分整理總結(jié) 知道大概之后,我以為要多加深記憶的地方:對(duì)于每一個(gè)重兒子,其top必然是其父親的top,并且由于要用其它數(shù)據(jù)結(jié)...
思路:將n個(gè)數(shù)的序列不斷劃分,根節(jié)點(diǎn)是原序列,左子樹是原序列排序后較小的一半,右子樹是另一半。留意,子數(shù)中的元素的相對(duì)位置是和父親序列一樣的,見圖,這部分參考了這個(gè)博客: 首...
題目鏈接戳這里題意:有一個(gè)X*Y的區(qū)域,每塊可能是墻壁‘X'或者是空的'.',或者門'D',每個(gè)空位有1個(gè)人,上下左右4個(gè)方向移動(dòng)要1s,每個(gè)門1秒鐘只能通過一個(gè)人,問所有人...
題目鏈接戳這里整理3道小題立刻睡了。 1-偏差排列 時(shí)間限制:10000ms單點(diǎn)時(shí)限:1000ms內(nèi)存限制:256MB描述如果一個(gè)1~N的排列P=[P1, P2, ... P...
題目鏈接戳這里題意:抽屜里有C種無限數(shù)量的巧克力,取n個(gè)出來放在桌上,若桌上出現(xiàn)了2個(gè)1樣的巧克力,就把這2塊吃掉,問:桌上有m塊巧克力的概率?概率dp問題:令dp[i][j...
題目鏈接戳這里太菜了..覺得這題好難...大意是有n個(gè)按x坐標(biāo)遞增順序給出的一些點(diǎn),如何從最左點(diǎn)走到最右點(diǎn),再從最右點(diǎn)走到最左點(diǎn),路徑總長度最短。要求除最左和最右外每個(gè)點(diǎn)恰好...
題意: 給出數(shù)n, 問用2的冪來湊n,有幾種湊法(取后9位)。 我們令dp[i]意義為:數(shù)字i的湊法總數(shù)。 如果是奇數(shù),直接相當(dāng)于前面的數(shù)字各種湊法序列隨便多插個(gè)1,所以dp...
題目鏈接戳這里 大意是在一條直線上,有N個(gè)從0..N-1編號(hào)的城市,每個(gè)城市之間的道路有最大負(fù)載ai,現(xiàn)在有M張從i城到j(luò)城的運(yùn)貨訂單,假設(shè)每個(gè)城市的貨物無限,問在某一時(shí)刻,...
判斷點(diǎn)是否在線段上、判斷兩條線段是否相交 這里采用向量的解法。有2個(gè)概念:向量的內(nèi)積和外積。內(nèi)積又稱為點(diǎn)積dot product,公式即 a·b = |a||b|cosΘ。 ...
題目傳送門 poj1990題意: 農(nóng)夫的N (N∈[1, 20,000])頭牛參加了"MooFest"之后有了不同程度的耳聾, 現(xiàn)在它們排在一條直線上,每頭牛有2個(gè)屬性值:...
題目鏈接在此題意是給定一個(gè)長度n, 再給一個(gè)[0,n-1]的排列, 可以循環(huán)地將第一個(gè)數(shù)放置序列末尾, 問這樣循環(huán)出來的所有序列中, 最小的逆序數(shù)是多少? 思路: 先求得原序...
Digital Signature Algorithm (DSA)是Schnorr和ElGamal簽名算法的變種,被美國NIST作為DSS(DigitalSignature ...