2015-10-30 18:30:00 ~ 2015-10-30 22:00:00
"同桌的你"杯第二弹，CYD大神和XHY同学送温暖啦！ 为了让大家体验打表的快乐，增加联赛的信心，这场比赛的所有题目都是这样： 输入一个正整数，输出一个非负整数。 分送得哗啦哗啦的，绝对良心，绝对温暖~
赛后有题解哦 邀请码：7230 /----------以下为说明----------/ 1.第一题可能有点晕，你们可以把环断成链考虑，最后答案减一。 2.这是乐多赛，得分=测试得分*(0.95^提交次数)，建议不要重复提交同样的程序。 3.第一题的伤痕是直线（曲面上的直线），注意多线共点的情况
/----------以下为题解----------/ 1.心碎 40%：手玩，打表 70%：我们发现，分的块数=N+交点个数。如果不考虑多线共点，交点个数恰好为逆序对数。我们构造一个排列{Ai}，则多线共点的条件为Ai中存在三个或以上元素在同一个等差数列的对应位置上。 于是，在构造的过程中，可以从中间选择一段移到最前面。设f(i)表示i个点由于多线共点至少损失的逆序对个数，则f(i)=min{f(j)+f(k)+f(i-j-k)}.O(n^3) 100%：在70%的基础上，设立数组g(i)表示f(j)+f(i-j)的最小值，则刚才的方程转化为f(i)=min{g(j)+f(i-j)}.O(n^2) 彩蛋：OEIS大法好！把前几项输进OEIS，容易得到规律：答案=|n*n/2|+1. 2.排版 30%：手玩 70%：显然，照片排列可以划分为两部分，所以可以DP。用f[i]存储i张照片的所有可能排出的矩形一边的长，和对应的最小旋转张数。 枚举j，枚举边长，在f[j]和f[i-j]中寻找可以合并的，合并。O(n^3) 100%：用桶记录f[i]中的元素。边长最多只有sqrt(N)种。O(n^2.5) 彩蛋：直接输出0，得65分。 3.报纸 30%：手玩 60%：这是一个经典的算法，像国际象棋棋盘一样黑白染色，相邻不同色点若都有答案，则连边，二分图匹配。O(n^4) 100%：稍微优化一下构图，然后……暴力出奇迹！拼的是RP！O(n^3*RP) 彩蛋：贪心。对于每个点，拍一张照，如果与它相邻的点也有答案，那么覆盖掉。有多个时随便选一个。这样似乎能得90分。
真心送温暖！写三个彩蛋算法能得到255分，满分的85%！ 祝大家NOIP2015 RP++！