FireInIce's Blog

几个组合构造的证明有人问无标号海胆计数,然后大喊CYC构造,然后发现大家都把各种构造是啥忘了. 设$A(x)=\sum_i a_ix^i$是我们要构造的东西 可重集构造MSETEI在WC上讲过,MSET是这样的:$$\begin{gathered} \mathrm{MSET} A(x)=\prod (\dfrac{1}{1-x^i})^{a_i}\ =\exp \sum_i -a_i\ln (1-x^i)\ =\exp \sum_i a_i \sum_{j=1} \dfrac{x^{ij}}{j}\ =\exp \sum_{i=1} \dfrac{A(x^i)}{i}\end{gathered}\$$ 幂集构造PSET类比MSET,写式子,求ln,展开ln,交换求和号. $$\begin{gathered} \mathrm{PSET} A(x)=\prod_i (1+x^i)^{a_i}\ =\exp \sum_i a_i \ln (1+x^i)\ &#x ...

Day 1模拟赛AQoj4907 djq 学生物 容易想到一张图,然后邻接矩阵的幂,然后要求$\sum_i M^i=\dfrac{1}{1-M}$. 然后容易想到换成”排列幂级数”多项式,转移多项式$F(x)=\sum_p c_p x^p$,$p$为一个排列,$x^p\cdot x^q=x^{p\circ q}$,要求$\sum_i F(x)^i=\dfrac{1}{1-F}$,就是要给这个东西求逆.容易发现若答案存在逆一定存在. 因为每一位分别做,容易想到类似FWT的形式,回想 “FWT本质” 类似物,比如试着找矩阵$C$使得$C_{i,j}$为$i\to j$的贡献,然后变换完之后点积就对应卷积.但是这里不适用(找不到合法的$C$).$p\circ q$不交换本身性质不好,拆成三个矩阵也是未知数少于方程数的. 然后感觉这里见识到更本质的FWT,我们实际上是在找可逆线性变换$T$使得$T(a)\cdot T(b)=T(a\times b)$,$T$把数变换到矩阵也是合法的.用矩阵强行模拟$S_3$的结构,构造出 $$M_{123}&# ...

2024NOI准备[ABC225H] Social Distance 2考虑 $k$ 个确定的人把问题分成若干长度固定的段, 设长 $l$ 的段内有 $j$ 个人的贡献和是 $f_{l, j}$, 则 $[x^{m-k}] \prod_{l\in S} \sum_j f_{l, j}x^j$ 即为答案. 考虑 $f_{l, j}$ 怎么求, 显然相当于 $j+1$ 段, 和为 $l+1$, 求每段长度乘积的和, 这个是经典的, 一段的贡献显然是 $\dfrac{x}{(1-x)^2}$, 于是总贡献是 $\dfrac{x^{j+1}}{(1-x)^{2j+2}}=\binom{l+j+1}{l-j}$ 即可. 然后两端点的段要特殊处理(不含第一段的贡献), 方法一样. [ARC101F] Robots and Exits容易发现洞把序列分成若干段, 对于任意一段其一定是左边的点从左边出右边的点从右边出, 所以其实相当于数合法 $01$ 序列, $0$ 表示某个机器人从左边出 $1$ 表示从右边出. 然后考虑段间的限制, 设 $i$ 到左右出口的距离分别为 $l_i, r_i$ ...

APIO2024Day1-概率论AGC060C考虑拿出最左边和最右边两条链共 $2(n-1)$ 个点, 归并它们, 然后以钦定顺序得到一棵新树(合并成一条链), 于是设 $f_{i, j}$ 为左边链到第 $i$ 个右边到第 $j$ 个答案, 看起来贡献计算简单. 复杂度 $n^2$. Pro数据范围都是 $10^7$ 首先原问题你直接就会了, 枚举最大值个数和最大值的值然后上一个二项式反演. 但是重点是怎么处理从最大值中等概率选一个这件事, 设最大值位置随机选一个选到 $1$, 问题相当于算 $\dfrac{P(x=1, a_1\ge r, sum_i a_i=s)}{P(a_1\ge r, sum_i=s)}=\dfrac{P(x=1, \max a_i\ge r, sum_i a_i=s)}{P(a_1\ge r, sum_i=s)}$, 发现此时分子对每个元素是等价的, 于是直接分子等于 $\dfrac{1}{p}P(\max a_i\ge r, \sum_i a_i=s)$, 剩下部分简单线性. ...

二轮省集Day1模拟赛A. 数 $1\ldots 10^L$ 内有多少个数满足, 通过每次删三个连续且相同的数位可以删空($\texttt{011100}\to \texttt{000}$) $L\le 10^7$ 提前几个观察: 前导 $0$ 不重要, 只要不管然后乘 $\dfrac{9}{10}$ 即可. 考虑建树, 容易发现对于一个序列, 可以建一棵树, 每三个匹配的作为一个节点, 两个空隙往下连儿子, 于是设树的GF是 $T(x)$, 最后长恰好 $3n$ 的串个数就是 $[x^n]\dfrac{1}{1-10T(x)}$, 答案就是 $[x^n]\dfrac{9}{10(1-x)}\dfrac{1}{1-10T(x)}$, 显然有 $T(x)=\dfrac{x}{(1-9T(x))^2}$, 于是想到设 $T$ 的复合逆是 $R(x)$, 代入得 $x=\dfrac{R(x)}{(1-9T(x))^2}$, 拉反有 $[x^n]T(x)=\dfrac{1}{n}[x^{n-1}]\left(\dfrac{x}{R(x)}\right)^n&#x ...

一轮省集Day1, 2模拟赛fibonacci串 $n=\vert t\vert\le 1. 5\times 10^5$ 首先考虑不存在连续三个字符相同, 答案长度是 $O(n)$ 的. 再考虑超过 $\vert s\vert$ 超过答案长度后后面的都是重复, 所以合理的 $\vert s\vert$ 也是 $O(n)$ 的. 对斐波那契串这个递归结构应该想到建树, 对 $s_n$ 中间切一刀连向两个子节点, 树高是 $\log n$ 的, 于是像线段树一样任意一个区间可以拆成 $\log n$ 个完整的 $s_k$ 相拼 考虑枚举起点的话, 我们需要能 $\log n$ 找到对应终点, 也就是 $O(1)$ 跳一个完整的 $s_k$, 则预处理 $f_{i, j}$ 表示从 $t_j$ 开始完整匹配过一个 $s_i$ 能匹配多少即可. 复杂度 $n\log n$ 水龙头 $n\le 5\times 10^5$ 考虑期望的线性性, 则期望值是每个水龙头被打开的概率和. 另外容易想到建图, 每个点向两个下方的点连边. 则一个点被打开当且仅当自己在所有前驱之前, ...

Top Tree

NOIWC2024Day1-lxl基础知识部分持久化, 完全持久化, 可合并的持久化: 只能在最后一个版本改/可以在任意版本改/可以合并历史版本, 版本之间连有向边分别是链, 树, 图 离线建操作树可以解决完全持久化 实现可持久化的三种方式: 路径复制, 肥节点和节点分裂. 设修改和查询次数分别为 $m_1$ 和 $m_2$ 路径复制类似主席树状物可以支持可合并的持久化 肥节点对每个节点用可持久化数组记录不同时间的版本, 查询时在这个节点的版本序列上二分, 可以实现部分可持久化, veb可以平衡到 $(m_1, m_2)\log \log m_1$ 对于完全可持久化, 考虑版本树的括号序, 相当于可以插入一对括号和在括号序列上二分, 查询某个版本的值这三个操作, 因为有二分要求插入log查询 $O(1)$, 方法是开重量平衡树(深度 $\log n$, 每次调整 $\log n$ 个点), 每个点维护值域区间, 父亲区间 $[l, r]$ 则两个儿子分别是 $[l, mid]$ 和 $[mid+1, r]$, 另一个点的标号为 $\dfrac{l+r}{2}$, 则 ...

THUWCDay1T1 有 $n$ 个人, $m$ 个任务, 第 $i$ 个人完成第 $j$ 个任务的收益是 $a_{i, j}$, 雇佣第 $i$ 个人的代价是 $c_i$, 一个人可以完成多个任务, 雇佣代价不重复计算, 最大化收益减代价. $n\le 15, m\le 3000$ 最显然的暴力是 $f_{i, S}$ 表示前 $i$ 个人, $S$ 中任务要被完成的最大收益, 复杂度 $nm2^n$, 过不了. 预处理 $g_S$ 表示一个人完成 $S$ 的任务的最大收益, 则答案就是 $g_S$ 子集卷积, 暴力 $3^n$ 就过了. T2 给定长 $n$ 的环 $a$, $m$ 次随机位置 $p\in [0, n]$ 和 $l\in [1, n]$, 把环上从 $p$ 开始的长 $l$ 的区间随机等概率重排, 求最后每个位置的期望.$n=2^k, k\le 17, m\le 10^9$ 容易发现相当于有固定的 $c_{i, j}$ 使得变换一次后的期望 $a’i=\sum_j a_j c{i, j}$, 而列 $c$ 的式子的时候容易发现其只和 $\m ...

省选准备?P3726 [AH2017/HNOI2017] 抛硬币要求 $$\sum_i \sum_j [j<i] \binom{a}{i}\binom{b}{j}$$ 这就不会了, 然而这是双射题, 考虑 $a=b$ 的时候赢的翻转能映输的, 就只需要求平局的 $\sum_i \binom{a}{i}^2$ 是经典问题. 现在 $a>b$, 设实际各证明 $x, y$ 次, 则 $a$ 输/平的翻转都会变成赢($x\le y, a-x>b-y$), 而问题就是A赢的可能仍然是赢, 这种情况要求 $a-x>b-y, x>y$, 于是 $x-y\in [0, a-b]$, 而 $a-b$ 很小, 枚举个差, 就是 $\sum_d \sum_i \binom{a}{i+d}\binom{b}{i}=\sum_d \sum_i \binom{a}{i+d}\binom{b}{b-i}=\sum_d \binom{a+b}{b+d}$ 暴力算就行了. 最后你需要用exlucas算组合数 P5279 [ZJOI2019 ...

转置原理其实两年前就集训听过了但是懂了0 向量用小写字母, 矩阵用大写字母 基本内容是对于一个问题给定 $v$ 计算 $vM$ 的问题, 考虑如果给定 $v$ 计算 $vM^T$ 的转置问题是容易的就可以直接改造出一个复杂度相同的算法计算原问题. 适用范围要求算法是线性的, 可以表示成上面的计算 $vM$ 的形式, 或者具体的对于输入的 $v$, 算法全程没有关于 $v$ 的判断类语句, 所有关于 $v$ 的运算都是赋值和线性运算. 改造一个非奇异矩阵 $M$ 可以拆成若干个初等矩阵的积 $M=E_1E_2\ldots E_k$, 则 $M^T=E_k^TE_{k-1}^k\ldots E_1^k$, 于是只要转置每一步并倒序算法. 对于不同的初等矩阵的转置($v$ 为输入向量, 其他均为常数): 交换 $v_i, v_j$: 不变 $v_i=cv_i$: 不变 $v_i=v_i+cv_j$: $v_j=v_j+cv_i$ $v_i=v_j$: 先拆成 $v_i=0v_i, v_i=v_i+v_j$, 于 ...

NOIP后南外省选集训NOI2024省选训练赛5A. 两棵树原题是BZOJ crash和陶陶的游戏 $n\le 10^5$ 考虑加入一个 $A$ 树的叶子对答案的贡献是 $B$ 中的祖孙链上的子串数, 更好的是 $A$ 这个叶子作为 $B$ 字典树上的后缀的个数, 加入 $B$ 的叶子相当于对 $A$ 的字典树的一条从根的链求和. 具体的考虑如何解决 $A$, 相当于求字典树的子串出现次数, 相当于阿狸的打字机带修. 或者考虑直接求出 $B$ 字典树上所有字符串的字典序排序, 这样包含一个串的一定是一个后缀, 就是区间问题了. 考虑如何解决 $B$, 需要先匹配一下 $B$ 这个叶子往上跳多远还在 $A$ 里, 然后随便求和. 于是可以维护出 $B$ 中每个点 $u$ 向上跳 $2^i$ 步的hash值, 这个可以同时用于求字典序排序和 $B$ 这个叶子往上跳多远的问题. B. 头文字 O 你在无限的数轴上从 $0$ 开始随机游走 $n$ 步, 每次位置 $+- 1$, 由 $m$ 个给定的区间, 若你的路径中存在一段以 $s_i$ 开头, $t_i$ 结尾则会获得 $v_i ...

文章太长, 拆出一个新的 NOIP后南外省选集训NOI2024省选模拟赛20A. 网络单纯形 给定连通无向图 $Graph(n, m)$, 边有边权 $w_i$, 点有颜色 $c_i$, $q$ 次修改一个点的颜色询问所有连通不同颜色点的边的边权最小值.$n, q\le 2\times 10^5$ 考虑两个颜色的答案就是给定的两个集合间的最近的一条边, 那么这条边一定在最小生成树上. 用堆维护每个点的所有儿子的信息, 修改时更新父亲节点的数据结构即可. B. 原神账号 给定 $a_n$, $m$ 次询问第 $i$ 次给定 $k_i$ 个区间和 $k_i$ 个区间 $[l_j, r_j]$ 问区间并的颜色数. 强制在线. 空间8Mb. $n, \sum k, m\le 10^5$ 早上刚看了跳进兔子洞就开到这个题, 容易想到bitset, 问题变成如何在8Mb下提取区间bitset. 容易想到st表, 空间爆炸, 容易想到分块, 时间爆炸. 但是分块是可以调块长的! 设块长为 $B$, 每 $B$ 个分一块, 块间st表, 空间时间都是 $\dfrac{n^2}{Bw}\log \d ...

THUPC2024 邮寄和Mikefeng和Harry23182组队, 来看看往年题. THUPC2023 PreP9140 [THUPC 2023 初赛] 背包因为 $V$ 远大于 $v_i$ 和 $n$, 所以考虑贪心, 选出其中性价比最高的元素 $i$, 则就是要在模 $m=v_i$ 的意义下求恰好为 $V$ 的最大价值, 这个几乎是同余最短路, 因为此时总代价是 $\dfrac{V-v}{m}c_i + res$, 其中 $res$ 为选出的元素的 $c$ 之和, 所以实际上是最大化 $res-\dfrac{v}{m}c_i$, 于是同余最短路时先 $i\to j+v_i$ 连 $c_i-\dfrac{v_i+j}{m}c_i$ 的代价即可. 然后同余最短路实际上不用写最短路, 它是个模 $m$ 的完全背包问题, 加入物品时这个物品的转移形成 $gcd(m, v_i)$ 个环, 只要对每个环转移两圈即可保证转移完全. 复杂度 $nm$ P9143 [THUPC 2023 初赛] 众数从大到小排即可. P9134 [THUPC 2023 初赛] 拧螺丝老板肯定每次拿走最 ...

NOIP2023游记Day0试机看到do_while_trueand yyh, MLE, LgxTpre, modinte win7, 但有安了C++插件的vscode 但是1e8 rand 跑1. 5s的机子, 想起报数lcez机子线性过不去的故事. 打了ntt和sam Day1Before Contest看样例, 哟, 有字母? , 剩下三个看不出来是啥, tribool啥词不认识 During Contest吸取经验, 上来先喝咖啡. 先看T1, 这直接对字符串排序, 比最小次小就能过吧 看T2, 看起来模拟每个位置最后是一开始的什么, 然后并查集扩展域处理相等不等限制就行了 看T3, 没懂, 看起来让求若 $a_i>b_i$ 连边, 选出不相交的若干条每个点度数至少是 $1$, 一会再说. 看T4, $n\le 10^9$ 大概是离散化坐标, 像个dp. 开始写T1, 直接sort吧卡常了再搞桶, 0. 5s大样例, 相信lcez的机子, 开T2. 写T2, 开始脑子不对劲, ($a$ 数组是维护每个变量最后的值是哪个变量的初值)赋值 $a_x=y$, 没初始化 ...

又做了几个杂题CF1305F Kuroni and the Punishment 给定 $n$ 个数. 每次可以选择将一个数 $+1$ 或 $-1$ . 求至少多少次操作使得整个序列都是正数且全部元素的 $\gcd>1$ .$n\leq 2\times10^5, 1\le a_i\leq 10^{12}$ . 答案不超过 $n$(全调成偶数). 值域很大, 直接做要求一些 $\sum a_i\bmod g$ 状物, 是困难的, 考虑因为答案不超过 $n$, 那么至少有一半的数被操作至多一次, 于是随一个数, 再随一种操作, 它被这么操作的概率有 $\dfrac{1}{6}$, 随错了的是 $\dfrac{5}{6}$, 那么只要随比如 $50$ 组就行, 然后对着这些可能的操作分解质因数, 只对它们的约数作为gcd去求答案即可. 哦, 一直以为cf的possibilities都是概率期望题, 结果是随机化 CF605E Intergalaxy Trips $n$ 个点的有向完全图. $i \to j$ 的边每天出现的概率均为 $p_{i, j}$, 若 $i = j ...

CF1375E Inversion SwapSort 给定一个长度为 $n$ 的序列 $a$, 求 $a$ 中的所有逆序对 $(i_1, j_1), (i_2, j_2), \cdots, (i_m, j_m)$ 的一个排列 $p$,使得依次交换 $(a_{i_{p_1}}, a_{j_{p_1}}), (a_{i_{p_2}}, a_{j_{p_2}}), \cdots, (a_{i_{p_m}}, a_{j_{p_m}})$ 后序列单调不降.$1 \le n \le 10^3$, $1 \le a_i \le 10^9$. 感觉还可以. 不过大概是因为前两天那道ssfz友好联测的D. 因为这个你需对是跟一开始的值位置相关而不是跟某时刻的值相关, 从位置角度, 考虑先用所有和 $n$ 构成逆序对的东西把 $n$ 换到最后一位, 这个是简单的, 从小到大换和 $a_n$ 构成逆序对的即可, 发现这样的好处是前面的顺序不变. 于是可以递归下去. CF741C Arpa’s overnight party and Mehrdad’s silent entering 有 $2n$ 个人围成 ...

NOIP模拟赛44A. K 近查询 给定序列 $a_n$, 对每个 $k\le lim$ 求 $j$ 使得 $j$ 是 $j < i, a_j\ge a_i$ 中第 $k$ 大的. $n\le 10^7, lim=1$ 或 $n\le 3\times 10^6, lim=5$ 简单题, 对 $10^7$ 的部分直接单调栈, 对 $lim=5$ 的部分建出链表, 然后从小到大删元素并统计答案. B. 树上流水 给一棵 $n$ 个点的外向树, 根有无限水, 边有容量限制, 每秒可以把水延边推动, 求最少几秒使得叶子处总水量至少为 $K$.$K\le 10^9$, $n\le 1000$ 容易想到dp, 设 $f_{u, i}$ 表示点 $u$ 发出 $fw_u=w_{fa_u\to u}$ 的流量在 $i$ 秒后最多有多少到叶子, 转移大概是 $f_{u, i}=\min (\sum f_{v, i}, fw_u)$, 然后求出 $1$ 的就可以算答案了. 然而赛时一开始没看到 $n\le 1000$(它写 $\sum n\le ...

CSP2023游记文中杜赢指do_while_true. Day -n开始停课, 打了4场模拟赛, 第一场爆了一个标, 剩下的都挺寄. Day 0上午复习数位dp, 看以前的blog, 中午出发, 晚上到达日照一个民宿, 晚霞很好! 试机, 抽到win10. 发现虚拟机不能用, 说晚上解决. 机子上放了3个不同的mingw, 最后只有dev自带的那个能用. 但是机子配了vscode, 即使没有c++插件也是vscode, 即使没有虚拟机也是vscode. 最可惜的是没有python. 考试过程中习惯性拿python当计算器/暴力弹出的是微软商店. 面到杜赢, 他们机房虚拟机能用. 面到whc, 面到一个也来打比赛的初中同学. 晚上复习圆方树, 虚树, kmp. 没有python于是背了一个bat对拍板子. Day 1 比赛上午又看了看字符串打开知乎, 听说普及组某机房没断网(问号脸). 特意带了杯咖啡和零食, 切一个题吃一个. 提前30min左右进场, 配vscode, 打了空模板, 考场大概提前几分钟给了压缩包密码, 压缩包里看到名字”tree”打一个存树的模板, 看”st ...

Day1A. [21 ZR联赛集训 day1]数字变换 你有一个素数 $p$ 和二元组 $(a, b)$, 它们的和不被 $p$ 整除. 你想对这个二元组进行若干次操作, 让它变成另外一个二元组. 每一步, 你可以二元组做如下操作中的一个: 把 $(a, b)$ 变成 $(2a \mod p, (b+p-a) \mod p)$ 把 $(a, b)$ 变成 $((a+p-b) \mod p, 2b \mod p)$ 你需要回答 $q$ 次询问, 每次询问, 给你 $a_i, b_i, c_i, d_i$, 问最少需要多少步能将 $(a_i, b_i)$ 变成 $(c_i, d_i)$. 如果不可行, 那么输出 $-1$. 注意, 这里 $(a, b)$ 和 $(b, a)$ 是不同的. $2 \leq p \leq 10^9, 1 \leq q \leq 10^5, 0 \leq a_i, b_i, c_i, d_i < p$, 保证 $a_i + b_i \not\equiv 0 \pmod p, c_i + d_i \not\equiv 0 \pmod p$. 操作不 ...

DSCF1672H已收录 CF1290E大根笛卡尔树子树大小就是当前点作为最大值的区间, 于是想到逐个插入维护左右端点, 但相邻两个插入的元素之间未被插入元素多算的贡献是不好去除的, 所以需要插入的时候不是插入的原序列对应位置上而是无空隙紧挨着插入, 每次是区间取max/min和区间加. CF809DLIS两个主要做法分别是记录以某值结尾的最短长度和某长度对应的最小结尾. 此题一维表示当前前 $i$ 个数, 若第二维表示当前的值那么转移是跳跃的, 如果记录长度则是连续的. 于是 $f_{i, j}$ 表示前 $i$ 个, 长度为 $j$ 的结尾最小值, 那么显然 $$f_{i, j}=\max f_{i-1, j},\begin{cases} f_{i-1, j-1}+1, f_{i-1, j-1}+1\in [l_i, r_i]\ l_i, f_{i-1, j-1}+1<l_i\ inf, f_{i-1, j-1}+1>r_i\end{cases}$$ 显然 $f_i$ 是递增的, 考虑数据结构维护状态, 那么第二种转移显然就是直接区 ...

记录奇怪的思考 存在确定结果的游戏等价于决策透明, 于是可以等价于一个人提出一个策略另一方对着你的策略卡. 记录代码细节错误 noip2022 旅行: 手动实现矩阵乘法*=, 注意顺序, 可能要用旧的值更新而旧的被变了. csp2022 假期计划: 取max的初始值应设为-inf而不是0 csp2021 回文: 函数没有返回值, dev默认值为true(? ) P7916 区间dp时若转移到长度偶数则答案错的, 没有判 P7077 初始化问题 P7116 拉插次数没想清楚就往上试到不变化, 同时注意数组开小了 P5666 线段树合并怎么会有人想到写 $x&y==0$ 判断是否有一个是空? /fn, 动态开点编号多测没清空/fn P5021 multiset erase(iter)会删除一个元素, erase(value)会删除所有等于这个值的元素. P4606 圆方树点数最大是图的两倍, 点双弹栈连放点时不是”删到栈顶为 $u$”而是”直到把 $v$ 删掉”(指处理 $u\to v$ 这条边) nfls vector, deque pu ...

2023夏令营Day0垃圾山外宿舍6人 Day1ContestT1 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$ 或没有 ...

CF1827B Range Sorting 对一个数组 ${p_i}$ 的一段区间 $[l, r]$ 排序的代价为 $r-l$ , 对整个数组 $p_i$ 排序的代价为选定若干区间并排序, 使得整个数组有序的代价之和.求 ${a_i}$ 的所有子段排序的代价之和.$n\le 3\times 10^5$ 首先排序区间不交, 不然相交的用一个大的代替. 考虑贡献拆分到, 没有一个区间覆盖 $i, i+1$ 之间的间隔, 等价于 $\max p_{l: i}\le \min p_{i+1: r}$, 计数 $l, r$ 组数即可 直接枚举间隔+维护单调栈+双指针可以过 B1 考虑一个剪枝, 扫 $[i+1: ]$ 时若 $\min p_{i+1: j}<p_i$ 则显然可以跳, 复杂度可以考虑一个小根笛卡尔树, 在后半部分前缀min的单调栈上走相当于身为左儿子跳父亲. C Palindrome Partition 称一个字符串是好的, 当且仅当它是一个长度为偶数的回文串或由若干长度为偶数的回文串拼接而成. 给定一个长度为 $n$ 的字符串 $s$, 求有多少 $s$ 的子串是好的. ...

2023省队集训模拟赛Day3T1 给定 $n$ 点简单无向图, 对每对 $(x, y)$ 求是否有一条 $x$ 开始 $y$ 结束的哈密顿路. $n\le 24$ 注意到因为哈密顿路一定经过所有点, 所以对于 $x\to y$ 可以拆成 $1\to x, 1\to y$. 考虑求出 $f_S$ 表示经过 $S$ 能走到哪些点, 然后枚举每一个 $S$, 对于其中每一个 $x$, 考察 $f_{U/S}$ 是否包括 $y$, 复杂度是 $n2^n$. 至于如何求 $f_S$, 考虑每次对于 $f_S$, 轮流拿出其中的点扩展一个得到新的 $f$, 复杂度是 $n2^n$ 总复杂度 $n2^n$ T2 对于 $100%$ 的数据, $1 \leq n, q \leq 10^6$, $1 \leq l_i \leq n$, $1 \leq H, a_i \leq 10^{12}$, $1 \leq t_i \leq 3$. 相当于给了三种函数: $f(x)=\begin{cases}x-a_i, x\ge a_i\-inf, x<a_i\end{cas ...

2021省队集训-模拟Day1A. 数排列 给定 $n$, 和排列 $x_m$, 求有多少个排列 $a_n$ 满足 $x$ 为 $a$ 字典序最小的长 $m$ 的子序列.膜 $998244353$$m\le n\le 2. 5\times 10^5$ 开门降智 考虑 $x$ 为字典序最小的子序列的条件. 容易发现, 如果某个位置存在 $x_i\le x_{i-1}$, 那么可以选择 $x_{1\ldots i-2}, x_{i\ldots m}$ 以及再往后一个, 这种情况不行当且仅当剩下的位置不够多, 也就是 $x_i$ 的位置后面恰好全是 $x_i$ 往后的部分. 于是我们只需要解决对于一个递增的 $x$ 的问题去凑组合数, 考虑把 $x$ 放一排, 从小到大插空即可. 复杂度线性. B. 取石子游戏 Alice 和 Bob 在玩取石子游戏, 游戏规则是这样的: 游戏开始时在他们面前有若干堆石子, Alice 先手进行游戏, 两人轮流操作, 玩家每轮操作时可以选取一堆石子, 并从中至少取走 $1$ 颗石子, 可以把这堆石子取空, 如果某轮中某位玩家无法进行任何操作(即所有石子均被 ...

Problem ? 给定排列 $a_n$, 求 $\sum_i \sum_j gcd(i, j)gcd(a_i, a_j)$ $n\le 10^5$ $$\begin{gathered}\sum_i \sum_j gcd(i, j)gcd(a_i, a_j)\=\sum_i \sum_j \sum_{d|i, j} \varphi(d) \sum_{k|a_i, a_j} \varphi(k)\=\sum_d \varphi(d) \sum_k \varphi(k) (\sum_{d\vert i}[k\vert a_i])^2\end{gathered}$$ 设 $g(d, k)=\sum_{d\vert i}[k\vert a_i]$ 考虑一个 $(i, a_i)$ 对的贡献, 那么发现 $g$ 一共是 $\sum d(i) d(a_i)$, 又因为是排列, 于是这个就是 $\sum_i d^2(i)$, 据说是 $n\log^3 n$ 的. 那么你只枚举 $g$ 有值的 $i, j$ 就能做3log了. 简单想法是哈希表, 空间爆炸. 考虑逐个 $ ...

Day1 数据结构rprmq1分治+同一分治深度的一起处理+扫描线+区间历史最大值, 参见sdjx1 P8512 [Ynoi Easy Round 2021] TEST_152 转转有一个操作序列 $(l_i, r_i, v_i)$. 现在, 有 $q$ 个询问 $l$, $r$. 每次询问, 你初始有一个长度为 $m$ 的序列 $c$, 初值全是 $0$. 现在我们从 $l$ 到 $r$ 执行这 $r-l+1$ 个操作. 每个操作是将 $c[l_i]$ ~ $c[r_i]$ 赋值为 $v_i$. 询问所有操作结束后整个 $c$ 的序列所有数的和. 询问之间互相独立.$n, q\le 5\times 10^5$ 考虑扫描线, 看出扫序列没前途, 于是扫操作. 那么扫描操作维 $r$, 过程中珂朵莉树维护序列维, 并在珂朵莉树每个节点上维护其插入时间 $t$, 对某个 $r$, 每个节点的贡献就成了当 $l>t$ 时答案加上 $sum$. 注意此时珂朵莉树不会真删而是加入一个贡献 $-sum$ 的(理所当然) 于是在珂朵莉树维护的同时用一个树状数组维护在这个时刻后的连续段之和, ...

图论选做先开个坑. CF1687B Railway System [mst] [kru] 有一张图 $Graph(n, m)$ , 现在给定 $n, m$ , 要求你通过 $2m$ 次询问一个边集的最大生成树森林权值和, 得到整张图的最小生成树森林权值和. $n\le 200, m\le 500$ 最小生成树题基本模拟Kru或Br, 随便想想就知道不会是Br, 所以考虑Kru. 考虑从小往大加边, 那么一条边是否加入就直接判断已经得到的边集再加上这条边的最大生成树森林是不是原来的值加上这条边的边权, 如果是就加上, 否则说明它把另一条边顶下去了. 于是就先 $m$ 次问每一条的边权, 再 $m$ 次加边即可. 很套路. Gym102331F Fast Spanning Tree 给定 $n$ 点树, 点有点权边有边权, 用Kru求mst, 但每次是选择所有两端点不在同一个连通块中, 编号最小, 且两个连通块的点权和之和大于边权, 按顺序输出选择的边. $n, m\le 3\times 10^5$ 考虑如果限制是, 两边任意一个连通块的和大于边权的做法, 可以每个连通块开数据结构维护 ...

做ZR题触及了知识盲区() Prufer序列与Caylay定理不特殊说明均指有标号无根树. Prufer序列对于一个有标号无根树, 其prufer序列是, 每次删掉一个编号最小的叶子, 然后在序列上push_back这个叶子连向的点, 直到只有两个点. 于是Prufer序列的特征(不好意思叫性质): 长度是 $n-2$ . 最后留下的两个点中一个是Prufer序列上最后一个点, 另一个是 $n$ . 每个点出现次数为度数-1. 于是发现显然可以直接对着序列重建树, 倒着做就行, 所以它是有标号无根树与序列的双射. Caylay定理1. $n$ 个点构成的树的方案数为 $n^{n-2}$ .Prufer序列, 每个位置是在 $1\ldots n$ 中, 长 $n-2$ . 2. $n$ 个点, 和指定的 $k$ 个点, 做出 $k$ 棵树的森林使得 $k$ 个点都不在同一棵树立的方案树为 $kn^{n-k-1}$ .考虑不指定这 $k$ 个点, 而是直接算最后除以 $\binom{n}{k}$ , 那么为了保证每一个 $k$ 子集只被算了一次, 钦定这 $k$ 个点为其所在生成树的根 ...

ZROI2022Day122冲刺day1-匹配 给定 $n$ 个区间 $[l_i, r_i]$ , 两个区间之间的贡献是 $\max \vert a-b\vert , \ s. t. \ a\in [l_i, r_i], b\in [l_j, r_j]$ , 求把区间两两配对, 最大化贡献和. $n\le 10^6, l_i, r_i\le 10^9$ [trick] $\vert x-y\vert =\max x-y, y-x$ [think]见到绝对值想拆贡献 绝对值都拆开, 每个区间的贡献一定是最大值 $ma$ 或最小值 $-mn$, 那么先全选最大值减去最小的 $\dfrac{n}{2}$ 个 $ma+mn$. 22冲刺day1-狼人 给定一个 $n$ 个点的树, 点有颜色 $c_i$ , 求有多少个连通块有绝对众数, 绝对众数指出现次数大于一半的数.$n\le 3000, c_i\le n$ , 膜998244353 考虑一个连通块显然最多被一个颜色贡献. 那么对每个颜色计算连通块个数. 把当前颜色看成1, 其他颜色看成-1, 则相当于求有多少个和大于0的连通块 ...

21 BCT NOIP Day 1-2 暨<高龙强总结>登顶纪念赛[21 BCT NOIP Day 1-2] 宝石 (gem)智障题 [21 BCT NOIP Day 1-2] 小恐龙 (dino) 位置 $x$ 可以跳到 $x+1$ 或 $x+k$ , 若目标位置有障碍则不能跳, $q$ 次询问, 每次将一个格子变成障碍或者求恰好到第 $x$ 个格子的最小大跳(跳长 $k$ 的)次数. $n, q\le 2\times 10^5, k\in [\dfrac{n}{100}, n-1]$ 我天看错题了! 看这个 $k\ge \dfrac{n}{100}$ 的特殊含义. 考虑一个朴素dp, $f_i$ 表示跳到 $i$ 的次数. 那么 $f_i$ 总和是 $100n$ 的. 考虑把这个做为势能. 那倒着做, 一开始每个势能都当成 $101$ , 每次会让一个位置能用, 就暴力更新它能更新到的所有位置, 如果一个位置更新了就往下接着更新否则就停, 就做完了. [21 BCT NOIP Day 1-2] 序列 (sequence) 给定序列 $a_n$ , 对每个 $k\in ...

LYHDPslide. pptxday6那个做不动啊, 还是看看简单点的. CF1409F Subsetsequences of Length Two 给定 $s_n, t(\vert t\vert=2)$ , 可以修改 $s$ 的最多 $k$ 个字符使得 $t$ 作为子序列在 $s$ 中出现次数最大. $n\le 200$ $f_{i, j, k, l}$ 表示前 $i$ 个, 修改 $j$ 个, $t_1$ , $t_2$ 的个数分别为 $k, l$ 的 $t$ 出现次数. 哦, $t_1, t_2$ 只需要记录一个. CF1404B Tree Tag 给定一棵树 $T=Tree(n)$ , $AB$ 初始时在 $a, b$ 两点, 每次可以移动到距离不超过 $d_a, d_b$ 的点, 交替移动 $A$ 先手, 若 $A$ 能抓住 $B$ , $A$ 获胜. 问谁赢.$n\le 10^5$ . 考虑因为无限步数, 可以忽略前面过程, 直接想什么时候必然抓住: $A$ 站在直径中点上, $B$ 死了 $d_b\le 2d_a$ , 此时它不能跨过 $A$ ...

DFA最小化学习笔记定义DFA: 众所周知啊. DFA的等价类: 若DFA中两个节点相同字符的出边指向的节点属于同一等价类, 则它们是等价的. 算法简介大致原理是选择一个等价类 $A$ 作为”证据”, 若所有能到 $A$ 中的节点集合为 $X$ , 而存在等价类 $Y$ 满足 $X\cap Y\ne \varnothing, X/Y\ne \varnothing$ , 则可以把 $Y$ 划分成这两个部分. 于是算法流程就是初始化一个证据集合包含结束节点, 一个等价类, 每次取出一个证据, 然后执行上面的过程, 然后把它删了, 如果 $Y$ 在证据中就把 $Y$ 删了, 分成的两个部分, 否则加入两个部分中少的那一个, 直到证据集合为空. 复杂度是 $n\vert \sigma\vert \log n$ . 应用感觉主要用在dpofdp上, 因为本质相同的dfa最小化结果唯一, 就是说你内层dp的状态设计有很多种, 但最小化的结果应该是相同的. 会得到和你本质相同的所有dfa中最小的一个. 遇到这种题要大胆猜能用到的状态没看上去那么多.

随机化杂题[sdfzoj contest #1]记录 构造一个有向图满足其以1为根的内向生成树个数对 $10^18+3$ 取模为 $k$ .要求构造的有向图点数不超过100, 边数不超过 $3\times 10^5$ 首先众所周知的一个DAG的生成树个数是所有节点的入度的乘积. 那么要控制入度, 考虑直接让1到每个节点连一堆边就控制了入度, 所以现在问题是要选若干个数乘积在膜意义下等于 $k$ . 这个东西我们不会做, 可以智慧. 假设要等于一个数, 那么给2号点随机一个入度, 就直接给 $k$ 乘上一个逆元, 这很好因为你发现这样做把出题人精心构造的 $k$ 变成了近乎随机的. 那么现在你手里由一个随机的 $k$ , 于是接着随机每个节点的入度, 判断此时乘上一堆逆元之后的 $k$ 是否可以由小于某个阈值的质数表示, 如果随到最后还没弄出来就从头再来. 复杂度算不出来, 但qyc说他写出来之后只跑了1s多一点. 考虑剪枝, 考虑判断一个数是不是可以分解为小于某个数的质数这件事比较费时, 所以仅在它膜常数 $C$ 为0的时候去判断. 这样做相当于把值域缩小到 $\dfrac{1}{C ...

比赛记录已经不光是比赛了, 还有看的成套的题. 已经又都是比赛了, 成套的题移走了. ZSContest很久以前写下zscontest的编号. . . zs是什么啊? 是不是振声啊 A [博弈论] [打表] $n\times m$ 的网格上有若干硬币, 初始时全部为反, $q$ 次翻转一个矩形并询问, 若两人轮流操作, 每次先选择一枚正面硬币 $(x, y)$ , 再选择一个 $(a, y), a<x$ 或 $(x, b), b<y$ , 同时翻转这两个格子的硬币, 不能操作的人输, 是先手必胜还是后手必胜. $n, m\le 10^9, q\le 10^5$ 首先结论: 每一枚硬币是独立的. 这个操作实际上相当于硬币可以向左或向下移动若干步, 两枚硬币碰到一起就一起消失, 那么考虑假设硬币不会消失的情况和这个是等价的, 因为若选择移动多枚硬币位置相同, 后手仍然以相同方式移动这个位置到先手移动到的位置是不会让局面更优也不会更劣等, 所以是等价的. 于是每一枚硬币分别的SG值求出来异或, 打表SG值和其矩形前缀和找规律吧. B 有 $n$ 个数对 $(a, b)$ 构成 ...

Day1-Wyj模拟赛T1智障题 T2 给定 $a$ , 计数满足以下条件的排列个数: $b_1b_3<b_4\ldots$ $b_2<b_4<b_6\ldots$$n\le 5000$ 排列上的问题, 基本上只要 $n\ge 20$ 就是顺着值域扫了. 同时显然偶数位上的性质比奇数位上的好的多. 确定偶数位后, 对每一个奇数位, 它可以被插入在一个后缀里. 此时只看奇数位方案数 $\prod (c_i-i)$ 这样的. 考虑dp, $f_{i, j}$ 表示值域上前 $i$ 个数, 这 $i$ 个数中有 $j$ 个在偶数位上的方案数. 但这里要提前计算奇数位的费用. 转移就是考虑当前这一位选不选, 选就是 $f_{i-1, j-1}$ , 否则就直接 $f_{i-1, j}$ 再乘上这一个数作为奇数位上的贡献. 但现在相同数. 只要改一下转移: 枚举是否拿其中一个作为偶数位, 乘上剩下的数作为奇数位的一个下降幂贡献再除掉自己内部顺序. T3 求选树上点两条不相交链, 最大化两条链各自的异或和的和.$n\le 2\times 10^9, w\le 10^9$ ...

线性规划单纯形标准型与松弛型标准型是 $$\sum_i a_{i, j}x_j\le b_i\max \sum_i c_ix_i$$ 松弛型是 $$\sum_i a_{i, j}x_j=b_i\max \sum_i c_ix_i$$ 标准型转化为松弛型, 只要在所有限制左侧一个松弛变量即可. $\sum_i a_{i, j}x_j + x\le b_i$ . 一般写的单纯型求解的应该是标准型转化成的松弛型, (当然, 也有可能因为UOJ上模板题是输入标准型) 核心思想每一条不等式限制限制的是多维空间的一个”半空间”(类比二维空间的半平面), 若干个这个的交应该是一个凸多维几何体. 而因为目标函数是线性的, 所以必然有一个顶点可以取到最优解. (可以理解一下, 线性函数等值线全部平行, 也就是朝着一个固定的方向函数值最大, 可以沿着等值线平移到一个顶点上). 因为是凸的所以只要贪心的走就能走到最后的最优解. 单纯形说的是, 选择一组线性无关的变量, 为基变量, 其他变量都可以由基变量表示. 单纯形实现中, 我们让基变量形式上都是松弛变量(对于每一个基变量, 其只在一个限制中 ...

贪心发现自己贪心跟没学一样, 完全不会. 贪心 做题笔记题库里筛选greedy, 2600, 通过人数降序. 1400E Clear the Multiset 给定 $1\ldots n$ 每个数的个数 $a$ , 每次给一个区间个数减1或对一个数减去任意, 求清空次数. $n\le 5000, a_i\le 10^9$ “能大力dp的谁贪心啊” –qyc 好像给人感觉很经典. 很能dp, $f_{i, j}$ 表示前 $i$ 个数, 有 $j$ 个区间操作延伸到 $i$ 清空的最小代价. 复杂度 $n^2$ . 好吧, 贪心就是, 每次大力给全局减掉全局最小值, 然后全局裂开成若干区间, 再递归下去做, 如果这么算出来的答案大于区间长度直接变成区间长度(全用单点) 1537E2. Erase and Extend (Hard Version) 给定一个字符串, 可以任意多次删掉末尾字符或者把当前字符串复制一份接在后面, 求能得到的字典序最小的, 长度恰好为 $k$ 的字符串.$n, k\le 5\times 10^5$ 切不动2200了? ! 结论是最优解一定先用删再用复制. ...

JOI刷题笔记NOI考完了, 挂分80还有没打完的30遗憾打铁 另一方面也发现自己观察性质, 思维题, dp方向差很多啊 看到身边人都刷穿JOI, 板刷CF, 就从这里开始了. 写这篇博客时hexo爆炸换成了qyc的jekyll, 主要是省心不用配置, 并增加了折叠功能, 就把题目都粘过来提高阅读体验了. 「JOI 2017 Final」T1 焚风现象 给定序列 $a$ , 构造序列 $b$ : 若 $a_i=a_{i-1}, b_i=b_{i-1}$ . 若 $a_i>a_{i-1}, b_i=b_{i-1}-(a_i-a_{i-1})t$ 若 $a_i<a_{i-1}, b_i=b_{i-1}+(a_{i-1}-a_i)s$ $q$ 次对 $a$ 区间加一个数, 询问 $b_n$ . $n, q\le 2\times 10^5$ 一脸差分, 差分后变成单点修改, 那么直接维护 $b$ 的差分就好了, 树状数组单点修改区间求和. 「 JOI 2017 Final」T2 准高速电车 JOI 铁路公司是 JOI 国唯一的铁路公 ...

夏令营游寄Day 1比赛题T1 P7163 给一个树, 每个点有一个灯, 可能为开或关, 每经过一个点会把灯的状态翻转, 不能停留, 任选起点, 求最短路径把所有灯打开. $n\le 10^5$ 尝试构造发现方案不唯一而十分复杂, 考虑dp. 由于起点为自选, 想到换根dp, 发现换根过程很困难, 考虑把换根的信息也放进状态里, 最后设 $f_{u, 0/1, 0/1/2}$ 表示节点 $u$ 的子树内, $u$ 的状态为开或关, 子树内有几个路径端点的情况下让子树内全亮的最短路程, 转移时: 路径拼接时可能会重复走某个点 若走出时发现某个 $v$ 并没有被关闭, 那么就在走到 $v$ 后再走回 $v$ 再走回 $u$ , 会把 $u\to v$ 走两遍. T2 3d空间内有 $n$ 个块, 每个块都是一个长方体, 第 $i$ 块对角 $(x, y, z)$ 坐标分别为 $(i, 0, 0)$ , $(i+1, a_i, b_i)$ , 要求在这些块内的空间内找到一个最大的长方体 $n\le 2\times 10^5, a_i, b_i\le 1 ...

NOI系列刷题P7738 [NOI2021] 量子通信 [乱搞] 给定一个 $n$ 个单词的字典, 每个单词为长256的01串, $q$ 次询问一个串是否可以由字典中的串翻转 $k$ 位得到.$n\le 4\times 10^5, q\le 1. 2\times 10^5, k\le 15$ ,字典是随机生成的. 没看输入格式的时候没有意识到字典是随机生成的, 想了些字典树上dp之类的东西. 没想到其实是个乱搞题. 如果把每个单词每16位一组分成16组, 那么翻转15位的情况下至少有一组是相同的. 所以对于询问的串直接枚举是哪一位相同, 字典里这一位恰好相同的只有 $\dfrac{n}{65536}$ 个, 于是复杂度就是 $\dfrac{nq}{256}$ . 最后的问题就是如何快速找到字典里确定了某一组所有单词, 用vector存即可. 不要智障的打算插入到set/map/有序数组里就不会TLE. P7737 [NOI2021] 庆典 [图论] [tarjan] [虚树] [拓扑排序] 给定一张 $n$ 点 $m$ 边有向图, 记 $a\Rightarrow ...

LJC讲dpsdfzoj contest2 但当我用上了换行 给 $n$ 个长 $T$ 模式串, 含能匹配任何一个字符的通配符, 求有多少个字符串 $S$ 能匹配其中恰好 $k$ 个模式串. $n\le15, \vert T \vert \le50$ 首先考虑了一个容斥做法, 算能匹配每一个模式串子集的方案数再容斥就结束了. 不过还有个DP, 如果设 $f_{i, S}$ 表示考虑前 $i$ 位能匹配集合 $S$ 的方案数, 转移就是枚举这一位填谁, 然后根据这个算能满足哪些模式串, 复杂度应该是 $O(26\times2^n \vert S \vert n)$ , 但是很容易发现卡不满, 据说实际上跑的飞快. 感觉这个dp做法的对所有串同时考虑的想法还挺不错? sdfzoj contest0 T1 给一个数列 $A$ , 若一个位置为 $-1$ 表示你可以随便填, 求最长上升子序列长度. $n\le 10^6$ 先给每个位置减去它的下标, 就可以是求最长不降子序列了, 考虑此时我们可以任意在两个元素间插入一个-1, 所以直接不带-1求最长不降子序列然后加上-1的个数. 这 ...

数数题会把计数相关问题放在这里. 一做数数发现现在已经不会做蓝题了. 1. Appleblue17这一部分是appleblue17的cf和其他数数选做里的前几个. CF1515E Phoenix and Computers 有 $n$ 台电脑排成一排, 每次可以手动打开一台没被打开的, 同时若一台电脑左右的电脑都被打开, 那么它会自动打开. 求把所有电脑打开的方案数. $n\le 400$ 发现自动打开的电脑两边一定是手动打开的, 即它们不可能相邻, 所以其实是若干段手动打开的, 段段之间夹着一个自动打开的. 手动打开一个连续区间的方案数是 $2^{len-1}$ , 原因是我们每次只能像左边和右边拓展, 那么设第一个打开的是第 $k$ 个, 方案就是在剩下 $len-1$ 步中选 $k-1$ 步是向左拓展的, 所以方案数是 $$\sum_{k=1}^{len} \binom{len-1}{k-1}=2^{n-1}$$ 那么把一个自动打开的和紧跟着的一段手动打开的作为一段, 设 $f_i$ 表示前 $i$ 个的方案, 则加上一个新段的方案数时除了乘上这一段的方 ...

置换群论学习 我们要解决的问题是, 给定一个对象集合 $A$ , 一个颜色集合 $B$ 和一组针对映射的变换 $G$ , 求有多少种映射(将对象集合映射到颜色集合)的方案是本质不同的, 这里两种映射本质不同指不能通过变换把一个变成另一个. 简单理解就是对对象染色, 如果可以通过翻转旋转之类的操作变化到的算一种, 求有多少种染色方案. 要求这个变换操作关于他们的复合构成一个群, 称为置换群, 变换称为置换. 符号约定: $F(A, G)$ 表示对 $A$ 染色, 在 $G$ 的情况下的本质不同方案数 $G(c)$ 表示应用到 $C$ 上不改变的置换组成的集合 $C(f)$ 表示 $f$ 作用上去不改变的方案组成的集合 $S(c)$ 表示和 $c$ 本质相同的染色方案组成的集合 方案 $c$ 经过置换 $f$ 得到的东西为 $cf$ , 先进行 $f$ , 再进行 $g$ (就是复合 $f$ 和 $g$ )的置换为 $h=fg$ Burnside引理引理0$G(c)$ 是群 照着定义显然成立 引理1$$\sum \vert G(c) \vert =\sum ...

Day1 contest of TYYT1 小N的独立集给一棵树, 每个点权 $a_i$ 在[0, m]间, 每次独立的钦定一个点 $a_x=y$ , 求此时有多少方案满足对所有 $v\in [1, m]$ , 满足 $a_i\le v$ 的点构成一个连通块. 考虑如果不钦定怎么做, 设f_{u, i, 0/1}表示 $u$ 的值为 $i$ , 且子树内是否有比 $i$ 大的时考虑 $u$ 子树的方案数, 对于1的情况容易转移 $$f_{u, i, 1}=\prod_v \sum_j f_{v, j, 1} s. t. j\le i$$ 对于0的情况, 可以枚举哪一个儿子是比它大的: $$f_{u, i, 0}=\sum_k (\prod_v \sum_{j\ne k} f_{v, j, 0} s. t. j\le i) \times f_{k, j, 1} s. t. j\ge i$$ 用前缀和和后缀和处理空出k后其他儿子的信息再和k合并不然复杂度爆炸. 那么现在要支持单点修改, 于是ddp和整体dp拍上去, 然后你发现这玩意ddp用矩阵表 ...

记录一些技巧一半的半平面交当求半平面交的一半(相当于求一个直线构成的下凸壳或上凸壳)时, 可以把如 $y=kx+b$ 的直线转化成 $(a, b)$ 求凸壳 长剖换根长链剖分的换根说的是, 你做完长链剖分之后跑换根dp, 那么现在一个点有其长儿子的信息, 短儿子的信息和子树外的信息, 那么直接把所有短儿子都合并到子树外的信息上, 进入一个轻儿子的时候把自己删了, 把重儿子前 $h$ 个加入, 退出的时候撤销, 进入重儿子的时候就用全部的即可. 要求信息可合并, 可删, 且信息量是仅深度相关对. 二项式系数$$\sum \binom {n}{i}^2=\binom{2n}{n}$$ 证明考虑 $x^k^{2k}$ 排列模 $n$ 的环上存在排列 $p_n$ 满足 $i-p_i$ 互不相同当且仅当 $n$ 为奇数. 必要性显然. 充分性考虑率 $\sum_i i=\sum_i i-p_i=\sum i-\sum p_i=0$ 即可. 末尾添加删除节点的线段树动态构建UOJ191 Bitset字符串匹配抄写 alexwei 对 $s$ 和多个 ...

网络流选做建图套路深 费用流边的描述用 $u \stackrel{f, c}{\longrightarrow} v$ , $f, c$ 分别是流量和费用. 题目P5458 水晶 [网络流] [最小割]对于水晶, 染色时能量源染成一种, 能量源周围六个点间隔着染两种, 发现若共振则一定三种颜色都包含且相邻, 同色格子互不影响 于是可以每个能量源拆三个点, 分别表示三种颜色删去哪一种, 串联起来跑最小割, 表示从这三种任意删一个 P2774 方格取数问题 [网络流] [最小割]黑白染色, 做成二分图, 两种颜色各一边. 对于一个格子, 向源点或汇点连自己点权的边(取决于自己在哪一边), 向周围四个格子连容量inf的边, 跑最小割即可 [思考] : 限制明显而许可(可以这么做)不明显时最小割 P5038 奇怪的游戏 [网络流] [思维]看到相邻的两个格子想到黑白染色后一定一黑一白 于是黑白染色, 统计黑, 白色格子个数和权值和, 记为 $cnt_b, cnt_w, sum_b, sum_w$ , $sum_b-sum_w$ 始终不变 设最后所有数都变成x, 接下来分两种情况 如果黑白格子数 ...

数据结构综合选做高妙分块都塞进分块选做了 P3714 树的难题 [点分治] [线段树] [单调队列]线段树解法用线段树维护之前的子树中, 与当前子树颜色相同和不同的情况, 把颜色排序, 可以保证先前碰到的颜色不相同后后面不会再相同, 每次到新颜色则把相同颜色插入到不相同颜色中. 单调队列合并to do P3345 幻想乡战略游戏 [点分树] [线段树] 重心的性质, 可以利用对当前答案移动一条边的方式证明答案既是全树点带权重心(边权无影响), 每次会走向自己儿子中点权和大于一半的儿子, 解法1: 线段树由于所有大于一半的儿子形成了由根开始的一条链可以直接在线段树中二分出重心, 问题变为求所有点到重心的距离, 设重心为u, 点到根距离为dis, 则答案为: $$ \sum dis_u+dis_v-dis_{lca(u, v)}\\=\sum dis_u + \sum dis_v - \sum dis_{lca(u, v)}$$ 其中前两个式子可以直接求解, 最后一个式子则考虑首先 lca 一定在u到根的链上, 其中考虑边 e 被 dis_{lca(u, v)} 计算的次数为 ...

SAM字符串题目选做~~这类题好多也可以用后缀数组和后缀平衡树, 但我还是热爱SAM. ~~ 一开始是SAM题目选做, 现在也会加入部分其他字符串. P4022 熟悉的文章 [SAM] [dp] 给定01串标准文章, 定义一个01串是熟悉的当且仅当长度大于 $L$ 且z在标准文章中出现过. 现 $q$ 次给定询问串 $T$ , 求最大的 $L$ 使得可以把 $T$ 分成若干段, 其中有90%以上是熟悉的. 输入文件小于1100000Byte. 对于一篇作文, 可以求出每个点向前最多匹配多长还在标准作文库中(zsy数组), 这里前是指向下标小的方向(似乎对于序列, 前和后会产生歧义) 把这个长度记为 $len_i$ , 方法: 建出包含所有作文库作文的SAM. 初始匹配长度为0, p 借点在根, 每次若能匹配沿自动机边向前走, 否则跳parent tree, 注意向前匹配时匹配长度不能直接用 p 点 sam 节点的len值, 但跳parent tree树时可以. -qyc: 这里暴力跳parent tree是对的因为跳一步深度减一, 匹配一个深度加一, 所以总复杂度O(n) 然 ...

机房杂题奇怪通信题通信题1 [线性基] [随机化] [构造]A程序输入 $x\le 10^18$ 和最多40个位置, 要求编码长为150的01串给B, 其中给定的位置必须为0, B从这长150的串里恢复信息. 法1: 每3个分一块, 若一块内有两个位置必须为0则全填0, 否则按照如下方式编码: 1234567块编码 -> 实际信息001 -> 1010 -> 0101 -> 00100 -> 01110 -> 10111 -> 11 构造满足不管是哪个位置挂了, 都可以用一种编码表示它, 最坏情况下我们也能有40个坏了的和10个没坏的, 其中没坏的可以表示2位, 坏了的表示至少1位, 就能表示 $2^40*4^10=2^60$ , 正好表示 $10^18$ 法2: 每2个分一块, 如果有一个位置挂了就全0, 否则可以编码3种信息, 那么能表示 $3^35$ 个信息, 发现 $3^38$ 才行, 发现这种最坏情况仅当每个数单独占一块, 这时可以两个程序选用同一个种子把位 ...

数竞趣题来自数竞同学, 有12个球和一个天平, 天平可以比较两组球的重量和的大小关系, 其中一个球是假的, 可能更重或更轻, 称3次找出 这类题的关键是对获得信息量的考虑, 要使得每次询问的最坏情况下获取的信息量最多, 相当于尽量均衡 这个题第一步可以划分成4, 4, 4也可以是3, 3, 6, 发现若是3, 3, 6, 则不相等比相等多知道一个大小关系, 而4, 4, 4则更均衡 于是先考虑4, 4, 4, 如果相等则用2次从剩下的4个里找, 简单 如果不相等, 就要想办法利用这个不相等关系, 设球从1编号, 两组分别为1, 2, 3, 4和5, 6, 7, 8, 显然可以设1, 2, 3, 4>5, 6, 7, 8, 于是考虑问1, 2, 5和3, 4, 6, 如果相等仍然简单 如果又不相等, 考虑如果那个假球比正常的大, 则只能在1, 2, 3, 4和两组中大的那组的交中, 只有两个, 如果更小则是5, 6, 7, 8和两组中更小的那组的交中, 只有一个, 可以假设更大称那两个, 如果相等说明假设错了就是那一个, 否则取更大的一个. 还是很有意思的

分块选做省选分块显然也挂了, 感觉又能数据结构又练码力, 唯一的问题是不会做 P4108 HEOI2015 公约数数列 [分块] [分析性质][结论]:**一个序列前缀 gcd 是 log 段的函数!**因为每次gcd改变至少要除以2, 所以就 $\log n$ 段, 这个性质还挺优秀. 第二是发现序列长度为 $10^5$ , 但询问 $10^4$ , 放过了 $O(q\sqrt n \log n)$ 的做法 于是只需要考虑计算对于gcd的每一种取值是否可行即可, 如果线段树需要支持后缀异或一个数和查询一个区间是否存在某个数, 这是不可做的, 因为首先标记显然不能pushdown, 那么对于标记永久化, 可能会走到一个节点, 它一部分被打上了标记, 然后就G了 所以只能分块, 设块长为 $B$ , 对每个块维护块内 gcd 和 xor和, 再开一个哈希表存储当前块内前缀xor和为 $x$ 的最早的位置, 修改时暴力 $O(B)$ 重构当前块, 并对后面 $O(\frac{n}{b})$ 个块暴力, 询问则在外层从前到后遍历每一个块, 并在过程中记录当前块前缀 gcd 和 xor, 如果 ...

dp选做省选dp挂了不会来补一补 刷题记录-2022暑假前UVA1626 括号序列 [dp] [区间dp]区间dp(似乎括号类的都是区间dp? ) 设 $f_{l, r}$ 表示把区间l到r中补到合法的操作步数, 则转移是: 最外侧是匹配的括号: $f_{l, r}=f_{l+1, r-1}\ \ s. t. \ s_l=s_r$ 区间由若干 $f_{l, r}=\min_{l\le k\le r}{f_{l, k}+f_{k+1, r} }$ 在最右侧添加一个与最左侧的括号匹配的括号或相反, 发现这种情况不优于直接在与这个新添加的括号匹配的括号旁边直接匹配 然后初始情况就是 $f_{i, i}=2$ , 表示为每个括号加一个反括号匹配 这题输出方案, 所以记录最有解位置即可. P1220 关路灯 [dp] [区间dp]由于老王走过去关一盏灯时顺手关掉路上经过的一定不劣, 所以被关掉的灯是一个区间, 于是记 $f_{l, r}$ 表示已经被关了的灯的区间, 发现这样转移不了, 比如当我们向右扩展一位时我们不知道老王是刚刚关完左端点的灯还是右端 ...

The Forest题解题意:t组询问, 每次给两棵n个点的树A和B, 求有多少点集满足B树上是一个连通块而A树上是一条链. $n\le1e5, t\le3$ 解法链比连通块性质更好, 从A树角度考虑 A是链的解法这是后面的基础. 对于树上的一个连通块, 满足 $V-E=1$, 当A是链也就是每条链成了一个区间, 于是每次移动区间右端点, 数据结构维护左端点, 于是可以开一棵线段树, 下标 $i$ 位置表示以链上下标为 $i$ 的位置为左端点, 到当前右端点这一段区间的 $V-E$, 因为 $V-E$ 不可能比 $1$ 更小, 所以维护区间最小值和最小值个数, 支持区间加, 每次 $r’: =r+1$ 给 $1$ 到 $r’$ 加一, 对于它们所有都多了 $r’$ 这个点 遍历 $r’$ 在B树上的每一条边, 若指向的顶点在当前区间内, 给这个点到 $r’$ 的这个区间减一, 因为左端点在这个区间时点集会包含这条边. 完整解法一 – 换根把刚才的解法拓展到树上, 维护每个点到根 $rt$ 的这条路径的 $V-E$, 对任意一个根, 可以 $O(n)$ ...

Hello World新博客开通啦洛谷每篇文章只有一个标签过于烦人, 所以就这样啦以前洛谷上的文章已经都迁移过来, 但以后的可能只在这里发 写一些杂项 hexo迁移到jekyll. jekyll又迁移到hexo为了支持加密文章. 一点说明序列常常会用 $a_n$ 表示长度为 $n$ 的序列. 标签咕咕表示还在更新(或表示总有一天会更新) 标签日志指做题记录, 笔记是记录某些人的讲课或自己学的科技, 训练多半是还包括模拟赛等. 半角标点是信仰. 问题记录jekyll的部分现在支持emoji和折叠了 博客副标题里不能用%, 否则会死 死亡特点是没有标题, 并且时间不对(为你push的日期) latex里不能出现{ { . . . } }, 因为这个是jekyll的模板语法. 死亡特点是居中对齐的latex源码. hexo的部分要clean以应用更改.

感性理解网络单纯形传说最快费用流 前置知识单纯形, 费用流基本概念 符号说明$n$ 为点数, $m$ 为边数, 先假设图为联通的(显然不联通没有影响) 边 $e$ 的单位费用为 $cost_e$ , 流量上界为 $cap_e$ , 由 $u_e$ 指向 $v_e$ 认为我们建网络流的图时是建了反向边的 理论基础我们知道费用流模型在线性规划标准形式的系数矩阵是全幺模矩阵, (这个矩阵有 $n$ 行 $m$ 列, 仅由 $0, 1, -1$ 组成, 每一列可以表示一条边, 设这条边由 $u$ 指向 $v$, 则矩阵中 $u$ 行为 $-1$, $v$ 行为 $1$). 直接单纯形, 我们会设每一条边的流量, 然后再转化标准形式, 所以这里可以认为边的流量是线性规划中的变量(忽略松弛变量). 注意到此矩阵的一组基对应图的一棵生成树. 证明: 若选中的基包含一个环, 则将这个环的边的列顺次相加得到0, 则这不是一组基, 所以基的列对应的图无环, 又因其能张成原图, 所以其联通, 因此能唯一对应一棵生成树. 于是得到这样对应关系: 单纯形中变量对应边的流量 单纯形中基的选择对应图的一棵生成 ...

点分治优化树上连通块DPqyc只摆了一个优化连通块背包dp的例题, 所以我理解并不透彻( 概念有时我们处理树上连通块, 由于在树上, 对于包含根的连通块, 连通块若不包含父亲则一定不能包含儿子, 根据这个性质, 我们可以把dp进行不重不漏的划分, 选这个父亲的方案或不选的方案, 从而可以直接将对应状态直接合并来代替困难的dp合并. 既然划分成选或不选根, 就容易理解通过点分治进行根的选取从而达到优化效果了 适用于解决合并困难而插入一个点较简单的计数dp (也可能不是计数? 但这种划分还能怎么用没见过) 例题Tree Cutting - HDU 5909 - Virtual Judge (vjudge. net):题意:点有点权, 对每一个k求点权异或和为k的连通块个数 解法:首先对于每个分治部分处理: dp[j]为当前异或和为j的连通块个数 一开始dp[j]全为空, dp[0]=1, 即都不选时异或和为0 dfs当前点分治的部分, 进入一个节点就有两种情况 不选这个节点, 则这个点的儿子也不能选了, 那么答案仍然是是其父亲传下来的dp[j], 我们叫他dp0[j] 选这个 ...

板子图论tarjan: 割点 条件: 对于点 $u$ 存在儿子 $v$ 使 $low_v\ge dfn_u$ (实现时 $low$ 可以算 $u$ 的 $dfn$, 也对) 感性理解: 说明 $v$ 的子树内除了 $u$ 之外没有其他方法走到外面 注意: 对于 dfs 树的根(开始 dfs 的节点), 要通过统计子树个数方法判断( $>1$ 则为割点) 代码: 1234567891011121314151617181920void dfs(int u,int rt=0){ if(rt==0)rt=u; dfn[u]=low[u]=++dcnt; int children=0; for(int v:G[u]){ if(dfn[v]){ low[u]=min(low[u],dfn[v]); continue; } dfs(v,rt); children++; low[u]=min(low[u],low[v]); if(u!=rt&am ...

做题笔记 几个杂题P2150 寿司晚宴 [dp] [状压dp]大于 $\sqrt n$ 的质因数最多只有一个, 最多出现一次, 相同大质因数一起处理, 背包合并 [trick] 大于 $\sqrt n$ 的质因数只有一个单独处理 P2048 超级钢琴 [greedy]要求所有区间的前k大, 考虑处理 $k$ 次取最大, 开一个堆记录 $(l, rl, rr, t)$ 表示左端点为 $l$ , 右端点在 $rl$ 到 $rr$ 间时最优位置为 $t$ 的答案, 每次从堆中取出最优解, 把区间分裂成 $(l, rl, t-1)$ 和 $(l, t+1, r)$ 两个区间放回堆中 [trick] 把 $n^2$ 个点对贡献压缩成 $n$ 个 $p, l, r$ 表示一个点和区间 $l, r$ 中的点的贡献, $n^2$ 个可能贡献取前 $O(n)$ 个, 可能是先放能代表所有的, 一边拿一边把新的加入堆. P3783 天才黑客 [ds] [virtual-tree] [最短路] [前缀和优化建图]点边互换, 考虑对于一个点怎么把这些边连到一起. 考虑边之间的贡献是lcp, 那么可以转字典树上 ...