[CQOI2011] 放棋子
因为不同颜色的棋子不能在同一行或同一列,所以可以将不同颜色的棋子分开来考虑。
对于每一种颜色,转移时用总方案数减去不合法的方案数,也就是存在行或列没有棋子的方案数。
最后再把每种颜色合并起来即可。
[AGC043D] Merge Triplets
让我们考虑什么样的排列 \(P\) 是能被构造出来的。
可以得出一个性质,排列 \(P\) 中不存在连续的 \(4\) 个整数满足 \(P_{i}>P_{i+1}>P_{i+2}>P_{i+3}\)。
也就是说,若我们按照前缀 max 来划分序列,那么没有一段的长度会大于 \(3\),并且每一段一定是被同时接上来的。
但这并不充分,我们还需要保证长度为 \(2\) 的段数量不大于长度为 \(1\) 的段。
因为我们在构造序列 \(P\) 时,要么是直接接上一个长度为 \(3\) 的段,要么是接上一个长度为 \(2\) 的段再接上一个长度为 \(1\) 的段,或者干脆直接接上三个长度为 \(1\) 的段。这样子长度为 \(1\) 的段的个数不会少于长度为 \(2\) 的段的个数。
所以,我们设 \(f_{i,j}\) 表示考虑了前 \(i\) 个数,其中长度为 \(1\) 的段的个数减去长度为 \(2\) 的段的个数为 \(j\) 的方案数。
转移是平凡的。
时间复杂度 \(O(n^2)\)。
[AGC059C] Guessing Permutation for as Long as Possible
让我们考虑三个数 \(a,b,c\),若我们想要 \(a\) 和 \(c\) 的关系在最后被得出,就必须得保证 \(b\) 不在 \(a,c\) 之间。
不然我们总可以从 \(a,b\) 和 \(b,c\) 的关系来推出 \(a,c\) 的关系。
所以我们可以用 2-sat 或者并查集来维护每个数之间的关系。
每一个连通块之间的关系可以唯一确定一个排列,所以设连通块个数为 \(k\),答案就为 \(2^k\)。
[ARC117C] Tricolor Pyramid
我们给每种颜色赋上一个数 \(0,1,2\)。
我们可以发现,对于一个颜色为 \(k\) 的积木,若它下面的两块积木颜色分别为 \(i,j\),那么 \(k=-(i+j)\bmod 3\)。
可以发现最下面积木对对最顶层积木贡献的形式就是杨辉三角。
可以用卢卡斯定理来求组合数。
[AGC035D] Add and Remove
每删除一个数,这个数就会对它左边和右边的数造成贡献。
其中,第 \(1\) 个数和第 \(n\) 个数不会被删除,我们不用考虑它。
考虑从最后一个被删除的数开始 dp,设 \(dp[l][r][ls][rs]\) 表示现在的区间是 \([l,r]\) 其中会对左边的数贡献 \(ls\) 次,对右边的数贡献 \(rs\) 次。
那么有 \(dp[l][r][ls][rs]=\min(dp[l][i-1][ls][rs+ls]+dp[i+1][r][ls+rs][rs]+(ls+rs)\cdot a[i])\)。
直接暴力 dfs 的时间复杂度 \(O(3^n)\),实际上 \(n\) 只有 \(16\)。
[EGOI 2022] Lego Wall
积木有两种,分别是 \(1\times 1\) 的和 \(1\times 2\) 的。
可以发现,若两列是联通的,当且仅当这两列之间存在一个 \(1\times 2\) 的积木。
由此,我们可以设计出一个 \(wh^2\) 的 dp,设 \(f_{i,j}\) 表示目前在第 \(i\) 列且这一列的 \(1\times 2\) 的积木数量为 \(j\)。
那么有转移 \(f_{i,j}=\sum_{k=1}^{h} f_{i-1,k}\times C_{h-k}^{j}\)。
但 \(O(wh^2)\) 的复杂度无法通过此题。
注意到 \(wh\le 5\cdot10^5\),考虑另外一种做法。
刚才我们是一列一列的来考虑,现在我们一行一行的来考虑。
对于单独的一行,它的方案数为 \(f_{i}\),有 \(f_{i}=f_{i-1}+f_{i-2}\) 也就是斐波拉契数列。若我们先不考虑联通的限制,那么对于所有的 \(h\) 行来说,就有 \(F_i=f_i^h\) 种方案。
同时,我们设 \(g_i\) 表示前 \(i\) 列都联通的方案数,转移可以用容斥,那么有 \(g_i=F_i-\sum_{k=1}^w g{k}\times F_{w-k}\)。
时间复杂度为 \(O(w^2)\)。
我们只需要将上述的两种做法合在一起就行了。
平衡过后的复杂度为 \(O(w^{\frac{4}{3}})\)。
待补
- [AGC036F] Square Constraints
- [AGC058D] Yet Another ABC String