2018-Reconquista-T124

从 Trac 迁移的文章

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

原文章内容如下：

== Contest Information ==

''' 2011 ICPC - World Finals '''

[https://codeforces.com/gym/101175 CF Gym]

== 流水账 ==


== 总结 ==

=== lsmll ===
这次中前期都很不错...?但是后面第8题的时候由于我和jsb交流有些问题导致一个关键条件没有理解清楚，lzw也没有认真看题，所以就爆炸了...感觉第一，以后我们三个打比赛都要更专注一点；第二，以后大家写题前都要自己看一遍题目，我目前是有这样的习惯的，我觉得一般情况下还是应该这样做的，除非时间特别紧。

=== jsb ===


=== lzw ===
颜学长说的很有道理，写题前还是大致看一看题目，尤其是从队友那里听来的题意。这个B题一上来就被带入了大致做法里，没有自己思考过。

== 补题 ==
B [lzw]

D []

G []

I []

== 题解 ==

A: 一个数x经过某个a和m构成的操作序列之后，大致会变成x*m^k^ + a * sigma {b_i * m^i^}，k是m的个数。 枚举m，限制转化为a * sigma {b_i * m^i^} 在某个区间内。sigma部分看做一个m进制数，序列长度最小就是b_i的和尽可能小，字典序最小就是b_i高位尽可能大。 贪心填就好了。

B: 首先平移+放缩完全可以由放缩+平移替代。 先枚举旋转方式(a, b)，然后枚举对应关系，就可以解出(放缩量，平移量)的方案是无解还是单解还是多解，如果多解那么肯定是inconsistent solution。最终的三个点互不相同，旋转完之后对应方式实际上只会有一种。旋转方式(a, b, scale, translate) = (-a, -b, -scale, translate)，consistent solution只可能是这样的2个解。 

C: 根据每个图形包含的空白联通块个数判断。

E: 曼哈顿距离转化成切比雪夫距离，变成矩形加，二维差分一下就知道每个点能走到多少个邮局了。

F: 按Di排序，F_i 表示在Di天最多能有多少钱。 列一下式子就可以发现是个斜率式子，cdq一下就好了。

H: 先BCC缩点，BCC构成的树，每个叶子节点放一个特殊点就好了（割点不能放）。 特判只有一个BCC的情况。

J: 金字塔种类只有200种左右，直接背包，输出方案似乎有什么trick。

K：求个凸包，暴力枚举求最远距离。


 http://www.csc.kth.se/~austrin/icpc/finals2011solutions.pdf

Contest Information

2011 ICPC - World Finals

CF Gym

流水账

总结

lsmll

这次中前期都很不错...?但是后面第8题的时候由于我和jsb交流有些问题导致一个关键条件没有理解清楚，lzw也没有认真看题，所以就爆炸了...感觉第一，以后我们三个打比赛都要更专注一点；第二，以后大家写题前都要自己看一遍题目，我目前是有这样的习惯的，我觉得一般情况下还是应该这样做的，除非时间特别紧。

jsb

lzw

颜学长说的很有道理，写题前还是大致看一看题目，尤其是从队友那里听来的题意。这个B题一上来就被带入了大致做法里，没有自己思考过。

补题

B [lzw]

D []

G []

I []

题解

A: 一个数x经过某个a和m构成的操作序列之后，大致会变成x*m^k + a * sigma {b_i * mⁱ}，k是m的个数。 枚举m，限制转化为a * sigma {b_i * mⁱ} 在某个区间内。sigma部分看做一个m进制数，序列长度最小就是b_i的和尽可能小，字典序最小就是b_i高位尽可能大。 贪心填就好了。

B: 首先平移+放缩完全可以由放缩+平移替代。 先枚举旋转方式(a, b)，然后枚举对应关系，就可以解出(放缩量，平移量)的方案是无解还是单解还是多解，如果多解那么肯定是inconsistent solution。最终的三个点互不相同，旋转完之后对应方式实际上只会有一种。旋转方式(a, b, scale, translate) = (-a, -b, -scale, translate)，consistent solution只可能是这样的2个解。

C: 根据每个图形包含的空白联通块个数判断。

E: 曼哈顿距离转化成切比雪夫距离，变成矩形加，二维差分一下就知道每个点能走到多少个邮局了。

F: 按Di排序，F_i 表示在Di天最多能有多少钱。 列一下式子就可以发现是个斜率式子，cdq一下就好了。

H: 先BCC缩点，BCC构成的树，每个叶子节点放一个特殊点就好了（割点不能放）。 特判只有一个BCC的情况。

J: 金字塔种类只有200种左右，直接背包，输出方案似乎有什么trick。

K：求个凸包，暴力枚举求最远距离。

http://www.csc.kth.se/~austrin/icpc/finals2011solutions.pdf