Solution Set -「ABC 217」
大家好屑兔子又来啦!
【A - Lexicographic Order】
说个笑话,\(\color{black}{\text{W}}\color{red}{\text{alkingDead}}\) 和 \(\color{black}{\text{O}}\color{red}{\text{neInDark}}\) 在这题各罚了两次时,我因为不会所以没有被罚。
【B - AtCoder Quiz】不会。
【C - Inverse of Permutation】不会。
【D - Cutting Woods】
我本来不会的,但上次都是从 D 开始讲的所以就……
用 std::set
维护切割点,标记 \(x\) 所在段的长度就是它在集合里的后继减去前驱。
- 参考代码。
【E - Sorting Queries】
讲个笑话,我以为 std::merge
的复杂度是较短容器的长度。
基础的势能算法吧,用 std::multiset
维护前缀有序段,用队列维护其他无序元素。进行排序操作时暴力把队列全部塞到 set 里即可。
- 参考代码。
【F - Make Pair】
讲个笑话,我一度想要优化一个睿智的 \(\mathcal O(n^4)\) DP。
看到“相邻配对删除”,应该想到区间 DP,并且利用“在某一时刻相邻而现在不相邻”这一条件将序列划分为独立子问题。
令 \(f(l,r)\) 表示将区间 \([l,r]\) 内的人全部配对的方案数(那么自然需要 \(2\mid(r-l+1)\))。转移时枚举与 \(l\) 配对的人 \(i\),得到转移
\]
其中有边界 \(f(i,i+1)=1\)。组合数对应这个计数场景:“左边有 \(a\) 次操作,右边有 \(b\) 次操作,\((l,i)\) 还有一次配对操作,且必须在左边 \(a\) 次完成后进行”,那么把这一次归类为第 \(a+1\) 次左边操作,方案数即为 \(\binom{a+1+b}{b}\)。复杂度为 \(\mathcal O(n^3)\)。
- 参考代码。
【G - Groups】
为什么 G 永远比 F 简单,永远是计数问题,永远存在更优秀的多项式算法。(其实上次就不是。
还是想象成把球(人)放进盒子(组)里会比较舒服。我们忽略掉题目中要求“盒子相同”“盒子非空”的要求之后,会发现此时的方案数就是组合数的若干次方。具体地,我们能求得 \(f_i\) 表示将这些球放进至少 \(i\) 个盒子里,且非空的盒子本质不同的方案数,有
\]
其中 \(A_n^m=\binom{n}{m}m!\) 即 \(n\) 个里选 \(m\) 个排列的方案数,\(n<m\) 时值为 \(0\)。
此后,令答案为 \(g_i\),根据组合意义(我当时随便凑了几个式子过样例就交了√),可以得到 \(g\) 的表达式
\]
由于是 ABC,直接递推出这个东西就可以 \(\mathcal O(n^2)\) 求解了。
不过,显然可以用分治 FFT 优化至 \(\mathcal O(n\log^2 n)\)。我写出来大概是十倍速度。但是最优解貌似是 \(\mathcal O(n\log n)\),仅用一次卷积的做法,有空研究√
UPD: 谢谢,移项之后就是 \(e^x G=F\) 了,确实可以直接卷,我是屑。
【H - Snuketoon】
令 \(f_i(x)\) 表示前 \(i\) 次射击后,站在 \(x\) 位置,受到的最小伤害。注意水枪伤害的性质,我们断言 \(f_i(x)\) 的是下凸的。虽然不难证明,但的确是本题的重点。
所以,可以用两个 std::multiset
维护左半凸壳和右半凸壳的转折点,并保证转折点两侧的斜率差为 \(1\)(所以需要维护重点)。那么转移过程中,我们需要完成一次整体取邻域最小值和叠加一段斜率为 \(\pm 1\) 的一次函数。维护一下就好√
- 参考代码。
最新文章
- 希尔排序(java)
- 手把手教你编写Logstash插件
- Chrome Dev Tools :成为更高效的开发人员
- SharpGL学习笔记(十四) 材质:十二个材质球
- Munin监控的安装与配置
- [改善Java代码]频繁插入和删除时使用LinkedList
- Linux 下Nginx 的安装及负载均衡的简单配置
- Flask 扩展 Flask-PyMongo
- 微机原理基础(四)—— MSC51
- 双目立体匹配——归一化互相关(NCC)
- CoreException: Could not get the value for parameter compilerId for plugin execution default-compile Maven项目pom文件报错,插件引用不到
- Mac 10.8.5 上运行cgi
- Linux学习笔记3
- ES6中新添加的Array.prototype.fill
- Cropper
- 关于object-c类目的理解
- MNIST数据集分类简单版本
- hdoj-3342-Legal or Not(拓扑排序)
- 如何用php实现qq登陆网站
- 【【henuacm2016级暑期训练】动态规划专题 I】Gargari and Permutations