摘要：
【TopCoder10697】RabbitNumbering 题面 "Vjudge" 给定$n$个数，每个数的范围是$[1,ai]$，求所有数都不同的方案数。 题解 把这个直接当做一个套路来用 对于$a_i$排序，那么无论前面的选什么，因为它能够选择的最大值都小于当前数的限制， 所以必定对于当前数产 阅读全文
posted @ 2018-07-29 16:29
小蒟蒻yyb
阅读(363)
评论(0)
推荐(0)
摘要：
【BZOJ4311】向量（线段树分治，斜率优化） 题面 "BZOJ" 题解 先考虑对于给定的向量集，如何求解和当前向量的最大内积。 设当前向量$(x,y)$，有两个不同的向量$(u1,v1),(u2,v2)$，并且$u1 u2$ 假设第一个向量的结果优于第二个。 $xu1+yv1 xu2+yv2$ 阅读全文
posted @ 2018-07-28 22:11
小蒟蒻yyb
阅读(575)
评论(0)
推荐(0)
摘要：
【BZOJ4184】shallot（线段树分治，线性基） 题面 权限题啊。。。。。好烦。。 Description 小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。 每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且 让小葱从自己手 阅读全文
posted @ 2018-07-28 19:41
小蒟蒻yyb
阅读(642)
评论(1)
推荐(0)
摘要：
【BZOJ4137】火星商店问题（线段树分治，可持久化Trie） 题面 "洛谷" BZOJ权限题 题解 显然可以树套树，外层线段树，内层可持久化Trie来做。 所以我们需要更加优美的做法。——线段树分治。 什么叫做线段树分治呢？ 我们发现每次询问都是区间的形式，看到区间我们就可以想到线段数。 我们接 阅读全文
posted @ 2018-07-27 22:14
小蒟蒻yyb
阅读(1147)
评论(3)
推荐(3)
摘要：
【BZOJ3712】Fiolki（并查集重构树） 题面 "BZOJ" 题解 很神仙的题目。 我们发现所有的合并关系构成了一棵树。 那么两种不同的东西如果产生反应，一定在两个联通块恰好联通的时候反应。 那么，我们按照并查集的合并顺序，类似于克鲁斯卡尔重构树的方法构建一个并查集重构树， 发现所有的反应恰 阅读全文
posted @ 2018-07-25 22:09
小蒟蒻yyb
阅读(496)
评论(0)
推荐(0)
摘要：
【BZOJ2151】种树（贪心） 题面 "BZOJ" 题解 如果没有相邻不能选的限制，那么这就是一道傻逼题。 只需要用一个堆维护一下就好了。 现在加上了相邻点的限制，那么我们就对于当前位置加入一个撤销操作。 怎么撤销呢？ 如果我们选择了一个点，那么我们就把他前后两个位置删去， 然后将当前点合并为$a 阅读全文
posted @ 2018-07-25 19:47
小蒟蒻yyb
阅读(808)
评论(1)
推荐(0)
摘要：
【NOI2018】屠龙勇士（数论，exgcd） 题面 "洛谷" 题解 考场上半个小时就会做了，一个小时就写完了。。 然后发现没过样例，结果大力调发现中间值爆$longlong$了，然后就没管了。。 然后又没切掉。。。~~我是真的傻逼。。。~~ 首先每次选择的刀一定，直接一个$multiset$就算出 阅读全文
posted @ 2018-07-22 22:11
小蒟蒻yyb
阅读(707)
评论(2)
推荐(0)
摘要：
【NOI2018】归程（克鲁斯卡尔重构树） 题面 "洛谷" 题解 我在现场竟然没有把这道傻逼题给切掉，身败名裂。 ~~因为这题就是克鲁斯卡尔重构树的模板题啊~~ 我就直接简单的说一下把 首先发现答案就是在只经过海拔大于$p$的边的情况下，所有点到$1$号点中最短路最小的那个点。所以预处理最短路径，构 阅读全文
posted @ 2018-07-22 21:34
小蒟蒻yyb
阅读(516)
评论(0)
推荐(0)
摘要：
【BZOJ4596】黑暗前的幻想乡（矩阵树定理，容斥） 题面 "BZOJ" 有$n$个点，要求连出一棵生成树， 指定了一些边可以染成某种颜色，一共$n 1$种颜色， 求所有颜色都出现过的生成树方案数。 题解 一脸的容斥啊。 先矩阵树定理暴力算出所有符合条件的生成树，然后减去$n 2$中颜色的方案数， 阅读全文
posted @ 2018-07-16 10:52
小蒟蒻yyb
阅读(324)
评论(0)
推荐(0)
摘要：
【BZOJ1951】古代猪文（CRT，卢卡斯定理） 题面 "BZOJ" "洛谷" 题解 要求什么很显然吧。。。 $$Ans=G^{\sum_{k|N}{C_N^k}}$$ 给定的模数是一个质数，要求解的东西相当于是上面那坨东西的结果对于$\varphi$的取值。 但是$\varphi$不是质数，不好 阅读全文
posted @ 2018-07-16 10:14
小蒟蒻yyb
阅读(407)
评论(0)
推荐(0)
摘要：
【BZOJ3162】独钓寒江雪（树哈希，动态规划） 题面 "BZOJ" 题解 忽然翻到这道题目，突然发现就是前几天一道考试题目。。。 题解： 树哈希，既然只考虑这一棵树，那么，如果两个点为根是同构的， 他们的重心相同，所以直接找出树的重心，以重心为根进行转移 提前预处理每一棵子树的哈希值，因为相同的 阅读全文
posted @ 2018-07-16 09:35
小蒟蒻yyb
阅读(421)
评论(0)
推荐(0)
摘要：
【POJ2891】Strange Way to Express Integers（拓展CRT） 题面 "Vjudge" 板子题。 题解 拓展$CRT$模板题。 cpp include include using namespace std; define ll long long define MA 阅读全文
posted @ 2018-07-16 09:18
小蒟蒻yyb
阅读(279)
评论(0)
推荐(0)
摘要：
【Luogu3676】小清新数据结构题（动态点分治） 题面 "洛谷" 题解 先扯远点，这题我第一次看的时候觉得是一个树链剖分+线段树维护。 做法大概是这样： 我们先以任意一个点为根，把当前点看成是一棵有根树。比方说以$1$为根。 那么，在询问以$p$为根的时候的答案，我们看看哪些子树发生了变化。 发 阅读全文
posted @ 2018-07-16 09:16
小蒟蒻yyb
阅读(416)
评论(0)
推荐(0)
摘要：
[复习]动态点分治 点分治，动态点分治，等等等各种分治。 因为我的智商经常欠费，导致我对于分治这个方面一窍不通。 但是动态点分治这个东西我又不是没有学过，只是过了这么久我什么都不会了。 所以还是重新理解一下吧。。。 首先，动态点分治需要构建出点分树，这个很好处理。 找重心是$O(n)$，每次重心分出 阅读全文
posted @ 2018-07-16 09:15
小蒟蒻yyb
阅读(537)
评论(0)
推荐(0)
摘要：
中国剩余定理 CRT 正常版本CRT 要解的是一个很容易的东西 $$ \begin{aligned} x\equiv a_1(mod\ m_1)\\ x\equiv a_2(mod\ m_2)\\ ...\\ x\equiv a_n(mod\ m_n) \end{aligned} $$ 保证$m_1 阅读全文
posted @ 2018-07-16 08:54
小蒟蒻yyb
阅读(1390)
评论(4)
推荐(0)
摘要：
NOI2018游记 注：本文底下一切没有意义的评论都将被删除。 尽管yyb也写了很多和NOI无关的话 Day 1 $\qquad$今天是$2018$年$7$月$15$日，明天就是$NOI2018$的报道日了。从$THUSC$考完之后到现在，不知不觉已经过去了一个半月。说真的，这段时间我对于$NOI$ 阅读全文
posted @ 2018-07-15 09:54
小蒟蒻yyb
阅读(6802)
评论(16)
推荐(7)
摘要：
题面 "BZOJ" 题解 动态点分治什么的完全不记得了。这回重新写一写。 首先我们把点分树给建出来。 操作只有两种，修改和询问距离某个点的距离不超过$k$的点的和。 两点之间的距离可以树链剖分之类的算，这里不再重复。 考虑如何计算答案。 对于每个点，把对于它的点分树上所有祖先的贡献给加好。 因为要方 阅读全文
posted @ 2018-07-14 14:47
小蒟蒻yyb
阅读(1259)
评论(0)
推荐(1)
摘要：
【BZOJ1226】学校食堂（动态规划，状态压缩） 题面 "BZOJ" "洛谷" 题解 发现$b$很小，意味着当前这个人最坏情况下也只有后面的一小部分人在他前面拿到饭。 所以整个结果的大致顺序是不会变化的。 对于一个人，他要占用的时间之和前面那个拿饭的人有关。 而他前面那个拿饭的人在队列中只有两种情 阅读全文
posted @ 2018-07-14 11:07
小蒟蒻yyb
阅读(428)
评论(0)
推荐(1)
摘要：
【BZOJ2216】Lightning Conductor（动态规划） 题面 "BZOJ，然而是权限题" "洛谷" 题解 $\sqrt {|i j|}$似乎没什么意义，只需要从前往后做一次再从后往前做一次就好了。 只考虑从前往后，把给定的式子移项，可以得到 $p\ge a[j] a[i]+\sqrt 阅读全文
posted @ 2018-07-14 09:19
小蒟蒻yyb
阅读(262)
评论(0)
推荐(0)
摘要：
【BZOJ4709】柠檬（动态规划，单调栈） 题面 "BZOJ" 题解 从左取和从右取没有区别，本质上就是要分段。 设$f[i]$表示前$i$个位置的最大值。 那么相当于我们枚举一个前面的位置$j$，然后找到这一段中最大的$s_0t^2$ 但是这样子很不优秀。 我们贪心的思考一下，既然这一段最后加起 阅读全文
posted @ 2018-07-13 20:38
小蒟蒻yyb
阅读(486)
评论(0)
推荐(0)
摘要：
【BZOJ3203】保护出题人（动态规划，斜率优化） 题面 "BZOJ" "洛谷" 题解 在最优情况下，肯定是存在某只僵尸在到达重点的那一瞬间将其打死 我们现在知道了每只僵尸到达终点的时间，因为僵尸要依次打死。 所以我们假设血量的前缀和是$s_i$ 那么我么必须在它到达的时间$t_i$之前打出总共不 阅读全文
posted @ 2018-07-13 19:32
小蒟蒻yyb
阅读(364)
评论(0)
推荐(0)
摘要：
【BZOJ3437】小P的牧场（动态规划，斜率优化） 题面 "BZOJ" 题解 考虑暴力$dp$，设$f[i]$表示强制在$i$处建立控制站的并控制$[1..i]$的最小代价。 很显然，枚举上一个控制站的位置$j$ $f[i]=min(f[j]+Calc(i,j)+a[i])$，其中$Calc(i, 阅读全文
posted @ 2018-07-13 16:00
小蒟蒻yyb
阅读(305)
评论(0)
推荐(0)
摘要：
【BZOJ3156】防御准备（动态规划，斜率优化） 题面 "BZOJ" 题解 从右往左好烦啊，直接$reverse$一下再看题。 设$f[i]$表示第$i$个位置强制建立检查站时，前面都满足条件的最小代价 $f[i]=min(f[j]+sum[i j 1])+A[i]$ 即枚举上一个检查站建立的位置 阅读全文
posted @ 2018-07-13 15:03
小蒟蒻yyb
阅读(293)
评论(0)
推荐(0)
浙公网安备 33010602011771号