这类题我怎么都做不出来。猜也猜不到，证也证不来。。。 dalao 们有什么好办法吗？

难度定位：洛谷上的绿到紫，CF 2100 到 2700

``` 3 2 B<A C<A ``` 应该输出 ```Sorted sequence cannot be determined.```。 我输出：```Sorted sequence determined after 2 relations: BCA```。

## 前言 好题，实在是一道很好的数学题。 本文主要参考了 [这篇题解](https://www.luogu.com.cn/article/bj8tcza8)。 ## 思路 看到这种题，特别是和因数相关，就可以往质数这一块多想想。 下面要证明一些定理。 >引理 1：对于合数来说，$2$ 永远是满足条件的生成器。 > >…

## 前言 什么最小割、最大权闭合子图之类的，我不知道啊。就是二分图的最大独立集呀。 ## 思路 先考虑每一个数。 数与数之间互不干扰，数位与数位之间也互不影响。只有数与数位会互相影响。二分图？ 建一张二分图，左侧为 $n$ 个数，右侧为 $60$ 个二进制位。考虑连边。如果一个数 $a_i$ 二进制下的第 $j$ 位…

在文章《题解：CF2028E Alice's Adventures in the Rabbit Hole》发表评论：

%%%

在讨论《建议修改翻译》回复：

@[Maxmilite](luogu://user/274993)

在讨论《建议修改翻译》回复：

@[realskc](luogu://user/35672)

在讨论《建议修改翻译》回复：

还有我该 @ 谁？

"If there are multiple answers, you may output any of them" 。 这句话指输出**任意一个**解，**而非最小解**。

```cpp #include using namespace std; int n,m,q; const int N=5e5+10; struct tree{ int l,r; int up,down; long long num; }tr[N c.up){ a.up=b.up; a.down=b.down-c.up…

## 前言 一道很好的 dp + 最短路/01-bfs 练习题。 ## 思路 看到最优性问题，应该快速想到 dp。 首先可以发现：我们只用去枚举安全岛，不用把所有路口都枚举一次。为什么？ 1. 开始和结尾都保证是安全岛。 2. 能否移动的条件只和是不是安全岛有关。 3. 安全岛之间的移动距离显然可以算出来。 因此，只需…

随机化是个好东西。 看到没有奇环，可以想到二分图。 想到二分图，就可以想到染色法。 因此，$u \to v$ 当且仅当两个点颜色不同。 但题目中一点关于颜色的信息都没有，怎么办？ 还有**随机化**！ 随机给每一个点分配颜色即可。 然后就是 dp： $$ dp_{i,st}=\min_{col_i \ne col_j}…

算多维最短路的模板了吧。 类似于 dp，维护三个状态： - $u$：遍历到了那个点。 - $sc$：对于第奇数条边（奇数特指已选了奇数条边），该边权值。 - $now$：当前是第奇/偶次选择。 以下设 $dist$ 为最短路数组，$w_{a,b}$ 指 $a \to b$ 的边权。 转移： $$ dist_{j,w_{…

看到和边以及连通性相关，自然可以想到边双连通分量，所以先跑一边 tarjan 再说。 下面的图都是指缩点后的图。 因为**连接了所有电网**，因此图连通，不用考虑含有多个连通块的情况。 考虑一下什么情况无解。显然是一条链。你只要首尾连接一下就是一个环了，删哪个边都没用了。 再思考一下，发现它具有二段性。如果你删除权值在…

在文章《【解题报告】CF2042F Two Subarrays》发表评论：

dalao，对于b数组应该怎么处理？WA了好多次了...

在文章《退役了，这份重担我终究是放下了》发表评论：

祝好

### 思路 这道题的思路是这样的： 1. 从 $1 \to n$ 遍历。 2. 找到序列中**位置最靠后的一个零，该位置上的数即为我们当前遍历的数**。 3. 将该位置删除。 4. 减去该位置上的数对之后的数的贡献。 然后逐个来解释（第一个略过）。 - 考虑简单证明一下第二个。 设当前遍历的数为 $i$，当前找到的位…

在文章《题解：CF1239C Queue in the Train》发表评论：

@nkhuangyuxuan 蒟

## 前言 奇怪的 STL 应用题，但说实话比较考验思维。 ## 思路 显然，对于每一个时刻，都有这三类人： - $noidea$：还没有进入等待队列的想法（就是没有到去接水的时间）。 - $want$：想去接水但是不能到队列里面去。 - $wait$：已经在等待的队列里面了。 对于第一个，我们用一个小根堆，来存他们想…

update：发现写的有点简单，就多加了一点文字的描述。 ### 思路 折半搜索模版题（之前确实没接触过）。 简单来说，就是分两段来搜索（当然有的时候并不是非要等分，一般两边均值是最佳的），然后**用排序加二分或双指针来处理**。 这道题大致思路是这样的： - 先去搜一下行的被选的状态，中途用一个数组来记录一下哪些行是…

## 前言 今天五道题只 A 了一道题，做得不是很好。 做题的时候感觉这些题有点难度，但下来发现其实都不是很难（除了第四道题考察的算法确实没学过）。 这次感觉时间分配得不是很好，第三道题花了太多时间（结果发现推了一个多小时的性质时间的），导致简单一点的第五道题都没怎么去看，看来下一次必须要调整一下策略来做更多的题。 感…

在讨论《求推性质的题》回复：

@[Ice_lift](luogu://user/857626) thx. 绝对是大佬

别太难就可以（早上发结果没人理）。

别太难就可以

在文章《题解：P11511 [ROIR 2017 Day 2] 大型直线对撞机》发表评论：

%%%

在讨论《急需一些推性质的题》回复：

已关

在讨论《急需一些推性质的题》回复：

@[tybbs](luogu://user/527303)

在讨论《急需一些推性质的题》回复：

@tybbs thanks

rt，感觉练的题难度上来之后推性质也越来越重要。