TP2010

2026年3月30日

题解：CF1930H Interactive Mex Tree

摘要：题目传送门好吧，我也不知道这是交互还是伪装成交互的构造了。好吧，居然有图，我太强了。由于是排列，所以可以把 \(\operatorname{mex}\) 转为补集的 \(\min\)。在此图中，我们就是要用 \(5\) 个区间来覆盖 \(rt,A,B,C1,C2,D1,D2,E,F,G\) 阅读全文

posted @ 2026-03-30 16:42 TP2010 阅读(0) 评论(0) 推荐(0)

题解：P13614 [IOI 2018] highway 高速公路收费

摘要：前言题目传送门看刘海峰老师的讲座来做的这道题。前置知识：最短路，二分，广度优先搜索 (bfs)。解析分三步骤拆解问题：一对于 \(A,B\) 权值做一步转化，初始时先把所有边权设为 \(A\)，得到一个初始的最短路大小 \(D\)，那么如果将一条边变为 \(B\)，可以等效为把这条边断阅读全文

posted @ 2026-03-30 09:49 TP2010 阅读(0) 评论(0) 推荐(0)

2026年3月29日

AT_abc451_e [ABC451E] Tree Distance 题解

摘要：题目传送门考虑直接构造一组合法的解。由于树上两点的距离都给出了，且边权为正整数，所以显然是最多有一组解。方便构造，考虑随便把一个点作为根，那么根到其他点的距离记作 \(b_u\)。随手将所有点按 \(b\) 从小到大的顺序排序（不排好像也是一样的），那么如果能判断点 \(u\) 是否为 \( 阅读全文

posted @ 2026-03-29 09:59 TP2010 阅读(8) 评论(0) 推荐(0)

2026年3月27日

题解：CF1806D DSU Master

摘要： DSU：并查集。拆贡献，考虑每个点对 1 号点入度的贡献。如果一个点 \(i\) 想直接接在 1 号点上，则是通过执行 \(i-1\) 做到的，且 \(1\thicksim i-1\) 的点一定接到 \(1\) 的连通块里面了，而其他的点对此过程没有影响，最后乘上排列数即可。记 \(f_i\) 阅读全文

posted @ 2026-03-27 17:16 TP2010 阅读(1) 评论(0) 推荐(0)

CF1523H Hopping Around the Array 题解

摘要：前言前置知识：ST 表，倍增，背包 DP，贪心。题目传送门解析考虑 \(k=0\) 当 \(k=0\) 时显然是可以用倍增解法的，基于贪心的想法发现每一步的最优走法唯一，所以可以直接记录下来做倍增。贪心解释最优走法就是走 \(p+a_p=\max\limits_{j\in [i,i+a_ 阅读全文

posted @ 2026-03-27 14:40 TP2010 阅读(1) 评论(0) 推荐(0)

2026年3月24日

P9399 「DBOI」Round 1 人生如树题解

摘要：前言好典呀~，一眼看出做法，但细节好烦人，还好很快调出来了，跑得很快。前置知识：\(\operatorname{LCA}\)（最近公共祖先），倍增，字符串哈希，二分。解析说下我第一眼的想法：发现这个 \(\operatorname{LRP}\) 和 \(\operatorname{LCP}\ 阅读全文

posted @ 2026-03-24 12:38 TP2010 阅读(1) 评论(0) 推荐(0)

P7357 「PMOI-1」中位数题解

摘要：前言题目传送门请注意，本题中的中位数的定义与数学中的定义略有不同：这里一个长度为 \(t\) 的序列的中位数定义为这个序列第 \(\left\lceil\frac{t+1}2\right\rceil\) 小的数。首先自嘲一下我的无知，\(\lceil x \rceil\) 是上取整，\(\lf 阅读全文

posted @ 2026-03-24 12:34 TP2010 阅读(2) 评论(0) 推荐(0)

P14580 【模板】有源汇上下界最小流题解

摘要：前置知识无源汇上下界可行流 (可以参考我的另一篇题解 )。网络流基本概念。题目传送门由于有源汇上下界最大流和最小流原理相近，本文一起介绍，加深理解。主要以有源汇上下界最大流为例。算法介绍先说具体流程：记 \(S,T\) 为超级源汇点 (用来跑无源汇上下界可行流)。加 \(t\) 到阅读全文

posted @ 2026-03-24 12:32 TP2010 阅读(1) 评论(0) 推荐(0)

P14579 【模板】有源汇上下界最大流题解

摘要：前置知识无源汇上下界可行流（可以参考我的另一篇题解）。网络流基本概念。题目传送门由于有源汇上下界最大流和最小流原理相近，本文一起介绍，加深理解。主要以有源汇上下界最大流为例。算法介绍先说具体流程：记 \(S,T\) 为超级源汇点（用来跑无源汇上下界可行流）。加 \(t\) 到 \(s 阅读全文

posted @ 2026-03-24 12:30 TP2010 阅读(0) 评论(0) 推荐(0)

2026年3月23日

P14578 【模板】无源汇上下界可行流题解

摘要：前置知识最大流算法 (EK,Dinic 等)。网络流基本概念。题目传送门算法介绍先说具体流程：读入时把 \(r_i-l_i\) 作为第 \(i\) 条边 \((u_i,v_i)\) 的边权。同时求出每个点 \(p\) 的 \(\sum\limits_{(u_i,p)\in E}l_i-\ 阅读全文

posted @ 2026-03-23 23:34 TP2010 阅读(0) 评论(0) 推荐(0)

公告