Codeforces Round #740 部分题解

题目评分：

Div.2 D/Div.1 B Up the Strip

Solution

设 $f_i$ 表示从 $n$ 到 $i$ 的方案总数。

使用减法转移的话，也就是 (f_i=f_i+sum_{j=i+1}^n f_j)。

而使用除法，考虑填表法，考虑一个除数 (d)，那么能够被影响的是 ([di,di+d-1]) 这样一个区间。

发现这两个东西都可以后缀和优化，所以减法转移可以做到 (O(1))，而除法呢，容易发现这是个调和级数 (O(log n)) 的。

Solution

强构造，不过我是傻逼没想到突破口。

先考虑判无解，容易发现翻转不改变某个数所在位置的奇偶性，可以直接判无解。

操作步数为 (frac 5 2n)，这启示我们，对于每一个数对 ((i,i+1))，使用 (5) 次操作把他丢到对应的位置。

比如序列 (1,6,4,5,3,7,2)，我们想要将 (6,7) 放到最后，考虑如下方案：

操作奇数所在的位置，即 (6)，序列变为 (color{red}{7}color{black},3,5,4,color{red}{6}color{black},1,2)。
操作偶数所在位置的前一位，即 (4)，序列变为 (color{black}4,5,3,color{red}7color{black},color{red}6color{black},1,2)。
操作偶数所在位置的下一个位置，即 (6)，序列变为 (color{black}1,color{red}6color{black},color{red}7color{black},3,5,4,2)。
操作奇数所在位置，即 (3)，序列变为 (color{red}7color{black},color{red}6color{black},1,3,5,4,2)。
逆转整个序列，序列变为 (color{black}2,4,5,3,1,color{red}6color{black},color{red}7)。

按照这个方式模拟整个过程即可，时间复杂度 (O(n^2))。

Solution

数据结构与组合的精妙结合。

发现最后的序列顺序是确定的，比如 (a_1le a_2le a_3)，容易发现如果只有 (le) 可以直接隔板出答案。

但是会有插入的情况，如果发生一次形如 ((x,y)) 的插入，意味着 (a_x<a_y)。

那么，依据隔板法，总的方案数为 (inom{2*n-1-c}{n})，其中 (c) 表示 (<) 的个数。

考虑维护这个 (<)，一个数前面是 (<)，那么一定有数被插入到了前面，考虑维护一个集合 (S)，初始时里面被放进了 (1sim n)。

倒序处理每一个插入，对当前插入，设排名为 (y_i) 的数为 (p)，排名为 (y_i+1) 的数为 (q)，删除 (p) 并为 (q) 打上标记，最后 (c) 即为打上标记的数的个数。

使用线段树上二分，时间复杂度 (O(mlog n))，注意别写成了 (O(nlog n))。

Solution

*3000 神题。

考虑二分答案转化成判定性问题，好了现在问题变成给定一个 (x)，问能否走完。

如果没有第三个条件，直接贪心，爽哉，傻逼题！！！！1

完了，有了第三个条件怎么做，我只好自闭。

考虑我们现在已经走过的点集为 (S)，考虑现在这些点中开始 BFS 找路，发现合法的路径要么是一个 ( ho) 形，要么是一个走出去再走回 (S)，这两都可以在 BFS 中找出来。

那么，做 (n) 次 BFS，每次扩展 (S)，在 (S) 大小为 (n) 时就发现有解。

每次 (S) 至少增加 (1)，那么时间复杂度就是 (O(n^2log v)) 的，实际上可能完全跑不满。