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

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

P2257 YY的GCD

P2257 YY的GCD 按照套路化到最后是： 问题就在于怎么求 法 : 对 做唯一分解，则 然后用数组记录 含有的质数个数，是否为以上两种形式之一，即可递推。 法 : 考虑在线性筛的时候处理。 筛合数时， ， 若 的唯一分解中每一项...
2020-01-02
0 631

P2522 [HAOI2011]Problem b

P2522 [HAOI2011]Problem b 与 P3455 类似，只不过 变成了 。 两种方法解决： 用前缀和，转化为 四个 。 整除分块的时候分为四条轴。要注意的是其中两条 轴很快会变为0，此时就不能用 来更新 了。 否则分母会为 #include<algo...
2020-01-02
0 518

P3455 [POI2007]ZAP-Queries

P3455 [POI2007]ZAP-Queries 由莫比乌斯反演， 方便计算，改变一下枚举方式，我们枚举 ，则 可以看出莫比乌斯反演的实质：容斥原理 将 代入， 然后用整除分块即可。 #include<algorithm> #include<iostrea...
2020-01-02
0 659
牛客博客，记录你的成长
关于博客 意见反馈 免责声明 博文推荐 牛客网首页
公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层
联系方式：010-60728802(电话)
admin@nowcoder.com
京ICP备14055008号-1
京公网安备 11010502036488号