雅礼集训2018选做()

D1T1 树

首先我们设 \(f_{i,j}\) 表示点数和深度固定的方案数,然后我们尝试转移。按照我之前的思路我会只关注其儿子,会再设一个 \(g\) 表示森林的方案数,但是这题有一个更为高妙的具有启发性的转移做法:合并两棵树。同时我们注意到2点只会连1点,所以组合数也很好处理。

Code

D2T3 操作

首先我们差分,这样就是间隔为 \(k\) 的点同时改,然后你就可以 \(pos \bmod k\) 来干一些事( 然而我居然想不到取模 )。发现一个区间有解的充要条件是这个区间里所有 \(\bmod k\) 相同点1个数为偶数(注意到把它当成一个序列来看,还需要对两边的节点置为0,这个在稍后求解需要反转一个前缀会给我们带来一些麻烦)。求解的话你发现它若干间隔长度相加,可以这样前缀和 \(sum_i=i-sum_{i-1}\) 。

Code

D4T2 Divide

这道题非常考察性质的发掘能力。

我们肯定要对 \(w\) 排序,然后我们可以轻松得出一下结论:若 \(w_1+w_n \ge a\) 则不管 \(w_i\) 放哪组之后另一组每一个数都和他有联系;反之则 \(w_1\) 带不来任何贡献。(好理解是好理解,但是真的很难发现这种结论有用)这样的话我们就可以通过设 \(f_{i,j}\) (剩 \(i\) 个数,有 \(j\) 个在 A 组)来表示所有方案。

Code

————————

D1T1 树

首先我们设 \(f_{i,j}\) 表示点数和深度固定的方案数,然后我们尝试转移。按照我之前的思路我会只关注其儿子,会再设一个 \(g\) 表示森林的方案数,但是这题有一个更为高妙的具有启发性的转移做法:合并两棵树。同时我们注意到2点只会连1点,所以组合数也很好处理。

Code

D2T3 操作

首先我们差分,这样就是间隔为 \(k\) 的点同时改,然后你就可以 \(pos \bmod k\) 来干一些事( 然而我居然想不到取模 )。发现一个区间有解的充要条件是这个区间里所有 \(\bmod k\) 相同点1个数为偶数(注意到把它当成一个序列来看,还需要对两边的节点置为0,这个在稍后求解需要反转一个前缀会给我们带来一些麻烦)。求解的话你发现它若干间隔长度相加,可以这样前缀和 \(sum_i=i-sum_{i-1}\) 。

Code

D4T2 Divide

这道题非常考察性质的发掘能力。

我们肯定要对 \(w\) 排序,然后我们可以轻松得出一下结论:若 \(w_1+w_n \ge a\) 则不管 \(w_i\) 放哪组之后另一组每一个数都和他有联系;反之则 \(w_1\) 带不来任何贡献。(好理解是好理解,但是真的很难发现这种结论有用)这样的话我们就可以通过设 \(f_{i,j}\) (剩 \(i\) 个数,有 \(j\) 个在 A 组)来表示所有方案。

Code