牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共10篇）

模拟8 题解

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

Hash KMP 字符串 tarjan 图论三分

2019-07-25

0 308

模拟30A 题解

A. 树联想起远古考试时做的题记忆的轮廓。树上走一些步数的期望。显然可以直接解方程。然而复杂度$O(qn^3)$，利用树上的性质优化一下，直接一遍dfs过程中解出来，可以$O(qnlogmod)$，其中的log是求逆元。然而只有20分。预处理出每个点走到每个儿子的期望步...

dp 期望 Hash 二分答案字符串启发式合并

2019-08-25

0 306

模拟61 题解

A. 砖块简单模拟。对于最后一问，算一算复杂度就可以知道开map没有任何问题，然而map真的方便很多，所以为什么不用呢。 B. 数字容易发现末尾的0一定是被质因子2和5凑出。并且，对于任意的$n!$，质因子2的个数不小于质因子5的个数。简单的暴力$O(n)$做...

线段树模拟吉司机线段树 Hash 中国剩余定理数学

2019-10-06

0 416

模拟78 题解

A. 串串香送分题。发现用$kmp$复杂度也是$O(n)$，和直接哈希的复杂度是一样的。所以直接双模哈希硬干就完了。 B. 糊涂图在不加边的情况下，因为存在拓扑序，问题是简单的。所以可以先处理出不加边情况下，每个点达哥获胜的概率，其实这个数组也表示走奇数步后无...

Hash KMP 拓扑排序 dp 倍增直径

2019-10-18

0 360

模拟84 题解

A. Smooth 考虑用已有的光滑数推出新的光滑数。显然每次可以取出最小的光滑数，并乘每个质因子插入堆中。需要通过哈希表打标记来解决重复计数的问题。复杂度为$O(kblogk)$，空间应该也承受不住。正解显然不带$log$。因为我们每次取出的都是最小的光滑数，其实堆有些多余。...

单调队列 Hash dp

2019-10-24

0 0

模拟108 题解

A. 打表正确的题意是：求出最优决策下取得的值与答案的差绝对值的期望。考虑到本题中二者选择的概率各占一半。二者都选择各自的最优策略，在按位划分的情况下，只有$0$,$1$两种取值，如果前者选择$0$，那么后者可以选择$1$ 最终每个下标都会被等概率的选择，所以最终的答案就是对绝...

dp Hash 结论题

2019-11-11

0 473

省选模拟13 题解

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

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

2020-02-01

0 474

省选模拟18 题解

A. 编码一眼原题，是一道数据结构（？）优化2-SAT建图的题。 2-SAT还是比较容易看出来的，每一个串只有$0/1$两种取值，一个串对另一个串起到了限制的作用。于是暴力的做法就是先将所有的串按照长度排序，由小到大分别将两个副本插入字典树。对字典树上每个节点维护一个vector，表示...

单调指针 Hash dp 高斯消元二分答案折半搜索 2sat trie树

2020-02-05

0 387

省选模拟19 题解

A. 鱼死网破（clash）对于$k=1$的数据，容易发现只要维护每个$x$轴上面的点关于障碍两个端点的极角，并对每个端点对应的极角排序。对于每个$x$轴下面的点，可以通过极角来二分查找哪些点是看得到的。感觉和正解的思想差的不多。正解用到了一步补集转化。考虑每个$x$轴上面的点，...

线段树字符串后缀数组 Hash

2020-02-06

0 413

省选模拟76 题解

A. MiniumCut 首先看到这个题，可以想到最小割树。然后发现原图的最小割树与原图是等价的。那也就是说，答案可以表示为一个树。然后考虑如何求出来这个树。大概的思路就是由小到大考虑每一组关系或者由大到小考虑每一组关系。这里用后一种思路，大概套用一下类似克鲁斯卡尔重构树的思想，然...

最小生成树回文自动机 Hash dp

2020-04-21

0 419