摘要：
CF922 CodeForces Round 461(Div.2) 这场比赛很晚呀 果断滚去睡了 现在来做一下 A "CF922 A" 翻译： 一开始有一个初始版本的玩具 每次有两种操作： 放一个初始版本进去，额外得到一个初始版本和一个复制版本 放一个复制版本进去，额外得到两个复制版本 一开始有$1 阅读全文
posted @ 2018-02-08 20:25
小蒟蒻yyb
阅读(800)
评论(0)
推荐(0)
摘要：
【BZOJ2442】修建草坪（动态规划，单调队列） 题面 "权限题。。洛谷" 题解 设$f[i]$表示前$i$个里面选出来的最大值 转移应该比较显然 枚举一个断点的位置，转移一下就好 $f[i]=max(f[j 1]+s[j] s[i])$ 所以可以单调队列优化一下 (不优化用各种玄学可以拿90分。 阅读全文
posted @ 2018-02-07 21:37
小蒟蒻yyb
阅读(299)
评论(0)
推荐(0)
摘要：
【BZOJ1415】【NOI2005】聪聪和可可（动态规划，数学期望） 题面 "BZOJ" 题解 先预处理出当可可在某个点，聪聪在某个点时 聪聪会往哪里走 然后记忆化搜索一下就好了 cpp include include include include include include include 阅读全文
posted @ 2018-02-07 19:25
小蒟蒻yyb
阅读(225)
评论(1)
推荐(0)
摘要：
【Luogu1291】百事世界杯之旅（动态规划，数学期望） 题面 "洛谷" 题解 设$f[i]$表示已经集齐了$i$个名字的期望 现在有两种方法： 先说我自己的： $$f[i]=f[i 1]+1+(1 p)(1 p^1+2 p^2+....)$$ 其中$p=\frac{i 1}{n}$ 为什么，很简 阅读全文
posted @ 2018-02-07 16:47
小蒟蒻yyb
阅读(203)
评论(0)
推荐(0)
摘要：
【BZOJ1855】股票交易（动态规划，单调队列） 题面 "BZOJ" 题解 很显然，状态之和天数以及当天剩余的股票数有关 设$f[i][j]$表示第$i$天进行了交易，剩余股票数为$j$的最大获利 每次枚举可以转移过来的天数以及股票数 再枚举买入或者卖出的数量， 时间复杂度$O(T^2Mp^2)$ 阅读全文
posted @ 2018-02-07 15:43
小蒟蒻yyb
阅读(289)
评论(0)
推荐(0)
摘要：
【Uoj34】多项式乘法（NTT，FFT） 题面 "uoj" 题解 首先多项式乘法用$FFT$是一个很久很久以前就写过的东西 直接贴一下代码吧。。 cpp include include include include include include include include include 阅读全文
posted @ 2018-02-07 14:15
小蒟蒻yyb
阅读(515)
评论(2)
推荐(0)
摘要：
【BZOJ3992】序列统计（动态规划，NTT） 题面 "BZOJ" 题解 最裸的暴力 设$f[i][j]$表示前$i$个数，积在膜意义下是$j$的方案数 转移的话，每次枚举一个数，直接丢进去就好 复杂度$O(nm|S|)$，10pts 现在就是最大的问题了 $n$已经优化到了$logn$ 转移现在 阅读全文
posted @ 2018-02-07 11:58
小蒟蒻yyb
阅读(592)
评论(1)
推荐(3)
摘要：
【BZOJ4009】接水果（整体二分，扫描线） 题面 "为什么这都是权限题？？？，洛谷真良心" 题解 看到这道题，感觉就是主席树/整体二分之类的东西 （因为要求第$k$大） 但是，读完题目之后，我们发现路径之间的包含关系很不好搞 那么，我们来画画图 这是第一种情况，$lca$不是$u,v$ $u,v 阅读全文
posted @ 2018-02-07 09:39
小蒟蒻yyb
阅读(413)
评论(0)
推荐(0)
摘要：
【POJ1151】Atlantis（线段树，扫描线） 题面 "Vjudge" 题解 学一学扫描线 其实很简单啦 这道题目要求的就是若干矩形的面积和 把扫描线平行于某个轴扫过去（我选的平行$y$轴扫） 这样只需要求出每次和$x$轴覆盖的长度 就可以两两相乘，求出面积 最后累计和就行啦 cpp incl 阅读全文
posted @ 2018-02-06 22:12
小蒟蒻yyb
阅读(421)
评论(1)
推荐(0)
摘要：
【BZOJ2428】均分数据（模拟退火） 题面 "BZOJ" 题解 先说说黄学长的做法： 当温度比较高的时候，贪心 每次随机一个数，把他放进当前和最少的那一组里面 温度足够低的时候就完全随机然后转移 这样子写貌似会挂？？？ （我只有70分。。，洛谷测的） 然后看到了$ZSY$巨神的做法 （太强啦，实 阅读全文
posted @ 2018-02-06 17:00
小蒟蒻yyb
阅读(452)
评论(2)
推荐(1)
摘要：
【UOJ207】共价大爷游长沙（Link Cut Tree，随机化） 题面 "UOJ" 题解 这题太神了 $\%\%\%myy$ 看到动态的维护边很容易的想到了$LCT$ 然后能否堵住一条路 我们也不难想到，以这条路的一个端点为根的子数 是否恰好包含了集合中所有点对的中的恰好一个点 但是怎么算恰好包 阅读全文
posted @ 2018-02-06 12:49
小蒟蒻yyb
阅读(311)
评论(0)
推荐(1)
摘要：
【BZOJ4872】分手是祝愿（动态规划，数学期望） 题面 "BZOJ" 题解 对于一个状态，如何求解当前的最短步数？ 从大到小枚举，每次把最大的没有关掉的灯关掉 暴力枚举因数关就好 假设我们知道了当前至少要关$tot$次 如果一个灯被动两次以上是没有任何意义的 所以，相当于，要动的灯只有$tot$ 阅读全文
posted @ 2018-02-05 22:31
小蒟蒻yyb
阅读(276)
评论(5)
推荐(0)
摘要：
【BZOJ4237】稻草人（CDQ分治，单调栈） 题面 "BZOJ" 题解 $CDQ$分治好题呀 假设固定一个左下角的点 那么，我们可以找到的右下角长什么样子？？？ 发现什么？ 在右侧是一个单调递减的东西 那么，对于每一个已经固定好的左下角 我们可以通过单调栈来维护答案 既然只有左下角对右上角会产生 阅读全文
posted @ 2018-02-05 19:31
小蒟蒻yyb
阅读(416)
评论(0)
推荐(0)
摘要：
【BZOJ1146】网络管理（整体二分） 题面 "良心洛谷，有BZOJ权限题" 题解 要看树套树的 "戳这里" 毕竟是：智商不够数据结构来补 所以， 我们来当一回智商够的选手 ~~听说主席树的题目大部分都可以整体二分~~ 这题丢进去整体二分就行了 只需要查询树上贡献的前缀和 但是，对于这种带修改的 阅读全文
posted @ 2018-02-05 14:40
小蒟蒻yyb
阅读(310)
评论(2)
推荐(0)
摘要：
【BZOJ1146】网络管理（主席树，树状数组） 题面 "BZOJ权限题，洛谷题面" 题解 树上带修改主席树 貌似和$Count\ On\ A\ Tree$那题很相似呀 只需要套上一个树状数组来维护修改好就好了 但是记住是用$dfs$来记录主席树的标号 一定不要搞错了 每一次修改只会影响他子数的值 阅读全文
posted @ 2018-02-05 09:08
小蒟蒻yyb
阅读(523)
评论(0)
推荐(0)
摘要：
【BZOJ3110】K大数查询（整体二分） 题面 "BZOJ" 题解 看了很久整体二分 一直不知道哪里写错了 。。。 又把树状数组当成线段树区间加法来用了。。 整体二分还是要想清楚在干什么： 我们考虑第$K$大是什么 就是还有$K 1$个比他小 这样子就可以考虑二分之后如何$check$ 当前二分出 阅读全文
posted @ 2018-02-04 22:11
小蒟蒻yyb
阅读(482)
评论(1)
推荐(0)
摘要：
题面 题目详见 "CodeForces" 先大概的写个翻译。。。 A 有一个长度为$n$的花园 有$K$个水龙头， 假设水龙头的位置在$x$ $1s$后$x$会被灌溉 $2s$后$[x 1,x+1]$会被灌溉 $js$后$[x j+1,x+j 1]$会被灌溉 问这个花园在什么时候会被灌溉完 B 阅读 阅读全文
posted @ 2018-02-03 17:21
小蒟蒻yyb
阅读(341)
评论(2)
推荐(0)
摘要：
【Luogu1337】平衡点（模拟退火） 题面 "洛谷" 题解 和BZOJ3680吊打XXX是一样的。。 但是数据很强呀。。 疯狂调参 各种WA。。。 很无奈呀。。。。 cpp include include include include include include include inclu 阅读全文
posted @ 2018-02-03 11:08
小蒟蒻yyb
阅读(395)
评论(0)
推荐(0)
摘要：
【BZOJ3680】吊打XXX（模拟退火） 题面 "BZOJ" 题解 模拟退火。。。 就是模拟退火 然后这题有毒 各种调参数之后终于$AC$了。。 这种题就是玄学呀。。。 温度要调大 最后跑完还要向四周多$rand$几次 保证能够找到最优解。。。 cpp include include includ 阅读全文
posted @ 2018-02-03 11:06
小蒟蒻yyb
阅读(460)
评论(0)
推荐(0)
摘要：
【BZOJ2527】MET Meteors（整体二分） 题面 "BZOJ权限题，良心洛谷链接" 题解 其实我也不会做 看了zsy博客才会做。。。 这题如果直接爆算做显然行不通 如果只有单次询问，我们就可以二分答案 但是询问太多。。 不会二分。。 怎么办？ 我们来想想瓶颈在哪里 如果每次都进行一次单次 阅读全文
posted @ 2018-02-02 20:34
小蒟蒻yyb
阅读(328)
评论(0)
推荐(0)
摘要：
【BZOJ1996】合唱队（动态规划） 题面 "BZOJ" 题解 很容易的一道题 因为每个人不是放在了左边就是放在了右边 所以每次放好的人必定是原序列的一个子串 所以，很容易想到区间$dp$ 设$f[i][j]$表示已经放好了第$i$个人到第$j$个人的方案数 因为不知道这个人的前面是当前序列的左端 阅读全文
posted @ 2018-02-02 16:40
小蒟蒻yyb
阅读(265)
评论(0)
推荐(0)
摘要：
【BZOJ2337】Xor和路径（高斯消元） 题面 "BZOJ" 题解 我应该多学点套路： 对于xor之类的位运算，要想到每一位拆开算贡献 所以，对于每一位拆开来看 好了，既然是按位来算 我们就只需要计算从$1$号点开始 到$n$的路径中，路径的异或和为$1$的概率 显然没法算 还是一样的 考虑高斯 阅读全文
posted @ 2018-02-02 16:20
小蒟蒻yyb
阅读(318)
评论(0)
推荐(0)
摘要：
【BZOJ3143】游走（高斯消元，数学期望） 题面 "BZOJ" 题解 首先，概率不会直接算。。。 所以来一个逼近法算概率 这样就可以求出每一条边的概率 随着走的步数的增多，答案越接近 （我卡到$5000$步可以拿$50$分） 这样子算出来会有精度问题 所以就挂了 现在考虑怎么算这个概率 显然不能 阅读全文
posted @ 2018-02-02 14:54
小蒟蒻yyb
阅读(339)
评论(1)
推荐(0)
摘要：
THUWC2018滚粗记 前言 又是一篇滚粗记， 不过可能还要写过很多很多篇滚粗记， 才会有一篇不是滚粗记的东西啦 总而言之，我现在还是太菜了 还要过一大段时间我才会变强啦 Day inf 联赛考完，停训一个个月 我和学科度过了美好的一个月 然后月考$100$多名英勇滚粗 ~~ZSY月考照样吊打我~ 阅读全文
posted @ 2018-02-02 09:54
小蒟蒻yyb
阅读(1308)
评论(10)
推荐(0)
摘要：
当年$NOip$考场配置不记得啦 存在这里搞事情 豪华版超级配置 阅读全文
posted @ 2018-01-27 14:44
小蒟蒻yyb
阅读(1263)
评论(2)
推荐(1)
浙公网安备 33010602011771号