1827

不妨先考虑一个弱化版的问题，这个问题和原来的问题仅有一个区别：\(k\) 是给定整数。 称最后 \(n-k\) 个数是“特殊的”。那么我们可以注意到，每个特殊的数字的极大段必然递增放置或者递减放置。例如我们有排列 \([7,5,8,1,4,2,6,3]\) 而且 \(k=2\)，那么极大段的下标应该 ......

前情提要-三分 1827. 线段传送带 P2571 [SCOI2010] 传送带 省流：三分套三分。 在二维平面上有两个传送带，一个从 A 点到 B 点，一个从 C 点到 D 点，速度分别是 p 和 q，在平面内其他点的速度为 r。求 A 点到 D 点的最小速度。 考虑从 A 到 D 的路程一定是 ......

题目链接 点击打开链接 题目解法 首先考虑一个朴素的 \(dp\) 令 \(f_i\) 表示以 \(i\) 结尾的合法子串的个数 为了不重不漏，我们令 \(le_i\) 表示以 \(i\) 为右端点，离 \(i\) 最近的偶回文串的左端点，然后不难得到转移为 \(f_i=f_{le_i-1}+1\) ......

原题 翻译 首先，很典的，对于一个区间\([l,r]\)，他的最少操作次数为： \[r - l + 1 - \sum_{i=l}^{r-1}{[\max_{j=l}^{i}{a_j}<\min_{j=i+1}^{r}{a_j}]} \]正难则反，我们考虑先算出\(\sum_{l=1}^{n-1}{ ......

Range Sorting (Easy Version) 题面翻译 对一个数组 \(\{p_i\}\) 的一段区间 \([l,r]\) 排序的代价为 \(r-l\) ，对整个数组 \(p_i\) 排序的代价为选定若干区间并排序，使得整个数组有序的代价之和。 求 \(\{a_i\}\) 的所有子段排序 ......

Counting Orders 题面翻译 求有多少种重新排列 \(a\) 的方式，使得对于任意 \(1\le i\le n\)，都满足 \(a_i>b_i\)，结果对 \(10^9+7\) 取模。 \(1\le n\le 2\times 10^5,1\le a_i,b_i\le 10^9\)，保证 ......

[problem](https://www.luogu.com.cn/problem/CF1827D) & [blog](https://www.cnblogs.com/liangbowen/p/17541713.html)。 很好的题。用到一些关于重心的 trick。 不妨认为只有一个重心 $\t ......

# CF1827 ## A. Counting Orders 简单计数。 两个都排序，双指针维护一下 `a[i]` 在 `b[p]` 的位置（`a[i] ## C. Palindrome Partition ~~回文好题~~。 考虑利用 `Manacher` 求出每一个偶数的回文串。 > 参考：[算 ......

# CF1827题解 ### A 将$a$和$b$排序，对于每个$a_i$，可以找到最大的$j$，使得$a_i > b_j$，由于排序，这个$j$一定具有单调性，且$a_i$排列后对应的数一定是这$j$个中的一个。 又因为前面$i - 1$个数已经选了$i - 1$个$b_t，t \leq j$，（ ......

吓人题。 一个显然的想法是对于 $k$, 将贡献分为 $3$ 类 ：$[1,k]$ 子区间的贡献，$[k+1,n]$ 子区间的贡献和跨过 $k$ 的贡献。 首先 $[1,k]$ 的贡献我们可以沿用 Pudding Monsters 的做法，从左往右枚举 $r$，统计 $r$ 作为右端点的贡献。发现一 ......

CF1827E Bus Routes 很有思维含量的一道题。 任意钦定一个根 $rt$，对于每个节点，如果它不能到达，那么他的子树内所有点一定也不能到达，因此，我们只用考虑每一个叶子节点的情况。对每个叶子节点 $u$，设 $low_{u}$ 表示他能通过一条路线到达的最浅的祖先。对于任意两叶子节点， ......

# [$\color{purple}\text{Palindrome Partition}$](https://www.luogu.com.cn/problem/CF1827C) >该说不难，只待一切走上正轨。 显然我们不能枚举每个子串，所以我们考虑枚举以 $i$ 结尾的**“好的”子串**的个数。 ......

[洛谷传送门](https://www.luogu.com.cn/problem/CF1827E "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1827/E "CF 传送门") 比较神奇的题。 定一个非叶子 $r$ 为根。 显 ......

一道比较诈骗的题，放在现场最大的挑战在于做完 B2 C D 这三道不算太签的题以后还有时间开这个题。 首先特判 $n=2$。以任意一个不是叶子的点为根。那么一棵树合法，当且仅当其中所有叶子都能在 $2$ 步内互相到达，因为如果一对不能在 $2$ 步内互相到达的点 $(u,v)$ 中存在至少一个不是叶 ......

洛谷传送门 CF 传送门 考虑固定一个重心，设 $k$ 为重心最大子树大小，答案为 $n - 2k$。构造方法是往最大的子树塞叶子。 树的重心有一个很好的性质，就是加一个叶子，重心最多移动一条边的距离。简单证一下，设重心为 $x$，往儿子 $u$ 的子树中加叶子。 如果 $sz_u > \left\ ......

洛谷传送门 CF 传送门 考虑拆贡献 $i - 1 \sim i$，发现当 $[1, i - 1]$ 的最大值大于 $[i, n]$ 的最小值时 $i - 1 \sim i$ 产生 $1$ 的贡献。 考虑枚举左端点 $j$，设 $x = \max\limits_{k=j}^{i-1} a_k$。设 ......