摘要：
【BZOJ2109/2535】【NOI2010】航空管制（贪心） 题面 "BZOJ2109" "BZOJ2535" 题解 很好玩的一道题目 先看第一问，显然是要找一个合法的拓扑排序的序列。 直接拓扑排序，把队列变成堆？发现这样子不能保证满足时间的限制。 因为这样子有后效性，你永远不知道把这个点给选走 阅读全文
posted @ 2018-06-16 20:04
小蒟蒻yyb
阅读(226)
评论(0)
推荐(0)
摘要：
【BZOJ1565】【NOI2009】植物大战僵尸（网络流） 题面 "BZOJ" "洛谷" 题解 做了这么多神仙题，终于有一道能够凭借自己智商能够想出来的题目了。。。。 好感动。 这就是一个比较裸的最小割模型。 先考虑能够得到所有的正贡献，只需要减去所需的最小代价就可以了。 考虑两个点保护与被保护的 阅读全文
posted @ 2018-06-15 22:33
小蒟蒻yyb
阅读(287)
评论(0)
推荐(0)
摘要：
【Luogu1912】【NOI2009】诗人小G（动态规划） 题面 "洛谷" 题解 原来$NOI$这么多神仙题。。。 考虑一个极其明显的$dp$ 设$f[i]$表示前$i$个句子产生的最小代价 转移也很显然，就懒得写了。 仔细思考一下，转移具有单调性。 但是我们用单调队列似乎无法直接维护。 继续思考 阅读全文
posted @ 2018-06-15 21:31
小蒟蒻yyb
阅读(495)
评论(2)
推荐(0)
摘要：
【BZOJ1562】【NOI2009】变换序列 题面 "BZOJ" "洛谷" 这题面写的是真的丑，还是先手动翻译成人话。 让你构造一个$0..N 1$的排列$T$ 使得$Dis(i,T_i)$为给定的值，如果有多个满足条件则输出字典序最小的那个。 其中，$Dis(x,y)=min(|x y|,N | 阅读全文
posted @ 2018-06-15 19:10
小蒟蒻yyb
阅读(278)
评论(0)
推荐(0)
摘要：
【BZOJ1566】【NOI2009】管道取珠（动态规划） 题面 "BZOJ" 题解 蛤？只有两档部分分。一脸不爽.jpg 第一档？爆搜，这么显然，爆搜+状压最后统计一下就好了 阅读全文
posted @ 2018-06-15 16:52
小蒟蒻yyb
阅读(350)
评论(5)
推荐(0)
摘要：
【BZOJ1065】【NOI2008】奥运物流（动态规划） 题面 "BZOJ" "洛谷" 题解 先不考虑环的情况，于是变成了一棵树。 这样子我们答案的贡献是$\sum_{i=1}^nC_i\times k^{dep[i]}$ 其中$dep$是点的深度 考虑环的影响，显然是$R(1)$的贡献沿着环反复 阅读全文
posted @ 2018-06-15 15:35
小蒟蒻yyb
阅读(314)
评论(0)
推荐(0)
摘要：
题面 "LOJ" 题解 "戳这里" cpp include include include include include include using namespace std; define ll long long define MAX 222222 define MOD 1000000007 阅读全文
posted @ 2018-06-14 21:46
小蒟蒻yyb
阅读(4176)
评论(8)
推荐(0)
摘要：
min_25筛 用来干啥？ 考虑一个积性函数$F(x)$，用来快速计算前缀和$$\sum_{i=1}^nF(i)$$ 当然，这个积性函数要满足$F(x),x\in Prime$可以用多项式表示 同时，$F(x^k),x\in Prime$要能够快速计算答案 需要预处理的东西 先不考虑求前缀和的问题， 阅读全文
posted @ 2018-06-14 21:44
小蒟蒻yyb
阅读(16047)
评论(10)
推荐(11)
摘要：
【洛谷5月月赛】玩游戏（NTT，生成函数） 题面 "Luogu" 题解 看一下要求的是什么东西 $(a_x+b_y)^i$的期望。期望显然是所有答案和的平均数。 所以求出所有的答案就在乘一个逆元就好了。 现在考虑怎么算上面那个东西。 对于单个的计算，我们可以用二项式定理直接展开 得到 $$\begi 阅读全文
posted @ 2018-06-13 07:54
小蒟蒻yyb
阅读(712)
评论(0)
推荐(0)
摘要：
【BZOJ1063】【NOI2008】道路设计（动态规划） 题面 "BZOJ" 题解 发现每个点最多只能被修一次等价于每个点最多只能和两条铁路相邻 考虑一个$dp$ 设$f[i][0/1/2]$表示以$i$为根，当前点与他的儿子已经有$0/1/2$条铁路相邻的方案数 转移也很简单，考虑每个儿子，枚举 阅读全文
posted @ 2018-06-08 15:31
小蒟蒻yyb
阅读(275)
评论(0)
推荐(0)
摘要：
【BZOJ1494】【NOI2007】生成树计数（动态规划，矩阵快速幂） 题面 Description 最近，小栋在无向连通图的生成树个数计算方面有了惊人的进展，他发现： ·n个结点的环的生成树个数为n。 ·n个结点的完全图的生成树个数为n^(n 2)。这两个发现让小栋欣喜若狂，由此更加坚定了他继续 阅读全文
posted @ 2018-06-08 11:17
小蒟蒻yyb
阅读(531)
评论(0)
推荐(1)
摘要：
【Aizu2292】Common Palindromes（回文树） 题面 "Vjudge" ~~神TMD日语~~ 翻译： 给定两个字符串$S,T$，询问$(i,j,k,l)$这样的四元组个数 满足$S[i,j],T[k,l]$都是回文串并且$S[i,j]=T[k,l]$ 题解 自己$yy$一下就会做 阅读全文
posted @ 2018-06-07 20:38
小蒟蒻yyb
阅读(429)
评论(0)
推荐(0)
摘要：
【LOJ6436】【PKUSC2018】神仙的游戏（NTT） 题面 "LOJ" 题解 看到$zsy$从$PKUSC$回来就秒掉了这种神仙题 吓得我也赶快看了看$PKUSC$都有些什么神仙题 然后就找到了这样一道神仙题 考虑一个奇怪的暴力： 我们只需要对于$0/1$进行匹配 如果出现了$0/1$匹配的 阅读全文
posted @ 2018-06-07 17:28
小蒟蒻yyb
阅读(634)
评论(0)
推荐(0)
摘要：
【BZOJ3672】【NOI2014】购票（线段树，斜率优化，动态规划） 题解 首先考虑$dp$的方程，设$f[i]$表示$i$的最优值 很明显的转移$f[i]=min(f[j]+(dep[i] dep[j])·p[i])+q[i]$ 其中满足$dep[i] dep[j]\le L[i]$ 然后就可 阅读全文
posted @ 2018-06-07 14:25
小蒟蒻yyb
阅读(353)
评论(0)
推荐(2)
摘要：
【CF600E】Lomsat gelral（dsu on tree） 题面 "洛谷" CF题面自己去找找吧。 题解 $dsu\ on\ tree$板子题 其实就是做子树询问的一个较快的方法。 对于子树的询问，我们不难想到子树就是$dfs$序上的连续一段， 可以把树转化成序列再用莫队来解。 其实可以对 阅读全文
posted @ 2018-06-06 21:49
小蒟蒻yyb
阅读(479)
评论(0)
推荐(0)
摘要：
THUSC2018滚粗记 前言 大家好，我是$yyb$，我的博客里又多了一篇滚粗记， 我记得我原来在某篇滚粗记中曾经写过 $yyb$还会写很多很多次滚粗记才会有一篇不是滚粗记的东西。 看起来这一天要等到高二了。 总的来说，$THUSC$真是。。菜爆了。 明明会写的却写不出，明明可以得的分却没有交。 阅读全文
posted @ 2018-06-06 21:36
小蒟蒻yyb
阅读(1555)
评论(7)
推荐(1)
摘要：
【CF700E】Cool Slogans（后缀自动机） 题面 "洛谷" "CodeForces" 题解 构建后缀自动机，求出后缀树 现在有个比较明显的$dp$ 设$f[i]$表示从上而下到达当前点能够满足条件的最优值 只需要检查父亲节点是否在当前串中出现过两次就行了 这个判断用$endpos$来判断 阅读全文
posted @ 2018-05-31 16:38
小蒟蒻yyb
阅读(1380)
评论(0)
推荐(0)
摘要：
【BZOJ5319】军训列队（主席树） 题面 "BZOJ" "洛谷" 题解 一眼题既视感。。。 首先很明显，每次询问的结果显然是做一次离散。 然后直接上主席树就好了。。。 查询答案的方式也很简单 考虑一下那个绝对值是个什么东西 如果所有的点都在目标区间以左 则直接区间和去算一下。 如果所有的点都在目 阅读全文
posted @ 2018-05-30 22:33
小蒟蒻yyb
阅读(339)
评论(0)
推荐(0)
摘要：
【BZOJ2306】幸福路径（动态规划，倍增） 题面 "BZOJ" 题解 不要求确切的值，只需要逼近 显然可以通过移动$\infty$步来达到逼近的效果 考虑每次的一步怎么移动 设$f[i][j]$表示走$i$步到了$j$能够得到的最大权值 $f[i][v]=max(f[i 1][u])+W[v] 阅读全文
posted @ 2018-05-30 22:03
小蒟蒻yyb
阅读(338)
评论(0)
推荐(0)
摘要：
【BZOJ4754】独特的树叶（哈希） 题面 "BZOJ" 给定一个$n$个节点的树A和一个$n+1$个节点的树$B$ 求$B$的一个编号最小的节点，使得删去这个节点后$A,B$同构 题解 树哈希 一个奇怪的姿势 总而言之，就是把树的各种信息乱七八糟的拼在一起强行哈希一下 真搞不懂这种丧病的东西为什 阅读全文
posted @ 2018-05-30 20:16
小蒟蒻yyb
阅读(367)
评论(0)
推荐(0)
摘要：
【CF809E】Surprise me!（动态规划，虚树，莫比乌斯反演） 题面 "洛谷" "CodeForces" 翻译： 给定一棵$n$个节点的树，每个点有一个权值$a[i]$，保证$a[i]$是一个$1..n$的排列。 求$$\frac{1}{n(n 1)}\sum_{i=1}^n\sum_{j 阅读全文
posted @ 2018-05-29 22:06
小蒟蒻yyb
阅读(707)
评论(2)
推荐(2)
摘要：
【BZOJ1941】Hide and Seek（KD Tree） 题面 "BZOJ" "洛谷" 题解 $KD Tree$对于每个点搜一下最近点和最远点就好了 cpp include include include include include include include include inc 阅读全文
posted @ 2018-05-29 19:13
小蒟蒻yyb
阅读(386)
评论(0)
推荐(0)
摘要：
【BZOJ5329】【SDOI2018】战略游戏（圆方树，虚树） 题面 "BZOJ" "洛谷" Description 省选临近，放飞自我的小Q无心刷题，于是怂恿小C和他一起颓废，玩起了一款战略游戏。 这款战略游戏的地图由n个城市以及m条连接这些城市的双向道路构成，并且从任意一个城市出发总能沿着道路 阅读全文
posted @ 2018-05-29 08:10
小蒟蒻yyb
阅读(272)
评论(0)
推荐(0)
摘要：
【CF613D】Kingdom and its Cities（虚树，动态规划） 题面 "洛谷" "CF" 翻译洛谷上有啦 题解 每次构建虚树，首先特判无解，也就是关键点中存在父子关系。 考虑$dp$，设$f[i]$表示解决$i$子树以内的最小点数 再用一个数组$g[i]$表示$i$的子树中还未阻断的 阅读全文
posted @ 2018-05-28 21:56
小蒟蒻yyb
阅读(558)
评论(1)
推荐(1)
摘要：
【CodeChef】Palindromeness（回文树） 题面 "Vjudge" "CodeChef" "中文版题面" 题解 构建回文树，现在的问题就是要求出当前回文串节点的长度的一半的那个回文串所代表的节点 定义$half$表示长度最长并且长度小于等于当前节点长度一半的回文串所代表的节点 $ha 阅读全文
posted @ 2018-05-28 20:46
小蒟蒻yyb
阅读(547)
评论(0)
推荐(0)
浙公网安备 33010602011771号