- 博客(103)
- 收藏
- 关注
RSS订阅转载 长链剖分优化dp三例题
首先，重链剖分我们有所认识，在dsu on tree和数据结构维护链时我们都用过他的性质。 在这里，我们要介绍一种新的剖分方式，我们求出这个点到子树中的最长链长，这个链长最终从哪个儿子更新而来，那个儿子就是所谓的“重儿子”，也可以叫长儿子。 我们的做法就是，在统计一个点的信息时，对于重儿子，我们直O(1)接继承它的答案（这里有指针技巧，只能看代码，不可言传），对于轻...
2019-03-23 20:04:00
497
转载 CF815D Karen and Cards 官方题解翻译
看到这道题，网上没有中文版的官方题解，于是就自己翻译了一遍。 不是机器翻译，是一个字一个字纯手翻译的，如果有错误欢迎指正。 比如我们有一张卡片，三个参数分别是a1 = 4, b1 = 2, c1 = 3. 方便起见，我们令p = q = r = 5. 考虑什么样的卡片能够击败这张. 我们可以固定一个参数c，来观察对于不同的c，有什么特殊的性质：...
2019-03-08 17:35:00
311
转载 [九省联考2018] IIIDX 线段树+贪心
题目： 给出 k 和 n 个数，构造一个序列使得 d[i]>=d[i/k] ，并且字典序最大。分析： 听说，当年省选的时候，这道题挡住了大批的高手，看上去十分简单，实际上那道弯段时间内是转不过来的。 首先，一个套路是，将这个序列的关系抽象成一棵树，i的父亲是floor(i/k)，我们要要求子树内部的点的权值都比父亲大。 我们观察子任务的特殊限制，d...
2019-03-01 22:52:00
205
转载 BZOJ 4016 最短路径树问题 最短路径树构造+点分治
题目： BZOJ4016最短路径树问题分析： 大家都说这是一道强行拼出来的题，属于是两种算法的模板题。 我们用dijkstra算法算出1为源点的最短路数组，然后遍历一下建出最短路树。 之后就是裸的点分治算法，一个桶，两个变量就解决了这道题。代码： 1 #include<bits/stdc++.h> 2 #define pi...
2019-02-27 20:07:00
177
转载 Luogu P3727 曼哈顿计划E 点分治+hash
题目： P3727曼哈顿计划E分析： 大长题面容易给人一种不可做的错觉，但是这题考的知识点都是我们熟悉的。 稍加分析我们可以得到，我们可以把每个点当成一个单独的游戏，如果k=1，就是简单的nim游戏，这样，当多个游戏放在一起的时候，我们就可以根据一条链的权值异或和来判断必胜必败。 这个给我们启发，根据SG定理（应该是这个定理？）当我们选一条链，根据这条链上所有...
2019-02-27 16:10:00
119
转载 Luogu P2664 树上游戏 dfs+树上统计
题目： P2664 树上游戏分析： 本来是练习点分治的时候看到了这道题。无意中发现题解中有一种方法可以O(N)解决这道题，就去膜拜了一下。 这个方法是，假如对于某一种颜色，将所有这种颜色的点全部删去，原树会被割成若干棵小树，那么这个颜色对每个点的贡献就是：树的大小n - 所在小树的大小sz。所以我们要求出对于每个点来说，删去所有这个点颜色的点，这个点以下的小树...
2019-02-27 09:26:00
147
转载 CF724E Goods transportation
题意： 小明升任了 CF 国的大总管，他管辖的 n 个城市，编号为 1..n。每个城市生产了 pi 个货物，限制最多可以卖掉 si 个货物。对于每两个城市 i, j，如果 i < j，则可以最多从 i 运送 c 个货物到 j。注意不能反向运送，却可以在多个城市之间送来送去。现在小明想知道，经过运输后，最多能卖掉多少个货物。分析： 我们按照题意试试建图跑网络流？...
2019-02-25 20:31:00
293
转载 CF547D Mike and Fish 建图
题意： 有点长→CF547DMike and Fish。分析： 其实也没什么好分析的，我这也是看的题解。 （不过，那篇题解好像文字的代码不太对劲） 这里直接说做法，正确性自证： 对输入的，将横、纵坐标相等的点分别两两连边，之后只需要dfs跑一个染色，使得一条边两个端点颜色都不一样即可，这样就可以确定每一个点放红色还是蓝色，输出即可。（至于哪个是红哪...
2019-02-25 17:52:00
178
转载 BZOJ4513 SDOI2016 储能表 记忆化搜索（动态规划）
题意： 题面中文，不予翻译：SDOI2016储能表分析： 据说有大爷用一些奇怪的方法切掉了这道题%%%%% 这里用的是大众方法——动态规划。 其实这是一道类似于二进制数位dp的动态规划题，（但是实际上还不是特别典型的数位dp）这里就要我们对问题的深入理解。 如果我们按照思路进程来发展的话，首先，我们会想到把求和式和k拆开，先求出所有大于k的(i^j...
2019-02-25 16:57:00
135
转载 CF716E Digit Tree 点分治
题意： 给出一个树，每条边上写了一个数字，给出一个P，求有多少条路径按顺序读出的数字可以被P整除。保证P与10互质。分析： 统计满足限制的路径，我们首先就想到了点分治。 随后我们就需要考量，我们是否能统计过某个点的合法路径。我们看，由题目性质，我们可以求对于一个根，所有点到根的路径组成的数，以及根到所有点的路径所组成的数。然后我们就可以对前者开一个数组（其实是...
2019-02-25 10:57:00
116
转载 IOI2011 Race 点分治
题意： 给一棵树，每条边有权。求一条简单路径，权值和等于K，且边的数量最小。分析： 对于这道题，和计算长度恰好为k的路径数量差不多，只不过那个所谓的桶里不装数量，装达到这个长度的最小的边数。 （感觉把这个桶应用好，能解决点分治的不少题目） 当然呢，为了进一步节约时间，我们不必每次都把桶memset一次，只需要把用过的位置都记录下来，用完后还原即可。 ...
2019-02-23 21:25:00
172
转载 CF161D Distance in Tree 点分治
题目： 输入点数为N一棵树，求树上长度恰好为K的路径个数分析： 题目的数据范围不是很紧，点分治也可以过，树形dp也可以过。这里采用点分治做法。 我们只需要单开一个类似于桶的数组，跑点分治套路，统计即可，每次处理一棵子树，先在桶上跑统计，处理完一棵子树再更新桶。这样可以保证每一段路径都直接跨过根节点内。 记得开long long。代码： 1...
2019-02-23 19:53:00
188
转载 Luogu P3806 点分治模板1
题意： 给定一棵有n个点的树询问树上距离为k的点对是否存在。分析： 这个题的询问和点数都不多（但是显然暴力是不太好过的，即使有人暴力过了） 这题应该怎么用点分治呢。显然，一个模板题，我们直接用套路，每次找重心，对于这个重心处理，过当前点的符合要求的路径。 我们可以看到这个最大长度1e7，开数组是开得下的，所以维护一个数组（或者bitset也行）来保存之前...
2019-02-23 17:36:00
110
转载 CF528D Fuzzy Search 字符串匹配+FFT
题意： DNA序列，在母串s中匹配模式串t，对于s中每个位置i，只要s[i-k]到s[i+k]中有c就认为匹配了c。求有多少个位置匹配了t。分析： 这个字符串匹配的方式，什么kmp，各种自动机都不灵。 所以有一个邪门功夫，fft字符串匹配。（做过洛谷《残缺的字符串》一题的应该都不陌生，带通配符的匹配字符串可以用fft卷积来做） 首先，由于字符集大小只有4...
2019-02-23 11:57:00
178
转载 CF666E Forensic Examination SAM+倍增，线段树和并
题面： 给你一个串S以及一个字符串数组T[1..m]，q次询问，每次问S的子串S[p_l..p_r]在T[l..r]中的哪个串里的出现次数最多，并输出出现次数。如有多解输出最靠前的那一个。分析： 第一次见这道题时，由于对算法十分陌生，就将其压进了任务计划，这一天又提到了这道题，这才算是重见天日。 数据结构题，越来越注重多种数据结构的搭配使用。搭配使用呢，我们就...
2019-02-23 08:59:00
166
转载 CQOI2018 九连环 打表找规律 fft快速傅里叶变换
题面： CQOI2018九连环分析： 个人认为这道题没有什么价值，纯粹是为了考算法而考算法。 对于小数据我们可以直接爆搜打表，打表出来我们可以观察规律。 f[1~10]: 1 2 5 10 21 42 85 170 341 682 我们可以发现的规律是，当i为奇数时，f[i]=f[i-1]*2+1，偶数时f[i]=f[i-1]*2。 既然这样，我们...
2019-02-21 17:39:00
269
转载 CF993E Nikita and Order Statistics 多项式卷积 快速傅里叶变换
题意： 给你一个数组a1~an，对于k=0~n，求出有多少个数组上的区间满足：区间内恰好有k个数比x小。x为一个给定的数。n<=10^5。值域没有意义。分析： 大神们都说这道题是一个套路题，真是长见识%%%。 首先我们可以将题面转化，因为x是预先给出的，所以我们可以对其进行预处理，将数列中小于x的数都设为1，其他都为0，然后求一个前缀和，另前缀和数组为s...
2019-02-20 20:52:00
200
转载 NOIP2016 天天爱跑步 线段树合并
题意： 给出一棵n个点的树，以及m次操作，每次操作从起点向终点以每秒一条边的速度移动（初始时刻为0），最后对于每个点询问有多少次操作在经过该点的时刻为某值。 （题面太毒瘤建议自己去题库食用）分析： 记得当初做这道题的时候，又差分又倍增还开桶，十分毒瘤，后来学到了线段树合并，又看到了这道题，所以就写了这篇解题报告。 每一条从S到T的路径（其实就是链），可以...
2019-02-18 16:14:00
153
转载 BZOJ 3123 SDOI2013 森林 启发式合并+主席树
题意： 给出一个森林，强制在线，支持动态加边和询问链上第k大，保证加边后图仍然是森林。分析： 有一点经验的选手都清楚，动态加边想LCT，第K大想主席树，于是有大爷LCT+主席树秒了%%%（我并不会） 观察问题，出题人在这里摆下了一个疑阵，故意引我们向link-cut tree上去思考，但是，我们发现，这个招数未免太过手下留情，如果出题人想要让我们非用LCT不可呢，不...
2019-02-17 17:20:00
118
转载 BZOJ3545 Peaks 离线处理+线段树合并
题意： 在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。分析： 我们把题目中的限制分离出来： 1. 困难值不超过x。 2. 能达到的第k高的...
2019-02-17 16:59:00
140
转载 BZOJ2212【POI2011】ROT:Tree Rotation 线段树合并
题意： 给一棵n(1≤n≤200000个叶子的二叉树，可以交换每个点的左右子树，要求叶子遍历序的逆序对最少。分析： 求逆序对我们可以想到权值线段树，所以我们对每个点建一颗线段树（为了避免空间爆炸，采取动态开点的科技） 两个子节点可以交换，于是我们可以递归，自底向上贪心解决问题，每次线段树合并，在合并时，统计交换左右子节点后，横跨当前位置的逆序对数量，以及不交换子节点...
2019-02-17 16:40:00
109
转载 BZOJ 2502 Luogu P4843 清理雪道 最小流
题意： 滑雪场坐落在FJ省西北部的若干座山上。 从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。 你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。 由于每次飞行的耗费是固定的，...
2019-01-11 20:19:00
114
转载 BZOJ 4464 旅行时的困惑 最小流
题面： Waldives 有 N 个小岛。目前的交通系统中包含 N-1 条快艇专线，每条快艇 专线连接两个岛。这 N-1条快艇专线恰好形成了一棵树。 由于特殊的原因，所有N-1条快艇专线都是单向的。这导致了很多岛屿之间 不能相互到达。因此，Waldives 政府希望新建一些公交线路，使得建设完毕后， 任意两个小岛都可以互相到达。为了节约开支，政府希望建设最...
2019-01-11 19:48:00
95
转载 BZOJ 3876 支线剧情 有源汇有上下界最小费用可行流
题意： 给定一张拓扑图，每条边有边权，每次只能从第一个点出发沿着拓扑图走一条路径，求遍历所有边所需要的最小边权和分析： 这道题乍一看，可能会想到什么最小链覆盖之类的，但是仔细一想，会发现不行，一是因为每条边都会有贡献，而不是每条链，二是因为边有特定的边权，所以这道题只能用建图复杂一些的网络流来解决。 其实也挺简单的。都不用建超级源点，直接从1号点当源点就行，每条边费...
2019-01-11 19:25:00
176
转载 BZOJ 2055 80人环游世界 有上下界最小费用可行流
题意： 现在有这么一个m人的团伙，也想来一次环游世界。 他们打算兵分多路，游遍每一个国家。 因为他们主要分布在东方，所以他们只朝西方进军。设从东方到西方的每一个国家的编号依次为1...N。假若第i个人的游历路线为P1、P2......Pk(0≤k≤N)，则P1<P2<......<Pk。 众所周知，中国相当美丽，这样在环游世界时就有很多人经过中国。...
2019-01-11 19:03:00
143
转载 BZOJ 2406 LuoguP4194 矩阵 有上下界可行流
分析： 这道题乍一看……卧槽这都什么玩意…… 然后发现给了个A矩阵，要求一个可行的B矩阵，使得矩阵C=A-B的每一行的和的绝对值和每一列的和的绝对值的最大值最小…… 好拗口啊…… 什么最大值最小之类的，考的无非就是二分，我们二分一个答案，之后建图跑网络流。 因为要判断是否合法，所以我们想到了用有上下界的可行流，在这里我们采用有源汇的有上下界可行流。...
2019-01-11 17:53:00
129
转载 BZOJ4873 LuoguP3749 寿司餐厅
题面太长，请诸位自行品尝—>寿司餐厅分析： 首先题目中给了限制条件，假如选了D(i,j)（i<j），那么也就选了D(i+1,j)和D(i,j-1)两个点。 于是我们一下就明白了，哦，最大权闭合子图~ 所以我们让每一个D代表一个点，然后对于每个D(i,j)代表的点，分别向D(i+1,j)和D(i,j-1)所代表的点连边（容量为inf）,然后按照最大权...
2019-01-11 17:20:00
67
转载 51nod 1551 集合交易 最大权闭合子图
题意： 市场中有n个集合在卖。我们想买到满足以下要求的一些集合，所买到集合的个数要等于所有买到的集合合并后的元素的个数。 每个集合有相应的价格，要使买到的集合花费最小。 这里我们的集合有一个特点：对于任意整数k(k>0)，k个集合的并集中，元素的个数不会小于k个。 现在让你去市场里买一些满足以上条件集合，可以一个都不买。分析： 根据集合的特点...
2019-01-11 16:05:00
110
转载 BZOJ 1565 植物大战僵尸 最大权闭合子图+网络流
题意： 植物大战僵尸，一个n*m的格子，每 个格子里有一个植物，每个植物有两个属性： （1）价值； （2）保护集合，也就是这个植物可以保护矩阵中的某些格子。 现在你是僵尸，你每次只能从(i,m) 格子进入，从右向左进攻。若一个格子是被保护的那么你是不能进入的。每进入一个格子则吃掉该格子的植物并得到其价值（价值有可能是负的)，可以中途返回。问可以得到的最大价值是多少...
2019-01-11 15:41:00
157
转载 Hihocoder #1938 最大权闭合子图模板
这里的讲解很不错，适合作为入坑题：Hihocoder#1938代码：#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#defi...
2019-01-10 21:58:00
107
转载 BZOJ 4519 不同的最小割 最小割树
题面： 把每两个点当成源汇，求N*(N-1)个最小割中不同的有多少个 N<=850分析： 有这样一个结论：一张无向图不同的最小割最多有n-1个。 那么我们一定可以建出一棵树，使得这棵树中每两个点之间的最小割等于原图的两个点间的最小割。 我们倒也没必要吧这棵最小割树建出来。我们只需要做做样子，跑一下建树的过程就好，怎么办呢： 我们在原无向图中任选两...
2019-01-10 21:49:00
84
转载 BZOJ2007 NOI2010 海拔 平面图转对偶图 最小割
题面太长啦，请诸位自行品尝—>海拔分析： 这是我见过算法比较明显的最小割题目了，很明显对于某一条简单路径，海拔只会有一次变换。 而且我们要最终使变换海拔的边权值和最小。 我们发现变换海拔相当于将图割开，左上右下两个点分别属于两个不同的集合，那这就是一个很形象的最小割模型。 我们只需要平面图转转对偶图，将图中每个面变成点，连边跑最短路即可。转换的...
2019-01-10 21:35:00
144
转载 BZOJ1001 狼抓兔子 平面图转对偶图 最小割
现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：左上角点为(1,1),右下角点为(N,M)(上图中N=3,M=4).有以下三种类型的道路1:(x,y)<==>(x+1,y)2:(x,y)<==>(x,y+1)3:(x,y)&l...
2019-01-10 21:27:00
122
转载 BZOJ 2039 人员雇佣 二元关系 最小割
题面太长了，请各位自行品尝—>人员雇佣分析： 借用题解的描述： a.选择每个人有一个代价Ai b.如果有两个人同时选择就可以获得收益Ei,j c.如果一个人选择另一个不选会产生代价Ei,j 这是一道模型题（不是模板题是模型题）我们要记住这种建模。 之前说过，最小割问题关键在于“舍弃”，所以说我们这个也是，要么舍弃Eij，要么...
2019-01-10 21:22:00
139
转载 BZOJ 3996 线性代数 最小割
题意： 给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得 D=（A*B-C）*A^T最大。其中A^T为A的转置。输出D分析： 这道题比较绕，我们需要看清题目中那个式子的本质。A*B的贡献是正的，说明这是价值。C的贡献是负的，说明这是代价。 仔细理解这句话“只有ai和aj同时为1的时候，才对答案有bij的贡献。使ai为1的代价为ci”...
2019-01-10 20:41:00
103
转载 BZOJ 3144 切糕 最小割
题意： 一个矩阵，每个格子分配一个数，不同的数字，代价不同，要求相邻格子数字差小等于d 求最小代价。分析： 我猜肯定有人看题目就想到最小割了，然后一看题面理科否决了自己的这个想法…… 没错，就是最小割…… 你是否还记得，在第一篇网络流题解中，我们了解了网络流最重要的是“限制”二字。 我们在这道题中，先把限制放宽，考虑在不限制编号差小于等于d的...
2019-01-10 20:01:00
119
转载 BZOJ 4823 Luogu P3756 老C的方块 染色+最小割
题面太长了请各位自行品尝—>老C的方块分析： 我们要解决掉所有使人弃疗的组合，还要保证花费最小，容易想到最小割（当然你要是想费用流的话，我们就没办法定义流量了） 我们来分析一下那些令人弃疗的组合，他们的规律： 首先是两个和特殊边直接相邻的方块（以下简称轴方块），加上两侧各任意一个边缘方块，组成了令人弃疗的组合。 所以我们有三种选择（准确地说其实只有两种，...
2019-01-10 18:00:00
94
转载 BZOJ 3158 千钧一发 最小割
分析： 偶数对满足条件2，所有奇数对满足条件1。 如果你能一眼看出这个规律，这道题就完成了一半。 我们只需要将数分为两类，a值为奇数，就从S向这个点连容量为b值的边，a值为偶数，就从这个点向T连容量为b值的边。 暴力枚举，对于奇集合和偶集合中不能共存的两个数，连容量为无穷大的边。 求出最小割，代表这个割集要被我们舍弃。 然后直接用b值总和减去...
2019-01-10 17:05:00
1048
转载 WC2007 石头剪刀布 数学+最小费用最大流
题面： 有N个人参加一场比赛，赛程规定任意两个人之间都要进行一场比赛：这样总共有N*(N-1)/2场比赛。比赛已经进行了一部分，我们想知道在极端情况下，比赛结束后最多会发生多少剪刀石头布情况。即给出已经发生的比赛结果，而你可以任意安排剩下的比赛的结果，以得到尽量多的剪刀石头布情况。 剪刀石头布情况，即无序三元组(A, B, C)，满足其中的一个人在比赛中赢了另一个人，另一个人赢了...
2019-01-10 16:48:00
179
转载 BZOJ 1070 修车
题意： 同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。分析： （个人认为这题如果改成个第三代排队接水之类的，得有好多人拿贪心做） 这题就是...
2019-01-10 16:12:00
90
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人