摘要：
题目链接 题意分析 尽管是莫队题 但是对于我来说 也是一道bitset入手题 这道题就是 三个区间元素总个数-3*区间元素重复个数 对于区间元素的个数操作 很容易想到使用莫队算法 求区间元素重复个数 也就是区间的交 这个时候我们可以使用bitset 首先 由于$ai≤10^9$ 所以我们需要离散化
阅读全文
posted @ 2020-10-21 11:03
tcswuzb
阅读(160)
推荐(1)
摘要：
#题目链接 题意分析 我们把所有的坐标按照行进行排序 然后列就成为了一个排列 把题意进行简单的转化之后就是 求排列中有多少个子串 且该子串排序之后是公差为1的等差数列 这道题其实真的很锻炼思维 首先 对于一个字串$[L,R]$ 其中的最大值以及最小值为$Max,Min$ 那么显而易见的就是$Max-
阅读全文
posted @ 2020-10-21 07:49
tcswuzb
阅读(168)
推荐(0)
摘要：
题目链接 题目分析 这道题目让我暂时一段时间内不想玩植物大战僵尸了 其实我们只要搞清楚之后 建个模 就会发现 这其实是一道最大权闭合子图问题 只有消灭了所有护着这株植物的所有植物 才可以消灭这株植物 也就意味着我们要消灭这株植物 就不可以不管护着ta的植物 符合闭合子图的概念 首先 这株植物在哪些植
阅读全文
posted @ 2020-10-11 10:43
tcswuzb
阅读(170)
推荐(0)
摘要：
题目链接 题意分析 这道题其实就是一个裸的最大权闭合子图问题 如果把实验看作一个点的话 ta的出度连接着的点就是ta对应的仪器 符合闭合子图的概念 那么我们建好图之后就可以跑最小割最大流了 #CODE： #include<iostream> #include<cstdio> #include<cst
阅读全文
posted @ 2020-10-11 10:03
tcswuzb
阅读(167)
推荐(0)
摘要：
写在之前 最近又开始更新博客了 所以就学习了一些之前没有学过的东西 正式开始 什么是最大权闭合子图？ 首先 我们需要明白 什么是闭合子图 首先 子图我们很好明白 至于闭合子图 就是子图中所有的点 他们的出度指向的点也在这个子图中 我们来一个DAG网上找的 上图理解一下 在这幅图中 {1,2,3,4}
阅读全文
posted @ 2020-10-11 09:56
tcswuzb
阅读(208)
推荐(1)
摘要：
学科技 博弈论的核心 : 寻找必胜策略 或者 统计要求方案 【好好学科技吧您馁】 1.ICG游戏 (1)游戏有两个人参与 二者轮流做出决策 且这两个人的决策都对自己最有利 (2)当存在一人无法做出决策时 当前人lose 无论二人如何决策都可以在有限步数内解决游戏 (3)游戏中的同一个状态不会存在多次
阅读全文
posted @ 2020-10-01 15:21
tcswuzb
阅读(493)
推荐(0)
摘要：
无向图删边游戏 【友情链接1】 【友情链接2】 树上删边游戏 在某一棵树上删除一条边，同时删去所有在删除后不再与根相连的部分 双方轮流操作，无法再进行删除者判定为失败 一个游戏中有多棵树， 我们把TA们的根都放在地板上，方便之后的处理 、 轮到谁是无法删的一方获胜 树上问题@leige 竹子 为了方
阅读全文
posted @ 2020-10-01 15:19
tcswuzb
阅读(488)
推荐(1)
摘要：
威佐夫博弈 有两堆石子，两个顶尖聪明的人在玩游戏， 每次每个人可以从任意一堆石子中取任意多的石子 或者从两堆石子中取同样多的石子，不能取得人输 分析谁会获得胜利 不想听的的话直接看结论 与前两种博弈不同的是 不可以将两堆石子 分开计算 所以类似需要一个扩展的二维SG 我们定义先手必输的局势就是奇异局
阅读全文
posted @ 2020-10-01 15:13
tcswuzb
阅读(222)
推荐(0)
摘要：
#SG函数 Nim游戏 n堆石子 \(a_1\ \ a_2\ \ a_3\ \ a_4\ \ ......\ \ a_n\) 规则(......) \(a_1\ \ xor\ \ a_2\ \ xor\ \ a_3\ \ xor\ \ a_4\ \ xor\ \ ......\ \ xor\ \ a
阅读全文
posted @ 2020-10-01 15:12
tcswuzb
阅读(382)
推荐(1)
摘要：
存在n个从高到低排布的阶梯 我们只可以从到相邻的低阶梯移动棋子 最低阶梯的棋子就相当于拿走 例如 1.我们可以从3到2移动一个棋子 2.我们不可以从4到3移动3个棋子 3.我们可以直接从1阶梯上拿走棋子 结论有些直接 \(a_1\ xor \ a_3\ xor \ a_5\ xor \ ......
阅读全文
posted @ 2020-10-01 15:09
tcswuzb
阅读(349)
推荐(0)
摘要：
斐波那契博弈 有一堆个数为n的石子，A，B轮流取石子，满足： (1)先手不能在第一次把所有的石子取完； (2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间 (包含1和对手刚取的石子数的2倍) 同之前的不同点就是:取的规则动态化 约定取走最后一个石子的就是赢家 就连我看博弈名都知道 这必须
阅读全文
posted @ 2020-10-01 14:58
tcswuzb
阅读(365)
推荐(1)
摘要：
部分例题选讲 【BZOJ1115 [POI2009]石子游戏Kam】 我们把相邻的石子差分一下 然后发现相邻石子堆之间的差值不可以<0 那么最终的结果就是差值均为0 然后我们思考一下 每拿走一堆石子 如何去使用差分求解 对于石子数 1 5 14 16 20 差分之后就是: 4 9 2 4 然后我们例
阅读全文
posted @ 2020-10-01 11:41
tcswuzb
阅读(324)
推荐(0)
摘要：
巴什博奕 开始之前 先来一个简化版本(小学奥赛版本): 某毒瘤给hsez2017级信息奥赛生一堆胸牌 共n个 而且十分大方 这个n是<=10^6滴 每一次只可以取一个或者两个 规定取走最后一个的人是胜者 现在zmj与leizi玩这个游戏 由于zmj有一对"沙包大的拳头",所以leizi让zmj先取
阅读全文
posted @ 2020-10-01 11:40
tcswuzb
阅读(353)
推荐(0)
摘要：
Nim 谁取到最后一个谁赢 定义 : 异或和为0 T态 异或和不为0 S态 定理1 对于任意一个S态 总能合理合法地使其转化为T态 这是可以证明的 还记得取火柴游戏吗 ? ? ? \(x=a_1\ xor\ a_2\ xor\ a_3\ xor\ ......\ xor\ a_n>0\) 那么根据异
阅读全文
posted @ 2020-10-01 11:37
tcswuzb
阅读(202)
推荐(0)
摘要：
Multi-Nim 有n堆石子， 两个人可以从任意一堆石子中拿任意多个石子(不能不拿) 或把一堆数量不少于2石子分为两堆不为空的石子， 没法拿的人失败。问谁会胜利 #分析 我们实质上还是可以把TA分为若干个子问题 可以使用SG定理解释 如果只有操作1 那么就是裸的Nim游戏 操作2就是把一个子游戏分
阅读全文
posted @ 2020-10-01 11:36
tcswuzb
阅读(249)
推荐(0)
摘要：
Anti-Nim 地上有n堆石子（每堆石子数量小于10000）， 每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。 每次只能从一堆里取。谁取走最后一刻谁输。 假如甲是先手，且告诉你这n堆石子的数量，他想知道是否存在先手必胜的策略 定义使人快乐 孤单堆：一堆火柴仅有1根火柴 充裕堆
阅读全文
posted @ 2020-10-01 11:32
tcswuzb
阅读(437)
推荐(0)
摘要：
写在之前 我打算发一个大篇的博弈论 这是一个大纲 这其中也存在来自多方大佬的转载 希望可以解答一些各位心中的疑惑 透彻博弈论 cdy:@xkj 博弈论是个啥？ ？ ？ xkj:@cdy 学科技的【科普时间】 我们接下来会讲些什么 1.四大经典博弈 2.博弈树(构造状态图) 3.SG函数 4.一些杂讲
阅读全文
posted @ 2020-10-01 11:27
tcswuzb
阅读(514)
推荐(0)
摘要：
【写在之前】 由于最近要写后缀数组 以及要给高一讲课 所以就写了这个。。。。。。 【正式开始】 计数排序(≠桶排序) 计数排序的算法显然更加高明 $ O(n+MAX\ NUM)$ int n,maxn; int num[N],key[MAX_NUM],rank[N]; for(int i=1;i<=
阅读全文
posted @ 2020-10-01 11:05
tcswuzb
阅读(224)
推荐(0)
摘要：
【写在之前】 其实听说过这个东西 据说很牛B dalao (1) dalao (2) dalao (3) dalao (4) 但这其实是一个蒟蒻无力的挣扎 【正式开始】 后缀排序 求SA 这里只介绍倍增算法 \(SA[i]\) 表示排名为$i$的后缀的开头位置 \(rnk[i]\) 表示第$i$个位
阅读全文
posted @ 2020-10-01 11:03
tcswuzb
阅读(199)
推荐(0)
摘要：
题目链接 题意分析 为了保证食用愉快 题目链接我给了vjudge 给你52张扑克牌 一开始依次取7张牌 每张牌成一个牌堆的首发 然后从取第8张牌开始依次往每个牌堆积上 如果发生了这样的情况的一种 注意 存在优先级顺序 1.牌堆堆首的2张牌与牌堆堆尾的1张牌 2.牌堆堆首的1张牌与牌堆堆尾的2张牌 3
阅读全文
posted @ 2020-09-01 22:46
tcswuzb
阅读(180)
推荐(0)
摘要：
题目链接 题意分析 这道题的题意:给定一个无向图,每一次询问u与v之间是否存在一条路径使得ai最大值是a,bi最大值是b 我一开始以为是离线+瓶颈树 后来发现 这道题必须是恰好等于 而不是大于等于或者小于等于 我们看一下 这道题如果路径上只有一个权值的话 我们可以使用双指针 把对于当前询问ai 路径
阅读全文
posted @ 2020-08-23 21:17
tcswuzb
阅读(171)
推荐(0)
摘要：
思路很简单 由于高精度开根十分难搞 所以考虑逆向思路 二分答案 然后利用$mid^m$同原始数据进行比较 但是由于这其中涉及到了乘法而且高精度乘法是$n^2$级别的 肿么办???一开始想到了FFT但是后来果断放弃了 可以考虑压位高精度 就是把10进制转化为1e8或者1e9进制 注:1.为了卡常 数组
阅读全文
posted @ 2020-07-18 16:20
tcswuzb
阅读(350)
推荐(1)
摘要：
Day 1 简要的说了些注意事项 一整天都在刷树套树的水题 退役的感觉近了 Day 0 早上收拾好东西去了火车站之后 火车站居然还没有开门 等了半天 我们是从衡水到德州再到秦皇岛 到了德州之后 去车站吃了肯德基 然后做了三个多小时的车 到了燕大宾馆之后 发下行李 先吃了饭 然后去试机 试机之后 下午
阅读全文
posted @ 2019-04-24 19:51
tcswuzb
阅读(445)
推荐(4)
摘要：
"题目链接" 题意分析 这是一道状压$DP$的题 一个人只可以欣赏到$5$只动物 显然可以状压 我们用$dp[i][j]$表示当前$[i,i+4]$中这$5$只动物的状态$j$ 在或者不在 最多可以满意的小朋友数 $num[i][j]$表示当前$[i,i+4]$中这$5$只动物的状态$j$ 在或者不
阅读全文
posted @ 2019-04-20 16:37
tcswuzb
阅读(198)
推荐(0)
摘要：
"题目链接" 题意分析 一句话题意 : 树上一条链中挑选出某些数 异或和最大 我们可以考虑维护一个树上倍增线性基 然后倍增的时候 维护一个线性基合并就可以了 写起来还是比较容易的 CODE: cpp include include include include include include in
阅读全文
posted @ 2019-04-20 15:37
tcswuzb
阅读(228)
推荐(0)
摘要：
"题目链接" 题意分析 一开始看了之后 没有什么思路 后来直接观察了 "$ghj1222$" 的博客之后 明白了 首先我们可以任意找出来一条路径$1→n$ 然后我们思考一下有什么更优的吗 对了 我们没准可以舍近求远 然后用 环来优化一下 具体看图 首先 从原路径到达环的被抵消掉了 那么有贡献的就是环
阅读全文
posted @ 2019-04-17 22:02
tcswuzb
阅读(193)
推荐(0)
摘要：
写在之前 线性基是一个神奇的东西 曾经傻傻的以为一趟序列dp下来就可以求最大异或和了 正式开始 由于我比较菜 所以只写了求序列最大异或和 线性基资瓷插入以及查询两种操作 $1.$插入 我们对于当前的数 由高位向低位进行比较 如果当前这一位$i$没有数的话 我们就把当前值为$a_i=x$ 结束比较 否
阅读全文
posted @ 2019-04-17 21:53
tcswuzb
阅读(297)
推荐(0)
摘要：
"题目链接" 题意分析 首先考虑链的话 就是将$1$部分的两条子链排序之后 贪心合并即可 那么考虑树的话 我们照样合并就行了 首先 排序的话 我们使用堆就可以了 然后 涉及到了两点问题 $1.$我们对于$u$以及$v$这两个维护好的堆合并的话 为了保证时间复杂度 我们需要使用 启发式合并 $2.$我
阅读全文
posted @ 2019-04-17 20:37
tcswuzb
阅读(202)
推荐(0)
摘要：
"题目链接" 题意分析 结论题 + $DP$ 我们可以将从左上到右下走看成一个$DAG$ 那么 就是要我们求当前$DAG$的最小覆盖 首先 $D$氏定理 一个$DAG$的最小覆盖就是这个$DAG$的最大独立集 然后就是$DP$求最大独立集 根据这个方格 最大独立集中任意两个元素都是满足 左下 右上
阅读全文
posted @ 2019-04-17 19:09
tcswuzb
阅读(208)
推荐(0)
摘要：
题意分析 这题一看没有什么思路 幸好我们机房的红太阳$ghj1222$切了这道题 首先我们考虑风跑一个来回之后人怎么样 就是跑了一个区间 也就是风跑了若干个来回之后 人跑了若干个区间 所以我们考虑求出距离最小的那个区间 距离是一个单峰函数 所以我们用 三分 求 然后的话 问题就是求 两条有向线段之间
阅读全文
posted @ 2019-04-13 20:27
tcswuzb
阅读(162)
推荐(0)
摘要：
"题目链接" 题意分析 三分套三分 我们不经意间发现 这是一个单峰套单峰函数 我们假设 $AB$上最优点是$x$ $CD$上最优点是$y$ 那么就是求$min\{dis(A,x)/p+dis(y,D)/q+dis(x,y)/r\}$ 我们首先 在$AB$上三分这个点$x$ 然后在当前情况下再在$CD
阅读全文
posted @ 2019-04-13 19:58
tcswuzb
阅读(162)
推荐(0)
摘要：
写在之前 今天学习了三分法 真的好好用 回去直接把模板切了 正式开始 三分法就是单峰函数求最值 当前我们位于$[le,ri]$ 然后我们我们有两个三等分点$mid,mmid(midf(mmid)$ 那么可以确定的是$mmid$一定位于极值点右边 证明 : 画图之后显然啊 $2.f(mid) incl
阅读全文
posted @ 2019-04-13 19:53
tcswuzb
阅读(515)
推荐(0)
摘要：
"题目链接" 题意分析 首先 如果当前序列中一头奶牛拿不到礼物的话 那么他后面的奶牛也拿不到礼物 所以我们可以二分 由于可以操作无限次 所以我们对于当前$[1,mid)$的奶牛按照$c$值排序之后 贪心的先放$c$中最小的奶牛 如果依然存在一头奶牛被放在$mid$之前 那么就无法使$mid$得到礼物
阅读全文
posted @ 2019-04-12 08:31
tcswuzb
阅读(266)
推荐(0)
摘要：
"题目链接" 题意分析 一看就知道是一道$01$分数规划的题 我们二分值之后 跑树形背包就可以了 CODE: _HEOI 2019 RP++_
阅读全文
posted @ 2019-04-04 08:57
tcswuzb
阅读(245)
推荐(0)
摘要：
"题目链接" 题意分析 我们考虑 交换两个数$[le,ri]$的贡献 减少的逆序对数$[le,ri]$中小于$num[le]$以及大于$num[ri]$的数 增加的$[le,ri]$中大于$num[le]$以及小于$num[ri]$的数 同时注意 如果$num[le]!=num[ri]$ 二者相互的
阅读全文
posted @ 2019-04-04 08:12
tcswuzb
阅读(298)
推荐(0)
摘要：
"题目链接" 题意分析 首先对于一个可以匹配的字符串 我们发现 差分之后出除了最后一位外是相等的 所以我们要求的就是拆分之后最长匹配长度+1 首先 我们将差分之后的拼成一个长串 然后建出$SA$ 发现答案具有可二分性 然后我们再使用$height$数组 将$lcp≥now$的后缀分成一组 如果存在共
阅读全文
posted @ 2019-04-04 08:03
tcswuzb
阅读(282)
推荐(0)
摘要：
"题目链接" 题意分析 带修改树链第$k$大 首先我们使用树链剖分将树上问题转化为区间问题 然后对于当前修改 我们直接修改即可 对于链上第$k$大 我们先求一个总点数 转化为链上第$k$小 然后我们将$x$到$y$之间所有的重链都提出来 那么在$dfs$序上就是一堆连续区间 而且最多$log$个 类
阅读全文
posted @ 2019-04-03 19:03
tcswuzb
阅读(154)
推荐(0)
摘要：
"题目链接" 题意分析 首先我们需要求的是统一以后的值$x$ 并且一般的棋盘操作我们都需要黑白染色 那么对于棋盘格子是偶数的情况的话 答案是存在单调性的 因为如果统一之后 两两搭配还是可以再加一个的 如果棋盘格子是奇数的话 那么黑格子数量为$num1$ 权值和为$sum1$ 白格子数量为$num2$
阅读全文
posted @ 2019-04-03 14:43
tcswuzb
阅读(254)
推荐(0)
摘要：
"题目链接" 题意分析 首先一看就知道这是一道最小割 这里奉上最小割的代码 cpp include include include include include include include include include include include include include incl
阅读全文
posted @ 2019-04-02 19:35
tcswuzb
阅读(227)
推荐(0)
摘要：
"题目链接" 题意分析 我们考虑维护两个栈 分别支持左边的插入删除以及右边的插入删除 然后对于两两个栈的我们需要用背包求出最优答案 注意 删除时如果不够的话 我们需要从另一个栈中取出一半加入另一个栈中 注意保持顺序 CODE: cpp include include include include
阅读全文
posted @ 2019-04-02 16:12
tcswuzb
阅读(446)
推荐(0)
浙公网安备 33010602011771号