2018-Sp05-lyk

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(QQ截图20180727143131.jpg,500px)]]

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

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

== 流水账 ==
开门先四处看题，因为没有榜。lyk看到D题是个构造题，然后构造出偶数的解，上机写了个爆搜，搜不出奇数的解，直接猜了结论，一发过了,'''D1y28'''。然后lgl看了签到题G题，随便搞了下就过了，'''G1y55'''。这时候大致题目都看过了，决定挑一些看起来可做的题做。lgl写G时另两个人挑了C开始做，想到先像二叉树一样搞，然后想了一会儿，讨论出了分层然后按二进制搞，lyk上机写了一发，很快过了样例，交了一发就过了，'''C1y84'''。期间jhguai和heltion讨论出了J的暴力，上机写了一发，算法有点错误，数组也开小了，罚时三发。这时lyk和heltion讨论A题，讨论了一会儿就想出了正解，但是幂次要取模，所以要欧拉函数一下，有点烦。jhguai的J题卡了就换lyk上机写了A，写了一会儿就写好了，交了一发，TLE。自认为复杂度是对的，尝试卡下常数，结果还是TLE了，造了几组数据发现死循环了，然后发现幂次变负数了，改了改就过了，'''A3y193'''。之后jhguai继续上机fixJ题，lyk和heltion尝试开其他题，觉得不太行，然后就决定帮jhguai一起看J题。尝试交一个错误暴力，TLE了。然后jhguai在lyk和heltion的反复误导下，坚持了正解，并说服了两个傻逼。写完之后稍微的debug了下，过了样例，交了一发，又是TLE。然后发现多组数据memset，改了改就过了，'''J6y276'''。

== 总结 ==

=== LYK ===
首先，把楼下heltion打一顿。今天其实并不算太顺利的，J题卡的时间比较久，在错误的算法下搞了半天，还好jhguai想到了正解，导致A题出的比较慢。A题还被卡了常数，有点不太开心，最后把2的幂次的取模项优化了下。优化完发现还是TLE,原来取模的时候幂次变负数了，导致了大数据的死循环。我在取模的时候好像经常出问题，要注意下。回去后各自学习一下各自应该要会的算法，熟练一下虽然会了但理解还不深的算法。

=== Jhguai  ===
签到题G写的有点慢，后来和Heltion讨论J，尝试各种方法建边都没有A，最后想到了连续区间建边可以用线段树优化，稍微调了调就过了，感觉一些模型的应用还是不熟练，要多练习。
=== Heltion ===

不用写代码真的爽...

== 题解 ==
  * C 正解是数位DP，我们是按二叉树的形式，把1-n的和分成前log(n)层和最后一层，预处理出每一层统计各个数出现多少次，前log层直接加起来，最后一层按二进制分割成不同深度的最后一层再相加。
== 补题 ==
 * B ：线段树优化DP lyk
 * E ：期望 线段树 jhguai
 * F ：计算几何 heltion （这题牛客网现场被换成签到题了。。无语）
 * I ：口胡  heltion

返回Helianthus

Legilimens+题解

流水账

开门先四处看题，因为没有榜。lyk看到D题是个构造题，然后构造出偶数的解，上机写了个爆搜，搜不出奇数的解，直接猜了结论，一发过了,D1y28。然后lgl看了签到题G题，随便搞了下就过了，G1y55。这时候大致题目都看过了，决定挑一些看起来可做的题做。lgl写G时另两个人挑了C开始做，想到先像二叉树一样搞，然后想了一会儿，讨论出了分层然后按二进制搞，lyk上机写了一发，很快过了样例，交了一发就过了，C1y84。期间jhguai和heltion讨论出了J的暴力，上机写了一发，算法有点错误，数组也开小了，罚时三发。这时lyk和heltion讨论A题，讨论了一会儿就想出了正解，但是幂次要取模，所以要欧拉函数一下，有点烦。jhguai的J题卡了就换lyk上机写了A，写了一会儿就写好了，交了一发，TLE。自认为复杂度是对的，尝试卡下常数，结果还是TLE了，造了几组数据发现死循环了，然后发现幂次变负数了，改了改就过了，A3y193。之后jhguai继续上机fixJ题，lyk和heltion尝试开其他题，觉得不太行，然后就决定帮jhguai一起看J题。尝试交一个错误暴力，TLE了。然后jhguai在lyk和heltion的反复误导下，坚持了正解，并说服了两个傻逼。写完之后稍微的debug了下，过了样例，交了一发，又是TLE。然后发现多组数据memset，改了改就过了，J6y276。

总结

LYK

首先，把楼下heltion打一顿。今天其实并不算太顺利的，J题卡的时间比较久，在错误的算法下搞了半天，还好jhguai想到了正解，导致A题出的比较慢。A题还被卡了常数，有点不太开心，最后把2的幂次的取模项优化了下。优化完发现还是TLE,原来取模的时候幂次变负数了，导致了大数据的死循环。我在取模的时候好像经常出问题，要注意下。回去后各自学习一下各自应该要会的算法，熟练一下虽然会了但理解还不深的算法。

Jhguai

签到题G写的有点慢，后来和Heltion讨论J，尝试各种方法建边都没有A，最后想到了连续区间建边可以用线段树优化，稍微调了调就过了，感觉一些模型的应用还是不熟练，要多练习。

Heltion

不用写代码真的爽...

题解

  • C 正解是数位DP，我们是按二叉树的形式，把1-n的和分成前log(n)层和最后一层，预处理出每一层统计各个数出现多少次，前log层直接加起来，最后一层按二进制分割成不同深度的最后一层再相加。

补题

  • B ：线段树优化DP lyk
  • E ：期望 线段树 jhguai
  • F ：计算几何 heltion （这题牛客网现场被换成签到题了。。无语）
  • I ：口胡 heltion
附加文件