一些简单题目总结
一些简单问题。
可以一句话题解。
problem 1
题意给一堆木棍长度 \(a_i\)。
让你保证首尾相连，问你最少覆盖多少长度。
Solution
\(f_i\) 表示 \(i\) 是否能被选。
转移很简单 \(f_i\gets f_{i\pm a}\)。
可以二分，可以哦直接 dp。
\(\texttt{Complexity : }\mathcal{O(n^2\log_2 n/n^2)}\)。
problem2
省选2020 day2t1
Solution
暂时只会淀粉质一种做法。
对于一堆点 x,y。
我们在他俩恰好在分治中心两颗子树时，统计答案。
只会统计一次，显然。
能往上走越多越好，维护 \(f(x)\) 表示 \(x\) 开始（第一个是 \(w[x]\)）最多走多远，到分治中心停止。
在记录一个 \(x\) 到分治中心上最靠近 \(x\) 的一个 \(w[1]\) 在哪里。
这样解决了往上爬。
往下爬。统计 x,y我也在y处统计。
二分 y 的答案。看 y上面最靠近 y 的 mid 是哪个，在维护一个反着走的 \(g(x)\rightarrow revf(x)\)，。然后判断能不能和往上爬的接上 。
tips : 需要注意 y是分治中心时的处理的方法。
需要准确维护 mask(x)，就是当前链最靠下的 x 位置。
可以把 \(w(x)\rightarrow [1,n]\)，映射。
分治中心的特殊处理需要格外注意。
Solution
可以用 dp。
首先你只可能先选随机操作，然后在选+1操作。
那么我们考虑dp方程。
\[{f}(x)=\min\begin{cases} \sum\limits_{i=1}^{n}\frac{f(i)}{n}+b\\ (T-x+1)a \end{cases}\]
发现这个方程上面 \(\sum\limits_{i=1}^{n}\frac{f(i)}{n}+b\) 是定值，下面是一次函数，那么取 上面那段必然是一个前缀，取下面那段必然是剩余的。
那么 rephrase 题意可以变成：确定 \(x\) 使得 \(s\geq x\) 的直接 +1,否则 随机直到 \(s\geq x\)。
那么答案 \(E_x(a\cdot k+b\cdot w)=E_x(a\cdot k)+E_x(b\cdot w)\) 分别计算对于 \(x\) 随机到 \(s\geq x\) 的期望 和 当\(s\geq x\) 时到 \(T\) 的期望。
发现用 \(x\) 似乎比较繁琐，重定义 \(x\gets （T-x+1）\)。
前面那段 \(b\frac{n-x}{n}\sum_{i=1}^{\infty}i(\frac{n-x}{n})^{i-1}\)。
这个设后面的是 \(S\)，\(S=\frac{x}{n}S+\sum(\frac{n-x}{n})^i=\frac{n-x}{n}S+\frac{1}{1-\frac{n-x}{n}}=\frac{n-x}{n}S+\frac{n}{x}\)。
所以 \(S=(\frac{n}{x})^2\)，所以 \(E_x(b\cdot w)=b\frac{n}{x}\)。
后面那段比较 simple，直接 \(E_x(a\cdot k)=a\sum_{i=0}^{x-1} \frac{i}{x}=a\frac{(x-1)}{2}\)。
\(E_x=b\frac{n}{x}+a\frac{x-1}{2}\)。这个类似均值不等式，对号函数，直接 x 最小值大概落在根号附近的一个整点，暴力算即可。
注意 \(S\leq T\) 时要考虑直接 +1 是否更优。
limit the width of the DFS-tree.
Interesting Problem
However the result whick you have DFS is not ordered,so binary search works well.
By the way,dreamoon's code style is pretty good.
欢迎来到老cage碍世界。
今天小编带大家来了解 BZOJ5267 fwt。
fwt到底是怎么一回事呢？让我们一起来看看吧。
说起fwt，相信大家一定很熟悉，但是 BZOJ5267 fwt什么呢？就让小编带大家一起了解吧。
其实，fwt就是分治，大家可能会惊讶，fwt竟然就是暴力分治！
你可能会感到疑惑，我靠，那你怎么计算原先的 \(sum\)？
其实，显然 \(sum(j+mid,j+2\cdot mid-1)=f_{now}(j+2\cdot mid-1)-f_{now}(j+mid-1)\)。
这究竟是为什么呢？小编也十分疑惑。(考虑 \(x\leq j+2\cdot mid-1\) 的 \(x\) 都是 \(j+2\cdot mid-1\) 的子集，\(j+mid-1\) 同理)。
这就是fwt了，不知道大家有什么想法呢？欢迎在屏幕下方留言哦
本来以为挺简单的东西，就是把Y找出来，然后对 \(\sum|x_i-i|\) 算 min，显然排序中位数，着我没看出来不降，我直接上的线段数二分，啊啊啊啊啊啊啊，我是伞兵。。。。啊啊啊啊啊啊，俩log拉死了。。。。
k染色等价于k个独立集。
单位根反演： \([k|n]=\displaystyle\sum_{i=0}^{k-1}w_k^{in}\)。记忆方法，考虑 \(w_k^{m}=1\Leftrightarrow k|m\)。
考虑只要 \(k\not=1\) 那么转一圈就是 \(0\)，\(\sum_{i=0}^{k-1}w_k^{i}=\frac{1-w_k^{k}}{1-w_k}=0\)，乘法就会使把一个环分成很多小环。。
卡特兰数递推式，这个对于现在的你还没有那么简单。 \[ c_0=1\\ C_k=\sum_{a+b=k-1}C_aC_{b} \] 含义是枚举第一个括号内部是什么。注意，由于钦定了第一个括号，这样不会算重。我觉得这个钦定的想法还是很巧妙的。