水原_
水原_
全部文章
ACM
题解(28)
归档
标签
去牛客网
全部文章 / ACM （共13篇）

nim游戏

对于 对石子，每堆有 个，每次可以从一堆取走任意多个，求每个状态是必胜还是必败。 结论是当且仅当 ^ ^ ^ 时必败。 证明： 1：若 ^ ^ ^ ，那么操作后 ^ ^ ^ 。因为若存在 满足 ^ ^ ^ ^ ^ ，那么将两式异或，则 ^ ，矛盾。 2：若 ^...
2020-01-20
0 488

二分图匹配

二分图匹配 匹配 是指两两没有公共点的边集 给出一个二分图，找一个边数最大的匹配。 增广路：从一个未匹配点出发，依次经过未匹配边，匹配边...未匹配边到达一个未匹配点 增广：将增广路上的非匹配边和匹配边互换，得到的匹配比之前多一条边。 如果找不到增广路，那么已是最大匹配。 每次选一个未...
2020-01-02
2 889

manacher

Manacher 的时间复杂度内求出一个字符串的任意位置为中心的最大字符串。 首先为了统一奇字符串和偶字符串， 我们在字符串每个位置加入一个特殊字符 # ， 在字符串开头加入特殊字符 $ 。 然后所有回文串就都是寄回文串了。 记 为以 为中心的回文串的最长半径， 那么 就是原串长度。 然后...
2020-01-02
0 639

字符串哈希

标准模板 将字符串映射到数，以便实现 的字符串判重。 我们自己取一个滴数 , 膜数， 那么 。 就是整个字符串的哈希值。 为了避免哈希冲突（及两个不同的字符串哈希值相同）的情况，我们一般将 选为质数。 如果只需判重，可以同时计算几个不同底数、模数的哈希值，防止哈希碰撞。 区间的哈希 那么...
2020-01-02
0 932

强连通分量 - 割点桥 - 双缩点

无向图连通分量： 即可。 有向图强连通分量: 中记录每个结点能到达的最前祖先，并入栈；若某个结点有 ，则当前栈顶到 是一个强连通分量。 缩点： 有些一般图的问题可以把一个强连通分量视作一个点， 然后转换成 上的问题，就可以用拓扑排序解决。 注意，缩点后需要对每个得到的强连通分量重新加边。 ...
2020-01-02
0 994

数位dp

数位 思想 其本质思想是暴力从高位到低位枚举每一个数,用记忆化记录答案。 因为根据题目的要求，这种搜索方式会导致大量的状态重复。 实现 我们用 表示每一个状态，可见状态数比较少。 如果搜索时发现 已经搜过，就直接返回。 代表当前搜到哪一位， 代表当前位是否有限制。 举个栗子：数是 ，当前枚...
2020-01-02
0 671

min_25筛

用于求 ，复杂度“据说”是 ，会比杜教筛略快 需满足 是积性函数，且 是关于 的低次多项式（如果次数过高，需要用拉格朗日插值求系数） 中定义了两个函数： 是质数位上的前缀和， 就是答案。 又当 即 时 才不为 , 故 ，因为 当 时...
2020-01-02
0 597

莫比乌斯反演

前置知识 积性函数 若函数 为正整数 对任意的满足 的两个数有 ，则称 为积性函数。 特别的，若对任意 ，则称 为完全积性函数。 常见积性函数 莫比乌斯函数 约数函数 对于迪利克雷卷积的乘法单位函数 （完全积性） 迪利克雷卷积 定义 对于两个以正整数为定义域的...
2020-01-02
1 592

lca(倍增)

用 记录 的 入序和出序，就可以 判断 是不是 的祖先。 在找 的时候就可以只跳一个点。 注：需先设定 习题： #10131. 「一本通 4.4 例 2」暗的连锁 掉附加边不会影响原图的连通性，所以分成哪两部分取决于去掉树上的哪条边。 我们枚举去掉树上的哪条边，如果这条边去掉后分成...
2020-01-02
0 603

单调队列

求每个固定长度区间最值 顾名思义,单调队列即是一个单调的队列. 这里只考虑求区间最小值. 建立一个单调递增的队列,队首是最小值. 开始队列为空,每次添元素的时候,从队尾向前比较, 直到找到最靠前的比自己小的数,将待添加元素添加到这个数后面, 舍弃后面的所以数.(这是因为新添加的数一定比后面的数更优)...
2020-01-02
0 601
牛客博客，记录你的成长
关于博客 意见反馈 免责声明 博文推荐 牛客网首页
公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层
联系方式：010-60728802(电话)
admin@nowcoder.com
京ICP备14055008号-1
京公网安备 11010502036488号