摘要：
【洛谷4005】小Y和地铁（搜索） 题面 "洛谷" 有点长。 题解 首先对于需要被链接的两个点，样例中间基本上把所有的情况都给出来了。 但是还缺了一种从下面绕道左边在从整个上面跨过去在从右边绕到下面来的情况（从反过来是一样的） 然后把所有方法分类之后发现实际上只有$4$种决策。 而$4$种决策中，两 阅读全文
posted @ 2018-08-29 07:49
小蒟蒻yyb
阅读(344)
评论(0)
推荐(0)
摘要：
【BZOJ3064】CPU监控（线段树） 题面 "BZOJ" "洛谷" 题解 神仙$zsy$出在了$noip$模拟的题目。（然而$zsy$出的还是这题的升级版） ~~首先明确一点，这题是一个吉司机线段树。~~ 如果只有区间加法，区间赋值，区间最大值，那么这题很简单。 但是加上了一个区间历史最值，这就 阅读全文
posted @ 2018-08-28 21:44
小蒟蒻yyb
阅读(555)
评论(0)
推荐(0)
摘要：
【Luogu4609】建筑师（组合数学） 题面 "洛谷" 题解 首先发现整个数组一定被最高值切成左右两半，因此除去最高值之后在左右分开考虑。 考虑一个暴力$dp$ ，设$f[i][j]$表示用了$i$个数并且能够看到$j$个的方案数，强制最大值在最右侧。 每次添加最小的一个数放进来：$f[i][j] 阅读全文
posted @ 2018-08-28 13:59
小蒟蒻yyb
阅读(544)
评论(2)
推荐(0)
摘要：
【BZOJ4036】按位或（Min Max容斥，FWT） 题面 "BZOJ" "洛谷" 题解 很明显直接套用$min max$容斥。 设$E(max\{S\})$表示$S$中最晚出现元素出现时间的期望，$min$同理。 那么$E(max\{S\})=\sum_{T\subseteq S}( 1)^{ 阅读全文
posted @ 2018-08-21 17:35
小蒟蒻yyb
阅读(886)
评论(7)
推荐(0)
摘要：
【HDU4336】Card Collector（Min Max容斥） 题面 "Vjudge" 题解 原来似乎写过一种状压的做法，然后空间复杂度很不优秀。 今天来补一种神奇的方法。 给定集合$S$，设$max\{S\}$为$S$中的最大值，$min\{S\}$为集合$S$中的最小值。 那么我们可以得到 阅读全文
posted @ 2018-08-21 17:03
小蒟蒻yyb
阅读(353)
评论(9)
推荐(0)
摘要：
【LOJ2541】【PKUWC2018】猎人杀（容斥，FFT） 题面 "LOJ" 题解 这题好神仙啊。 直接考虑概率很麻烦，因为分母总是在变化。 但是，如果一个人死亡之后，我们不让他离场，假装给他打一个标记（猎人印记？？？） 如果在一次选择的时候选中了一个已经被打过标记的人，那么我们就重新做一次选择 阅读全文
posted @ 2018-08-21 16:03
小蒟蒻yyb
阅读(759)
评论(0)
推荐(0)
摘要：
【BZOJ2024】舞会（动态规划，容斥，高精度） 题面 "BZOJ" "洛谷" 题解 这种关系显然要先排序才不会不想影响。 设$f[i][j]$表示前$i$个女生中，选了$j$个女生配对，并且女生比男生高，剩余的随意匹配的方案数。 转移： $f[i][j]=f[i 1][j]+f[i 1][j 1 阅读全文
posted @ 2018-08-20 17:06
小蒟蒻yyb
阅读(321)
评论(0)
推荐(0)
摘要：
【BZOJ4710】分特产（容斥） 题面 "BZOJ" 题解 比较简单吧。。。 设$f[i]$表示至多有$i$个人拿到东西的方案数。 $f[i]=\prod_{j=1}^m C_{m+i 1}^{i 1}$ 现在要算的是恰好有$n$个人拿到东西的方案数。 $ans=\sum_{i=1}^n ( 1) 阅读全文
posted @ 2018-08-20 15:32
小蒟蒻yyb
阅读(369)
评论(0)
推荐(0)
摘要：
【BZOJ2839】集合计数（容斥，动态规划） 题面 "BZOJ" 权限题 Description 一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得 它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~） Inp 阅读全文
posted @ 2018-08-20 15:16
小蒟蒻yyb
阅读(405)
评论(0)
推荐(0)
摘要：
【BZOJ4035】数组游戏（博弈论） 题面 "BZOJ" "洛谷" 题解 很明显是一个翻硬币游戏的变形，因此当前局面的$SG$函数值就是所有白格子单独存在的$SG$函数的异或和。 那么，对于每一个位置考虑$SG$函数。 $SG(x)=mex_{i=1}^{n/x}\{\oplus_{j=1}^i 阅读全文
posted @ 2018-08-20 07:38
小蒟蒻yyb
阅读(431)
评论(2)
推荐(0)
摘要：
【BZOJ4025】二分图（线段树分治，并查集） 题面 "BZOJ" 题解 是一个二分图，等价于不存在奇环。 那么直接线段树分治，用并查集维护到达根节点的距离，只计算就好了。 cpp include include include include include include include us 阅读全文
posted @ 2018-08-19 20:15
小蒟蒻yyb
阅读(717)
评论(0)
推荐(0)
摘要：
博弈论总结 开头&一些基本性质 本文的大部分内容来自于$YMD$的课件。($orz\ YMD$) 一、必胜点和必败点 $P$点：必败点，在双方都聪明无比的情况下（比如$zsy$和$ppl$在玩游戏），当前先手的人必败的情况。 $N$点：必胜点，在双方操作都正确的情况下先手必胜的位置。 几个性质 所有 阅读全文
posted @ 2018-08-17 20:19
小蒟蒻yyb
阅读(3873)
评论(8)
推荐(12)
摘要：
【HDU3595】GG and MM（博弈论） 题面 "HDU" 一个游戏由多个游戏组成，每次每个操作者必须操作所有可以操作的游戏，操作集合为空者输。 每个游戏由两堆石子组成，每次可以从较多的那一堆中取走较小那堆的数量的倍数个石子。 判断胜负。 题解 $Every SG$，所以我们只需要分开考虑两堆 阅读全文
posted @ 2018-08-17 19:53
小蒟蒻yyb
阅读(660)
评论(3)
推荐(0)
摘要：
【BZOJ3576】江南乐（博弈论） 题面 "BZOJ" "洛谷" 题解 无论一堆石头怎么拆分，都并不能改变它是一个$Multi SG$的事实。 既然每一组的$F$都是固定的，那么我们预处理所有的可能的堆，而将石子拆分成若干堆，也只需要考虑$SG$函数的值就好了。 但是这样子求$SG$值的复杂度是$ 阅读全文
posted @ 2018-08-17 17:09
小蒟蒻yyb
阅读(455)
评论(0)
推荐(0)
摘要：
【BZOJ1188】分裂游戏（博弈论） 题面 "BZOJ" "洛谷" 题解 这道题目比较神仙。 首先观察结束状态，即$P$状态，此时必定是所有的豆子都在最后一个瓶子中。 发现每次的转移一定是拿出一棵豆子，放两颗豆子，所以一个瓶子中无论豆子数量是多少，我们都可以把所有的豆子拆开看成单个的$Nim$游戏 阅读全文
posted @ 2018-08-16 22:12
小蒟蒻yyb
阅读(596)
评论(0)
推荐(1)
摘要：
【BZOJ2940】条纹（博弈论） 题面 "BZOJ" 神TM权限题。 题解 我们把题目看成取石子的话，题目就变成了这样： 有一堆$m$个石头，每次可以取走$c,z,n$个，每次取完之后可以把当前这堆剩下的石头分成任意数量的两堆（可以为空），不能操作者输，判定胜负。 那么这就是一个比较简单的$Mul 阅读全文
posted @ 2018-08-16 21:41
小蒟蒻yyb
阅读(418)
评论(0)
推荐(0)
摘要：
【HDU3032】Nim or not Nim?（博弈论） 题面 "HDU" 题解 $Multi SG$模板题 阅读全文
posted @ 2018-08-16 21:19
小蒟蒻yyb
阅读(409)
评论(0)
推荐(0)
摘要：
【BZOJ1022】小约翰的游戏（博弈论） 题面 "BZOJ" 题解 $Anti SG$游戏的模板题目。 cpp include include include include include include using namespace std; define ll long long defi 阅读全文
posted @ 2018-08-16 20:18
小蒟蒻yyb
阅读(375)
评论(0)
推荐(0)
摘要：
【HDU1848】Fibonacci again and again（博弈论） 题面 "Hdu" 你有三堆石子，每堆石子的个数是$n,m,p$，你每次可以从一堆石子中取走斐波那契数列中一个元素等数量的石子数，两人轮流取，不能操作者输，判定先后手的胜利。 题解 根据$SG$定理，三堆石子可以拆开来看， 阅读全文
posted @ 2018-08-16 20:07
小蒟蒻yyb
阅读(531)
评论(0)
推荐(0)
摘要：
【POJ1704】Georgia and Bob（博弈论） 题面 "POJ" "Vjudge" 题解 这种一列格子中移动棋子的问题一般可以看做成一个阶梯博弈。 将一个棋子向左移动时，它和前面棋子的距离变小，和后面棋子的距离变大，并且减小的值和增大的值是相等的，因此，这个过程我们就可以等价成一个阶梯博 阅读全文
posted @ 2018-08-15 22:18
小蒟蒻yyb
阅读(538)
评论(0)
推荐(0)
摘要：
【BZOJ1299】巧克力棒（博弈论，线性基） 题面 "BZOJ" 题解 $Nim$博弈的变形形式。 显然，如果我们不考虑拿巧克力棒出来的话，这就是一个裸的$Nim$博弈。 但是现在可以加入巧克力棒。加入巧克力棒的意义是修改当前的异或和。 如果不能够改变当前先后手赢的状态的话，那么必定不能够拿出一个 阅读全文
posted @ 2018-08-15 21:40
小蒟蒻yyb
阅读(739)
评论(0)
推荐(0)
摘要：
题面 "洛谷" 题解 $Nim$游戏模板题 阅读全文
posted @ 2018-08-15 20:17
小蒟蒻yyb
阅读(387)
评论(0)
推荐(0)
摘要：
题面 "HDU1527 取石子游戏" "洛谷2252 取石子游戏" 题解 裸的威佐夫博弈 cpp include include using namespace std; const double phi=(sqrt(5)+1)/2; int a,b; int main() { ios::sync_ 阅读全文
posted @ 2018-08-15 19:58
小蒟蒻yyb
阅读(469)
评论(0)
推荐(0)
摘要：
题面 "HDU" 题解 $Bash\ Game$模板题 cpp include using namespace std; int T,n,m; int main() { ios::sync_with_stdio(false); cin T; while(T ) { cin n m; if(n%(m+ 阅读全文
posted @ 2018-08-15 19:44
小蒟蒻yyb
阅读(378)
评论(0)
推荐(0)
摘要：
【CF888G】Xor MST（最小生成树，Trie树） 题面 "CF" "洛谷" 题解 利用$Kruskal$或者$Prim$算法都很不好计算。 然而我们还有一个叫啥来着?$B$啥啥的算法，就叫$B$算法吧。 思想是对于每个点找到一条最小边，并且将这条边连上，不难证明每次至少连上了$n/2$个点。 阅读全文
posted @ 2018-08-15 09:39
小蒟蒻yyb
阅读(946)
评论(0)
推荐(1)
浙公网安备 33010602011771号