喜报：$[0,100]+\varepsilon$. 场上我在干什么：10:30 前在玩原神，10:30 之后整个人脑子都是乱的，不知道自己 T2 在数什么东西。 12:30 的时候急了，瞎 jb 写了个 T3 暴力还过不了小样例。 出考场的时候人都是恍惚的。 回家发现我 T1 没判 $pre>m$。 再想 1= 只能寄…

线段树矩乘维护数位 DP。 令 $dp_{i,0/1,0/1}$ 表示当前第 $i$ 位，是否顶到上界，第 $i$ 位是否为 $1$ 的方案数量，$x_i$ 为 $x$ 从高到低第 $i$ 位。 则有： - $dp_{i,0,0}=\begin{cases}9dp_{i-1,0,0}+8dp_{i-1,0,1}+(x_…

显然你一定是移动到捕捞点或者基地之后返回，然后逆流而上时仅捕捞，顺流而下时仅出售肯定是最优的。 不妨考虑枚举移动到哪个点之后返回。 先考虑查询，查询显然最优策略就是每次尽量选择范围内 $c_i$ 最大的出售，直到对于一个基地出售数量达到 $b_i$ 或者总出售数量达到捕捞的数量 $k$。 然后这个考虑把 $c_i$ 离…

在文章《sol? csp-s 2025 t3》发表评论：

考完之后补的

***梦破碎了，塔坍塌了。*** 【14：30】 先开 T3，想到把 LCP 和 LCS 以外的部分拿出来，然后只会 $L^2$ 【16：30？】 此时我一道题都没写，看眼 t1 不然要保单了，哦 t1 秒了，t2 一眼看过去应该是 $O(2^knk)$ 的东西，肯定需要枚举 $k$ 的状态，然后只会 $O(2^k(n…

口胡做法。 为什么场上我会觉得 $O(L|\Sigma|)$ 过不去？？？ 首先根据数据范围会发现描述里的「子串 $y$ 的位置不同」是没用的。 把 $t_{i,1}$ 和 $t_{i,2}$ 分别变成形如 $x+y_1+z$ 和 $x+y_2+z$ 的形式，其中 $x$ 是 $t_{i,1}$ 和 $t_{i,2}$…

因为原先的图是一棵树，显然每次询问的子图都是森林。 森林连通块数量启发我们使用 $V - E$ 计算。 把边分成横向的和纵向的两部分，然后我们需要维护：一个子矩形内点数量，横向边数量，纵向边数量。 边数量显然是可以把每个边的贡献算到其中一个端点上进行维护的，这里不妨将 $(x, y)$ 和 $(x, y + 1)$ 的…

可以发现从 $(1,1)$ 走到 $(i,j)$ 和从 $(i,j)$ 走到 $(n,n)$ 是独立的，因此令 $f_{i,j}$ 表示 $(1,1)$ 走到 $(i,j)$ 和 $A_{i,j}$ 出售相同的食品的售货机最多的数量，$g_{i,j}$ 则表示 $(i,j)$ 走到 $(n,n)$ 售货机最多的数量，则…

题解里我把原题中的横纵坐标调换了，例如 $(y_1,x_3)$ 表示第 $y_1$ 行第 $x_3$ 列，$a$ 表示原数组. --- DP. 考虑把图分成三部分，第一部分最右边为 $x_3$，第二部分最右边 $x_4$，第三部分 $x_2$. 令 $f_{i,j,0/1/2}$ 表示 $(y_1,x_3)/(y_1,…

### 0x00 定义 积性函数定义为满足 $\forall x,y,\gcd(x,y)=1$，有 $f(x)f(y)=f(xy)$ 的函数. $\mu$ 为莫比乌斯函数，定义为： $$ \mu(x)=\begin{cases}1&x=1\\0&x\ \textsf{存在平方因子}\\(-1)^{\omega(x)}&…

$$ \begin{aligned} F(x)&=\sum\limits_{i\ge 0}f_ix^i\\ &=1+\sum\limits_{i\ge 1}\left(f_{i-1}+(i-1)+\binom{i-1}{3}\right)x^i\\ &=1+x\sum\limits_{i\ge 1}\left(f_{i…

整体二分。 先求出来点 $i$ 到守卫最近的距离 $dis_i$，然后二分 $x$。 然后问题就变成了是否可以只经过 $dis_i>x$ 的点从 $S$ 到 $T$。 点权不好维护，改成边权的形式，每条边 $(u,v)$ 边权为 $\min(dis_u,dis_v)$，二分时只连满足 $\min(dis_u,dis_v…

先考虑一条链的情况。 用 nth-element 的思路，先确定链的两端点 $L,R$，在 $[L,R]$ 范围内随一个点 $u$，显然可以询问 $(L,u,i)$ 知道 $u$ 在 $[L,i]$ 还是在 $[i,R]$。然后根据在 $[L,i]$ 和在 $[i,R]$ 的 $u$ 的数量选择递归到 $[L,i]$…

省流： $$ f_i=\sum\limits_{j}f_jf_{i-j-1}\\ g_i=\sum\limits_{j}2f_jg_{i-j-1} $$ - $f_i$ 表示 $i$ 个节点不同构二叉树数量，$g_i$ 表示叶子节点总数. - $g_i$ 这个是只算右子树，因为左子树这个是对称的所以直接乘以 $2$ 即…

比较目光呆滞的推柿子： $$ \begin{aligned} P(x=y)&=\sum\limits_{v_1,v_2}\dfrac{\min(v_1v_2)}{v_1v_2}\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^n\dfrac{3i(i+1)}{n(n+1)(n+2)}\…

考虑不带修改怎么做。 令 $f_{l,r,x,y}$ 表示 $[l,r]$ 区间内满足 $i<j,a_i=x,a_j=y$ 的 $(i,j)$ 数量，$t_{l,r,x}$ 表示 $[l,r]$ 区间内满足 $a_i=x$ 的 $i$ 的数量。 假如你知道了 $[l,mid]$ 区间和 $(mid,r]$ 区间的 $f…

考虑 $n=4$ 怎么做。 对 $(1,2,3),(1,2,4),(1,3,4),(2,3,4)$ 分别进行询问，可以发现一定能得到两个不同的中位数 $L,R$，令 $L R$。不妨令满足 $a_i\le L$ 的两个 $i$ 为 $l_1,l_2$，满足 $a_i\ge R$ 的两个 $i$ 为 $r_1,r_2$，…

令 $dp_{t,i}$ 表示时间为 $t$，此时在 $i$ 结束的最大利润，$m_{t,i}$ 表示时间 $t$ 时 $l$ 点展销会的盈利，若不存在展销会则 $m_{t,i}$ 为 $0$。显然最后答案为 $\max(\max\{dp_{T_{\max},i}+D\times (S-i)\mid i 0,dp_{t…

 令 $EP=6x$，则 $AP=8x,AE=10x$。 令 $BE$ 与 $AP$ 交于 $G$，过 $G$ 做 $GH\perp AE$ 交 $AE$ 于 $H$。 则有 $GH=PG$。…

> 给定一张无向图 $G=(V,E)$，求其三元环个数。 考虑给这张图定向。先对 $G$ 中的节点排序，度数小的排在度数大的前面，如果度数相同则按编号排序，即 $\text{deg}_i<\text{deg}_j\lor (\text{deg}_i=\text{deg}_j\land i<j)\Longrightarr…

- 一棵树上有两个城市 $A,B$，令 $x$ 到 $y$ 路径上的点集合（包括端点）为 $P_{x,y}$，你需要对点 $i$ 分配 $c_i$ 使得 $\sum c_i\le k$，同时对于一个点 $x$，如果 $\forall i\in P_{x,A},\operatorname{dis}(i,A)\le c_i…

$n\le 1000$ 直接并查集即可。令 $i$ 表示在点 $i$ 且此时树蛙颜色为绿色，$i+n$ 表示在点 $i$ 且此时的树蛙颜色为棕色，如果原平面上 $i$ 能跳到 $j$ 则 $i$ 和 $j+n$ 合并，$j$ 和 $i+n$ 合并，显然只要最后 $i$ 和 $i+n$ 在一个集合中就是合法情况。 考虑…

直接令 $f_{i,j}$ 表示前 $i$ 列，第 $i$ 列修高度为 $j$ 的长堤最大重量是很不好转移的，因为你没办法知道 $i-1$ 列的鱼是否已经计算过贡献了。 可以发现，如果钦定第 $i$ 列的鱼只能被其左边或只能被其右边的长堤抓住是不影响答案的，因为如果一个鱼被左边（或右边）的长堤抓住，则这一列高度低于这条…

KTT 做法。这里的变量可能和原题有一定不同。 以下令第 $i$ 个波特当前的移动速度为 $k_i$，当前时刻的位置为 $b_i$。初始 $k_i=0,b_i=a_i$。 首先离原点最远的显然就是 $b_i$ 最大或者 $b_i$ 最小的，这里只介绍 $b_i$ 最大的情况，$b_i$ 最小的情况只需要把初始位置和操作…

.

这个和追忆类似，考虑除以 $\omega$ 的做法。 首先您需要知道 bitset 优化 bfs，这个是 $O(\dfrac{n^2}{\omega})$ 的，在 $m$ 是 $O(n^2)$ 级别的时候比较有用。 然后是 DAG 的可达性问题，这个可以用 DP 实现，令 $f_{i,j}$ 表示 $i$ 是否能到 $…

Sol 区的都是 $O(Tm^2)$ 的。这里有一种 $O(m\log n)$ 做法.

### Day 2460751 vp 了 2024 语文和英语. 听力 skip，作文 skip. 英语 -5pts，看着还行 语文 -18pts，闹斯特麻麻了 听说去年 zj 一万个语文 100+ 的，那我 whk 不是烂完了/xk. 如此成绩，何以中考！ 周围的 oi 水平都比我好，whk 也是年级 rk50 的，…

在文章《P11833 [省选联考 2025] 推箱子》发表评论：

abc371f 吗/yiw

考虑： - 源点向每个开始区间 $i$ 连边，容量为 $1$，费用为 $a_i$。 - 每个开始区间 $i$ 向数轴上对应在区间 $[sl_i,sr_i]$ 的点连边，容量为 $1$，费用为 $0$。 - 数轴上的 $i$ 向 $i+1$ 连边，容量为 $1$，费用为 $1$。 - 数轴上每个在区间 $[el_j,er…