zhouhuanyi

摘要： 题意大概是说求有所有有标号有根树及其黑白染色方案使得定义 \(S_{x}\) 为 \(x\) 和其儿子节点构成的集合，则 \(S_{x}\) 中的黑色节点个数要求不少于白色节点个数，且定义 \(x\) 的白色节点个数为 \(cnt_{x}\)，则其方案的贡献为 \(\sum_{i=1}^{n}cnt 阅读全文

摘要： 如果原问题将三角剖分图换成一条链后可以使用树状数组，线段树与音符大师的乱搞 \(\text{trick}\) 三种不同的方法做，但由于三角剖分图比较复杂，这里第二种方法更易于扩展。 对于一般满足四边形不等式的决策单调性问题，通常我们会将一个满足四边形不等式的 \(w(i,j)(i<j)\)，将其扩展 阅读全文

摘要： 某人在换根时根还设置成 \(1\) 交了整整 \(11\) 发，我不说是谁。 先考虑一下 \(2\) 询问的实际用途，因为我们可以用它来确定深度，根据树上交互题的常见技巧，我们通过这种方式确定了一个拓扑序，只要能在拓扑序的前缀中快速查询一个点的父亲，就可以求出这棵树。 考虑先以一条边为根，那么其会有 阅读全文

摘要： 原问题可以看作是二分图博弈的模型，那么可以将博弈问题转化为最大匹配的一定性判定性问题。实际上博弈的 \(\text{dp}\) 过程直接摊开就是每次删任意一个叶子与其父亲，将父亲变为 \(1\)，这个也就是最大匹配的求解过程，而是否为匹配的上端点即该点的 \(01\) 状态，那么实际上每一行的 \( 阅读全文

摘要： 首先原题意可以转化为对于每一个 \(1\leqslant k \leqslant n\)，选择 \(k\) 个点染黑，使得给定区间中全白的区间尽量少。 这其实是非常强的，考虑基于四边形不等式的一类区间划分类问题，其区间代价函数可以写为 \(F(l,r)=\sum_{i=l}^{r}\sum_{j=i 阅读全文

摘要： 首先和 \(\text{Fast as Ryser}\) 一样，当 \(n\) 为奇数时加一个点，将 \(n\) 任意划分成 \(\frac{n}{2}\) 个匹配，则求的匹配和原来的匹配构成了若干个环和若干条链，那么有匹配大小 \(=\) \(\frac{n}{2}-\) 链的个数。令链的集合幂级 阅读全文

摘要： 一个和值域无关的算法，复杂度 \(O(4^nn^2)\)，不过好像可以用子集卷积和拉格朗日插值优化至 \(O(3^nn^3)\)。 如果说原问题在整数上做，我们通常可以用生成函数来刻画容斥的式子，求个二维 \(\exp\) 状物就可以了，但是在实数域似乎不太好扩展，但实际上是可以扩展的。 原问题实际 阅读全文

摘要： 原问题比较类似 \(\text{ZJOI 2020}\) 序列，可以划归为一个线性规划的形式，考虑将线性规划对偶，不难发现等价于求一个序列 \(b\)，使得对于任意 \(1\leqslant l\leqslant r\leqslant n,r-l+1\leqslant m\) 均满足 \(\sum_ 阅读全文

摘要： 注意到虽然图比较稠密，但是我们可以只保留一些有用的边。先考虑一个弱化版，找到一些有效的边构成的 \(G'\) 使得 \(G\) 与 \(G'\) 连通性相同，实际上如果我们按某个坐标进行扫描线，原问题相当于维护一个集合 \(S\)，支持： \(1.\) 动态在 \(S\) 集合中加删点。 \(2.\ 阅读全文

摘要： 赛时没有过又为队友拖后腿了。 考虑原限制具有什么性质，可以发现 \(j\) 能接到 \(i\) 后面仅当 \(\text{max}_{S_{i}} \leqslant \text{max}_{S_{j}}\)，而当 \(\text{max}_{S_{i}} = \text{max}_{S_{j}}\ 阅读全文