摘要: 兩個凸多邊形的交
閱讀全文
摘要: 我的做法是，對于每條新邊，記錄樹中與之對應的路徑。然后對于每條樹邊，統計被對應的次數。最后記錄每個點到樹根的路徑上，有多少個1（設為q[i]）。對于新邊(x,y)，它對答案的貢獻就是q[x] + q[y] - 2q[lca(x,y)]。除了這些，答案還應加上樹中0邊的數量 * m。
閱讀全文
摘要: 經典的DP，把環斷開，f[i][j][0]記錄i到j的最小值，f[i][j][1]記錄最大值，然后遞推計算。記錄最小值是因為兩個負數乘起來可能得到一個大的正數。
閱讀全文
摘要: 概率+DP，比較經典的題。按照遞推的方式計算概率。
閱讀全文
摘要: 詳情見內
閱讀全文
摘要: 簡單的幾何題，先把經緯度換算成球面坐標，再把球面坐標換算成直角坐標，然后求夾角，乘半徑得到球面距離
閱讀全文
摘要: 我的做法是，枚舉第一個多邊形的第i條邊和第二個多邊形的第j條邊重合，然后從這條重合的邊開始，盡可能的向后擴展重合邊，然后判斷剩下的多邊形是否是凸多邊形。
比賽的時候，我在某個地方忘記對多邊形點數求模，導致wa了很久，一直到比賽結束后才AC。以此為鑒！
閱讀全文
摘要: 聽著很有感覺：）于是找了歌詞翻譯
閱讀全文
摘要: 經典的狀態壓縮DP，狀態是f[i][j]，表示第i行，以3進制j為狀態。j的位代表一個格子，只能是：0表示第i行和第i - 1行都沒有炮兵，1表示第i行沒有炮兵而第i-1行有炮兵，2表示第i行有炮兵。然后用DFS進行狀態轉移。一開始我做了超時，后來預處理了一下合法狀態，快了不少，才AC。
閱讀全文
摘要: 今天郁悶了，貼個小代碼
閱讀全文