2018-Reconquista-T58

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== Contest Information ==

''' Petrozavodsk Summer 2011 - Andrew Stankevich Contest 40 '''

[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010152 Opentrains]

== 流水账 ==


== 总结 ==

=== lsmll ===
总体来说还是不错的，不过一方面也是由于这场不是很难...?早期的ASC好像都不难，这场是2011年的...可以提高之处感觉是A题花的时间太长了，很早就开始写，后来等我过了C才过...最后J没出来比较可惜...

=== jsb ===

bilibili [[br]]
以前训练时，遇到凸包删两个点的题，当时口胡通过了。A题是删一个点，感觉写起来挺稳的，中期就上机了。没写过不知道，其实还是有很多细节的（特别是，本题是计算凸包上点的个数，共线的情况要特判，凸包退化的情况也要特判）。看了半天没看出错，一拍就拍出来过了。[[br]]
题目比较水，也没啥好说的。最后J题我上去写了个爆搜部分，最后没过感觉还是有点可惜。

=== lzw ===
A题jsb WA掉了，其实应该早点对拍的，因为对拍只要求个凸包，是原问题的一个子函数，结果两个人在边上看了半天代码，早点对拍罚时可以优秀一点。最后J题没过，有些可惜，再多出半个小时应该稳的。


== 补题 ==

D []

J [lsmll+jsb]


== 题解 ==
 * [A by jsb] 先建出凸包。显然只有删在凸包上的点答案才可能改变。枚举删除一个点i，然后把x轴在它凸包上相邻点之间的所有点都拎出来暴力再跑一遍，看看加了几个点即可。这样暴力做复杂度是对的，因为每个点只会被上下凸壳各扫到两次。具体实现的话，每次看看i是上凸壳还是下凸壳，暴力重建的时候也要是对应的凸壳。如果i是最左侧或最右侧的点，特判起来比较麻烦，不如此时暴力把剩下所有点重新跑一跑。

 * [B by jsb] 假设我们知道了原始串的一个后缀，而且该后缀不为全0。每次我们决策最后一个没填数字的位置i填什么。一通分析发现，若rk[i]<rk[i+1]必然不能填1，反之必然不能填0（注意这只是必要条件，构出来后还要check一下）。然后再考虑原串的rk数组。比如其为?,?,?,x(x>4),3,2,1]（即我们找到一段从结尾开始极长的从1开始的连续串），一通分析发现，最后三位必然是填0；而且倒数第四位必然是填1。而既然已经填了1，就可以套用之前的做法了。

 * [C by lsmll] 首先先要求最近点对，表示一开始没有移动的情况。然后移动过程中的话按照方向旋转坐标系（共6种情况）全部转化为一些不动一些向下运动，然后对于每个不动的点求出在它上面向下运动点里x坐标最接近它的更新答案。

 * [E by lzw] A最多不超过100，枚举A, f[i][j][k]表示前i个party, sigma ai = j, sigma bi = k的最小代价，dp一下就好了。

 * [F by lzw] 暴搜了一下长度<=20的解很少，大概只有十几个。所以每次从长度为i的解出发搜索出长度为i+1的解就好了。 

 * [G by lsmll] 由于边的流量都是1，很显然f(A)=1时最优。所以直接最短路即可。

 * [H by jsb] 用py打个表即可。[[br]]

 * [I by lzw] 考虑+(x, y) -(x, y)这一对操作的贡献，其实就是统计它们之间有多少个!x，多少个!y。随便数据结构或者啥的搞一搞就好了。 [[br]]

Contest Information

Petrozavodsk Summer 2011 - Andrew Stankevich Contest 40

Opentrains

流水账

总结

lsmll

总体来说还是不错的，不过一方面也是由于这场不是很难...?早期的ASC好像都不难，这场是2011年的...可以提高之处感觉是A题花的时间太长了，很早就开始写，后来等我过了C才过...最后J没出来比较可惜...

jsb

bilibili [[br]]

以前训练时，遇到凸包删两个点的题，当时口胡通过了。A题是删一个点，感觉写起来挺稳的，中期就上机了。没写过不知道，其实还是有很多细节的（特别是，本题是计算凸包上点的个数，共线的情况要特判，凸包退化的情况也要特判）。看了半天没看出错，一拍就拍出来过了。[[br]]

题目比较水，也没啥好说的。最后J题我上去写了个爆搜部分，最后没过感觉还是有点可惜。

lzw

A题jsb WA掉了，其实应该早点对拍的，因为对拍只要求个凸包，是原问题的一个子函数，结果两个人在边上看了半天代码，早点对拍罚时可以优秀一点。最后J题没过，有些可惜，再多出半个小时应该稳的。

补题

D []

J [lsmll+jsb]

题解

  • [A by jsb] 先建出凸包。显然只有删在凸包上的点答案才可能改变。枚举删除一个点i，然后把x轴在它凸包上相邻点之间的所有点都拎出来暴力再跑一遍，看看加了几个点即可。这样暴力做复杂度是对的，因为每个点只会被上下凸壳各扫到两次。具体实现的话，每次看看i是上凸壳还是下凸壳，暴力重建的时候也要是对应的凸壳。如果i是最左侧或最右侧的点，特判起来比较麻烦，不如此时暴力把剩下所有点重新跑一跑。
  • [B by jsb] 假设我们知道了原始串的一个后缀，而且该后缀不为全0。每次我们决策最后一个没填数字的位置i填什么。一通分析发现，若rk[i]4),3,2,1]（即我们找到一段从结尾开始极长的从1开始的连续串），一通分析发现，最后三位必然是填0；而且倒数第四位必然是填1。而既然已经填了1，就可以套用之前的做法了。
  • [C by lsmll] 首先先要求最近点对，表示一开始没有移动的情况。然后移动过程中的话按照方向旋转坐标系（共6种情况）全部转化为一些不动一些向下运动，然后对于每个不动的点求出在它上面向下运动点里x坐标最接近它的更新答案。
  • [E by lzw] A最多不超过100，枚举A, f[i][j][k]表示前i个party, sigma ai = j, sigma bi = k的最小代价，dp一下就好了。
  • [F by lzw] 暴搜了一下长度<=20的解很少，大概只有十几个。所以每次从长度为i的解出发搜索出长度为i+1的解就好了。
  • [G by lsmll] 由于边的流量都是1，很显然f(A)=1时最优。所以直接最短路即可。
  • [H by jsb] 用py打个表即可。[[br]]
  • [I by lzw] 考虑+(x, y) -(x, y)这一对操作的贡献，其实就是统计它们之间有多少个!x，多少个!y。随便数据结构或者啥的搞一搞就好了。 [[br]]