目录
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 的模板, 只不过细节比较多