[8.3] Code Source - [meow ~ meow ~ meow~] [tree] [and]

#865. 喵 ~ 喵 ~ 喵~

题意：有 $m(1\le m\le 10^5)$ 次操作,每次操作：如果 $op=1$ ,Is added in the weight set is an interval $[l,r](1\le l\le r\le 10^5)$ ;如果 $op=2$ ,Is given a range $[l,r](1\le l\le r\le 10^5)$ ,How many q collection and a given interval intersect.

思路：This problem has a more classic solution.假设当前有 $m$ 个区间 ,给定区间 $[L,R]$ ,The fellowship with the given interval of the interval number is ：左端点在 $R$ On the left side of the interval number 减去 右端点在 $L$ On the left side of the interval number,即 ${\sum }_{i=1}^m[l_i\le R]-{\sum }_{i=1}^m[r_i<L]$ .Because the left endpoint in $R$ 左边的区间,If you don't intersect with the given interval,Is necessarily right endpoints in $L$ 左边.

Then how is open two tree array,一个维护 $\{l\}$ 一个维护 $\{r\}$ ,就可以了.

AC代码：http://oj.daimayuan.top/submission/317153

---

#154. 树

题意：有一棵 $n(1\le n\le 3000)$ 个节点的以 $1$ 为根的有根树.现在可以对这棵树进行若干次操作,每一次操作可以选择树上的一个点然后删掉这个点和它的儿子之间的所有边.

现在想要知道对于每一个 $k\in [1,n]$ ,最少需要多少次操作才能让图中恰好存在 $k$ 个联通块.

思路：Initial connecting piece number for $1$ ,定义 $siz(i)$ 表示点 $i$ How many sons,如果删去 $i$ Son to the side of the connecting block number will increase $siz(i)$ .

那么问题就转化成了 01 背包问题：背包体积上限为 $k(k\in [1,n])$ ,每个物品只有一个,体积为 $siz(i)$ ,价值为 $1$ ,Asked to fill a backpack $k$ A volume of the minimum value.

AC代码：http://oj.daimayuan.top/submission/317187

---

#155. 与

题意：给定 $n,k(1\le n,k\le 10^4)$ .Calculate how many length of $k$ 的数组 $a_1,a_2,\cdots ,a_k$ ,满足：

• ${\sum }_{i=1}^k{a}_i=n,a_i\ge 0$ .
• 对于任意的 $i=1,\dots ,k-1$ 有 $a_i\text{AND}{a}_{i+1}=a_{i+1}$ .其中 $\text{AND}$ 是与操作.

输出答案对 $10^9+7$ 取模的结果.

题解：（DP）代码源每日一题 Div1 与

思路：Consider the binary on every,从 $1\sim k$ 必然是 $1,1,\cdots ,1,0,\cdots ,0,0$ ,That we defined from the perspective of binary,This state the number of less,Move faster.定义 $dp(bit,j)$ 表示前 $0\sim bit$ These bits can be as $0/1$ ,且 $bit\sim \inf$ 位上都为 $0$ ,且总和为 $j$ 时的方案数 .那么我们枚举 $bit$ How many letters are there in the seat $1$ ,转移方程就是 $dp(bit,j)={\sum }_{j-k\times 2^{bit}\ge 0}dp(bit-1,j-k\times 2^{bit})$

AC代码：http://oj.daimayuan.top/submission/317348