牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

省选模拟14 题解

A. 开车关系似乎和欧拉回路很大。所以考虑首先通过构造欧拉回路的方式干掉所有的偶度点。然后发现问题转化为所有奇度点的最小带权匹配。刚开始的思路一直局限于靠原有的边匹配。后来发现只要是一条路径连接即可。考虑利用题中的特殊性质，二进制下所有小边的加和不大于大边。所以直接使用最小生成树...

最小生成树欧拉路杨氏矩阵

2020-02-01

0 335

省选模拟13 题解

A. 同桌的你每个人渴望与一个人当同桌。容易发现这个关系形成内向基环树森林。问题转化为求基环树森林的最大匹配。任意选一条环上的边，分别尝试该边为匹配边、非匹配边即可。 B. 大水题一个常用的但想不到的东西：将每种颜色出现次数的差值为定值，转化为对颜色序列差分后相等。然...

二分图二分答案 Hash 差分基环树 2sat

2020-02-01

0 474

省选模拟12 题解

A. Colorado Potato Beetle 暴力做法是直接bfs。优化的方法是离散化。将特殊的点的横纵坐标抽出来，然后用这些横纵坐标为1e12*1e12分成一个个块，容易发现每个块内的状态是一致的。然后用与暴力类似的方法即可，注意最后统计的是每个块的实际大小。 B. D...

后缀自动机 dp 状压搜索树链剖分线段树

2020-02-01

0 359

图论专项测试

A. center 分别考虑每一条边。二分答案，问题转化为判定是否存在可行区间。然后列式子发现存在三种限制的形态，而其中的一种（含有或运算）并不是一个线性算法能够解决的。盲猜这种情况并不多见，剪枝暴力$AC$。个人认为三分的算法是伪的，见数据（不能hack三分算法，但不单谷）： ...

二分答案最短路网络流三分二进制分组

2020-01-30

0 488

数学专题测试4

A. 猜拳游戏看到这个数据范围多半是高斯消元。所以问题是如何处理出每局的胜率。容易发现平局是没有意义的，要求的是最大的胜/负，这是一个分数问题，无法进行简单加和。所以正确的做法是01分数规划。通过二分答案，将分母部分直接作减法。于是只要维护最大的分子-$k*$分母就可以了。 ...

dp 高斯消元二分答案多项式拉格朗日插值分数规划

2020-01-29

0 499

省选模拟11 题解

A. 组合数问题还没想明白如何做，待补。 B. recollection 因为原图为trie树，树上两个点的lcp长度等于两个点的lca深度。考虑通过广义sam来维护两个点的lcs。树上同时对应着一个$endpos$，树上两个点对应的$endpos$对应的广义sam上节点在后缀...

并查集平衡树后缀自动机线段树

2020-01-29

0 405

省选模拟10 题解

A. 食物链在拓扑序上dp。 B. 选点游戏要求支持合并两棵树，并同时维护树上最大独立集。考虑特殊情况，每次只加一个标号最大的点，问题是一个简单的动态dp。离线出最终树的形态，考虑加入的一个叶子节点，更新该节点到1号节点的轻链上信息就可以了。其实想到这里，一个动态dp的做...

拓扑排序树链剖分 dp 期望动态dp

2020-01-29

0 365

省选模拟9 题解

A. Surprise me 直接将$\varphi(i*j)$展开为$\varphi(i)*\varphi(j)*\frac{gcd(i,j)}{\varphi(gcd(i,j))}$。于是可以套用莫比乌斯反演。最终的式子大概是$\sum \limits_{T=1}^{n}f(T)\su...

二分图虚树图论结论题莫比乌斯函数点分治提交答案

2020-01-17

0 654

省选模拟8 题解

A. 序列发现较难维护的是后一个信息。所以考虑直接分块维护。为每个块开一个vector，表示这个块中所有元素对vector中的所有元素依次取过max。因为取max的性质，这个vector中的元素只需要保留单调递增的部分。在查询的时候和暴力重构一些块的时候，可以直接在vector中...

网络流二分图分块线段树

2020-01-17

0 553

省选模拟7 题解

A. 翻转硬币第一眼以为只要保证给定的$k$个点反面就好了，是弱智水题，于是感觉秒切了。然后考完20分，就被秒切了。所以实际上是一道原题。思路大概是对原序列进行异或意义下的差分，于是区间修改转化为两个点的修改。于是问题变化为将初态共$2k$个$1$消为$0$。然后发现每个有意...

状压最短路线段树平衡树差分 dp manacher

2020-01-14

0 400