2023SDSC
2023夏令营
Day0
垃圾山外宿舍6人
Day1
Contest
T1 colour
有序列 $a_n$, 初始 $a_i=0$, 给定 $p_m$, $q$ 次询问按顺序遍历 $p_l\ldots p_r$, 对于 $p_i$, 选择给 $a_{p_i}$ 或 $a_{p_i+1}$ 赋值为 $i$.
$n\le 500, m\le 10^6, q\le 2000$
对于位置 $i$, 有一些是和右边选一个赋值, 有些是和左边, 称为向左伸/向右伸. 考虑每个位置最终颜色, 注意到 $i-1$ 中向右伸的最高的 $lt$ 是重要的, 如果 $i-1$ 的位置最终颜色比 $lt$ 小, 则右边必须选的比 $lt$ 大, 然后就想到 $f_{i, 0/1/2}$ 表示位置 $i$ 选的数与从 $i$ 向右伸的最后一次操作 $t$ 小于/相等/大于就能转移了.
复杂度 $nq\log m+m$
T2 binary
$n, m\le 5\times 10^5$
考虑已经选定了 $w$ 之后, 答案只在某一次没有 $x$ 或没有 $y$ 才变化, 很难注意到左右其实是独立的, 因为加入操作左边再操作右边, 你操作右边时的 $x$ 一定会找到刚才操作左边的操作位置的右边.
于是只考虑一边, 那么相当于给每个 $t=1$ 的操作位置配一个 $s=1$ 的, 相当于括号匹配, 于是 $t=1$, $s=1$ 分别赋值 $1, -1$, 然后求失配数, 所以直接线段树求最大前缀和/后缀和.
现在对于给定的 $w$ 是1log算. 发现 $w$ 是单调的, 满足条件的一定是一个后缀, 因为 $w$ 往后了你的 $u$ 就不断往前然后后面就越不可能填满前面就越可能填满这样的.
于是二分2log, 考虑在刚才的线段树上二分, 但 $mid$ 处不一定 $t=1$, 一种方法是 $mid$ 前后第一个 $t=1$ 的 $w_1, w_2$, . 但其实可以直接把中间当成可以二分的地方, 因为 $w_1, w_2$ 里一定有一个可以把答案拆成 $[1, w_1], [w_2, n]$ 算.
T3 tree
给定 $n$ 点带权无根树, $q$ 次询问对于给定的 $u, v, A, B$, 从 $u, v$ 出发的不交路径 $l_1, l_2$, 最大的 $A\cdot f(l_1)+B\cdot f(l_2)$, 其中 $f(l)$ 表示边权和.
$n\le 5\times 10^5, q\le 10^5$
容易想到可以用 $u\to v$ 上一条边分开树, 两个路径分别在一边. 然后答案就是两边的距离最大值.
距离最大值可以再拆开, 对于 $u\to x\to m$, 其中 $x$ 在 $u\to v$ 上, $m$ 在 $x$ 的子树中, 变成 $dis(u, x)+dis(x, m)$.
树剖之后这个 $dis(x, m)$ 可以预处理, 因为虽然它和所在链有关, 但是因为树剖之后只有 $\log n$ 个点所在的链不是重链, 这些单独处理即可.
然后继续拆贡献, 考虑 $u, v$ 为祖孙的情况, $dis(u, x)$ 差分成两个深度相减, 最后去掉只和 $u, v$ 相关的东西就成了 $Ag_u(x)+Bg_v(y)$, 其中 $g_u(x)=l_x-dep_x, g_v(x)=l_x+dep_x$ 这样的状物.
然后考虑这树剖后线段树对应的 $\log^2 n$ 个区间, 考虑 $x$ 和 $y$ 的位置, 他们要满足 $x<y$. 如果他们所在的拆出的线段树区间不同可以直接做(枚举一个区间, 算另一边最小值), 另一种情况考虑它们所在的区间相同, 此时考虑那个用一条边分开树, 那么枚举这个区间中的分界线, 此时两边贡献就是一个前缀/后缀max, 正反各扫一遍可以获得, 然后线性建凸壳. 这样建树就2log(每个区间跑一遍凸壳). 询问可以排个序砍掉在凸壳上二分的log.
法2是淀粉质
询问被拆成从分治重心出发的两部分, 仍然拆贡献, 然后直接从重心dfs, 维护凸包, 每进入一个点插入到凸包中, 退出一个点再撤销, 所以凸包要李超树, 复杂度是查询2log预处理1log.
得分100 + 0 + 15, 没打T2暴力大大失败
Class
CF1764G3 Doremy’s Perfect DS Class (Hard Version)
-这是一道交互题.
- 交互库有一个 $[1, n]$ 的排列 $p$.
- 你可以询问 $l, r, k$, 交互库会返回 $\left\lfloor\dfrac{p_l}k\right\rfloor, \left\lfloor\dfrac{p_{l+1}}k\right\rfloor, \cdots, \left\lfloor\dfrac{p_r}k\right\rfloor$ 中不同数的个数.
- 你需要在 $20$ 次询问内找到 $p$ 中 $1$ 的位置.
- $n\in[3, 1024]$.
$n$ 为奇数时, 考虑让 $k=2$, 因为除以 $k$ 相等的数两两配对. 这样问前缀 $[1, i]$ 得到 $t$, 那么 $2t-i$ 就是出现恰好一次的, 再同样的问一下另一边, 那么 $1$ 就在多的那一边. 复杂度 $2\log n$
$n$ 为偶数时, 除了 $1$, $n$ 也没有配对, 问完之后如果两边恰好一次的一样多显然就 $1$, $n$ 各一个, 然后问一遍 $n$ 就能找到谁是 $n$, 以后就不用再问了($n$ 已经在区间外了), 次数 $2\log n+1$
考虑如何把 $+1$ 砍了, 那么看起来考虑最后一次长为 $2$ 的时候, 假设当前为 $p, p+1$, 则因为二分成了这个区间, 一定已经知道 $[1, p-1], [1, p+1], [p+2, n], [p, n]$ 这些区间, 那么考虑 $[1, p-1]$ 和 $[1, p+1]$, 它们中间增加了一个 $1$ 和一个 $p$ 通过看种类数加2还是加1就可以判断这两个数中除了 $1$, 另一个数的配对出现在哪一边, 假设在后缀, 然后再问 $[p+1, n]$, 判断种类数是否增加, 这样就把数量减少到 $20$ 次.
luogu P9393 紫丁香
对于一个字符串 $A$, 记 $A_i$ 表示它的第 $i$ 个字符.
设 $S$ 是任意长度为 $m$ 的 $01$ 串. 我们有 $n$ 个操作, 第 $i$ 个操作可以表示成一个定义域和值域都是长度为 $m$ 的 $01$ 串集合的函数 $f_i$, 表示经过这次操作后 $S$ 会变成 $f_i(S)$. 而函数 $f_i$ 可以由一个长度为 $m$ 的串 $T_i$ 表示, $T_i$ 由 $\texttt{0, 1, -}$ 三种字符组成, 其中:
$T_{i, j}=\texttt{0}$ 表示 $[f_i(S)]_j=\texttt{0}$.
$T_{i, j}=\texttt{1}$ 表示 $[f_i(S)]_j=\texttt{1}$.
$T_{i, j}=\texttt{-}$ 表示 $[f_i(S)]_j=S_j$.
也就是说, 每个操作会将 $S$ 的一些位赋值为 $0$, 一些位赋值为 $1$, 还有一些位不变.
现在有 $q$ 次操作, 每次操作给定一个长度为 $m$ 的 $01$ 串 $S$, 你可以对它做任意多次操作, 操作的顺序任意, 一个操作可以做多次. 得到的串 $S’$ 可以被看做一个二进制数, 求对应二进制数最大的 $S’$.
$m\le 22, n, q\le 10^5$
考虑倒着做, 因为正着操作是不可逆的而倒着操作每次操作都会变的更好, 那么撤销一次操作后串由 $0, 1, ?$ 组成, 要找到最大的 $01?$ 串可以匹配一开始的 $s$.
你发现3进制我们没法用各种子集dp, 集合科技, 因为存不下 $3^n$.
然后注意到因为我们最后要找最大的答案, 所以直接把 $0$ 都变成 $?$ 是不劣的, 而找到最大的 $1?$ 串之后所有 $?$ 最后一定都是 $0$. 于是变成 $2$ 进制问题. 然后就是要从结果开始不断用操作把 $1$ 消成 $?$ 直到弄不动了, 再判断能不能和初始状态匹配.
然后考虑 $f_i$ 表示可以把 $i$ 消去至少一个 $1$ 的操作, 一个FWT搞定. 然后考虑 $g_i$ 表示 $i$ 可以变成什么, 则 $g_i=g_{f_i(i)}$ 就对了吧
最后要处理多组询问, 相当于求最大的 $g_i\supset s$, 也是一遍dp.
CF1693E Outermost Maximums
有一个长度为 $n+2$ 的序列 $a$, 其中 $a_0=a_{n+1}=0$, 其余元素均给定.
你可以进行下面两种操作任意次:
- 设 $x$ 表示序列 $a$ 最靠左的最大值的位置, 则令 $a_x\leftarrow \max_{i=0}^{x-1}a_i$.
- 设 $y$ 表示序列 $a$ 最靠右的最大值的位置, 则令 $a_y\leftarrow \max_{i=y+1}^{n+1}a_i$.
你需要求出使序列 $a$ 的所有元素均变成 $0$ 所需的最少的操作总次数.
考虑一个 $n^2$ 做法, 对于当前最大值, 找到次大值位置, 然后左边的都用操作1右边的都用操作2, 中间的随便.
然后考虑优化, 因为不能实时维护最大值次大值, 考虑每个数放一个箭头表示它是由操作 $1$(左箭头)或操作 $2$(右箭头)得到, 如果当前最大值为 $x$, 那么左箭头是一个前缀, 右箭头是一个后缀, 不会有两个箭头相对, 一串箭头指向一个 $x$ 这一串都是 $x$. 那么这一次操作只需要定位当前次大值, 算出新的分界线(不一定是次大值, 还可能是某个箭头).
CF1209G2 Into Blocks (hard version)
给你 $n$ , $q$, $n$ 表示序列长度, $q$ 表示操作次数.
我们需要达成这么一个目标状态:
如果存在 $x$ 这个元素, 那么必须满足所有 $x$ 元素都必须在序列中连续.然后你可以进行这么一种操作, 将所有的 $x$ 元素的变为任意你指定的 $y$ 元素, 并且花费 $cnt[x]$ 的花费, $cnt[x]$ 代表 $x$ 元素的个数.
现在有 $q$ 次询问, 每次询问单点修改一个位置的值, 求修改完之后最小花费使得序列满足目标状态.
注意: 更新不是独立的, 之前的更新会保留.
$n, q\le 2\times 10^5$
考虑合并到最后一定是若干段, 但合并是困难的, 所以改成考虑没有被同一个值覆盖的是分界线.
然后线段树维护, 分界线作为被覆盖次数最小的位置, 另外区间众数因为所有数都在一个区间里所以就是区间max.
CF1656G Cycle Palindrome
给定一个长度为 $n$ 的数列 $a_{1 \cdots n}$, 你需要找到一个循环数列 $b_{1 \cdots n}$ 使得数列 ${ a_{b_{1}}, a_{b_{2}}, a_{b_{3}}, \cdots, a_{b_{n}} }$ 是一个回文数列且 $b$ 是一个长度为 $n$ 的排列.
$\sum n\le 2\times 10^5$
因为循环排列很困难, 所以考虑随便构造一个回文串然后调整成这个
首先如果 $a_i=a_j$, $i, j$ 不在一个环上显然 $i$ 和 $j$ 交换合并两个环.
然后现在所有相对位置都在一个环上.
考虑两对 $a_i=a_j, a_k=a_l$, 那么按顺序交换 $i, k$, $j, l$, $i, j$ 的出边交换.
uoj783 新年的双区间操作
给定 $a_n$ 和 $m$ 个操作 $(l, r, x, l’, r’, y)$, 表示如果区间 $[l, r]$ 中最大值大于 $x$, 就让区间 $[l’, r’]$ 中每个数和 $y$ 取max, 接下来有 $q$ 次单点修改, 在每次修改后求出进行所有操作后序列的最大值为多少.
$n, m\le 2\times 10^5, q\le 6\times 10^5$, 4s
考虑每个操作可以写成如果被触发, 答案对 $f_i$ 取max, 于是如果求出 $f$ 只要考虑初始位置和修改贡献, 简单题.
那么问题就成了如何求 $f$, 那就是对每个区间找有哪些区间与自己有交, 自己的 $f$, 且 $x$ 比自己 $y$ 小, 且时间比自己晚, 对这些区间的 $f$ 取个max, 就是个偏序dp. 大概扫时间, cdq值域, 线段树维护序列维.
Day2
Contest
T1
给定 $a_n$, $q$ 次区间询问 $[l, r]$ 最多可以选出多少个不交的和为 $0$ 的区间.
$n, q\le 4\times 10^5$, 32M
先以每个点为左端点匹配出和为 $0$ 的区间, 然后每个点找到右端点最左的左端点在它右边的点, 于是询问就是不断跳这个.
倍增空间炸了, 写个树剖即可.
然后更强的方法是在得到的树上算出深度, 从询问左右端点分别向右找到第一个区间算出深度, 它们的深度差是答案或答案差 $1$, 于是离线树上 $k$ 级祖先可以做到时间空间线性.
T2
给定 $n$ 点树, 求一条链 $u\to v$ 最大化 $dis(u, v)\cdot f(u, v)$, 其中 $f(u, v)$ 表示最大的树上点到它的距离.
$n\le 5\times 10^5$
这个信息很全局, 不要淀粉质.
考虑这个结构其实是一个树上的三叉, 枚举三叉中心也就是那个离链最远的点连到链上得到的那个点 $r$, 此时 $u, v$ 和最远点 $w$ 分别在一个子树, 那么答案一定是这三个子树中最远的叶子搞出来的.
然后计数就直接一次换根dp算最远叶子及叶子个数.
然后这个会让人产生一个问题就是你可能枚举两个 $r$ 对应同一组 $u, v$, 那么情况就是选出一组 $u, v$, 然后链的不同部分可以连出两个长度相等的 $w$.
然后你发现一个 $u/v$ 换到 $w$ 一定会严格更大, 于是直接在每个 $r$ 上计数就不会重.
T3
$n\le 18$
杜赢说你随机调整后打表可以过16.
考虑把所有 $2^n$ 种状态建图成点, 人的策略作为边, 因为人无法区分 $x, y$ 如果 $x, y$ 只有自己所在位不同, 则把 $x, y$ 连一条边, 这条边就表示如果判断出局面是 $x, y$ 之中, 那么它选择谁, 那么问题就成了要给所有边定向满足任意一个点有不少于一半的边指向自己, 于是直接跑欧拉回路使得每个点的度数正好是对的.
Class
Swapping Operation
给定 $a_n$, 定义
$$
f(a)=\max_k \mathrm{and}_ {i\le k} a_i +\mathrm{and}_{i\gt k} a_i
$$
你可以进行至多一次交换两个数, 求之后的最大值.
你先把原答案暴力出来, 那么众所周知and只变化log次, 两边各有log个, 如果不换这些则答案一定只会变小. 把这些点称作关键点.
交换两个关键点之间暴力.
于是问题是交换一个关键点和一个非关键点, 假设把前缀的关键点换走了, 那么后缀的部分和换走了谁没关系, 先枚举分界线, 再枚举换走的东西, 最后就成了最大化 $f(1, i-1)\mathrm{and}f(i+1, k)\mathrm{and} a_j$ 然后因为两个 $f$ 的值只有log种, 于是一共只有 $\log^2$ 种, 直接对每一种, 算出 $g(v, k)$ 表示 $k+1\le j\le n$ 表示与 $v$ 亦或之后的最大值.
要用st表优化求and和. 复杂度2log.
Pair
平面上 $2n$ 个点, 两两匹配, 最大化好的匹配个数, 好的匹配定义为点在同一行或同一列.
考虑网格图网络流建模每个横坐标建点每个纵坐标建点, 原来的点变成行列之间的边.
此时就是有公共点的边之间是好的匹配, 上界显然是每个连通块 $\lfloor \dfrac{siz}{2} \rfloor$, 而这个是可以达到的, 只要把连通块拉成dfs树, 然后从下往上, 每个点都匹配完了或留一条父边就能构造出来了.
复杂度线性.
Be Careful $2$
$n\times m$ 的矩形有 $k$ 个特殊点, 一个正方形是好的当且仅当完全位于矩形内且不覆盖任意一个特殊点, 求好的正方形面积之和.
做到 $k^2$
先容斥算对覆盖 $S$ 所有点的方案数.
那么子集有 $2^k$ 个但点集包围盒只有 $k^4$ 个.
然后发现如果包围盒内部有点则容斥系数是 $0$, 因为每个点在/不在就让系数消了, 只考虑所有点都在边界上的 $k^2$ 个
然后考虑如何找到所有包围盒, 考虑先枚举矩形左边界上的一个点, 再枚举矩形右边界上的一个点, 那么两个点为对角围成的矩形之间肯定没点, 那么所有的右端点是单调的, 同时上下边就是对应的这横坐标两个点之间, 纵坐标前驱后继的点. 于是单调栈维护右端点, 再用链表维护每个横坐标下所有点的前驱后继.
然后要统计答案, 对每个答案贡献是一个分段四次函数, 直接再做前缀和结束了.
复杂度 $k^2$
Mystery Square
先从中间拆成两半, 考虑只有20个问号的一边.
todo
回
cdq分治让操作都在询问前 + 差分 + 维护关于原始数组的高次多项式
操作二维差分只会变成了主对角线副对角线加, 然后再差分成射线加, 再差分成一个点和一个方向.
然后维护奇妙而复杂的多项式, 找网上题解吧.
Difficult Constructive Problem
暴力枚举头尾的问号, 现在假设头尾已经确定.
然后发现翻转字符只改变2, 不改变奇偶性, 并且是连续的, 直接从前向后贪心, 每个位置看如果填了 $0$ 后面的能不能行
Permutation Arrangement
给定 $n$ 阶排列包含 $1\ldots n$ 和 $?$, 要求你在所有 $?$ 处填数补全排列, 满足任意相邻两位置不相邻
先假设所有问号不相邻, 那么问题是匹配, 于是一个数最多只有四个空不能放, 于是当 $n\ge 8$ 的时候, 每个点至少连出 $4$ 条, Hall定理发现是一定有解.
于是现在有空位了, 那么把空位随便填, 留出8个不相邻的, 于是如果有至少15个空一定有解
于是前面随便填, 最后15个状压爆搜.
workshop
数字最后要到 $2$
因为一开始是排列, 所以考虑不断利用初始序列压缩初始序列的值域并始终保持互不相同的性质.
那么第一次只知道自己和右边, 要求一个函数满足 $f(u, v)\ne f(v, w)$, 那么一个方法是 $u, v$ lcp后第一位是几以及lcp长度, 值域变成 $2\log v$
然后因为中午和晚上能同时看到两边, 所以可以做两次, 就是 $v\to f(f(u, v), f(v, w))$
然后这样的话这个 $2$ 不够优秀, 考虑怎么不乘 $2$, 考虑使用lowbit为长度一半的二进制来编码, 那么因为没有两个不同的数互相包含, 所以可以直接记录第一个 $u=1, v=0$ 的位置, 此时中午结束后答案到 $0\ldots 3$
那么为了压成 $0\ldots 2$, 直接对当前位分类讨论, 如果当前位是 $0, 1, 2$ 不管, 如果是 $3$, 那么两边一定是 $0, 1, 2$ 中的, 所以选剩下的一个就做完了.
Day3
Contest
T1
CF37E. Trial for Chief, 在greedy里写过
T2
维护 $n$ 个集合的序列 $s_n$, 每次给区间的集合都加一个数, 或者询问区间中集合最大的mex.
考虑mex需要底下的全都出现过, 可以转化成没出现过的”空”的最小值.
先上一个颜色段均摊, 然后保证了删除一个空时所有集合都有这个空, 插入时都没有这个空.
然后上线段树套平衡树+标记永久化, 每个点开一个堆表示所有完整覆盖了的被插入的空, 于是一个点的集合的并的mex是它到根的路径上所有空的最小值, 而答案是它下面的所有叶子到根的路径上的空的最小值的最大值, 那么开一个mx表示以自己为根的答案, pushup时把两个子节点的mx取max, 然后再对自己的集合取min即可.
复杂度2log.
T3
有 $n$ 个数, 每次可以擦掉两个和为偶数的数, 写上它们的平均数, 问最后是否能变成一个数. 构造方案.
考虑对 $\bmod 4$ 余数分类, 那么如果全是偶数, 只要把所有余 $2$ 的余 $4$ 的内部合并掉, 最后合一次即可. 当然全是奇数一样做, 然后结论是如果 $1$ 类 $3$ 类均多于 $1$ 或者 $2$ 和 $4$ 类均多于 $1$.
然后如果 $1, 3$ 中只有 $1$ 个有肯定寄了, 如果 $2, 4$ 有一个就找到最低的二进制位不全相同的位, 找两个不同的取平均一定会得到在下一位不同的, 重复即可.
Class
Eulerian
给定 $n$ 个点的图, 可以 $60$ 次问一个点集的点的导出子图边数, 判断图是否有欧拉回路.
看是否有点度数是奇数, 可以先问总点数, 然后问除了一个点的可以得到一个点的度数.
把点随机分两部分, 则总的减去两部分自己的就会得到两部分之间边的数量, 而它也就是一侧点的度数和的奇偶性, 因为对于所有的奇度点, 有 $\dfrac{1}{2}$ 的概率有一半分到奇数个, 所以一次成功概率为 $\dfrac{1}{2}$, 你可以进行最多29次, 十分正确.
Multiple Communications
Mapa
通信题, A收到 $100$ 组 $10^9$ 的 $G_x=y$, 可以传给B $3000bit$ 的信息, 然后 $Q$ 次询问B $G_x$ 的值.
在模 $10^9$ 之下把 $G(x)$ 看成 $n-1$ 次多项式, 然后拉格朗日插值出来把系数传过去.
琪露诺的符卡交换
$n$ 个人, 每个人有 $n$ 种卡, 每种卡有 $n$ 张, 然后进行交换使得每个人拿到所有种类卡片各一张, 每张卡只能被交换一次, 求方案.
发现写成 $a_{i, j}$ 表示 $i$ 人第 $j$ 个球的种数, 那么可以通过简单方案把 $a$ 转置($i$ 人 $j$ 球与 $j$ 人 $i$ 球换. )
然后只要重排 $a$ 的每一行让每一列互不相同, 这个是可以的因为考虑人向球连边形成二分图, 则是 $n$ 正则图, 你可以找出 $n$ 个完美匹配
Trokuti
先解方程得到 $5$ 个点的关系.
然后开始每次加入一个点, 询问 $u$ 和 $a_1, a_2$, 减去 $a_1, a_2$ 之间的得到这个点和 $a_1, a_2$ 之间的, 如果是 $0, 2$ 则直接确定了, 否则一定一条连一条不连, 否则再问 $u, a_2, a_3$, 每次有 $\dfrac{1}{2}$ 的概率解出来, 复杂度正确, 那么到最后因为中间间隔相连, 所以直接看 $u, a_1, a_3$ 就确定了. 因为每回合有分别 $\dfrac{1}{2}$ 概率确定 $1$ 条边或 $2$ 条边, 所以期望一次问出 $1. 5$ 条边, 十分正确.
Captivating process
给定序列 $f_n, g_n$, 对每个 $x, y$ 求 $f^{(k)}(x)=g^{(k)}(y)$, 多组询问.
首先这是内向基环树森林, 分类讨论.
如果最后都没进环, 合法则当存在 $u$ 使得 ${dep_F}_u-{dep_F}_x={dep_G}_u-{dep_G}_y$, 等价于 $u$ 在两个图的深度差为 $x, y$ 的深度差, 这样直接塞到桶里, 然后又要满足 $u$ 是 $x$, $y$ 的祖先, 那么考虑dfs序就是二维数点.
如果都在环里, 可以先把 $x, y$ 相对入环点退深度步, 然后相当于两个点直接从环上走, 那么如果 $x$ 最终位移 $a$, $y$ 偏移 $b$, 当且仅当 $a-b=0 \pmod gcd(l_f, l_g)$, 其中 $l$ 是环长, 最终条件就是走到的点 $u$ 在两个环里分别和 $x, y$ 同环, 以及刚才的同余式, 都是精确相等的.
最后一个在环里一个在环外的也形式相同.
Stacking Up
你有一个空栈, 每次可以添加一个 $1$, 添加一个当前栈顶元素, 或合并栈顶的两个元素添加它们的和, 并给栈里其他元素都减 $1$.
首先容易编出一个基于倍增的造出任意数, 问题变成减的部分.
于是倒着往后往回把减去的都加回来即可.
Icy Itinerary
增量构造, 对于已经有的链 $a\to b$ 维护分界点 $u$, 然后新添加一个点的时候考虑它连接到分界点的边是否存在, 再根据它前/后那条边是否存在移动分界点.
南京原神题
给定 $n\times m$ 矩阵 $A$, 你可以交换相邻元素, 旋转相邻 $2\times 2$ 的矩阵, 或者把 $k$ 个给定的若干个模板子矩阵粘贴到原矩阵任意位置.
可以认为没有步数无限
$n, m\le 20, k\le 40$
因为任意交换, 所以旋转没用, 首先和位置有 $0$ 个关系, 只要考虑每个东西的数量对了就行.
然后你倒着做, 每次把若干个字符换成若干个通配符, 去操作一定更优, 你每次至少粘贴至少要干掉一个, 于是就没有任何问题了.
然后操作数随便成 $k$ 次用没用过的章和 $nm-k$ 次用用过的章, 其中没用过的章可能会引起 $nm$ 个移动, 用过的只引起 $1$ 个移动
南京不原神题
平面上一个正方形 $(0, 0, {10}^9, {10}^9)$, 要求找到 $k$ 个互不相交的锐角三角形且所有三角形的并是正方形.
$k\le 50$
先人类智慧画出 $k=8, 9, 10$ 的情况, 更大的直接对着一个三角形拆即可.
然后证明 $k\le 7$ 无解, 考虑点分成正方形角点 $4$ 个, 边点 $x$ 个, 空地点 $y$ 个三种, 分析他们至少在几个三角形里, 于是 $180k=4*90+180x+360y, 3k\ge 2\times 4+3x+5y$, 得到 $y\ge 2$, 又因为每个点至少是 $5$ 个锐角三角形顶点, 同时拥有这两个点的三角形最多有 $2$ 个, 于是至少有 $8$ 个.
Day4
Contest
T1
给定 $n$ 点无向有权基环树, $m$ 次操作为修改一条边边权, 或者询问 $k$ 次把一条边加 $1$ 后最大的 $s$, 其中 $s$ 为最小的两个点之间最大流.
$n, m\le 5. 5\times 10^5$
注意到基环树, 问题解决. 树边和环边分别考虑, 注意到两个的答案都是 $k$ 的 $n$ 段一次函数, 一次函数是下凸的, 可以维护差分就成了区间加区间求和, 最后在数据结构上二分, 复杂度单log或2log(2log居然能过)
T2
给定 $n$ 点 $m$ 边有向带权图, 每条边权值为 $[l, r]$ 中任意一个数, 给定 $d_k$, 求所有情况下, 最大的 $i$ 使得 $d_1\ldots d_i$ 是 $1\to n$ 的最短路的一部分
$n, m\le 2\times 10^5$
dwt发现一个类似题是CF360E
首先每条边一定是 $l$ 或 $r$, 最短路的部分选 $l$, 其他地方选 $r$.
二分答案 $x$, $d_1$ 到 $d_x$ 的部分都取 $l$, 然后考虑点 $1$ 和点 $d_x$ 出发的两个人比赛到达 $n$, 最后是不是平局, 于是同时跑dij, 如果某个位置从 $d_x$ 出发的人先到或同时到就取 $l$, $1$ 先到就取 $r$ 看最后谁先到 $n$.
T3
$n\le 5\times 10^5$
考虑先求出所有 $(a, b, c, d)$ 表示一个人的移动范围为 $b, c$, 删掉左右的墙后为 $(a, c), (b, d)$. 于是按照纵坐标扫描线, 维护墙和竖线的交点, $(a, b, c, d)$ 就是相邻四个点, 直接插入删除时计算, 总数 $8n$(插入删除分别 $4$ 个)
然后考虑dp, 如果两个人能同时选当且仅当 $(b, c)$ 不交, 并且 $a, d$ 伸不进去, 那么按照 $a$ 排序, 就要找 $d_i<b, c_i<a$ 的部分中最小值转移, 简单数点1log
Class
ABC 306 Ex
关系建图, 等号变成一个连通块, 然后对连通块们求拓扑序数量, 那么可能算重是因为如果两个块都没有入度他们谁在前应该是一样的, 于是dp时每次枚举一个度数为 $0$ 的集合 $S$ 一起算, 但是钦定了这些入度为 $0$ 可能还有其他的, 所以容斥, 钦定 $T$ 的部分入度也为 $0$, 容斥系数是 $\vert T\vert$, 那么枚举 $C=S+T$, 则最后容斥系数是 $\sum_i \binom {\vert C\vert}{i}{-1}^i=(-1)^{\vert C\vert -1}$
但还留下一个问题, 因为有等号, 所以我们不知道一开始的连通块都长什么样, 但是这是没有关系的, 就是dp相当于每次钦点一些连通块, 那直接钦定选定的连通块内全是等号, 那些这里不是等号的部分会在钦点更小的连通块的时候计算, 而容斥系数按照连通块个数计算即可.
然后每次枚举入度为 $0$ 的dp即可. 复杂度 $3^n$
CF1081G Mergesort Strikes Back
求一个随机序列进行 $k$ 层归并排序后逆序对期望, 其中进行 $k$ 层指当递归深度为 $k$ 时直接输出原序列对应区间的归并排序.
大家都知道归并排序不改变前缀max, 然后不会了
哦, 实际上, 更厉害的是根据前缀max划分后段, 则段内顺序不变
对逆序对计数, 考虑 $x, y$ 形成逆序对的概率, 一开始在同一段的两个数概率是 $0. 5$, 否则和区间长度 $a, b$ 有关, 考虑 $a, b$ 一共只有两种取值, 枚举 $a, b$, 枚举 $i, j$ 表示 $x, y$ 在这 $a, b$ 中的位置, 再考虑 $s_x, s_y$ 表示 $x, y$ 所在段的开头的前缀max, 容易发现要想形成逆序对, 要满足 $s_y>s_x>x>y$, 那么形成一棵树:
然后这两块就是 $x$ 和 $s_x$ 之间的 $i-2$ 或 $y$ 和 $s_y$ 之间的 $j-2$ 个数, 因为 $x$ 以后都不影响 $s_x$ 称为前缀最大值, 于是只要满足这些关系就可以了, 那么答案就是子树大小倒数乘积, 处理逆缘前缀和就能优化成只枚举一个.
No Zero-Sum Subsegment Ucup Stage 4 Ukraine (Anton Trygub), Problem N
容易想到转化成前缀和模型, 然后你的每次拐一下就不能经过了.
假设总和为正, 那么路径最多是下到 $0$ 下走一个谷, 拐到 $0$, 上到总和, 再走一个单峰, 此时这几部分能选的都很有限.
比如最后一段一定是一段 $+2$, 一个 $+-1$, 一串 $-2$, 可以枚举 $+2$ 的个数, 原问题 $(a, b, c, d)\to (a-i, b, c, d-i)$, 就只需要考虑前面的部分, 剩下的直接组合数, 复杂度是一次 $min(a, d)$(枚举 $i$)
然后因为只有 $a, b$ 再变, 带入式子发现你的组合数是定值, 关于枚举的 $i$ 讨论直接加起来
CF1525F Goblins And Gnomes
先考虑spj怎么写, $i$ 个人看交不交的方法可以是, 把每个点变成入点出点, 出入之间连边建成二分图, 那么覆盖数等于点数减去最大匹配.
于是每次要删一个点, 删掉以后最大匹配减 $1$ 或不变, 那么因为最大匹配等于最小点覆盖所以一定存在点可以降低 $1$, 直接暴力枚举跑网络流验证.
于是知道了每次该删什么, 剩下的部分dp即可.
CF1712F Triameter
设 $m_u$ 表示离 $u$ 最近的叶子的距离, 那么 $dis(u, v)=\min(m_u+m_v+x, dep_u+dep_v-2dep_{lca})$
考虑在lca处统计子树内的答案, 那么因为 $m_u<$ 子树高度, 所以长链剖分维护 $g_{u, i}$ 表示 $u$ 子树内 $m_v=i$ 的最深的 $u$ 并合并答案即可. 更新答案的时候只要每次去看答案能不能 $+1$, 均摊就是对的, 于是合并新子树时, 要查 $\min (i+j+x, g_{u, i}+g_{u, j}-2dep_u)$, 可以枚举轻子树里那个 $i$, 然后考虑 $j$, 因为 $g_u$ 是随 $j$ 单减的, 所以直接看 $ans-i-x$ 位置的 $j$ 能不能行即可.
Ucup Stage 16 Gomel (tourist), Problem G
峰表示调整法可以过
如果删一条边不产生孤立点且还满足叶子那个条件那就可以删边, 暴力删. 然后考虑删完了的形状.
一部分点会挂两个叶子称为 $A$ 类点, 剩下的称为 $B$ 类点, $B$ 点将 $A$ 点连起来. 一个 $B$ 一定连着两个 $A$. 那么让选了的贡献 $1$, 没选的贡献 $-1$, 最后要求绝对值不超过 $1$, 那么合并多个连通块显然, 考虑单个连通块. $A$ 点少于 $3$ 特盘掉.
增量构造每次加入一个 $u$, $u$ 的两个叶子和 $u$ 的关系肯定相反, 贡献和自身选不选相反, 考虑与 $u$ 相连的 $B$ 类点, 判断选的多还是不选的多, 去贡献少的那边, 相等的调总和, 而 $B$ 类如果连着的两个 $A$ 确定了那么一定可以把 $B$ 的贡献得到, 否则 $B$ 尽量去调总和.
Day5
Contest
T1
$n\le 2\times 10^6$
写了log结果寄了.
先考虑一对点的贡献, 那么注意到它们能到只要它们走到各自走到最近的 $S$ 中的点然后一步冲过去这样, 算出这个路径的长度设为 $l$, 假设它们需要拆 $l$ 个点中的一个就不能连通, 贡献就是
$$
\begin{gathered}
\sum_t \dfrac{\binom{n-l}{t}}{\binom{n}{t}}\
\dfrac{(n-l)! }{n! }\sum_t \dfrac{(n-t)! }{(n-l-t)! }
\end{gathered}
$$
注意到和式里面是 $l! \binom{n-t}{l}$ 于是上指标求和得到结果为 $\binom{n+1}{l+1}$ 就得到了. (对就是这里写了愚蠢的ntt)
然后要考虑怎么算每个 $l$ 有多少对点, 记 $p_i$ 表示 $i$ 向前(下标增加)的第一个 $S$ 点, $s_i$ 表示向后, 那么按照 $S$ 把序列分成块, 块内和相邻两块的可以直接算, 问题只剩下 $g(l)=\sum_{i<j} [p_i+s_j=l]$, 注意到满足限制的正好是不考虑下标限制的一半, 于是扔了下标限制.
块间的可以按块考虑, 发现对于块 $a, b$ 之间的贡献, $g(l)$ 关于 $l$ 的斜率是 $-1, 0, 1$ 的函数, 所以可以用二阶差分实现加法统计 $g$, 又因为所有块大小之和为 $n$, 本质不同的只有 $\sqrt n$ 种, 直接枚举就解决了.
T2
给定 $n$ 个点 $m+n$ 条边的图, $m$ 条边确定, 另外 $n$ 条边都连向点 $0$, 单点修改这 $n$ 条边的权值 $a_i$, 询问最小生成树.
$n, m\le 2\times 10^5$
一种暴力是线段树分治加lct
考虑先求出 $m$ 条边的mst, 其他都都没有用, 然后问题就是把mst划分成若干连通块, 每个连通块中最小的 $a_i$ 连向 $0$.
于是一种厉害的暴力是线段树分治, 用树剖维护.
然后更厉害的是这个连通块选 $a_i$ 写成树形dp, 然后线段树树剖或静态lct维护ddp.
std是考虑Kruskal重构树, 在重构树叶子序列建线段树, 每个节点记录 $f_{u, 0/1, 0/1}$ 表示 $l$ 所在连通块有没有连 $0$, $r$ 所在连通块有没有连 $r$, 合并时看 $mid$ 和 $mid+1$ 是否连到 $0$, 这是对的因为如果两个有一个不连 $0$ 就一定要选lca, 选了lca还不连通的方法只会更劣.
T3
$n, m\le 10^6, nm\le 10^6$
todo
Class
P4672
如果知道了一个对应点, 就可以知道所有叶子节点, 因为它们到这两个点距离相等. 找到叶子之后一起跳父亲可以对应出其他点.
找对应点可以考虑直接找一个环, 然后删掉环图变成若干连通块, 那么一个连通块与环的交点最多只有两个点, 它们一定对应.
最后如果没有环或者没有两个交点都是平凡情况.
P6935
网格没有边界
考虑没有bug的模式, 状态从 $P_0\to P_1$, 考虑由 $P_1$ 转化成 $P_0$, 注意到 $P_1$ 的外边缘一定比 $P_0$ 的外边缘大一圈, 那么就可以从一个角顺着推出整个 $P_0$, 可以用最后两列检验, 直到 $P_0$ 不合法(推出矛盾)
当有bug时, 考虑假设一个位置是bug, 把bug取反后推回去得到 $P_0$ 会导致周围 $3\times 3$ 出问题, 于是再回来会导致 $5\times 5$ 的格子和实际不同, 但实际上只翻了一个, 结论是bug位置实际只有唯一合法位置.
那么考虑推过来的时候, 假设碰到错误的位置, bug后的位置会间隔推对, 推错(相邻两个推错了会让下一个推对)因为我们有最后两个来检验所以一定能检验到错的, 于是找到第一行有错的即可. 然后同理可以找到第一列有错的, 确定bug的坐标, 不断重复往回退即可.
P8392 [BalticOI 2022 Day1] Uplifting Excursion
有 $2m+1$ 种物品, 重量分别为 $-m, -m+1, \ldots, m-1, m$. 重量为 $i$ 的物品有 $a_i$ 个.
你需要拿走若干物品, 使得这些物品重量之和恰好为 $l$. 在此基础上, 你需要拿尽可能多的物品.
问在物品重量之和恰好为 $l$ 的基础上, 你最多能拿多少物品.
$1\leq m \leq 300$, $-10^{18}\le l \le 10^{18}$, $0\le a_i\le 10^{12}$.
首先这题肯定要背包, 考虑怎么转化成值域对的背包.
方法是, 先强制全选, 如果和大于 $l$ 就往下不选一个最大的, 小于就不选一个最小的, 直到现在和 $s\in [l-m, l]$
然后直接dp, 但这里值域仍然不确定, 考虑一定可以调整增删物体的顺序使得始终有 $s\in [l-m, l+m]$, 而调整过程中不应该出现两次有同一个和: 这说明可以用更多的之前删掉的数替换掉现在存在的一部分, 但我们一开始一直在操作绝对值最大的, 所以和相等的情况这是不可能的, 因此状态最多有 $2m$ 个, 我们最多只会增删 $2m$ 次, 值域开 $m^2$ 即可.
P4737
先按最终局面算一个答案, 假设都是先插里面再插外面, 按照最后局面算每个连通块内的答案. 可以扫描线, 假设从右往左走, 碰到一个栅栏就二分出它纵坐标上到哪(把它下方比他出现晚的都删了), 扫到一个标记就给对应栅栏贡献.
但是考虑时间之后, 若两个栅栏 $i, j$ 满足 $x_i<x_j, y_i<y_j, i>j$, 也就是 $i$ 被 $j$ 包含且 $i$ 更晚插入.
那么每个栅栏向它右上方包含它的那个点连边形成一棵树, 如果不考虑 $i>j$ 显然一个点就加上他的子树, 现在有了这个限制则一个 $i$ 贡献到 $j$ 当且仅当 $i\to j$ 路径上都比 $i$ 出现的早, 发现贡献是连通块, 可以用并查集维护.
CF1616G Just Add an Edge
给定一个 DAG, 边一定从编号小的点连向编号大的点, 求有多少对 $(x, y)$ 使得 $x>y$ 且添加 $(x, y)$ 这条边后的图存在哈密顿路径.
$n, m\le 1. 5e4$
考虑哈密顿路一定是 $1\ldots x-1 \Longrightarrow y \to x\Longrightarrow y+1\ldots n$, 那么问题就是中间这一段, 考虑dp, 要找到 $(x, y)$ 使得 $x-1\to y$ 和 $y+1\Longrightarrow x$ 是两条互补的路径. 那考虑dp, $f_{i, 0/1}$ 表示两条路径终点是 $i, i+1$ 或 $i+1, i$ 是否可行, 转移就是考虑一定是一条路径一个一个走, 另一个一下跳过来, 这样需要枚举起点复杂度 $nm$.
考虑优化掉枚举起点, 注意到如果 $i\to i+1$ 没有边, 那么两条路径一定要停留在这段点, 就可以以这两个点开始向前, 向后做刚才的dp, 然后直接乘起来两边选 $x$, $y$ 的方案. $x$, $y$ 在同一边的方案不存在因为无法跨过这个坎.
P3266
没讲
CF1110G
后手不可能赢, 只要看会不会平局.
容易发现如果没有白点, 容易发现存在度数大于 $3$ 的点, 或者度数等于 $3$ 且有两个分支链长大于 $2$, 先手必胜. 其他情况, 也就只有一条链的端点处可以再挂成3度点的情况可以是平局. 但是, 如果存在两个三度点, 中间链长是奇数则Alice仍然胜利.
然后有了白点.
发现一个三度点, Alice只要点三度点的在链上的相邻点, 那么Bob一定走那个三度点, 也就相当于白送给Alice点的这个点, 于是当有白点的时候, 可以把所有白点都替换成这个结构, 然后直接按没有白点判断即可.
P7070 [NWRRC2014] Kebab House
考虑分段dp, 设 $f_{i, j}$ 表示第 $i$ 段结束, 还要再填 $j$ 个 $1$ 才能填 $0$ 的方案数, 然后考虑转移. 那么容易发现 $f_{i}\to f_{i+1}$ 是一个线性转移, 乘上一个 $t\times t$ 矩阵, 直接考虑矩阵的系数: $a_{i, j}$ 表示的是开头先填 $i$ 个 $1$, $j>0$ 时末尾 $t-j$ 位置是 $0$ 后面是 $1$, 否则后面是一串 $1$ 随便.
先考虑 $j>0$, 那就是这一段, 前后已经确定, 中间要在若干个 $0$ 之间插入若干个 $1$ 使得两个 $0$ 之间至少有 $t$ 个, 这个就简单隔板法, 有, 同时加上一种前面全填 $1$ 一直到这的方案 $[i-j=q]$.
然后 $j=0$ 相当于对所有 $j<0$ 求和, 就是刚才的式子再加一个求和.
现在复杂度是 $nt^2$ 再乘上枚举 $01$ 数量的 $\dfrac{q}{t}$, 考虑优化, 注意到实际上刚才推出的式子只和 $i-j$ 有关, 然后 $j=0$ 的只有 $t$ 个, 于是复杂度成了 $q+t^2$, 总的是 $nt^2+\sum q_i$
Day6
Contest
T1
容易发现四边形不等式, 那么一个简单方法是wqs二分, 内层dp直接考虑每个点开始and和or最多变 $\log V$ 次, 又因为发现这个权值是单调的, 越长越大, 所以转移点直接就知道了, 复杂度 $\log^2 V$
然后因为决策单调性, 二分栈可以优化到单log.
T2
考虑直接把式子拆开:
$$
1+\dfrac{\sum_{i\ne j} w_iw_jt_{i, j}}{\sum {w_i}^2t_{i, i}}
$$
然后二分答案, 把答案乘过去拿回来, 就成了
$$
\sum_{i\ne j}w_iw_jt_{i, j}-ans\sum_i w_i^2 t_{i, i}>0
$$
然后这个可以建模成最大权闭合子图, 网络流.
嗯, 赛时退火初始化解初始错了, 改过来就能过. 退火感觉初始解还是随机好()
T3
首先双向奔赴的都可以不管, 它们一定会互相选到, 考虑剩下的部分.
考虑一个点成功邀请 $a_i$ 的概率, 那么要满足 $a_i$ 匹配失败, $a_i$ 在他前面, 并且其他会匹配 $a_i$ 的不在 $i, a_i$ 之间. 那就又要求 $a_i$ 匹配成功的概率, 就递归了. 但不要放弃, 考虑不管递归下去, 因为 $i\to a_i$ 构成内向基环树, 所以它会走成一个ρ形, 考虑设为 $x_1\ldots x_c, x_{c+1}\ldots x_d$, $a_{x_d}=x_c$ 这样, 设那些会插在 $x_i, x_{i+1}$ 之间的元素集合为 $b_i$, 显然 $b_i$ 互不相交, 不包含 $x$ 中的值, 答案只和 $b_i$ 集合大小有关.
然后怎么dp啊, 完全没懂todo
Class
CF364D
随机一个数答案有一半概率是其因子, 那么暴力check复杂度好像爆炸了.
不能暴力check, 假设随到 $x$, 直接把所有数和 $x$ 取gcd, 然后在用高维前缀和求每个因数的倍数个数.
AGC028D
首先环上等价于随意断掉, 环上相交等价于序列上区间相交(不包括包含).
考虑一个区间的最外边界 $[l, r]$ 出现次数, 显然区间外不能匹配外面的. 设 $g_x$ 表示 $x$ 个点任意连的方案数, 但保证 $l, r$ 连通是困难的, 钦定 $l$ 最大连通到 $k$, 容斥得 $f_{l, r}=g_{r-l+1}-\sum_i f_{i, k}\times g_{j-k}$
CF542E
你随便玩玩得到奇环一定不行, 那么显然二分图一定可以. 树的答案显然是直径.
猜一手图的直径, 然后把直径作为一条链拉出来, 考虑bfs树, 因为二分图所以同一层点一定不相邻, 每层之间随便合最后就是一条链. 然后因为删除一个点直径肯定不会变大所以确实是上界, 也可以考虑bfs树到叶子之后就没法往回走了.
CF566E
考虑两个点距离为 $3$ 则交只有中间的两个点, 这样能找出好多边, 只剩下叶子连向父亲的边.
然后相同点集都是兄弟叶子. 又因为一个叶子集合去掉父亲大小为 $1$ 的邻域, 去掉兄弟叶子就是父亲, 而除了叶子剩下点数不低于 $3$ 的时候, 每个点大小为 $1$ 的邻域不同, 但当只有 $2$ 的时候就是两个菊花连在一起特判就好了.
bitset可以优化掉一个 $w$
P6961
考虑钦定第 $k$ 大为 $w$, 把小于 $w$ 的设边为 $0$, 更大的设为 $w$, 让答案是 $dis_n+kw$.
发现如果 $w$ 比第 $k$ 大大那么 $w$ 加多了, 比第 $k$ 大小则消成 $0$ 的不够, 所以都是算大了, 所以就做完了.
P3771
先把直径拉出来, 变成一条链下面挂着若干子树, 显然不会选一棵子树内的点, 那么发现如果一个端点在子树内, 那么把它移动到父亲一定不劣, 因为只有子树底下的距离变大了, 但直径端点一定比这个子树最大深度大, 所以得到结论, 选的两个点都在直径上.
然后考虑二分答案, 设 $d_i, l_i$ 表示从点 $i$ 伸出去的子树最大深度和从直径一端到它的距离, 设我们连起来了 $a, b$, 那么对于任意 $d_i+d_j+l_i-l_j>ans$ 要满足 $\vert l_i-l_a\vert +\vert l_j-l_b\vert +d_i+d_j\le ans$, 直接拆开绝对值成四个式子, 然后 $i, j$ 搞到一边, $a, b$ 搞到一边, 枚举 $i$ 求一边的四个最值, 然后因为对于一个 $a$, $b$ 一定是一个区间, 直接看四个式子求出的四个区间有没有交即可.
复杂度2log
Astral Birth
有若干段 $0$ 有贡献, 若干段 $1$ 有贡献, 但有一段两个都有贡献, 那就再多分一段, 于是都只有一种数有贡献.
可以把原序列连续的 $01$ 缩起来. 那么把选择变成删除, 注意到如果一次删了相邻两个元素, 一定不如单选, 而对段数的贡献相等, 于是问题变成了从序列上选若干个元素删除, 位置不相邻, 选边上代价为 $1$, 中间权值为 $2$, 求代价为 $m$ 情况下的权值最小值.
另一种做法是考虑实际上是做背包, whq说考虑 $f_{l, r, 0/1, 0/1}$ 表示区间 $[l, r]$ 中左右端点选不选的答案多项式, 用闵和线性合并, 复杂度单log. 但没听懂todo
Day7
Contest
T1
简单题, 平衡树模板.
T2
考虑如果已经知道度数为 $1$, $n-2$, $2$ 的都是简单的, 对于 $u\to v\to w\to everything$, 如果知道了 $u, v, w$ 中任意一个都可以瞬间 $3n$ 验证.
考虑现在找到一个度数 $d\in [3, n-3]$ 的点, 考虑设 $S$ 为 $u, v$ 可能存在的点, $T$ 为 $w$ 可能存在的点, 让与一开始随便选的点与它相连的放进 $T$, 不相连的防到 $S$, 那么任取两个集合中各一个点 $u\in S, v\in T$, 查 $u\to v$, 那么如果有边可以从 $S$ 中删掉 $u$, 如果没有边, 考虑再选 $u’\in S$, 如果 $u’\to v$ 有边删掉 $u’$, 否则因为 $v$ 和他俩都没有边, 那么可以从 $T$ 中删掉 $v$.
于是可以用最多 $2$ 次询问从 $u/v$ 中删掉一个点, 那么用 $2n$ 次就能找到一个 $u, v, w$ 中的, 可以通过.
T3
P9109
todo
Class
萌萌哒
在ds里
P5605
$m$ 是 $p_m$ 保证存在原根, 于是 $x=g^a, y=g^b$ q, 求 $ak=b\pmod \varphi(m)$, 也就是 $gcd(\varphi(m))\vert b$
回去补原根和阶
LOJ2476
不会
[SCOI2010]连续攻击游戏
终于有阳间题了.
容易想到 $a_i, b_i$ 连一条边, 要定向让每个点至少有一个入度, 那么小于答案的边构成的连通块只要不是树就有解.
Ynoi2012 文化课
首先正常的维护线段树和, 积, 答案, 左右端点所在的段的乘积, 长度.
因为有改数所以要维护节点多项式, 但注意到次数是连乘段的长度, 因为总和是 $n$ 所以自然根号次数只有 $\sqrt n$ 种, 直接对每个点维护 $\sqrt n$ 项的多项式就行吧. 多项式求值直接快速幂增量是对的, 光速幂也是对的.
然后因为线段树区间长度每次除 $2$ 所以复杂度其实只有 $n\sqrt n$ 而没有log.
[HEOI2013] SAO
容斥成都是一个方向号+然后带着系数dp, 然后别忘了外向树拓扑序答案应该是先选父亲剩下随意, 答案是 $n! \prod_u \dfrac{1}{siz_u}$
反回文串
考虑对于一个回文串数能转出多少个不同的串, 容易发现如果如果它能转出回文串一定说明有一个不是 $n$ 的周期. 但是偶数移动 $n/2$ 是一个回文.
那么考虑把所有回文串都拆成小的, 设 $g_i$ 长 $i$ 的回文串数量, $f_i$ 是最小正周期为 $i$ 的数量, 发现 $f_i=g_i*1$, 于是上一个莫反就能求出 $f$, 然后问题就解决了.
趣味题
这谁想得到啊
先把箱子随机排序, 然后开到 $x$ 就去开 $x$ 号箱子, 这样失败条件是排成排列之后存在一个长度大于一半的环, 概率算出来趋近于 $ln2$
