摘要: 兩個凸多邊形的交

  閱讀全文      摘要: 我的做法是，對于每條新邊，記錄樹中與之對應(yīng)的路徑。然后對于每條樹邊，統(tǒng)計被對應(yīng)的次數(shù)。最后記錄每個點到樹根的路徑上，有多少個1（設(shè)為q[i]）。對于新邊(x,y)，它對答案的貢獻就是q[x] + q[y] - 2q[lca(x,y)]。除了這些，答案還應(yīng)加上樹中0邊的數(shù)量 * m。

  閱讀全文      摘要: 經(jīng)典的DP，把環(huán)斷開，f[i][j][0]記錄i到j(luò)的最小值，f[i][j][1]記錄最大值，然后遞推計算。記錄最小值是因為兩個負數(shù)乘起來可能得到一個大的正數(shù)。

  閱讀全文      摘要: 概率+DP，比較經(jīng)典的題。按照遞推的方式計算概率。

  閱讀全文      摘要: 詳情見內(nèi)

  閱讀全文      摘要: 簡單的幾何題，先把經(jīng)緯度換算成球面坐標(biāo)，再把球面坐標(biāo)換算成直角坐標(biāo)，然后求夾角，乘半徑得到球面距離

  閱讀全文      摘要: 我的做法是，枚舉第一個多邊形的第i條邊和第二個多邊形的第j條邊重合，然后從這條重合的邊開始，盡可能的向后擴展重合邊，然后判斷剩下的多邊形是否是凸多邊形。
比賽的時候，我在某個地方忘記對多邊形點數(shù)求模，導(dǎo)致wa了很久，一直到比賽結(jié)束后才AC。以此為鑒！

  閱讀全文      摘要: 聽著很有感覺：）于是找了歌詞翻譯

  閱讀全文      摘要: 經(jīng)典的狀態(tài)壓縮DP，狀態(tài)是f[i][j]，表示第i行，以3進制j為狀態(tài)。j的位代表一個格子，只能是：0表示第i行和第i - 1行都沒有炮兵，1表示第i行沒有炮兵而第i-1行有炮兵，2表示第i行有炮兵。然后用DFS進行狀態(tài)轉(zhuǎn)移。一開始我做了超時，后來預(yù)處理了一下合法狀態(tài)，快了不少，才AC。

  閱讀全文      摘要: 今天郁悶了，貼個小代碼

  閱讀全文