CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

====== 个人总结 ======
===== 陈铭煊 Max.D. =====

本周学习了一点计算几何，带花树算法，补了两次牛客竞赛的题各两道。其他暂无。


===== 龙鹏宇 Hardict =====

复习了下最大流的最大权闭合子图

复习min25筛
===== 肖思炀 MountVoom =====

本周主要做了两场牛客，和zzh队一起训练了一套区域赛。

自己随便做了点cf，这周学的有点少。
====== 本周推荐 ======
===== 陈铭煊 Max.D. =====

暂时没有好题，推荐两篇之前看过的文章，讲的是回文自动机和border原理的。

[[https://zhuanlan.zhihu.com/p/93152631|最小回文划分]]

[[https://www.cnblogs.com/Parsnip/p/12426971.html|Border Series在回文自动机上的运用]]

===== 龙鹏宇 Hardict =====

一道网络流的题，利用割来构造各种状态

最小割=最大流求最优解https://vjudge.net/contest/383596#problem/D

min25筛的一道https://vjudge.net/contest/361072#problem/E
===== 肖思炀 MountVoom =====

[[https://codeforces.com/contest/1375/problem/E|E. Inversion SwapSort]] : 构造

题意:

给定一个数组，对它所有逆序对的位置规定一个顺序，按照这个顺序交换以后使得数组的不严格单增的。数组长度不超过$10^3$

题解：

考虑数组为长度为$n$的排列的情况，不是排列可以等价的转换为一个排列。

设逆序对为$(u, v)$，考虑先处理$v = n$的情况，看这样如果处理完成后是否能得到一个不影响结果的但是规模更小的问题。

考虑现在比$a[n]$大的数，如果我们按照比它大的数从小到大与它进行交换，相当于把$n$放到了最后一个位置上，前面比它大的数-1，问题的规模就变小了而且对结果没有影响。

实现是直接对逆序对排序即可。

commet：

开始考虑的是把最大的数和后面的数交换，但是这样可能会引起交换的混乱，不变的是逆序对的位置，而位置上的值一直在变化，应该从不变的位置入手而不是从值入手，逐步减小问题规模从而将问题解决。
CVBB ACM Team

用户工具

站点工具

页面工具
