这个暑假注定是忙碌的一夏，渡渡鸟幼儿园采用分锅补题制度力求大幅度提升补题效率，基本上由$yangdavid$撰写训练实录总览，三人分别在各自博客上撰写所补题目的题解
opentrains 1531 300iq contest 1
problem D
题目描述：孙路约炮，$m\leq10^5$个女的，每个女的$l_i,r_i,p_i$表述这个女的在$l-r$区间可约且约了会有$p$的喜悦值，区间值域$[1,n]\leq10^5$,每个女的最多约一次，每天有一个属性$a_i\leq10^9$表示这一天最多约这么多次，求最大总喜悦值，有一个特殊的限制，保证$l_i\leq l_{i+1},r_i\leq r_{i+1}$
场上想出正解，但由于代码复杂度较高加上自己码力不够导致没有$A$掉，硬核线段树题
$solution$:把第$i$天拆成$a_i$天，变成每天最多只能约一次
根据经典贪心模型，可知按照女人的$p$从大到小考虑，尽量把$p$大的女生加入决策
下面我们把女生当成区间
设一个合法的区间集合为，存在一种方式，使得可以在每个区间内选一个点，使得这些点两两不重复
问题就变成了：动态维护一个合法区间集合，支持
$(1)$:询问如果把一个新区间加入当前区间集合，则这个区间集合是否仍然合法
$(2)$:把一个区间加入当前合法区间集合，保证加入后新区间集合仍合法。
我们首先考虑：给定一个区间集合，判定此集合是否合法
由于有$l_i\leq l_{i+1},r_i\leq r_{i+1}$的良好条件，我们把这些区间按$id$排序，则可以从小到大贪心在每个区间里选点，选点要尽量往左选。即可判定。
这就可以引出一个显然而重要的观察:一个合法区间集合中，按照贪心决策的选点方案，各区间所对应点的顺序和区间编号顺序相同
我们用一个支持动态插入的线段树维护当前合法区间集合，线段树基于的下标即区间的编号$[1,m]$,线段树上需要维护的东西叙述如下：
设已插入的$i$号区间所对应的点为$s$,它在集合中编号从小到大为$p$,我们记$r_i-s$为该区间的“后退余地$u$”，$s-p$为该区间的松散系数$v$。
对于每个节点，我们需要维护：
$(1)$.子树中后退余地最小值。
$(2)$.子树中松散系数最大值。
$(3)$.$lazytag1$表示$s$的整体变化。
$(4)$.$lazytag2$表示$p$的整体变化。
显然上述四个值容易维护。下面我们来诠释所需的两种操作如何进行。
1.询问如果把一个新区间加入当前区间集合，则这个区间集合是否仍然合法：
设当前加入的区间编号$x$
a.找到当前集合中关于编号$x$的$upper$_$bound\ y$的上一个区间$y_0$,则根据之前描述的贪心方案可知$x$区间对应的点为$s_x=max(s_{y_0},l_x)$
b.在$[y,n]$中找到集合中编号最小的后退余地为$0$的区间$z$，若没有则需使用虚拟节点特殊处理一下。
关于实现，这里找的话，需要用一些比平常有一点点麻烦的技巧（先左后右，找右则全左），保证复杂度一个$log$
c.如果$v_z>s_x-p_{y_0}$，则表明加入集合后该集合仍合法，否则不合法。这个式子的推导较容易
2.把一个区间加入当前合法区间集合，保证加入后新区间集合仍合法：
接上面的步骤：
d.找到$[y,z]$中编号最小的$v>s_x-p_{y_0}$的节点$h$,由于$z$满足条件，因此必然可以找到，然后我们就要将$x$插入了，相当于$[y,n]$的位次$p$整体后移$1$，$[y,h]$的选点位置$s$整体后移$1$,线段树区间修改即可。
冗长的代码：
1 |
|
Problem E.
给定一张$n$个点的平面图，$n\leq 3000$，随机游走，问从$1$号点期望走几步到达$n$号点
首先，根据欧拉公式：$V+F-2=E$,$F\leq\frac{2E}{3}$,可得$E\leq 3n-6$，按照习惯我们把边数称为$m$,可知平面图中$n,m$同阶。
我们设$n$阶列向量数列${A}$,$A_{ij}$表示走$i$步没走到过$n$第一次走到$j$的概率。我们可以轻易得到一个$n$阶方阵$B$,来递推这个向量数列，$BA_i=A_{i+1}$，$B$中非零元素的数量有$m$个
根据$Cayley-Hamilton$定理，$F(x)=|xI-B|$是$B$的$n$阶多项式，那么$F(B)=0$成立，也就是说
$B^n=\sum_{i=0}^{n-1}a_iB^i$，两边右乘$A_0$，就可以发现${A}$是$n$阶线性齐次递推数列，由于我们需要知道第$i$步第一次到达$n$的概率，因此我们只需要关心每个向量的第$n$项即可，而$A$是递推的也就说明：第$i$步首次到达$n$的概率$p_i$也是一个线性齐次$n$阶递推数列。
根据$Berlekamp-Massy$算法的相关理论，对于$n$阶递推数列，需打表出$2n$项，便可在$O(4n^2)$找到相应最短递推式。
打表，枚举矩阵中非零元素进行转移，需要$O(2nm)$的时间。
设$p$的生成函数为$P$，可知$P’(1)$即为答案所求的期望步数，由于我们有递推式$G$,我们可以列出方程
$P(1-G)=T$,$T$是数列前$n$项与$1-G$项乘产生的无法抵消的贡献，可以暴力$O(n^2)$计算
因此$P=\frac{T}{1-G}$,要求出$P’(1)$我们不能考虑用多项式除法求$P$因为我们要求精确值而不是模$x^n$意义下，直接使用分式求导公式即可
$P’(1)=\frac{T’(1)(1-G(1))+G’(1)T(1)}{(1-G(1))^2}$
1 |
|
opentrains 6311 SEERC2018
Problem D
一棵有边权的$n$个点的树，要求从$1$号点出发，经过每条边最少一次，最后回到$1$号点，经过一条边你就要花边权那么多的花费，你最多可以飞跃$m$次，飞跃一次要花费$k$，问最少花多少钱。$n\leq1000$
核心观察：将所有飞跃起始点和飞跃终点作为点不区分地放在树上，则对于一个点$x$，如果$x$的子树里有偶数个点，则这个点的父边经过了$2$次，否则经过了$1$次
问题就变成了在树上放点，最小化花费，经典树形背包问题，树形背包复杂度：
$O(\sum_xsiz[x]^2-\sum_{v\in son[x]}siz[v]^2)=O(n^2)$
注意树形背包时从后往前扫。
想的时候把需要返回$1$号点这个条件不小心忘掉了，导致没过，有点内疚
1 |
|
Problem H
这个题意就是一坨屎，其实题目想做这个事（原题意有歧义）
给定一个有向图，构造一种点黑白染色的方案使得至少有$m/4$条从白点到黑点的边。
构造算法：首先把边全都视为无向，每次染色的时候，看看当前点相邻的已经染色的点中是黑的多还是白的多，染成数量少的那一方，显然这样染色完后一定有至少$m/2$的边两边颜色不同。
恢复有向边，按照刚才的方案，从白到黑的边和从黑到白的边至少有一方的数量大于$m/4$，如果是后者，将所有点黑白反转即可。
随机还能过，也是惊了。
体验极差，没代码（都是题意的锅）
waiting：GP of china egh