2018-Reconquista-T33

从 Trac 迁移的文章

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

原文章内容如下:

== Contest Information ==

''' Petrozavodsk Summer 2017 - Warsaw U Contest '''

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

== 流水账 ==


== 总结 ==

=== lsmll ===
J题刚开始错误贪心做法一直没有被我和jsb看出来,后来lzw提出了反例,我才想到网络流的正解,导致这题罚时有点爆炸(我还WA样例了一次,因为测样例的时候跑错程序了)。其他来说总体还是可以?E题炸了精度是姿势水平不够,要继续学习。


=== jsb ===

H题一个裸分块竟然还卡常数是在是受不了。不过这也提示我们以后最好测一测极限数据再交;而且容斥的满数据并不是(1,10^6^),而是(10^6^-1,10^6^)。

这个J题开始搞了个看起来很靠谱的贪心,可是一直WA6,大家也看不出什么错误。
最后lsmll学长机智地换了一个优化版的网络流就过了。感觉以后也不能太自信?多用用网络流这种靠谱的东西,多证证正确性。

最后对A的配合我的还是挺不错的。lsmll学长想到了一个帅气的求答案的姿势:一个点哈希值定义为每一张图里的它的并查集的根。我再把它转化成xor值,就可以把一个点抽象成一个数,快速维护点与点之间的连通性了。然后开了个哈希动态维护,最后20min有惊无险地过了。

E题有点可惜,lzw学长最后20min写了个精度会爆炸的东西果然WA5了,然后学习了一波标程防卡精度的姿势。另:pow真的垃圾,特别是指数很小的时候(比如n的倒数)。


=== lzw ===
一开始H题有些卡,后面总体来说还行。E题推出了式子被卡精度,还是经验不足的原因,什么时候我们队能快速做出答案是实数的问题呢???

== Solution ==


== 补题 ==
B []

E [lzw]

F []

I []

== 题解 ==
[http://www.cnblogs.com/clrs97/p/7745589.html claris]

Contest Information

Petrozavodsk Summer 2017 - Warsaw U Contest

Opentrains

流水账

总结

lsmll

J题刚开始错误贪心做法一直没有被我和jsb看出来,后来lzw提出了反例,我才想到网络流的正解,导致这题罚时有点爆炸(我还WA样例了一次,因为测样例的时候跑错程序了)。其他来说总体还是可以?E题炸了精度是姿势水平不够,要继续学习。

jsb

H题一个裸分块竟然还卡常数是在是受不了。不过这也提示我们以后最好测一测极限数据再交;而且容斥的满数据并不是(1,106),而是(106-1,106)。

这个J题开始搞了个看起来很靠谱的贪心,可是一直WA6,大家也看不出什么错误。

最后lsmll学长机智地换了一个优化版的网络流就过了。感觉以后也不能太自信?多用用网络流这种靠谱的东西,多证证正确性。

最后对A的配合我的还是挺不错的。lsmll学长想到了一个帅气的求答案的姿势:一个点哈希值定义为每一张图里的它的并查集的根。我再把它转化成xor值,就可以把一个点抽象成一个数,快速维护点与点之间的连通性了。然后开了个哈希动态维护,最后20min有惊无险地过了。

E题有点可惜,lzw学长最后20min写了个精度会爆炸的东西果然WA5了,然后学习了一波标程防卡精度的姿势。另:pow真的垃圾,特别是指数很小的时候(比如n的倒数)。

lzw

一开始H题有些卡,后面总体来说还行。E题推出了式子被卡精度,还是经验不足的原因,什么时候我们队能快速做出答案是实数的问题呢???

Solution

补题

B []

E [lzw]

F []

I []

题解

claris