Day1

$T1:$

模拟乱搞。

$T2:$

一道期望$DP$

设状态为$f_{i,j,v}$表示当前已经到了$i$时间段,用了$j$次申请,且当前有无申请的期望长度,注意有可能申请失败。

$T3:$

一个人向上跑,若$i$号观测员能观测到他

必须满足$d_s-d_i=w_i$

一个人向下跑,若能观测到,

必须满足$d_s+d_i-2*d_{lca(s,e)}=w_i$

移项有$d_i+w_i=d_s,w_i-d_i=d_s-2*d_{lca(s,e)}$

可以观察到,左边都是定值,因此,对于一个观测点$i$,我们仅需开两个桶,分别记录一下两种情况的点,但由于点可能不合法(比如$s$在$i$上面还向上跑),因此可以发现,

一个人向上跑,$s$一定在$i$的子树内,且$lca(s,e)$在$i$上方,才合法。

一个人向下跑,$lca(s,e)$在$i$上方,$e$在$i$下方,才合法。

那么可以考虑树上差分,对于一个点向上跑的时候,在$s$这里桶的$d_x$这个位置$+1$,向上更新到$fa_{lca(s,e)}$时,$d_x$这个位置$-1$。

向下跑的时候,由于$s$的位置是不定的,但$e$确定在$i$下方,那么我们要在统计$i$的时候更新到$e$,因此在$e$这里的时候桶的$d_s-2*d_{lca(s,e)}$这个位置$+1$,在$fa_{lca(s,e)}$这里,$-1$.

但这里处理会有个问题,$s=lca(s,e)$时,会重复计算两次,那么我们可以令任意一个减操作移到$lca(s,e)$处即可。

Day2

$T1:$

根据$C^{n}_m=C_{m-1}^n+C_{m-1}^{n-1}$这个式子,可以有$C_{m}^n=C_{m-1}^{n}+C_{m-1}^{n-1}(\operatorname{mod} k)$

如果一个$C_{m}^n\operatorname{mod} k=0$,则说明$(n,m)$可行。

之后用一个二维前缀和随便搞搞。

$T2$:

维护两个递减序列,试证明如何维护递减,
设当前取出来的最大值为$s1$,次大值为$s2$(次大值在下一次为最大值,所以只关注次大值)
当前得到$u1=s1*p,u2=s1-u1$,遵从同类型比较,下一次得到 $u3=(s2+q)*p,u4=(s2+q)-u3$

$u1+q,u3,u2+q,u4$

$s1*p+q,s2*p+q*p,s1+q-u1,s2+q-u3$

$u1>u3$显然成立,

$s1+q-s1*p,s2+q-(s2+q)*p$

$s1-s1*p>s2-s2*p,q>q-q*p$

因此,$u2>u4 $。

证毕。

$T3:$

一道状压(暴搜)题。

主要推一下两点确定二次函数

$a*{x_1}^2+b*x_1=y_1\\a*{x_2}^2+b*x_2=y_2$

可得$\large b=\frac{y_1{x_2}^2-y_2{x_1}^2}{x_1{x_2}^2-{x_1}^2x_2}$

之后随便乱搞。

甚至可以将$O(T*2^n*n^2)$优化成$O(T*2^n*n)$

也就是$x\in S$没有必要选,先选后选$x$是等效的。