2018-Reconquista-T65

从 Trac 迁移的文章

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

原文章内容如下：

== Contest Information ==

''' Petrozavodsk Summer 2016 - Ural FU Dandelion Contest '''

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

== 流水账 ==


== 总结 ==

=== lsmll ===
H题卡的太伤了，从比赛开始都最后都没发现，目前也没发现什么问题...这场3题太少了，我认为我们的水平应该要至少达到4-5题。这种难的比赛一定要多补题。


=== jsb ===

感觉打得很艰辛。[[br]]
主要被坑的地方是：[[br]]
①H题之前想得太草率WA了两发。之后糊了一个感觉肯定对的做法WA14，一直在思考正确性+看代码，可是就是没发现问题，到赛后目前也没发现。[[br]]
②交互题没有给出具体的询问次数限制，我们一直在犹豫到底能猜几次。后来发现其实只要1次询问就够了>_<。[[br]]

=== lzw ===
感觉好久不训练状态下滑非常严重，想不出题。前面过题太慢了，H题到最后也没发现哪里错了，I题也没有花很多时间去想，还有很多提高的空间。

== 补题 ==
A []

C [jsb]题解：这个idea还是很不错的。[[br]]
1~x的数显然不变。变的数我们可以划成[x+1,2*x]和>2*x两部分。[[br]]
对于前者我们暴力修改；那么此时，后者那一段的相对大小不会改变，直接区间打标记即可。[[br]]
前面暴力部分，每个数每次至少/2，所以最多NlogN次。这样我们实时维护好了按key值排序的平衡树，询问时直接ask即可。[[br]]

D []

E []

F []

H [jsb]

I [jsb]

K []

== 题解 ==
[https://www.cnblogs.com/clrs97/p/6809850.html Claris]

Contest Information

Petrozavodsk Summer 2016 - Ural FU Dandelion Contest

Opentrains

流水账

总结

lsmll

H题卡的太伤了，从比赛开始都最后都没发现，目前也没发现什么问题...这场3题太少了，我认为我们的水平应该要至少达到4-5题。这种难的比赛一定要多补题。

jsb

感觉打得很艰辛。[[br]]

主要被坑的地方是：[[br]]

①H题之前想得太草率WA了两发。之后糊了一个感觉肯定对的做法WA14，一直在思考正确性+看代码，可是就是没发现问题，到赛后目前也没发现。[[br]]

②交互题没有给出具体的询问次数限制，我们一直在犹豫到底能猜几次。后来发现其实只要1次询问就够了>_<。[[br]]

lzw

感觉好久不训练状态下滑非常严重，想不出题。前面过题太慢了，H题到最后也没发现哪里错了，I题也没有花很多时间去想，还有很多提高的空间。

补题

A []

C [jsb]题解：这个idea还是很不错的。[[br]]

1~x的数显然不变。变的数我们可以划成[x+1,2*x]和>2*x两部分。[[br]]

对于前者我们暴力修改；那么此时，后者那一段的相对大小不会改变，直接区间打标记即可。[[br]]

前面暴力部分，每个数每次至少/2，所以最多NlogN次。这样我们实时维护好了按key值排序的平衡树，询问时直接ask即可。[[br]]

D []

E []

F []

H [jsb]

I [jsb]

K []

题解

Claris