2018-Sp04-lyk

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(1.JPG,500px)]]

[http://10.71.10.90/pia/trac/wiki/2018-team3 返回Helianthus]

[http://10.71.10.90/pia/trac/wiki/2017-Sp133-team2 Legilimens+题解]

http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001462

== 流水账 ==
先签了个E，'''E1y37'''。期间lyk和jhguai讨论了下D，对结论不太确定，然后heltion也看了看，也提出了结论，lyk写了一发，WA了。发现写了个假的映射。第二发也WA了，发现写了个假的下标。第三发也WA了，发现写了个假的顺序。第四发终于过了，'''D4y75'''。然后我看了A题题意，然后给jhguai说了说，然后写了个naive的区间DP，样例过不去。然后看了看样例，发现*号和+-号要分开讨论。交了一发WA了，发现有个地方没%爆ll了。改了就过了'''A2y104'''。heltion看了看G，跟jhguai讨论了下，然后jhguai上机写了G，稍微构造了会儿就过了'''G1y145'''。期间lyk和heltion讨论了下F，然后想了个模型维护了点对距离和，然后暴力去记忆化搜索。lyk跟heltion口胡了一下复杂度的正确性，然后lyk上机写了一发。写完就过了样例，然后交了一发WA。然后发现map都没清，又交了一发WA，发现子树个数乘的时候没%，直接%又WA了一发，分开记%了的和没%的，终于过了，'''F4y206'''.然后jhguai非常想写J的树链剖分，本来不想让他写的，看cjb过了就让他去写了。然后lyk和heltion讨论了C，没有想到lct维护最大生成树，一直在想找规律，凉了。最后jhguai的j题也凉了。5题凉凉。

== 总结 ==

=== LYK ===

今天D题写的非常开心，本来是我和jhguai在看，想了个结论不知道对不对，然后heltion看了看觉得肯定对的，然后我上机乱写...各种错误...写的时候脑子不太清楚。F题也有点无语，本来一发过了样例，结果因为乘法爆ll没发现又debug了半小时才发现。日A题也是有个地方没%，罚时一发。最后一个小时半本来是想全力攻C题的，但是错误判断了C题是个结论题，以为找个规律贪心一下就出来了，然后机子空着有点浪费，就让jhguai去写J题了。中途其实想到过正解，不是我跟heltion对lct都不了解，随口说了个这不会是lct吧...jhguai可能也有点忘了。
我们队会的算法还不太够..都靠jhguai的话，jhguai忘了那我们就凉了..这个J题其实不该开，说不定jhguai跟我们一起讨论着C题就想起来这个是lct了.

=== Jhguai  ===

开始看了C和D感觉可做，后来LYK讲了J的题意，感觉树剖可以做，准备放到最后写，后来帮LYK改正了一下A，按Heltion的构造方法写了G，最后写J没调出来，C忘了LCT维护最小生成树的做法，感觉退化了好多，过几天把以前写过的数据结构在写一写恢复一下
=== Heltion ===

E简单题动手签到了半个多小时,然后想出DGF都不想上机写。最后一小时讨论了C的做法，与正解擦肩而过，不懂LCT是什么东西。
== 题解 ==
 * [http://bestcoder.hdu.edu.cn/blog/2015-multi-university-training-contest-8-solutions-by-xudyh/ Official]
 * C ： LCT维护GCD最小生成树
 * J ：树链大剖分
== 补题 ==
 * ~~C~~ ： 写了一天大概明白splay和lct是个啥了(Heltion).
 * J ： jhguai  lyk
 * B ：口胡一下  heltion lyk
 * H ：数学题  heltion

返回Helianthus

Legilimens+题解

http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001462

流水账

先签了个E，E1y37。期间lyk和jhguai讨论了下D，对结论不太确定，然后heltion也看了看，也提出了结论，lyk写了一发，WA了。发现写了个假的映射。第二发也WA了，发现写了个假的下标。第三发也WA了，发现写了个假的顺序。第四发终于过了，D4y75。然后我看了A题题意，然后给jhguai说了说，然后写了个naive的区间DP，样例过不去。然后看了看样例，发现*号和+-号要分开讨论。交了一发WA了，发现有个地方没%爆ll了。改了就过了A2y104。heltion看了看G，跟jhguai讨论了下，然后jhguai上机写了G，稍微构造了会儿就过了G1y145。期间lyk和heltion讨论了下F，然后想了个模型维护了点对距离和，然后暴力去记忆化搜索。lyk跟heltion口胡了一下复杂度的正确性，然后lyk上机写了一发。写完就过了样例，然后交了一发WA。然后发现map都没清，又交了一发WA，发现子树个数乘的时候没%，直接%又WA了一发，分开记%了的和没%的，终于过了，F4y206.然后jhguai非常想写J的树链剖分，本来不想让他写的，看cjb过了就让他去写了。然后lyk和heltion讨论了C，没有想到lct维护最大生成树，一直在想找规律，凉了。最后jhguai的j题也凉了。5题凉凉。

总结

LYK

今天D题写的非常开心，本来是我和jhguai在看，想了个结论不知道对不对，然后heltion看了看觉得肯定对的，然后我上机乱写...各种错误...写的时候脑子不太清楚。F题也有点无语，本来一发过了样例，结果因为乘法爆ll没发现又debug了半小时才发现。日A题也是有个地方没%，罚时一发。最后一个小时半本来是想全力攻C题的，但是错误判断了C题是个结论题，以为找个规律贪心一下就出来了，然后机子空着有点浪费，就让jhguai去写J题了。中途其实想到过正解，不是我跟heltion对lct都不了解，随口说了个这不会是lct吧...jhguai可能也有点忘了。

我们队会的算法还不太够..都靠jhguai的话，jhguai忘了那我们就凉了..这个J题其实不该开，说不定jhguai跟我们一起讨论着C题就想起来这个是lct了.

Jhguai

开始看了C和D感觉可做，后来LYK讲了J的题意，感觉树剖可以做，准备放到最后写，后来帮LYK改正了一下A，按Heltion的构造方法写了G，最后写J没调出来，C忘了LCT维护最小生成树的做法，感觉退化了好多，过几天把以前写过的数据结构在写一写恢复一下

Heltion

E简单题动手签到了半个多小时,然后想出DGF都不想上机写。最后一小时讨论了C的做法，与正解擦肩而过，不懂LCT是什么东西。

题解

  • Official
  • C ： LCT维护GCD最小生成树
  • J ：树链大剖分

补题

  • C ： 写了一天大概明白splay和lct是个啥了(Heltion).
  • J ： jhguai lyk
  • B ：口胡一下 heltion lyk
  • H ：数学题 heltion
附加文件