- 博客(342)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 【LCS】BZOJ2423(HAOI2010)[最长公共子序列]题解
题目概述求两个字符串 AAA 和 BBB 的最长公共子序列以及最长公共子序列的数量。解题报告定义 f[i][j]f[i][j]f[i][j] 表示 AAA 的前 iii 位与 BBB 的前 jjj 位的最长公共子序列，g[i][j]g[i][j]g[i][j] 表示最长公共子序列的方案数。第一问没话说，第二问要注意重复的情况：当 Ai=BjAi=BjA_i=B_j 时，直接从三个状...
2018-02-24 10:30:52
664
原创 【矩阵DP】BZOJ1048(HAOI2007)[分割矩阵]题解
题目概述给出一个有权值的矩阵，一次操作将这个矩阵沿着行或列切成两半，然后这两半也可以执行同样的操作。操作 n−1n−1n-1 次后得到 nnn 个矩阵，求这 nnn 个矩阵的均方差（标准差？傻傻分不清啊QAQ）。解题报告五维DP f[i][j][x][y][k]f[i][j][x][y][k]f[i][j][x][y][k] 表示将矩阵 iii 行到 xxx 行 jjj 列到 yy...
2018-02-20 22:13:07
633
原创 【贪心】BZOJ1060(ZJOI2007)[时态同步]题解
题目概述有一棵有边权的有根树，现在从根开始传播JZ的神犇之力，经过一条边的时间是该边的边权。为了JZ神犇之力的平衡，要求神犇之力传播到所有叶子节点的时间相同。有一种操作是让某条边的边权增加 111 ，求最少的操作数使得神犇之力平衡。解题报告肯定是要把所有叶子节点的时间都变成最长时间叶子节点的时间，而且为了少花费，操作必然是越上面越好，所以只需要先DFS一遍记录一下 MAXiMAXi...
2018-02-19 23:37:57
417
原创 【二分+贪心】BZOJ1052: [HAOI2007]覆盖问题
题目概述有 nnn 个点，用 333 块 L×LL×LL\times L 的布盖住所有点，求最小的 LLL 。解题报告这是道套路贪心假题……首先二分将求最优解问题转换为判定问题，然后我们找出盖住所有点的最小矩阵，则第一块布一定是盖在这个矩阵的四个角上。为什么？因为最边上的点一定要盖住的，那么莫不如就贴着最边上的点盖，套路的贪心想法……第二块布也这么盖，第三块布直接判断就行...
2018-02-18 16:13:24
535
原创 【DP】BZOJ2298(HAOI2011)[problem a]
题目概述有 nnn 个人，第 iii 个人说有 aiaia_i 人排名在他前面， bibib_i 个人排名在他后面（可以有相同排名），问最少有几人说谎。 解题报告第 iii 个人的排名范围是 [ai+1,n−bi][ai+1,n−bi][a_i+1,n-b_i] ，aaa 不同或 bbb 不同的两个人都说真话时区间不能有冲突（否则两人可能为相同排名，这是不可能的）。所以我们可以DP...
2018-02-11 10:48:44
305
原创 【区间DP】BZOJ1055(HAOI2008)[玩具取名]题解
题目概述JZ选择WING四个字母中的任意一个字母作为JZ的基本网名。然后JZ会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替（会给出字母能变成哪些双字母），使得自己的网名能够扩充得很长。现在，他想请你猜猜某一个很长的网名，最初可能是由哪几个字母变形过来的。解题报告DP功底不行了啊QAQ，这应该不算很难的区间DP吧……定义 f[i][j][k]f[i][j]...
2018-02-10 19:32:25
348
原创 【C数学题D贪心】Codeforces Round #461(Div.2)
Acopy一个源文件会新产生一个源文件和一个副本，copy一个副本会新产生两个副本，现在有一个源文件，问能否copy出 xxx 个副本和 yyy 个源文件？瞎搞，注意一些特殊情况。#include<cstdio>using namespace std;int x,y;int main(){ freopen("A.in","r",stdin); ...
2018-02-08 03:42:32
272
1
原创 【LIS】BZOJ1046(HAOI2007)[上升序列]题解
题目概述给出 {an}" role="presentation">{an}{an}\{a_n\} ，求下标字典序最小的上升子序列。解题报告水题吧……先求出 fi" role="presentation">fifif_i 表示以 i" role="presentation">iii 为起点的最长上升子序列，然后只需要先找出第一个 fans1>x" role="presentat
2018-02-06 23:03:16
351
原创 【中位数】BZOJ1045(HAOI2008)[糖果传递]题解
题目概述有 n" role="presentation">nnn 个JZ坐成一圈，每人有 ai" role="presentation">aiaia_i 个神犇值。每人只能给左右两人传递神犇值。每人每次传递一个神犇值代价为 1" role="presentation">111 。用最少的代价使 n" role="presentation">nnn 个JZ神犇值一样，以便虐人。解题报告
2018-02-05 19:21:54
353
原创 【二分+DP】BZOJ1044(HAOI2008)[木棍分割]题解
题目概述有 n" role="presentation">nnn 根木棍, 第 i" role="presentation">iii 根木棍的长度为 Li" role="presentation">LiLiL_i , n" role="presentation">nnn 根木棍依次连结了一起, 总共有 n−1" role="presentation">n−1n−1n-1 个连接处
2018-02-04 23:01:12
1169
原创 【后缀自动机】BZOJ5084[hashit]题解
题目概述给出一个操作串：如果是小写字母，表示在当前字符串后面添加这个小写字母。如果是 −" role="presentation">−−- ，表示删除当前字符串最后的小写字母（保证合法）。求每次操作后当前字符串不同子串的个数。解题报告不同子串个数是后缀自动机裸题，由于每次只删除最后一个小写字母，所以瞎搞就行了……好像也可以后缀平衡树？但是我不会QAQ。示例
2018-02-03 19:08:37
802
2
原创 THUWC2018游记
Day0~2心路历程可以看我的日记啊QwQ。1.29初到长沙，宾馆颓废。1.30上午报到+试机，Ubuntu很滋瓷啊（反正不是NOILinux我都能接受）。打完Emacs配置之后发现括号匹配没用了，问了JZdalao之后才惊奇的发现我括号匹配的指令是背错的QAQ。 下午考试开始： T1：签到题送温暖，瞎搞就行了，真偷税。 T2：什么玩意？不想写了。 T3：什么玩
2018-02-02 18:28:36
1358
2
原创 【线性基】HDU3949[XOR]题解
题目概述给出 n" role="presentation">nnn 个数，求选出的非空集合中异或和第 k" role="presentation">kkk 小的异或和（异或和相同算一次），没有 k" role="presentation">kkk 个输出 −1" role="presentation">−1−1-1 。解题报告如果构造线性基时将矩阵消成对角矩阵，得到的线性
2018-01-25 20:28:27
950
2
原创 线性基
一些线性代数前置知识口胡我是蒟蒻，可能(一定)不严谨，dalao们可以去啃书QAQ。线性空间：在一个域（比如实数域，复数域）内有加法和数乘，加法和数乘都封闭。线性相关&无关：若 n" role="presentation" style="position: relative;">nnn 个向量能组成 0" role="presentation" style="position: rel
2018-01-25 20:23:56
411
原创 【FWT】51Nod1773[A国的贸易]题解
题目概述有 2n" role="presentation" style="position: relative;">2n2n2^n 个点，每次 i" role="presentation" style="position: relative;">iii 点会使 count(i xor j)=1" role="presentation" style="position: re
2018-01-24 10:38:15
480
原创 【LCT+并查集】BZOJ2959[长跑]题解
题目概述CHNJZ可以在 nn 个地方虐场，每次虐场可以踩若干个人。一个地方的人被踩后就不能再踩了（心态已爆炸）。有 mm 个事件：1.地点 xx 到地点 yy 新建了一条边。2.地点 xx 能踩的人变成了 yy 。3.询问从 xx 到 yy 最多能踩多少人。解题报告显然是动态树问题，可以用LCT解决。由于图中会出现边双，不能重复计算，所以需要将边双缩点。考虑合并 xx 到
2018-01-17 16:24:28
458
原创 【FWT】BZOJ4589[Hard Nim]题解
题目概述有 nn 堆石子，石子数都是不超过 mm 的素数。进行Nim游戏，求先手必败的方案数。解题报告就是求异或和为 00 的方案数。先构造向量 Pi=[i是素数]P_i=[i是素数] ，然后可以看作 nn 个 PP 求异或卷积。所以先DWT，然后用快速幂求出卷积，最后IDWT就行了。示例程序#include#includeusing namespace std
2018-01-15 14:09:38
502
原创 【树形DP+FWT】HDU5909[Tree Cutting]题解
题目概述定义一棵树 {vn}\{v_n\} 的权值为 v1 xor v2 xor v3 xor⋯vnv_1\ xor\ v_2\ xor\ v_3\ xor\cdots v_n 。给出一棵树，统计权值 [0,m)[0,m) 在这棵树子图（子图显然也是树）中的出现情况。解题报告定义 f[i][j]f[i][j] 表示以 ii 为根异或权值为 jj 的方案数，对于 ii 的儿子 son
2018-01-15 13:25:27
608
原创 FWT
另一种卷积多项式乘法的卷积是这样的： Ci=∑j+k=iAjBkC_i=\sum_{j+k=i}A_jB_k 然而还有种神奇的卷积（ ⊕\oplus 是位运算）： Ci=∑j⊕k=iAjBkC_i=\sum_{j\oplus k=i}A_jB_k FWT可以快速求这种卷积。快速沃尔什变换因为FFT用了系数 →\to 点值，用点值快速求卷积，再点值 →\to 系数的方
2018-01-15 11:14:01
2089
1
原创 【欧拉回路】UOJ117[欧拉回路]题解
题目概述判断无向图和有向图是不是欧拉回路。如果是，求出任意一条欧拉回路。解题报告判断欧拉回路：无向图：每个点的度数都是偶数。有向图：每个点的出度都等于入度。证明？我不会啊！怎么求欧拉回路呢？因为已经确定了是欧拉回路，所以我们可以直接DFS瞎搞。随便从一个点开始DFS，一条边走过后就删除。回溯时将其入队。最后的队列反过来就是答案。原理：最后的队列是返回路径，所以反过
2018-01-14 19:11:17
669
原创 【线段树】BZOJ2957[楼房重建]题解
题目概述ZigZagK在 (0,0)(0,0) ，有 nn 座建筑（刚开始高度为 00 ）和 mm 次改造：把第 ii 个建筑高度改为 yy ，求每次改造后ZigZagK能看见的建筑数量。解题报告吃我分块。这好像是套路题？显然就是要求斜率变大的次数。用线段树维护建筑高度，然后定义一个函数 Find(p,k)Find(p,k) 表示在 pp 节点前放一个斜率 kk 得到的斜率变大
2018-01-12 10:34:46
310
原创 【中国剩余定理-非互质】POJ2891[Strange Way to Express Integers]题解
题目概述求解模方程组，模数不一定互质。解题报告互质解法戳这里。当然，处理非互质的方法用来处理互质也是可以的。我们观察两个模方程：x≡a1(mod m1)x≡a2(mod m2)x\equiv a_1(mod\ m_1)\\x\equiv a_2(mod\ m_2) 。转化：x=a1+x1m1=a2+x2m2⇔x2m2≡a1−a2(mod m1)x=a_1+x_1m_1=a_2+x_2m_2\Left
2018-01-10 15:11:02
282
原创 【杜教筛】BZOJ4916[神犇(JZ)和蒟蒻(ZZK)]题解
题目概述给出 nn ，求 A=∑ni=1μ(i2),B=∑ni=1φ(i2)A=\sum_{i=1}^n{\mu (i^2)},B=\sum_{i=1}^n{\varphi (i^2)} 。解题报告第一问…… i2i^2 ？喜闻乐见输出 11 。第二问，由于 φ(i2)=iφ(i)\varphi(i^2)=i\varphi(i) ，所以要求 ∑ni=1iφ(i)\sum_{i=1}^{n}i\var
2018-01-09 22:28:21
588
原创 【普通型母函数+容斥+FFT】BZOJ3771[Triple]题解
题目概述ZigZagK有 nn 把价值不一样的斧子，CHNJZ偷走了 11 把或 22 把或 33 把，对于每个可能的总损失，计算有几种可能的方案。解题报告emm……显然是母函数啊？但是有数量限制。由于最多偷走三把，所以我们可以直接三种情况都讨论过去。11 把：母函数：A(x)=xa1+xa2+xa3+⋯+xanA(x)=x^{a_1}+x^{a_2}+x^{a_3}+\cdots+x^{a_n}
2018-01-09 18:48:38
413
原创 【指数型母函数】HDU1521[排列组合]题解
题目概述有 nn 个物品，第 ii 个物品有 numinum_i 个，求选出 mm 个物品组成排列的方案数。解题报告如果不是组成排列，就是经典的普通型母函数。我们发现无法用普通型母函数表示出“组成排列”这个条件，实际上这是经典的指数型母函数（摘自这里）。 口袋中有白球 22 个，红球 33 个，黄球 11 个，任取 33 个作为一个排列，总共有多少种排列？ 类似地用指数型母函数解决：用
2018-01-09 08:55:24
334
原创 【普通型母函数】HDU1085[Holding Bin-Laden Captive!]题解
题目概述有 num1num_1 个 11 元硬币，num2num_2 个 22 元硬币，num3num_3 个 55 元硬币，求不能组成的最小价值。解题报告显然是二进制拆分做01背包，然而数据范围比较大，所以效率不是很好。其实这道题可以用母函数轻松解决：（摘自维基和这里） 在数学中，某个序列的母函数是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。
2018-01-09 07:39:29
265
原创 【可并堆】BZOJ1367(Baltic2004)[sequence]题解
题目概述给出 {an}\{a_n\} ，选择一个上升序列 {bn}\{b_n\} 使得 ∑ni=1|ai−bi|\sum_{i=1}^{n}|a_i-b_i| 最小，求最小值。解题报告对于这道题，我们可以将 {an}\{a_n\} 改成 {an−n}\{a_n-n\} ，然后就转化为求不下降序列 {bn}\{b_n\} 。如果 {an}\{a_n\} 递减，那么 {bn}\{b
2018-01-08 11:46:02
333
原创 【后缀自动机+LCT】BZOJ2555[SubString]题解
题目概述给出初始字符串 initinit 和 mm 个操作，操作有两种：1.在当前字符串后插入一个字符串。2.询问一个字符串在当前字符串中的出现次数。强制在线。解题报告（之前做了后缀自动机和LCT就tm为了这道题）强制在线插入询问，后缀数组，KMP全都不行。数据范围又贼大，我们想到后缀自动机。后缀自动机求字符串 ss 出现次数：先识别 ss ，若无法识别，答案为 00 ，否则答
2018-01-08 08:24:25
429
原创 【LCT维护子树信息】BZOJ4530(Bjoi2014)[大融合]题解
题目概述有 nn 个点， mm 个操作。操作有两种：1.连接 xx 和 yy 。2.询问经过 (x,y)(x,y) 的路径数。解题报告答案显然就是 si(x)×si(y)si(x)\times si(y) ，但是有连接操作，可以考虑LCT（好像有很多离线做法，我不是很清楚QAQ）。问题就是如何维护子树信息。LCT实链上的信息可以方便维护，所以我们关注虚边：虚边只在Access和
2018-01-06 19:57:09
435
原创 【后缀自动机】POJ1509[Glass Beads]题解
题目概述给出小写环形字符串，问在哪个位置断开形成的字符串字典序最小（相同取靠前）？解题报告学了后缀自动机像一场梦一样……现在tm一点都不记得了QAQ。回顾：Right集合，father(parent)树，根据这两个东西脑补出拓展函数，千万别把自动机和father(parent)树搞混。这道题就是陈老师ppt上的那道题，先建好后缀自动机，然后每次跑编号最小边，就得到答案了。
2018-01-05 19:45:22
370
原创 【LCT+线段树】BZOJ4817(Sdoi2017)[树点涂色]题解
题目概述有一棵 nn 个点的有根树，其中 11 号点是根节点。每个点有颜色且刚开始颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。可能会进行 mm 次这几种操作：1 x：把点x到根节点的路径上所有的点染上一种没有用过的新颜色。2 x y：求x到y的路径的权值。3 x y：在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值
2018-01-05 13:04:34
363
原创 【LCT】BZOJ2843[极地旅行社]题解
题目概述有 nn 个点，第 ii 个点有 aia_i 个帝王JZ，给出 mm 个操作，操作有三种：1.连接 xx 和 yy 。2.令 ax=ya_x=y 。3.询问 xx 到 yy 路径上帝王JZ的总和。解题报告emm……LCT裸题……我在练板子……#include<cstdio>#include<cctype>#include<algorithm>using namespace std;c
2018-01-04 13:03:35
296
原创 【LCT】BZOJ2049(Sdoi2008)[Cave 洞穴勘测]题解
题目概述有 nn 个点， mm 个操作，操作有三种：1.连接 xx 和 yy 。2.断开 xx 和 yy 。3.询问 xx 和 yy 是否连通。解题报告LCT裸题喽，以前板子太长了，我来放个新板子QAQ。#include<cstdio>#include<cctype>#include<algorithm>using namespace std;const int maxn=10000;int
2018-01-04 09:57:55
296
原创 【分块+回文自动机】LibreOJ6070(2017 山东一轮集训 Day4)[基因]题解
题目概述给出一个由小写字母构成的字符串，有 mm 个询问 [l,r][l,r] ，表示求 s[l..r]s[l..r] 中本质不同回文字串的个数，强制在线。解题报告因为强制在线询问区间，所以我们想到分块。以每个块的左端点开始构造后缀的回文自动机，就可以得到 ans[i][j]ans[i][j] 表示从第 ii 个块左端点开始到 jj 中不同回文子串的个数。然后对于每个询问，我们都只需要查询至多一个块
2018-01-03 19:07:12
667
原创 【FFT】BZOJ3527(Zjoi2014)[力]题解
题目概述给出 {qn}\{q_n\} ，求： Ei=∑j=0i−1qj(i−j)2−∑j=i+1nqj(i−j)2E_i=\sum_{j=0}^{i-1}{q_j\over (i-j)^2}-\sum_{j=i+1}^{n}{q_j\over(i-j)^2}解题报告FFT其实是在求向量卷积，形式是这样的： ci=∑j=0iajbi−jc_i=\sum_{j=0}^ia_jb_{i-j}然
2018-01-03 09:39:12
491
原创 FFT
前置知识两种多项式表示法：系数表示法：A(x)=∑n−1i=0aixiA(x)=\sum_{i=0}^{n-1}a_ix^i ，其中 {an−1}\{a_{n-1}\} 就是系数。点值表示法：代入 nn 个不同的 xx 得到对应的 A(x)A(x) 记为 (x,y)(x,y) ，这 nn 个点 (x0,y0),(x1,y1)⋯(xn−1,yn−1)(x_0,y_0),(x_1,y_1)\cdots(
2018-01-02 18:49:46
656
1
原创 回文自动机
作用好像是2015年时战斗民族某巨佬发明的，可以快速求一个串里有多少本质不同的回文子串以及每个回文子串出现的次数。实现回文自动机由两棵树构成，一棵是 eveneven 树，另一棵是 oddodd 树。每个节点对应了一个回文子串，有如下信息：lenlen ：该回文子串的长度。failfail ：该回文子串最长回文后缀对应的节点。son[k]son[k] ：在该回文字串两端添加 kk 字符之后到达
2018-01-02 08:28:02
490
原创 【后缀数组+Manacher】BZOJ3676(Apio2014)[回文串]题解
题目概述给出一个字符串，定义一个回文子串的权值为长度 ×\times 出现次数。求最大权值。解题报告求回文子串可以用Manacher，每当找到一个回文子串，就用后缀数组求出其出现次数。因为是求子串出现次数，所以构造 heightheight 再二分就可以 O(log2n)O(log_2n) 查找。本质不同回文子串的个数是 O(n)O(n) 的，所以效率是 O(nlog2n)O(nlog_2n) 。由
2017-12-31 23:05:55
450
原创 【替罪羊树-动态标号+线段树】BZOJ3600[没有人的算术]题解
题目概述定义一种数，这种数只有 00 和 (a,b)(a,b) ，其中 a,ba,b 是这种数。定义 << ：1. 00 最小。2. (a,b)<(c,d),c>a(a,b)<(c,d),c>a 。3. (a,b)<(a,c),c>b(a,b)<(a,c),c>b 。现在有 nn 个这种数，刚开始都是 00 。给出 mm 个操作：1.将 a[k]a[k] 赋值为 (a[l],a[r])(a[l],a
2017-12-31 00:08:09
507
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人