目錄
P2523 [HAOI2011]Problem c [ DP + 組合數學 ]
[CQOI2014]數三角形 [ 組合數學 ]
P2606 [ZJOI2010]排列計數 [ DP + 組合數學 ]
P2962 [USACO09NOV]燈Lights [ 高斯消元 + dfs ]
JSOI2012 始祖鳥 [高斯消元]
P2474 [SCOI2008]天平 [差分限制]
P3281 [SCOI2013]數數 [稍難的數位DP]
P4130 [NOI2007]項鍊工廠 [Splay]
P3288 [SCOI2014]方伯伯運椰子 [ 分數規劃+spfa ]
P3280 [SCOI2013]機車交易 [貪心 + Kruskal重構樹]
P2523 [HAOI2011]Problem c [ DP + 組合數學 ]
我們令 s[i] 為 i 後方已經确定的個數, 顯然如果 s[i] > n - i + 1 就是不合法的
考慮用DP統計答案, f[i][j] 表示i後方确定了j個的方案數, 我們枚舉k個, 将後面j個中的k個放到i, 于是有方程
[CQOI2014]數三角形 [ 組合數學 ]
很明顯用全部個數 - 不合法
對于不合法的情況, 我們枚舉一條線段 (0, 0) -- (x, y), 顯然中間的個數為gcd(x,y) - 1
然後将這條線段移動, 移動範圍就是(n-x+1) * (m-y+1) , 根據對稱性 * 2 減掉就可以了
P2606 [ZJOI2010]排列計數 [ DP + 組合數學 ]
題意 : 求n個點構成的大根堆個數
f[i] 表示 編号為i的點的個數, siz[i] 表示大小, 考慮轉移
對于左兒子的任意一種構造, 右兒子的任意一種構造, 都可以從siz[i] - 1 個數中 選siz[l]個填到左兒子
P2962 [USACO09NOV]燈Lights [ 高斯消元 + dfs ]
構造異或方程, 先消元, 對于不定的元dfs就可以了
JSOI2012 始祖鳥 [高斯消元]
選0 表示上遊, 選1 表示下遊
對于出度為偶數的點, 不管它是什麼, 隻有選偶數個點(無論0/1)就可以了
對于出度為奇數的點, 如果它選0, 就要求有偶數個0, 奇數個1, 它選1, 就要求有奇數個0, 偶數個1
構造出異或方程組過後高斯消元 (可以用bitset)
P2474 [SCOI2008]天平 [差分限制]
我們令Min[x][y] 表示x比y最少重多少, Max表示最多重多少
P3281 [SCOI2013]數數 [稍難的數位DP]
P4130 [NOI2007]項鍊工廠 [Splay]
Splay 的模闆, 隻不過細節比較多