摘要：
Day 1 今年年初，留坑，以后补，多多关注。 Day0 上午吃了碗粉，就坐地铁到了高铁站。 做高铁从长沙到了广州，最大的感受就是热热热热热热热热。 所以太热了不说了。（雾 ~~汉堡王真香~~ Day1 上午从宾馆搬到了广二。报道的时候最大的感受就是大大大大大大大大大。~~似乎只要是个高中就比我们学 阅读全文
posted @ 2019-01-19 17:24
小蒟蒻yyb
阅读(2253)
评论(10)
推荐(2)
摘要：
THUSC2017题解 题目都是在LOJ上交的。 chocolate "LOJ 2977巧克力" 这题看着就让人想起了百度之星复赛的$T5$，就是 "这题" 。 因为种类的个数很多，所以把每个种类随意$rand$一个$[1,k]$的权值做一个映射，这样子随机若干次的正确率就会很高。 接下来考虑如何计 阅读全文
posted @ 2019-01-18 23:02
小蒟蒻yyb
阅读(911)
评论(2)
推荐(0)
摘要：
BM算法 用来求解一个数列的递推式。 即给定$\{x_i\}$求解一个$\{a_i\}$，满足$|a|=m,x_n=\sum_{i=1}^ma_i x_{n i}$。 考虑增量法构造。 假设当前有一个长度为$m$的$\{a\}$满足条件，并且对于$x_{1..n 1}$都满足递推关系。 定义$del 阅读全文
posted @ 2019-01-18 20:09
小蒟蒻yyb
阅读(1048)
评论(4)
推荐(0)
摘要：
【UOJ 450】【集训队作业2018】复读机（生成函数，单位根反演） 题面 "UOJ" 题解 似乎是$\mbox{Anson}$爷的题。 $d=1$的时候，随便怎么都行，答案就是$k^n$。 $d=2$的时候，可以做一个$dp$，设$f[i][j]$表示前$i$个复读机选了$j$个时间的方案数。 阅读全文
posted @ 2019-01-17 22:43
小蒟蒻yyb
阅读(928)
评论(1)
推荐(0)
摘要：
【UOJ 246】套路（动态规划） 题面 "UOJ" 题解 假如答案的选择的区间长度很小，我们可以做一个暴力$dp$计算$s(l,r)$，即$s(l,r)=min(s(l+1,r),s(l,r 1),abs(a_r a_l))$。 我们发现$s(l,r)\le \frac{m}{r l+1}$，那么 阅读全文
posted @ 2019-01-17 18:05
小蒟蒻yyb
阅读(427)
评论(0)
推荐(0)
摘要：
【CF1097F】Alex and a TV Show（bitset） 题面 "洛谷" "CF" 题解 首先模$2$意义下用$bitset$很明显了。 那么问题在于怎么处理那个$gcd$操作。 然后就莫比乌斯反演一下：$f[n]=\sum\limits_{n|d}g[d],g[n]=\sum\lim 阅读全文
posted @ 2019-01-17 16:48
小蒟蒻yyb
阅读(445)
评论(0)
推荐(0)
摘要：
【BZOJ4419】[SHOI2013]发微博（???） 题面 "BZOJ" "洛谷" 题解 一道$easy$，每个点维护一下要给周围的点加上多上，如果额外连了一个点进来就给他把标记减掉，如果删掉了一条边就给他把标记加上，然后最后把所有边都删掉就好了。 cpp include include inc 阅读全文
posted @ 2019-01-17 16:02
小蒟蒻yyb
阅读(257)
评论(0)
推荐(0)
摘要：
【BZOJ4771】七彩树（主席树） 题面 "BZOJ" 题解 如果没有深度限制，每次只询问子树内的颜色个数，除了树套树$dfs$序加前驱或者后继强行二维数点之外，还有这样一种做法： 把所有相同颜色的点按照$dfs$序排序，每个点给自己的位置贡献$1$，相邻的两个点给$lca$贡献$ 1$。然后只要 阅读全文
posted @ 2019-01-17 15:53
小蒟蒻yyb
阅读(841)
评论(0)
推荐(1)
摘要：
【BZOJ5317】[JSOI2018]部落战争（凸包，闵可夫斯基和） 题面 "BZOJ" "洛谷" 题解 很明显我们只需要两个凸包$A,B$。 假设询问给定的方向向量是$v$。 那么现在就是判断$B+v$与$A$时候有交集。 转移一下改为判定向量$v$时候在$A B$中，翻转$B$的坐标，做闵可夫 阅读全文
posted @ 2019-01-17 15:02
小蒟蒻yyb
阅读(976)
评论(0)
推荐(0)
摘要：
计算几何相关 向量表示法 这里最适合的就是用一个二维点对$(a,b)$来表示了。 点积 ${a.x b.x+a.y b.y}$ 在向量的含义下：$\vec{a}·\vec{b}=|\vec{a}||\vec{b}|cos$ 叉积 ${a.x b.y a.y b.x}$ 这个东西很有用，首先这个东西的 阅读全文
posted @ 2019-01-17 14:56
小蒟蒻yyb
阅读(712)
评论(8)
推荐(0)
该文被密码保护。 阅读全文
posted @ 2019-01-16 23:04
小蒟蒻yyb
阅读(15)
评论(1)
推荐(0)
摘要：
【BZOJ2618】[CQOI2006]凸多边形（半平面交） 题面 "BZOJ" "洛谷" 题解 这个东西就是要求凸多边形的边所形成的半平面交。 那么就是一个半平面交模板题了。 这里写的是平方的做法。 cpp include include include include using namespa 阅读全文
posted @ 2019-01-16 14:53
小蒟蒻yyb
阅读(423)
评论(0)
推荐(0)
摘要：
【BZOJ2823】[AHOI2012]信号塔（最小圆覆盖） 题面 "BZOJ" "洛谷" 相同的题： "BZOJ1" "BZOJ2" "洛谷" 题解 模板题。。。 cpp include include include include using namespace std; define MAX 阅读全文
posted @ 2019-01-16 08:15
小蒟蒻yyb
阅读(387)
评论(0)
推荐(0)
摘要：
【BZOJ1185】[HNOI2007]最小矩形覆盖（凸包，旋转卡壳） 题面 "BZOJ" "洛谷" 题解 最小的矩形一定存在一条边在凸包上，那么枚举这条边，我们还差三个点，即距离当前边的最远点，以及做这条边的垂线的最靠左和最靠右的两个点。 最远点很容易求，叉积计算面积来比就好了。 那么剩下两个点呢 阅读全文
posted @ 2019-01-15 23:02
小蒟蒻yyb
阅读(425)
评论(0)
推荐(0)
摘要：
【BZOJ2829】[SHOI2012]信用卡凸包（凸包） 题面 "BZOJ" "洛谷" 题解 既然圆角的半径都是一样的，而凸包的内角和恰好为$360°$，所以只需要把圆角的圆心弄下来跑一个凸包，再额外加上一个圆的周长就好了。 浮点精度卡不过，洛谷上有人给了一份代码，加上去特判一下就过了。。。 阅读全文
posted @ 2019-01-15 12:50
小蒟蒻yyb
阅读(367)
评论(1)
推荐(1)
该文被密码保护。 阅读全文
posted @ 2019-01-13 21:52
小蒟蒻yyb
阅读(11)
评论(0)
推荐(0)
该文被密码保护。 阅读全文
posted @ 2019-01-12 10:48
小蒟蒻yyb
阅读(16)
评论(0)
推荐(0)
该文被密码保护。 阅读全文
posted @ 2019-01-09 15:39
小蒟蒻yyb
阅读(18)
评论(0)
推荐(0)
该文被密码保护。 阅读全文
posted @ 2019-01-09 15:29
小蒟蒻yyb
阅读(12)
评论(0)
推荐(0)
摘要：
【BZOJ5285】[HNOI2018]寻宝游戏（神仙题） 题面 "BZOJ" "洛谷" 题解 既然是二进制按位的运算，显然按位考虑。 发现这样一个关系，如果是$or$的话，只要$or\ 1$，那么无论前面是啥，操作完之后都是$1$；同理$and\ 0$也是一样，无论前面是什么，操作完都是$0$。 阅读全文
posted @ 2019-01-06 22:34
小蒟蒻yyb
阅读(652)
评论(0)
推荐(0)
摘要：
【LOJ 2542】[PKUWC2018]随机游走（min max容斥，动态规划） 题面 "LOJ" 题解 很明显，要求的东西可以很容易的进行$min max$容斥，那么转为求集合的$min$。 那么怎么求解每个集合的$min$呢。 显然以起点为根节点，如果点集中一个点在另外一个点的子树内，显然不需 阅读全文
posted @ 2019-01-06 21:16
小蒟蒻yyb
阅读(437)
评论(0)
推荐(0)
摘要：
【BZOJ4008】[HNOI2015]亚瑟王（动态规划） 题面 "BZOJ" "洛谷" 题解 设$f[i][j]$表示前$i$张卡中有$j$张被触发的概率。 分两种情况转移，即当前这张是否被触发。 不被触发的概率是$\displaystyle (1 p[i])^{r j}$，即一共会考虑$r j$ 阅读全文
posted @ 2019-01-06 17:29
小蒟蒻yyb
阅读(241)
评论(0)
推荐(0)
摘要：
【BZOJ5416】【NOI2018】冒泡排序（动态规划） 题面 "BZOJ" "洛谷" "UOJ" 题解 考场推出了就是两个上升子序列，并且最长下降子序列长度不超过$2$。。。然后大力暴力状压$dp$混了$44$分。。。这个结论并不是很难证明，考虑一下冒泡排序的过程就好了。 实际上$O(n^2)$ 阅读全文
posted @ 2019-01-06 16:57
小蒟蒻yyb
阅读(577)
评论(0)
推荐(0)
浙公网安备 33010602011771号