专题：题解
共65篇相关文章
P11403软盘题解中是什么？
人生第一道通信题！ Solution 由题意得，(L) 最大值为 (2N)。而题目询问的是最大值的下标，这启示我们保存关于相对大小关系的信息。 注意到，区间最值可以转化成笛卡尔树上 LCA。因此只需要传笛卡尔树即可。 考虑单调栈建树...
How many multisets can be formed with [ARC107D]?
$text{Solution}$ 学习到了一些 $dp$ 的 $trick$ 设 $f_{i,j}$ 表示用了 $i$ 的元素，当前和为 $j$ 的方案数 $dp$ 有两样不好处理的东西 第一是当前和不一定为整数 第二是可重集合的重复计数...
What's the CF750H New Year and Snowy Grid model called?
$text{Solution}$ 这个问题是不好判断的 考虑简单点的，$(1,1)$ 到 $(h,w)$ 是否连通 那么只要在最外围一圈 #（显然一些位置不能加），判断 $(h+1,n)$ 和 $(0,w...
Is LG P5244 [USACO19FEB] Mowing Mischief P's solution optimal?
$text{Solution}$ 感觉是很套路的题 按 $LIS$ 分层后 $dp$ 很容易想到 注意到同层 $x$ 递增，$y$ 递减 所以很容易猜到决策单调性，但是每个点的决策集合是不同的区间，这与一般的决策单调性可不一样 怎么办呢？...
QOJ5402. 术树数是什么意思？
$text{Problem}$ 术树数 $text{Summary}$ 这题有许多优美的结论，并加深了对线性基的理解 图论中非常有用的结论（路径可重）： 1.包含一个点的简单环张成了包含一个点的所有环 2.考虑图的任意一棵生成树，取两点...
矩阵树定理如何应用于效应的优化决策？
$text{Conclusion}$ ~~显然只需要这个~~ 矩阵行列式 定义矩阵的行列式 $det(A)=sum_p mathbb{sgn} prod a_{i,p_i}$，$p$ 为一个排列 交换矩阵两行行列式变为相反数，一行...
P8421 [THUPC2022 决赛] rsraogps是什么算法？
$text{Solution}$ 肯定扫描线在考虑维护什么东西，假设 $r$ 右移时可以暴力得到所有新值，发现需要维护区间历史版本和以及区间当前值之和 这三个操作对于一个数来说变化次数都是 $O(logV)$ 的，所以可以暴力修改发生变化...
JZOJ 6664. 【2020.05.28省选模拟】最优化如何成？
$text{Solution}$ 原题：$text{Honorable Mention}$ 一个费用流做法，$S$ 向 $2i-1$ 连流量为 $1$，费用为 $0$ 的边，$2i$ 向 $T$ 连流量为 $1$，费用为 $0$ 的边...
CF223E平面图如何应用于分析？
$text{Solution}$ 很好的想法是用平面图欧拉定理 $E=V+F-2$ 那么就要解决的问题是环内的边数与面数 科技的使用：平面图转对偶图 建图过程大概就是将每条无向边拆成两条双向边，考虑找出所有按逆时针方向围...
CF1175G Yet Another Partiton Problem 是什么问题？
$text{Solution}$ 有关斜率优化的强势套娃题，感觉套出了巅峰 ~~我整整写了 5 个小时、、、~~ 简单 $dp$ $$ f_{i,j} = f_{i-1,k-1} + (j-k+1)m...
CTS2023琪露诺符卡交换是哪一种？
$text{Code}$ #include <bitsstdc++.h> using namespace std; template<...
CF590E生日是哪一天？
$text{Solution}$ 建出 ACAM 后利用 fail 树就可以确定子串关系了，如果建成有向图 然后看问题，考虑最长反链等于最小链覆盖，那么就是求一个可重路径覆盖问题 Floyd 传递闭包后变成不可重路径覆盖，拆点二分图就有最...
如何用集合划分容斥找出[ABC236Ex]的互不相同倍数？
$text{Solution}$ 关键限制是 $2.A_inot= A_j$ 这也是上午模拟赛 $T3$ 导致我暴力不会的东西 考虑更一般的，连边 $(i,j)$，表示 $a_i=a_j$ 的限制，那么本题考虑这样的一个完全图 那么枚举...
P6031 CF1278F Cards 加强版是哪款游戏卡牌？
$text{Solution}$ 推式子 有答案为 $$ begin{aligned} Ans &=sum_{i=0}^n i^kdbinom n i (frac 1 m)^i (1-frac 1 m)^...
How to find two subtrees in a given tree structure?
$text{Solution}$ 高维莫队的一次尝试 最小众数似乎要求我们刻画能回滚的高维莫队 但这并不友好 修改有 $O(n^{frac 7 4})$，询问只有 $O(n)$ 考虑友好的分块，那么就加个值域分块 询问便可以先得到众数的...