上一页 1 ··· 20 21 22 23 24 25 26 27 28 ··· 52 下一页
2018年8月15日
长链剖分学习笔记
摘要： 长链剖分学习笔记 简介 长链剖分也是一种树链剖分，平时我们说树链剖分，一般都是直接默认为轻重链剖分。 轻重链剖分的优秀性质在于从任意一个点开始，向上跳跃，跳过的重链数量不会超过$log$级别。 这样子可以很优秀的解决两点之间链的问题。 对于解决一些子树的信息问题，我们可以用$dsu\ on\ tre 阅读全文
posted @ 2018-08-15 07:58 小蒟蒻yyb 阅读(9507) 评论(9) 推荐(13)
【COGS2652】秘术「天文密葬法」（长链剖分，分数规划）
摘要： 【COGS2652】秘术「天文密葬法」（长链剖分，分数规划） 题面 "Cogs" 上面废话真多，建议直接拉到最下面看一句话题意吧： 给个树，第i个点有两个权值ai和bi，现在求一条长度为m的路径，使得Σai/Σbi最小 题解 看到这个式子就是裸的分数规划吧。。。 二分一个答案$k$，式子变成了找一条 阅读全文
posted @ 2018-08-15 07:39 小蒟蒻yyb 阅读(1461) 评论(0) 推荐(0)
2018年8月14日
【CF1009F】Dominant Indices（长链剖分）
摘要： 【CF1009F】Dominant Indices（长链剖分） 题面 "洛谷" "CF" 翻译： 给定一棵$n$个点，以$1$号点为根的有根树。 对于每个点，回答在它子树中， 假设距离它为$d$的点有$f_d$个，求最大的$f_d$，并且输出$d$，如果有多个$f_d$相同，输出最小的$d$。 题解 阅读全文
posted @ 2018-08-14 21:48 小蒟蒻yyb 阅读(1109) 评论(0) 推荐(0)
【BZOJ3653】谈笑风生（长链剖分）
摘要： 【BZOJ3653】谈笑风生（长链剖分） 题面 "BZOJ" "洛谷" 权限题啊。。。。 题解 首先根据题目给的条件，发现$a,b$都要是$c$的父亲。 所以这三个点是树上的一条深度单增的链。 因为$a,b$之间距离不超过$k$，并且$a$被钦定了，所以只有两种情况： 一种是$a$是$b$的祖先，贡 阅读全文
posted @ 2018-08-14 20:17 小蒟蒻yyb 阅读(1637) 评论(0) 推荐(0)
2018年8月13日
【BZOJ3252】攻略（长链剖分，贪心）
摘要： 【BZOJ3252】攻略（长链剖分，贪心） 题面 "BZOJ" 给定一棵树，每个点有点权，选定$k$个叶子，满足根到$k$个叶子的所有路径所覆盖的点权和最大。 题解 一个假装是对的贪心： 每次选择最大的路径，然后将路径上所有点的权值清零。 那么我们可以用长链剖分来实现这个贪心。 链长改为最大的路径权 阅读全文
posted @ 2018-08-13 22:16 小蒟蒻yyb 阅读(1348) 评论(0) 推荐(2)
【BZOJ4559】成绩比较（动态规划，拉格朗日插值）
摘要： 【BZOJ4559】成绩比较（动态规划，拉格朗日插值） 题面 "BZOJ" "洛谷" 题解 显然可以每门课顺次考虑， 设$f[i][j]$表示前$i$门课程$zsy$恰好碾压了$j$个$yyb$的方案数。 那么，思考转移，显然是原来碾压了$k$个人，但是在考虑到这一门课程的时候有些人没被碾压了， 所 阅读全文
posted @ 2018-08-13 20:33 小蒟蒻yyb 阅读(475) 评论(0) 推荐(0)
【BZOJ3622】已经没有什么好害怕的了（动态规划，容斥）
摘要： 【BZOJ3622】已经没有什么好害怕的了（动态规划，容斥） 题面 "BZOJ" 题解 很明显的，这类问题是要从至少变成恰好的过程，直接容斥即可。 首先我们要求的是(糖果 药片)=(药片 糖果)+k，再加上保证不存在相同的数， 所以(糖果 药片)+(药片 糖果)=n，解出(糖果 药片)=$\frac 阅读全文
posted @ 2018-08-13 16:50 小蒟蒻yyb 阅读(296) 评论(4) 推荐(0)
【CF710F】String Set Queries（二进制分组，AC自动机）
摘要： 【CF710F】String Set Queries（二进制分组，AC自动机） 题面 "洛谷" "CF" 翻译： 你有一个字符集合$D$，初始为空， 有三种操作： 往$D$中加入一个串；从$D$中删除一个串；给定一个串$S$，询问$D$中的串在$S$中总共出现了多少次。 题解 询问显然就是将$S$放 阅读全文
posted @ 2018-08-13 16:10 小蒟蒻yyb 阅读(711) 评论(0) 推荐(0)
【BZOJ4140】共点圆加强版（二进制分组）
摘要： 【BZOJ4140】共点圆加强版（二进制分组） 题面 "BZOJ" 题解 我卡精度卡了一天。。。。 之前不强制在线的做法是$CDQ$分治，维护一个凸壳就好了。 现在改成二进制分组，每次重建凸壳就好了。。 cpp include include include include include incl 阅读全文
posted @ 2018-08-13 15:11 小蒟蒻yyb 阅读(386) 评论(0) 推荐(0)
【BZOJ2961】共点圆（CDQ分治）
摘要： 【BZOJ2961】共点圆（CDQ分治） 题面 "BZOJ" 题解 设询问点$(x,y)$，圆心是$(X,Y)$ 那么如果点在园内的话就需要满足 $(X x)^2+(Y y)^2\le X^2+Y^2$ 拆开之后就变成了 $x^2+y^2 2xX\le 2yY$ 除过去就是$ \frac{x}{y} 阅读全文
posted @ 2018-08-13 09:49 小蒟蒻yyb 阅读(469) 评论(0) 推荐(0)
2018年8月12日
【BZOJ2989】数列（二进制分组，主席树）
摘要： 【BZOJ2989】数列（二进制分组，主席树） 题面 "BZOJ" 权限题啊。。。 Description 给定一个长度为n的正整数数列a[i]。 定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x y|+|a[x] a[y]|。 2种操作（k都是正整数）： 1.Mod 阅读全文
posted @ 2018-08-12 22:38 小蒟蒻yyb 阅读(513) 评论(2) 推荐(0)
【BZOJ4543】Hotel加强版（长链剖分）
摘要： 【BZOJ4543】Hotel加强版（长链剖分） 题面 "BZOJ，没有题面" "洛谷，只是普通版本" 题解 原来我们的$O(n^2)$做法是设$f[i][j]$表示以$i$为根的子树中，距离$i$的深度为$j$的点的个数，这样子可以每次在$LCA$处合并答案。 然后长链剖分优化一下，就变成了$O( 阅读全文
posted @ 2018-08-12 21:26 小蒟蒻yyb 阅读(2493) 评论(13) 推荐(1)
【BZOJ2989】数列（CDQ分治，扫描线）
摘要： 【BZOJ2989】数列（CDQ分治） 题面 "BZOJ" 权、。、。、权限题。。 题解 Description 给定一个长度为n的正整数数列a[i]。 定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x y|+|a[x] a[y]|。 2种操作（k都是正整数）： 1. 阅读全文
posted @ 2018-08-12 20:36 小蒟蒻yyb 阅读(471) 评论(0) 推荐(0)
2018年8月10日
【Vijos】lxhgww的奇思妙想（长链剖分）
摘要： 题面 给定一棵树，每次询问一个点的$k$次祖先，强制在线。 "Vijos" 题解 "长链剖分" 。 ~~链接暂时咕咕咕了。~~ 现在可以戳链接看题解了 阅读全文
posted @ 2018-08-10 21:05 小蒟蒻yyb 阅读(1777) 评论(3) 推荐(1)
2018年8月9日
【BZOJ5334】数学计算（线段树）
摘要： 【BZOJ5334】数学计算（线段树） 题面 "BZOJ" "洛谷" 题解 简单的线段树模板题？？？ 咕咕咕。 cpp include include include include include include using namespace std; define ll long long d 阅读全文
posted @ 2018-08-09 21:17 小蒟蒻yyb 阅读(314) 评论(0) 推荐(0)
【BZOJ1048】分割矩阵（记忆化搜索，动态规划）
摘要： 【BZOJ1048】分割矩阵（记忆化搜索，动态规划） 题面 "BZOJ" "洛谷" 题解 一个很简单的$dp$，写成记忆化搜索的形式的挺不错的。 cpp include include include include include include using namespace std; inli 阅读全文
posted @ 2018-08-09 20:28 小蒟蒻yyb 阅读(326) 评论(0) 推荐(0)
【BZOJ1054】移动玩具（搜索）
摘要： 【BZOJ1054】移动玩具（搜索） 题面 "BZOJ" "洛谷" 题解 这种小清新搜索题写出来好舒服啊。 要是原来的我来写代码肯定又臭又长吧。。 cpp include include using namespace std; queue Q; int pw[16],st[13&&!(u&pw[i 阅读全文
posted @ 2018-08-09 19:57 小蒟蒻yyb 阅读(296) 评论(0) 推荐(0)
【BZOJ1072】排列（搜索）
摘要： 【BZOJ1072】排列（搜索） 题面 "BZOJ" "洛谷" 题解 算下复杂度，如果用$next\_permutation$ 那就是$10!\times 10\times 15$，复杂度不太对 那好办啊，把$next\_permutation$改成搜索不就完了。。 cpp include incl 阅读全文
posted @ 2018-08-09 19:44 小蒟蒻yyb 阅读(223) 评论(0) 推荐(0)
【BZOJ1041】圆上的整点（数论）
摘要： 【BZOJ1041】圆上的整点（数论） 题面 "BZOJ" "洛谷" 题解 好神仙的题目啊。 "安利一个视频，大概是第$7$到$19$分钟的样子" 因为要质因数分解，所以复习了一下$Pollard\_rho$ cpp include include include include include i 阅读全文
posted @ 2018-08-09 19:33 小蒟蒻yyb 阅读(734) 评论(0) 推荐(0)
【BZOJ1034】泡泡堂（贪心）
摘要： 【BZOJ1034】泡泡堂（贪心） 题面 "BZOJ" "洛谷" 题解 很基础的贪心，然而我竟然没写对。。。身败名裂。 大概就是类似田忌赛马。 先拿看当前最大值是否能否解决对面最大值，否则检查能否用最小值来兑掉。 差不多类似把，有点点区别。 cpp include include include i 阅读全文
posted @ 2018-08-09 17:20 小蒟蒻yyb 阅读(209) 评论(0) 推荐(0)
2018年8月8日
【BZOJ1011】遥远的行星（？？？）
摘要： 题面 "BZOJ" "洛谷" 题解 大概就是分个块，然后每块取平均数算贡献啥的。 BZOJ上过不去？？？ cpp include include using namespace std; define MAX 100100 int n,sqr,blk[MAX]; double a,A,m[MAX], 阅读全文
posted @ 2018-08-08 20:35 小蒟蒻yyb 阅读(203) 评论(0) 推荐(0)
【BZOJ1046】上升序列（动态规划，贪心）
摘要： 【BZOJ1046】上升序列（动态规划，贪心） 题面 "BZOJ" "洛谷" 题解 我一开始看错题了，一度以为是字典序最小的序列。 最后发现它要求的字典序是位置的字典序最小。 那就很好办了。 设$f[i]$表示以$i$开头的$LIS$长度，用$BIT$转移。 然后每次询问暴力贪心即可。 阅读全文
posted @ 2018-08-08 19:46 小蒟蒻yyb 阅读(224) 评论(1) 推荐(0)
【BZOJ1052】覆盖问题（贪心）
摘要： 【BZOJ1052】覆盖问题（贪心） 题面 "BZOJ" "洛谷" 题解 这题好神仙啊。 很明显可以看出来要二分一个边长。 那么如何$check$呢？ 我们把所有点用一个最小矩形覆盖， 那么必定每个边界上都至少存在一个点， 但是我们有$4$个边界，但是只有$3$个矩形， 意味着至少有一个矩形卡住了两 阅读全文
posted @ 2018-08-08 17:22 小蒟蒻yyb 阅读(269) 评论(1) 推荐(0)
【BZOJ3293】分金币（贪心）
摘要： 【BZOJ3293】分金币（贪心） 题面 "BZOJ" "洛谷" 题解 和上一题一样啊。 cpp include include include using namespace std; define ll long long define MAX 100010 inline int read() 阅读全文
posted @ 2018-08-08 16:48 小蒟蒻yyb 阅读(202) 评论(0) 推荐(0)
【BZOJ1045】糖果传递（贪心）
摘要： 【BZOJ1045】糖果传递（贪心） 题面 "BZOJ" "洛谷" 题解 秉承者娱乐精神，我们必须写一个费用流，并且相信信仰跑不过去。 于是写了一个$zkw$费用流如下：（您可以无视此份代码） cpp include include include include include include i 阅读全文
posted @ 2018-08-08 16:36 小蒟蒻yyb 阅读(341) 评论(2) 推荐(0)
上一页 1 ··· 20 21 22 23 24 25 26 27 28 ··· 52 下一页