- 博客(54)
- 收藏
- 关注
RSS订阅原创 「算法笔记」后缀数组 —— 从入门到进阶
文章目录后缀数组后缀数组是什么？倍增法求后缀数组思路分析代码实现height 数组height 数组是什么？线性求 height 数组思路分析代码实现例题讲解例 1：LCP 询问题目大意思路分析例 2：Musical Themes题目大意思路分析例题 3：【NOI 2015】品酒大会题目大意思路分析代码实现例题 4：【NOI 2016】优秀的拆分题目大意思路分析代码实现例题 5：【SCOI 201...
2019-01-08 19:33:47
373
原创 【NOIP 2018】保卫王国（动态规划 + 倍增）
目录题目大意思路分析代码实现题目大意【NOIP 2018】保卫王国给定一棵 nnn 个结点的树，点有权值。有 qqq 次询问，每次要求固定两个点是否染黑，求将树上的所有其他点染色，每条边的两端至少有一个黑点的所有方案中被染黑的点的最小权值之和。思路分析我们可以通过树形 DP\texttt{DP}DP 在线性时间内求出一个点 uuu 如果颜色为 ccc，那么整棵树的最小代价为 fu,cf_...
2018-11-19 22:49:22
1480
原创 「算法笔记」莫比乌斯反演进阶
文章目录YY 的 GCD题目大意思路分析代码实现NOI 2016 循环之美题目大意思路分析代码实现UOJ 62 怎样跑的更快YY 的 GCD题目大意求下列式子的值：∑i=1n∑j=1m[gcd{i,j}∈P] (P 为素数集合)\sum_{i = 1}^{n} \sum_{j = 1}^{m} [\gcd\{i, j\} \in P]\ (P\ \text{为素数集合...
2018-11-05 20:42:03
507
原创 【UOJ 169】元旦老人与数列（线段树）
目录题目分析实现题目有两个长度为 nnn 的数列 AAA 和 BBB，mmm 次操作。共有四种操作：1 l r c\text{1 l r c}1 l r c 表示 Ai←Ai+c (i∈[l,r])A_i \leftarrow A_i + c\ (i \in [l, r])Ai←Ai+c (i∈[l,r])...
2018-11-02 17:55:59
259
原创 【IOI 2018】狼人（点权重构树 + 二维数点）
目录题目分析实现题目【IOI 2018】狼人给定 nnn 个点 mmm 条边的无向图，qqq 个询问，第 iii 个询问形如 (si,ei,li,ri)(s_i, e_i, l_i, r_i)(si,ei,li,ri)，表示询问是否存在一条从 sis_isi 出发后只经过 [li,n][l_i, n][li,n] 区间内的点，在 [li,ri][l_i, r_i][li,ri...
2018-10-16 23:00:43
621
原创 【杭电多校训练 2018】Always Online（仙人掌图 + 最小割）
目录题目分析仙人掌图定义性质本题分析问题转化树上问题实现找环细节代码题目【杭电多校训练 2018】Always Online给定一个 nnn 个点 mmm 条边的无向带权联通图，没有重边、自环，且每两个点之间都有至多两条路径，它们的边集不相交。求：∑1≤s<e≤ns⊕e⊕maxFlow(s,e)\sum_{1 \le s \lt e \le n} s \oplus e \o...
2018-10-16 20:40:10
632
1
原创 【标签整理】2018 年 8 月 24 日
文章类型算法笔记 杂文 模版数学数论 数论分块 素数筛法 莫比乌斯反演 杜教筛 完全平方数 中国剩余定理 组合计数 FFT 高斯消元 线性基 SG函数数据结构线段树动态规划普通动态规划 树形动态规划 概率动态规划 矩阵乘法优化 状态压缩动态规划 子集枚举 有后效性的动态规划图论构图方法 对偶图 最短路 Kr...
2018-08-24 00:13:24
222
原创 【NOI 2015】寿司晚宴（状态压缩动态规划）
Link【NOI 2015】寿司晚宴Description求满足以下条件的集合 A,BA,BA, B 对数：2≤Ai,Bj≤n2≤Ai,Bj≤n2 \le A_i, B_j \le ngcd(Ai,Bj)=1gcd(Ai,Bj)=1\gcd (A_i,B_j)=1数据范围 n≤500n≤500n \le 500。Solution这题看似很难处理。这时我们就需要观察...
2018-08-23 23:51:42
174
原创 【JSOI 2016】炸弹攻击（模拟退火）
Link【JSOI 2016】炸弹攻击Description平面上有 nnn 个好圆，mmm 个坏点。要求选出一个半径不超过 RRR 的圆，使得它不和任何好圆有交。求该圆包含的最多坏点个数。Solution本题并没有完全正确的多项式解法。我们考虑使用模拟退火的技巧。如果你不会模拟退火，请参考 SiyuanSiyuan\color{black}{\text S}\color{...
2018-08-23 14:49:27
259
1
原创 树上覆盖集计数【树形动态规划】
Description给定一棵 nnn 个节点的树，求它的最小覆盖集个数。Solution我们考虑同时维护节点的最小覆盖集和最小覆盖集个数。我们发现一个点被覆盖只有 333 种情况：父亲被选入集合，自己被选入集合和至少一个儿子被选入集合。我们写出 DPDPDP 状态：⎧⎩⎨⎪⎪ f[u][i][0] 表示 u 的父亲被选入集合，自己和...
2018-08-21 01:02:34
381
原创 「算法笔记」杜教筛
推荐博客：algocode 算法博客。简介：杜教筛是一种能在 Θ(n23)Θ(n23)\Theta(n^{\frac{2}{3}}) 的时间内求出积性函数 fff 的前缀和的方法，但是使用的前提是需要找到另一个数论函数 ggg 使得 ggg 以及 (f∗g)(f∗g)(f\!*\!g) 的前缀和都很容易计算。常见的数论函数：见 algocode 算法博客。常见的狄利克雷卷积：ϵ=μ∗1...
2018-08-18 21:24:04
428
原创 「算法笔记」莫比乌斯反演
莫比乌斯反演是数论中的一种小技巧，常用于解决一些数论函数的求和问题。通常做法是使用 μμ\mu 函数来将 [n=1][n=1][n=1] 转换成 ∑d|nμ(i)∑d|nμ(i)\sum_{d|n}\mu(i) 的形式。推荐博客：algocode 算法博客μμ\mu 的定义：如果 nnn 有至少一个平方因子，那么 μ(n)=0μ(n)=0\mu(n)=0如果 nnn 没有一个平方因...
2018-08-17 10:19:57
274
2
原创 【清华集训 2013】楼房重建（线段树）
题目链接：【清华集训 2013】楼房重建题意转化：动态维护一个单调栈，支持单点修改，整体查询单调栈长度。使用线段树。对于每个节点，维护 max[root]max[root]max[root] 表示区间最大值，cnt[root]cnt[root]cnt[root] 表示区间中的单调栈的长度。在自底向上 maintain 的时候，cnt[root]=cnt[lson]+calc(rson,ma...
2018-08-09 13:02:52
298
原创 「算法笔记」树上启发式合并
算法简介：树上启发式合并 (DSU on Tree) 是一种能够在 Θ(nlog2n)Θ(nlog2n)\Theta(n\log_2n) 的时间里快速统计子树信息的小技巧。大致的思想是：将小的子树的信息合并到大的子树的信息中。具体的实现步骤一般是先 DFS 不是最大的子树并将该子树信息清空，然后 DFS 最大的子树并保留子树信息，在根据保留下来的最大子树信息算出原子树的信息。例题一：子树...
2018-08-05 22:39:46
694
原创 【JOISC 2017】火车旅行（倍增）
题目链接：【JOISC 2017】火车旅行题目大意：有 nnn 个车站，每个车站有一个编号，第 iii 种车只会经过编号 ≥i≥i\ge i 的站台。有 qqq 次询问，每次询问从 iii 号站台到 jjj 号站台列车最少停靠几次。令 l[k][I]l[k][I]l[k][I] 表示从 iii 号车站出发，经过 2k2k2^k 次停靠能够到达的最左侧的站点，r[k][I]r[k][I]r[...
2018-08-01 01:32:39
917
转载 【HEOI / TJOI 2016】求和（CDQ 分治 + FFT）
题目链接：【HEOI / TJOI 2016】求和转载自：algocode 算法博客#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1 << 18 | 5;const ll P = 998244353, g = 3;int n, r[maxn...
2018-07-31 15:23:00
267
原创 【HDU 6331】Walking Plan（分块 + 动态规划）
题目链接：【HDU 6331】Walking Plan题目大意：给定一张 nnn 个点，mmm 条边的加权有向图，有 qqq 次询问，每次询问从点 uuu 出发经过至少 kkk 条边走到点 vvv 的最短路是多少。(n≤50,m≤10000,q≤100000)(n≤50,m≤10000,q≤100000)(n\le 50,m\le 10000,q\le 100000)首先，我们可以想到倍增...
2018-07-31 11:32:18
587
原创 「算法笔记」CDQ分治
CDQ 分治新手教程CDQ 分治是一种分治，可以解决许多重要问题。它的优点有：常数小，代码复杂度较低，并且可以替代一些高难度数据结构（如树套树）。缺点是只能解决离线的问题。CDQ 分治解决的基本问题是：给定一些修改和查询，离线求出查询的结果；它的基本思想是：Divide&nbsp;the&nbsp;Queries&nbsp;into&nbsp;[l,mid]&nbsp;and&nbsp;[...
2018-07-25 02:45:59
652
2
原创 【NOI2018】屠龙勇士（中国剩余定理）
题目链接：【NOI2018】屠龙勇士首先，我们可以用 multisetmultisetmultiset 求出杀死每一条龙所用的剑。设它的攻击力为 attackiattackiattack_i。然后，我们发现题目转化成了：求 attacki⋅x≡aimodpiattacki⋅x≡aimodpiattack_i\cdot x≡a_i\mod p_i 的最小非负整数解。我们将 attacki...
2018-07-23 00:36:28
1028
原创 【LOJ 565】mathematican 的二进制（分治 + FFT）
题目链接：【LOJ 565】mathematician 的二进制题目大意：有一个 nnn 位的二进制数，mmm 个操作。第 iii 个操作是将这个二进制串的数值加上 2ai2ai2^{a_i}，有 pipip_i 的几率被执行。每次操作的代价是这次操作改变的位的数量。求代价的期望值mod998244353mod998244353\mod 998244353 的结果。n,m≤2×105n,m≤2...
2018-07-21 16:18:43
575
原创 【CodeChef COUNTARI】Arithmetic Progressions（分块 + FFT）
题目链接：【CodeChef COUNTARI】Arithmetic Progressions题目大意：给定一个长度为 nnn 的数列，求数列中有多少个三元组 (i,j,k)(i,j,k)(i,j,k)，满足： + 1≤i&amp;lt;j&amp;lt;k≤n1≤i&amp;lt;j&amp;lt;k≤n1\le i\lt j\lt k\le n + ai−aj=aj−akai−aj=aj−aka_i-a_j=a_j-...
2018-07-21 00:00:19
363
原创 【NOI 2018】归程（Kruskal重构树 + 倍增）
题目链接：【NOI 2018】归程题目大意：给定一个加权无向图，qqq 次询问，每次询问从 vvv 点只经过海拔 &gt;w&gt;w\gt w 的边到达的点中到 111 号点的最短路为多少。强制在线。首先，预处理出 111 号点到所有点的最短路。然后，每个询问就可以变成：从 vvv 点只经过 &gt;w&gt;w\gt w 的边到达的点 uuu 中 dis[u]dis[u]dis[u] ...
2018-07-19 22:04:10
329
原创 【JSOI 2012】分零食（倍增 + FFT）
题目链接：【JSOI 2012】分零食题目大意：将 mmm 颗糖依次分给 nnn 个小朋友，每个小朋友的快乐度为 f(x=得到的糖果数)=ox2+sx+uf(x=得到的糖果数)=ox2+sx+uf(x=得到的糖果数)=ox^2+sx+u。特别地，f(0)=1f(0)=1f(0)=1。糖果分完后剩下的小朋友将得不到糖果。求每种情况下小朋友快乐度乘积之和mod998244353mod9982443...
2018-07-19 21:00:26
369
原创 【CodeForces 269D】Maximum Waterfall（扫描线）
题目链接：【CodeForces 269D】Maximum Waterfall题目大意：高度为 mmm 的墙上有 nnn 块木板，每个模板有一个高度 hihih_i，左端点 lilil_i，右端点 ririr_i。墙的顶端可以视作一个高度为 mmm，左端点 −109−109-10^9，右端点 10910910^9 的木板，底端同理，可以视作一个高度为 000，左端点 −109−109-10^9...
2018-07-19 20:26:57
271
原创 【NOI 2018】冒泡排序（组合计数 + 动态规划）
题目链接：【NOI 2018】冒泡排序题目大意：给定一个排列 ppp，求字典序严格大于 ppp 的，最长下降子序列长度不超过 333 的排列个数mod998244353mod998244353\mod{998244353} 的值。题目等价于：能划分成两个上升子序列的序列个数。假设在前 iii 个位置中，最大值是 kkk，我们发现在余下的数中，&amp;amp;amp;gt;k&amp;amp;amp;gt;k\gt k 的可以随便放...
2018-07-19 14:30:21
1882
1
原创 「算法笔记」Fast Fourier Transformation
推荐博客：algocode 算法博客个人见解：Fast&nbsp;Fourier&nbsp;Transformation(FFT)Fast&nbsp;Fourier&nbsp;Transformation(FFT)Fast\ Fourier\ Transformation(FFT) 是一种能在 O(nlogn)O(nlogn)O(n\log n) 时间内求多项式的乘积的算法，代码复杂度较小，...
2018-07-16 14:56:18
350
原创 【TopCoder 1570】DesertWind（有后效性的动态规划）
题目链接：【TopCoder 1570】DesertWind题目大意：n×mn×mn\times m的地图上有空地，障碍物和绿洲，每天有一个风向，在得知今天风向后你可以去周围888个格子，如果逆风行走需要耗费333点体力，否则只要耗费111点。求最坏情况下从起点走到绿洲耗费体力的最小值。dp[i][j]dp[i][j]dp[i][j]表示从(i,j)(i,j)(i,j)走到绿洲耗费体力的最...
2018-07-14 21:01:04
660
原创 【AtCoder 2069】Snuke's Subway Trip（构图方法）
题目链接：【AtCoder 2069】Snuke’s Subway Trip题目大意：有nnn个节点，mmm条边，每条边属于一条地铁线路。坐上或换乘一次地铁需要花费111日元，求从111到nnn的最小花费。// [AtCoder 2069] Snuke's Subway Trip#include &lt;queue&gt;#include &lt;cstdio&gt;#inc...
2018-07-14 20:47:46
429
原创 【TopCoder 10664】RowGame（有后效性的动态规划）
题目链接：【TopCoder 10664】RowGame题目大意：给定nnn个格子，每个格子有一个权值wiwiw_i。有一枚棋子，初始在111号格子。你要对棋子进行不大于kkk轮移动，奇数轮向右移，偶数轮向左移，每次移动任意格，获得的价值为原来棋子的位置到新棋子位置格子的权值之和。初始分值为000，每次移动后 分值+分值+分值+=移动获得的权值=移动获得的权值=移动获得的权值。要求每次移动后分...
2018-07-12 22:41:43
775
原创 【TopCoder 8404】WarTransportation（最短路 + 有后效性的动态规划）
题目链接：【TopCoder 8404】WarTransportation题目大意：有一个nnn个节点mmm条边的有向图，一个人要从图的111号节点走到222号节点。但是图的一条边断了，只有走到一条边的端点才能知道一条边是否断掉。问那个人在最坏情况下最少要走多少距离（无解输出−1−1-1）。n≤100,m≤500n≤100,m≤500n\le 100,m\le 500。首先，我们算出wor...
2018-07-12 11:45:12
838
原创 【清华集训 2014】玛里苟斯（组合计数 + 线性基）
题目链接：【清华集训 2014】玛里苟斯 推荐博客：【BZOJ 3811】玛里苟斯：线性基（详细证明）首先想到将kkk分类讨论。k=1k=1k=1时，我们考虑每一位的贡献。若有至少一个数第iii位为111，则对答案的贡献为valuei2valuei2\frac{value_i}{2}。k=2k=2k=2时，发现每个异或和的平方为∑i∑j2i+jbitibitj∑i∑j2i+jbiti...
2018-07-03 08:53:22
815
原创 「算法笔记」线性基
推荐博客：Sengxian的博客 推荐博客：YveH的博客 基：在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。 同样的，线性基是一种特殊的基，它通常会在异或运算中出现，它...
2018-07-02 22:45:20
250
原创 【CodeForces 997C】Sky Full of Stars（组合计数）
题目链接：【CodeForces 997C】Sky Full of Stars官方题解：Codeforces Round #493 — Editorial题目大意：有一个n×nn×nn\times n的网格和三种颜色，问有多少种染色方案，使得至少一行或者一列颜色一样。n≤1000000n≤1000000n\le 1000000如果n≤3000n≤3000n\le 3000，那么直接暴力...
2018-07-02 20:40:43
898
2
转载 【POJ 2311】Cutting Game（SG函数）
题目链接：【POJ 2311】Cutting Game题目大意：n×mn×mn\times m的网格，两个玩家每轮将一个网格切成两半，先切到1×11×11\times 1的网格的人胜利。求先手是否有必胜策略。链接：SG函数详细讲解 链接：题目详解SG函数的大坑到时候再填。先上代码：#include &amp;amp;lt;cstdio&amp;amp;gt;#include &amp;amp;lt;cstring&amp
2018-07-02 15:19:47
202
原创 【SDOI 2010】古代猪文（组合计数）
题目链接：【BZOJ 1951】古代猪文题目大意：给定正整数q,n(1≤q,n≤109)q,n(1≤q,n≤109)q,n(1\le q,n\le 10^9)，求q∑d|nCdnmod999911659q∑d|nCndmod999911659q^{\sum_{d|n}{C_n^d}}\mod 999911659。若q=999911659q=999911659q=999911659，则上试结...
2018-07-01 13:39:47
148
原创 【CQOI 2007】余数之和（数论分块）
题目链接【BZOJ 1257】余数之和题解∑i=1nk&amp;nbsp;mod&amp;nbsp;i=n×k−∑i=1ni×⌊ki⌋∑i=1nk&amp;nbsp;mod&amp;nbsp;i=n×k−∑i=1ni×⌊ki⌋\sum_{i=1}^n{k\ mod\ i}=n\times k-\sum_{i=1}^n{i\times\lfloor\frac{k}{i}\rfloor} 而⌊ki⌋⌊ki⌋\l...
2018-06-28 17:56:35
274
原创 【POJ 2689】Prime Distance（素数筛法）
题目链接【POJ 2689】Prime Distance题解题目的关键在于如何求出lll到rrr之间所有的素数。性质：如果一个数nnn是合数，则它一定有一个≤n‾√≤n\le \sqrt n的素因子。 思路：先筛出222到r√r\sqrt r的所有素数pipip_i，在一一标记lll到rrr中所有pipip_i的倍数。时间复杂度 O(q∑素数p≤r√r−lp)O(q∑素...
2018-06-28 16:24:22
441
原创 「算法笔记」AC自动机
学习笔记这篇Blog讲的很清楚下面是个人的见解。 AC 自动机 = Trie + KMP每一个节点有一个 fail 指针和 alphabet 个 next 指针。插入：同 Trie。 计算 fail 指针：bfs 版的 KMP。 字符串匹配：基本上与 KMP 相同。 详见代码。模版（指针版）// Luogu P3808 AC自动机模版#include ...
2018-06-28 12:24:06
246
原创 「一题多解」多模匹配（AC自动机 / 暴力）
引子难道模版题也可以一题多解？答案是：当然可以。 只要仔细分析题目性质并揣测出题人造数据的方法，就能用简单的暴力通过模版题。但是，切记一点，正式比赛时为了准确性和速度，千万不要使用非主流解法。题目链接本人ACACAC的是洛谷的ACACAC自动机模版。 【模板】AC自动机（简单版）解法一（384 ms）AC自动机直接上。 具体可以参考这篇博客。代码...
2018-06-24 18:22:14
354
原创 【ZJOI 2009】狼和羊的故事（最小割）
题目链接【BZOJ 1412】狼和羊的故事题解如果只有111和222的话，那么就将源点连羊，狼连汇点（容量infinf\inf），狼羊之间连一条容量为111的边。但是，有的领地既不是羊的，也不是狼的。 你可能会想把000归为111（或222），但是仔细想想可以发现还有更优的解。最终的解决方案：000点与四周的所有节点连一条边，这样就可以在000的四周自由切割，没有附加限制...
2018-06-24 09:22:06
245
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人