文章

1. 题目 传送门=￣ω￣= 2. 题解 额。。。 首先把 j 设为 $-1$，p 设为 $1$，求前缀和，设为 $d$数组。 若 $[l, r]$为符合条件子串，则 $d[l – 1] \leq d[i](i \in [l, r])$且 $d[r] \geq d[i](i \in [l 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 首先只出现了一次 => Right 集合大小=1 就搞个 SAM，建出 pre 树，对于一个 Right 集合大小=1 的点 a： 它的 endpos 唯一，设为 $x$，那么这个状态的最长子串（$maxlen$）一定是 $[1, x]$这个前缀。 且它的最 阅读更多…

Update(2019.01.26) 现在 VSCode 的官方 C++插件制杖得一匹 更新后的插件自带一个无法自定义的 “Code snippets”（代码片段），和我的代码风格又不同，而且在自动补全中总是排在你自定义的代码片段前面，一按 tab 就补全它的代码片段 然后 debug 也是，鼠标悬 阅读更多…

发出可爱的声音.wva 题目大意 给圆圈上的 2n 个点两两连线，事先给你连了 k 对点，让你求连完后的所有方案中的联通块个数之和，联通块的定义是如果两条线交叉那么同属于一个联通块。 Atcoder 的题太妙了 首先我们考虑转换思维，考虑每一个联通块对答案的贡献，我们就能这样设方程 设 $dp[i] 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 好神啊 QwQ 首先二分图就是没有奇环的图 因此如果只有加边的话可以用带权并查集维护两点之间的路径奇偶性。 因为存在删边操作因此我们需要对时间分治。 对于分治的时间区间为 $[l, r]$的情况，枚举每一条存在时间包含在 $[l, r]$的边，设其存在时间为 阅读更多…

喵呜 题目描述 规定 $s[i]=$树中是否存在一条边使得删掉后有联通块的 $size=i$ 请构造一棵这样的树 naive 的思考 显然 $s[1]=1,s[n]=0,s[i]==s[n-i](i \in [1, n – 1])$就不用说了吧 然后我们可以发现题目给的条件就相当于 $s 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 可以看出如果我们能建出后缀树就很简单了，只要在树上 lca 处数点就行了 然后我就去学了 Ukkonen，然而发现还不如老老实实用后缀自动机来得方便一些。 后缀自动机的 fail 树（也有人称之为 pre 树、next 树等等等等反正就是适配了跳转的边形成的 阅读更多…

之前一直是远控机房另外两台装了 windows 的电脑（美名其曰 “云 OIer”），新装的 Ubuntu 系统就没有安装 QQ 之类的软件了 今天 CY 跟我们说初中小朋友要跑到我们机房来，不准我继续做我的云 OIer 了 QQ 不能少，参照我之前发的教程安装 TIM 发现打不开，那个 Appim 阅读更多…

啊呜啊呜 因为 F 一直不会做，所以就水一篇 E 的 blog 吧 题目描述大概就是给你一个序列 a，求 $a_i + a_j$的最大值，其中 $i|j\leq k$ 一句话题解：高维前缀和子集取 max 所以为了不让这篇 blog 过于单薄我就再写一下详细过程吧 设 $f[s]$表示 $i|j=s 阅读更多…

不用说你也知道我是什么了吧 啊呜 题解 首先考虑暴力搞，分治，每次把当前区间最大的数拎出来，然后统计左右两边的贡献 这种方法显然会被一个严格升序列给卡成 $n^2$ 考虑优化上面的暴力，我们发现我们统计的实际上是分别以这 $n$个数为中心 (也就是最大的那个数 $max$) 并且求两边数对它的贡献的 阅读更多…