牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共5篇）

模拟8 题解

A. 匹配 $Hash$直接搞。如果使用$KMP$，注意B字符串与A完全匹配，这是原本的$KMP$无法处理的问题。 B. 回家刚开始以为是割点，打完后仔细一想发现不对。于是打了圆方树，没有什么技巧。另一种简单的做法：只判断割点，但修改判断割点的方法。 ...

Hash KMP 字符串 tarjan 图论三分

2019-07-25

0 308

模拟15 题解

A. 建设城市（city）相较于那一天我们许下约定，数据范围有所改变。如果不考虑k的限制，是显然的插板法。枚举至少超过限制的个数，大力容斥就完了。 B. 轰炸行动（bomb）论如何看懂题。如果能够理解题意，缩了scc，拓扑排序求个点带权最长链就完...

容斥组合计数数学 tarjan 图论 dp 期望

2019-08-10

0 337

模拟85 题解

A. 表达式密码观察样例，发现答案就是将减法拆为一个减法和多个加法，于是就完了。 B. 电压机制发现问题是认为一条边相邻的两个点颜色相同并不考虑这条边，问图能否二分图染色。暴力做法是$O(nm)$的。仔细想想就可以发现：对于奇环，不能二分图染色，所以必须选择奇...

二分图 tarjan 贪心

2019-10-25

0 697

省选模拟4 题解

A. 点点的圈圈因为题中保证的特殊性质，容易发现圆之间的关系形成树形结构。对于每棵子树，选择树的根或者累计所有子树的答案。问题在于建图，容易发现这个可以用KDTree优化。考虑将所有的点建在KDTree上。用每个点的圆覆盖KDTree，当完全覆盖时直接塞入对应点的vector中。...

结论题 set 扫描线 lct 主席树线段树 tarjan KD-Tree 计算几何

2020-01-12

0 875

省选模拟59 题解

A. 杨柳考虑实际上有这样一个结论，棋子之间是互不干扰的。可以使得最优方案上不存在两个棋子中途碰上的情况。然后问题就是一个二分图最小匹配，一个简单的想法就是 bfs 然后跑一个费用流，点数不多，边数很多。另外一个做法是直接在原图上建图跑个费用流，点数很多，边数不多。经过实验，只有...

区间dp 二分图 tarjan dp 网络流

2020-04-01

0 336