1830
CF1830E Bully Sort
我永远喜欢数据结构。 洛谷 CF 对于一个排列 \(P_1\sim P_n\)，定义 \(f(P)\) 为重复执行以下操作直至将其升序排序的操作次数： 找到一个位置 \(i\)，使得其是满足 \(P_i\ne i\) 的位置中 \(P_i\) 最大的那个位置。 找到一个位置 \(j\)，使得其是满足 ......
CF1830B
The BOSS Can Count Pairs 题面翻译 多组数据。 每组数据给你一个 \(n\) 和两个序列 \(a,b\)。 求有多少个数对 \((i,j)\) 满足 \(1 \le i < j \le n\) 且 \(a_i \times a_j = b_i + b_j\) 题目描述 You ......
【题解】CF1830D Mex Tree
我们考虑这道题一看题就特别难受，所有路径？\(mex\) 之和？这是什么东西？ 我们考虑 \(mex\) 之和其实是有一点诈骗的感觉，毕竟是 \(0\) 或 \(1\)，还比较简单。就是路径上全都是 \(1\) 的时候是 \(0\)，全都是 \(0\) 的时候是 \(1\)，有 \(0\) 和 \( ......
【题解】CF1830E Bully Sort
考虑一次交换，我们发现，被选出来的 \([i,j]\) 的区间里 \(p_i\) 一定是最大的，\(p_j\) 一定是最小的。 然后我们会发现，我们原序列的逆序对数量会减少 \(2(j-i) - 1\)，而 \(\sum|p_i-i|\) 会减少 \(2(j-i)\) 那么答案就是原序列的两部分相减 ......
【题解】CF1830C Hyperregular Bracket Strings
我们知道，一个长度为 \(n\) 的合法括号序列的种数就是第 \(\frac n 2\) 个卡特兰数（当然 \(n\) 是奇数答案肯定就是 \(0\)） 我们可以发现一件事情，如果两个区间相互包含，那么就可以将大区间分为中间被包含的小区间的部分和外面没有被小区间覆盖的部分。 如果两个区间相交，那么就 ......
【题解】CF1830B The BOSS Can Count Pairs
你考虑，我们观察数据范围，发现可以是 \(O(n\sqrt n) / O(n\log n)\) 的，我们又看到乘法，便有几个大概的想法： 数论分块 \(O(\sqrt n)\) 枚举其中一个乘数 还有什么……（笔者学识浅陋，读者可以帮忙补充） 我们可以找到两种 \(O(n^2)\) 做法： \(O( ......
【题解】CF1830A Copil Copac Draws Trees
你考虑对于每一条边打上时间标记，然后在树上 `DFS` 的时候维护一下以 $u$ 为根的答案即可，然后将答案合并，反正很简单，看代码就懂。 **code:** ```cpp #include using namespace std; const int NN = 2e5 + 8; int t,n; ......
9.6 CF1830 题解
# 9.6 CF1830 题解 ## A. Copil Copac Draws Trees [链接](https://www.luogu.com.cn/problem/CF1830A) 真弱智题不用讲 ## B. The BOSS Can Count Pairs ### 题意 每组数据给你一个 $n ......
[CF1830E] Bully Sort
## 题目描述 On a permutation $ p $ of length $ n $ , we define a bully swap as follows: - Let $ i $ be the index of the largest element $ p_i $ such that ......
[CF1830D] Mex Tree
## 题目描述 You are given a tree with $ n $ nodes. For each node, you either color it in $ 0 $ or $ 1 $ . The value of a path $ (u,v) $ is equal to the ME ......
[CF1830D] Mex Tree
[CF1830D](https://www.luogu.com.cn/problem/CF1830D) 贪心地想,黑白交替染色,这样每条大于1的路径的值都为2。但有些情况不优,树的形态是两棵子树中间由一条边相连,这样的最优方案是这条边上两点染1,其余点染0。 并且我们发现只用把每个同色连通块的贡献算 ......
[CF1830F] The Third Grace
## 题目描述 You are given $ n $ intervals and $ m $ points on the number line. The $ i $ -th intervals covers coordinates $ [l_i,r_i] $ and the $ i $ -th ......
CF1830C
[原题](https://codeforces.com/contest/1830/problem/C) [翻译](https://www.luogu.com.cn/problem/CF1830C) 前置知识：$catalan$数 首先我们先考虑如果没有线段怎么做 我们容易发现如果$n$为奇数肯定无解 ......
CF1830B
[原题](https://codeforces.com/contest/1830/problem/B) [翻译](https://www.luogu.com.cn/problem/CF1830B) 感觉挺好的题，但说不定挺典的？ 我一开始想到了值域分块的思路，但之后就一直想整除、余数组合之类的。~~ ......
P1830题解
### 思路： - 利用桶存储轰炸区域，双重循环。 - 在存储轰炸区域时将次数刷新，也就是`pos[j][k]=i;`。 下面是核心代码： ```cpp for(int i=1;i>x1>>y1>>x2>>y2; for(int j=x1;j<=x2;j++) { for(int k=y1;k<=y ......
Codeforces 1830E - Bully Sort
这种题肯定首先要**寻找不变量**。 显然后面排好序的后缀不会被改变。因此从整体上来看我们的流程肯定是，如果当前 $p_n=n$，就令 $n$ 减一，否则你一步换的 $i$ 肯定满足 $p_i=n$。而显然 $\min\limits_{j=i}^np_j\le i$，因此我们考察 $\sum|i-p ......
题解 CF1830C【Hyperregular Bracket Strings】
给定一个长度 $n$ 和 $k$ 个子区间 $\{[l1,r1],[l2,r2],…,[lk,rk]\}$。
问有多少个长度为 $n$ 的合法括号序列，使得每一个子区间也是合法的括号序列。
$n,k\leq 2^{18}$。 ......
CF1830E Bully Sort
[题面传送门](https://www.luogu.com.cn/problem/CF1830E) 我们考虑选中的 $i$，这个位置一定是 $p_i>i$，它想要往后走。而和它交换的 $j$，因为 $\leq i$ 的有 $i$ 个数，现在第 $i$ 个位置已经被 $p_i$ 占据了，所以 $\le ......
CodeForces 1830D Mex Tree
[洛谷传送门](https://www.luogu.com.cn/problem/CF1830D "洛谷传送门") [CF 传送门](https://codeforces.com/contest/1830/problem/D "CF 传送门") 考虑答案的下界。 对整棵树进行二分图染色，我们得到答案 ......
CodeForces 1830C Hyperregular Bracket Strings
[洛谷传送门](https://www.luogu.com.cn/problem/CF1830C "洛谷传送门") [CF 传送门](https://codeforces.com/contest/1830/problem/C "CF 传送门") 每一步思路都非常自然的题。 考虑先从一些简单的 cas ......