2015-E01-team2

从 Trac 迁移的文章

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

原文章内容如下：

||User||Problem||Result||Memory||Time||Language||Length||Submit Time||
||Siunaus||G||AC||2268||686||G++||2213||2015-08-19 13:39:52||
||Siunaus||C||RE||  ||  ||G++||2213||2015-08-19 13:39:38||
||Siunaus||G||CE||  ||  ||G++||2217||2015-08-19 13:38:43||
||Siunaus||C||CE||  ||  ||G++||2165||2015-08-19 13:33:17||
||Siunaus||C||CE||  ||  ||G++||2044||2015-08-19 13:14:12||
||Siunaus||J||AC||20892||1294||G++||1666||2015-08-19 12:41:38||
||Siunaus||J||TLE|| ||  ||G++||1667||2015-08-19 12:39:23||
||Siunaus||J||CE||  ||  ||G++||1645||2015-08-19 12:37:32||
||Siunaus||E||RE||  ||  ||G++||1635||2015-08-19 12:16:00||
||Siunaus||F||AC||17040||2480||G++||2274||2015-08-19 11:54:20||
||Siunaus||E||OLE|| ||  ||G++||1497||2015-08-19 11:21:08||
||Siunaus||E||AC||3768||546||G++||1960||2015-08-19 11:02:00||
||Siunaus||E||TLE|| ||  ||G++||1688||2015-08-19 10:57:49||
||Siunaus||H||AC||7084||842||G++||879||2015-08-19 10:51:39||
||Siunaus||C||RE||  ||  ||G++||1588||2015-08-19 10:43:05||
||Siunaus||C||AC||1408||15||G++||529||2015-08-19 10:13:10||
||Siunaus||C||TLE|| ||  ||G++||529||2015-08-19 10:10:43||
||Siunaus||C||TLE|| ||  ||G++||524||2015-08-19 10:07:31||
||Siunaus||C||TLE|| ||  ||G++||519||2015-08-19 10:00:50||
||Siunaus||I||AC||1916||1310||G++||594||2015-08-19 09:54:12||

比赛链接: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88564

== 流水账 ==

=== Patchouli Go ===

今天依旧是我从后面开始看。K看着有点厉害，就没看input output直接跳过了

J题是我去年学fft时做过的题目，7月集训时也给冯博的ntt验过题，就对这一套比较熟悉，也不想用旧姿势去做，看了看数据范围也怕fft tle就决定用ntt去做了（然而ntt并不能过），先放在一边等他们把简单的题写完。

I题看着也相当简单，模拟了一下99999X和个位数的情况，感觉y比x大不了多少。jtjl的LIS卡住下机时我跟他讨论了一下题意，他也觉得x y关系是这样，就让他上去写了。我还在想20是不是上界时，他直接跟我说“一个while不就好了么”，并顺利地'''I1y34'''。

H题我一开始想着是不是找树的重心进行往返，瞎搞了很久都没出来。sf学长写完C（我没参与debug啊，只是看到有人快速幂都能tle就觉得很好骑（奇？）过去看了一下……）下来的时候跟我说了一下树的直径，想了一下好像挺科学，推完两种情况的答案就让他上去写了。

G题比较长不高兴看，sf学长跟我说了一下BDF三题的题意，都是树上的题。F题sf学长提供了一种科学做法；大概是这个时候jtjl学长把E过了，我感觉F没多大问题就让sf想清楚细节，我自己上去写J，jtjl去看队里没人看过的G。

J题直接抄了模板的NTT，但是不知道发生了什么跑出来的结果不对，赶紧下来比对模板，却没发现任何问题。期间jtjl学长发现G经过简单处理后就是一个比较old的图论题，跟他讨论了一下发现了就是floyd+最小路径覆盖，给他找到模板上的最小路径覆盖模板后我就继续准备自己的J。sf学长很稳健地过了F后，我上去换成了自己写的ntt，把样例过了，这时他们提醒我ntt会炸，就改成了fft。由于hdu的编译器有点奇怪 CE 了一次，sf学长在我上厕所时把500001看成50001好心帮我把数组长度改小导致TLE了一次，最后终于'''J3y201'''。

G题jtjl学长发现最小匹配部分会妹控掉，输出似乎也有时不大正常，我和他一起比对模板分别找出一些小瑕疵后他顺利地通过了G。期间sf学长跟我说了一下D和K的想法，D题的策略挺显然，但我们都觉得细节好多不大好处理；K题sf学长提出了一种很科学的、枚举16种情况的做法，跟他讨论完最终部分的处理就让他在G出来后上去写，最后因为时间不够没能写完。

sf学长写K时我想了一下B，考虑过分层的做法和转化成二维询问的做法，都没能想出来。

=== sfiction ===

开场依然是我从前往后看，jtjl从中间开始看，wxj学长从后面开始看。看了一下A题感觉非常的诡异，刚看完就被jtjl喊去给E题写LIS。写好之后我继续看题，中途wxj学长想出了I的解法，问我们熟不熟悉java的高精度。一番讨论之后准备让正在写E的jtjl用C++来写I（因为只需要读入和递增，时候发现有些的java超时了）。'''I1y34'''。我看完B之后wxj学长告诉了我C题的题意，我很快推出了C的公式。然而因为智商掉线没有意识到n<k的情形，以及把n-1==k写成n==k-1，三个人一起debug，改一次交一次，贡献了大量罚时。'''C4y53'''。

下机之后我和wxj学长讨论题目。首先确认了J是FFT/NTT之类的姿势，但因为有些麻烦，E题也正在写，就打算延后。之后讨论H的相关策略，发现就是求树的直径。过了一会儿E又遇到了点问题，于是我上机开始写H，很快就写好了。'''H1y91'''。没几分钟E也写好了，一交超时。发现是有一处可能退化为O(n^2^)，改为二分之后就过了。'''E2y102'''。

通过E之前我和wxj学长讨论出了F的大致思路，之后wxj学长上机开始写J，我继续想F。J写好之后似乎出现了比较奇怪的问题，于是换我上机写F，写了约有半个小时。'''F1y154'''。这期间wxj学长和jtjl搞出了G的做法，似乎打算分别写一部分。之后wxj学长继续写J，中间间断由jtjl上机写G（在J通过之前G似乎也没有写多少，是还没有理清思路吗？）。J的NTT一直出问题，后来发现理论上NTT过不了极限数据，换成了FFT，努力修复之后终于通过了。'''J3y201'''。中间有次CE，可能是hdu编译器版本比较低。还有一次WA是因为我之前看错，把J的数组长度改小了。

wxj学长写J期间，我想到了D和K的做法，感觉都比较科学以及复杂。过了J之后我和wxj学长讨论了DK两题，综合了现在的ranklist，觉得还是K比较靠谱。之后我们两个就是在考虑其他题的做法和帮着抢救G。G又因为编译器的问题（命名冲突，本地编译通过）CE了一次，改好之后就过了。'''G2y259'''。之后我上机开始写K，然而因为码力不足，一开始姿势也不太对，到最后也没写完。

昨天刚说过要造数据，今天的C又……

=== JTJL ===

今天我还是从中间开始看题。先看了一眼E，感觉是用LIS就可以随意过的签到题，很激动，就让sf停下看题，先写了LIS的函数。然而我写剩下的代码时发现忽略了判重的问题，然后就gg了。成功背下了罚时的锅…… [[BR]]
这时候刷榜发现有好多人过了I，因为之前sf写LIS的时候我和wxj学长讨论过I，有科学的做法，只是在纠结用JAVA还是C++。eclipse打开太慢，就果断用了C++，'''I1y34''' [[BR]]
我写I的时候sf找到了C的规律，就来写了C，之后又写了H。 [[BR]]
期间每当机子空闲的时候我就上去调E。终于换了好几种姿势之后过了E。（囗囗囗） [[BR]]
之后学长们搞出了F科学的离线算法，sf去写，然后wxj学长做J的ntt（之后发现其实应该写fft），都顺利的过了 [[BR]]
这时候发现没有人看过G我就去看了一下，以为是复杂的计算几何，因为好像当时并没有队伍过，后来发现其实计算几何只是幌子，Floyd+最小路径覆盖就可以解决。然后模版敲错了一个字母，查了好久……[[BR]]

== 总结 ==

 * 提升码力，在复杂度允许的情况下可以采用更简单粗暴的做法提高编码速度。
 * 有多个坑可以跳的时候，要加强沟通选择编程复杂度相对较低的题。没有在写代码的人可以适当讨论一下接下来的安排，包括预估当前题目耗时。(from eternal reality)

== 补题 ==

A B D ~~K~~

=== sfiction ===

 * Unaccepted: K
UserProblemResultMemoryTimeLanguageLengthSubmit Time
SiunausGAC2268686G++22132015-08-19 13:39:52
SiunausCRE G++22132015-08-19 13:39:38
SiunausGCE G++22172015-08-19 13:38:43
SiunausCCE G++21652015-08-19 13:33:17
SiunausCCE G++20442015-08-19 13:14:12
SiunausJAC208921294G++16662015-08-19 12:41:38
SiunausJTLE G++16672015-08-19 12:39:23
SiunausJCE G++16452015-08-19 12:37:32
SiunausERE G++16352015-08-19 12:16:00
SiunausFAC170402480G++22742015-08-19 11:54:20
SiunausEOLE G++14972015-08-19 11:21:08
SiunausEAC3768546G++19602015-08-19 11:02:00
SiunausETLE G++16882015-08-19 10:57:49
SiunausHAC7084842G++8792015-08-19 10:51:39
SiunausCRE G++15882015-08-19 10:43:05
SiunausCAC140815G++5292015-08-19 10:13:10
SiunausCTLE G++5292015-08-19 10:10:43
SiunausCTLE G++5242015-08-19 10:07:31
SiunausCTLE G++5192015-08-19 10:00:50
SiunausIAC19161310G++5942015-08-19 09:54:12

比赛链接: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88564

流水账

Patchouli Go

今天依旧是我从后面开始看。K看着有点厉害，就没看input output直接跳过了

J题是我去年学fft时做过的题目，7月集训时也给冯博的ntt验过题，就对这一套比较熟悉，也不想用旧姿势去做，看了看数据范围也怕fft tle就决定用ntt去做了（然而ntt并不能过），先放在一边等他们把简单的题写完。

I题看着也相当简单，模拟了一下99999X和个位数的情况，感觉y比x大不了多少。jtjl的LIS卡住下机时我跟他讨论了一下题意，他也觉得x y关系是这样，就让他上去写了。我还在想20是不是上界时，他直接跟我说“一个while不就好了么”，并顺利地I1y34。

H题我一开始想着是不是找树的重心进行往返，瞎搞了很久都没出来。sf学长写完C（我没参与debug啊，只是看到有人快速幂都能tle就觉得很好骑（奇？）过去看了一下……）下来的时候跟我说了一下树的直径，想了一下好像挺科学，推完两种情况的答案就让他上去写了。

G题比较长不高兴看，sf学长跟我说了一下BDF三题的题意，都是树上的题。F题sf学长提供了一种科学做法；大概是这个时候jtjl学长把E过了，我感觉F没多大问题就让sf想清楚细节，我自己上去写J，jtjl去看队里没人看过的G。

J题直接抄了模板的NTT，但是不知道发生了什么跑出来的结果不对，赶紧下来比对模板，却没发现任何问题。期间jtjl学长发现G经过简单处理后就是一个比较old的图论题，跟他讨论了一下发现了就是floyd+最小路径覆盖，给他找到模板上的最小路径覆盖模板后我就继续准备自己的J。sf学长很稳健地过了F后，我上去换成了自己写的ntt，把样例过了，这时他们提醒我ntt会炸，就改成了fft。由于hdu的编译器有点奇怪 CE 了一次，sf学长在我上厕所时把500001看成50001好心帮我把数组长度改小导致TLE了一次，最后终于J3y201。

G题jtjl学长发现最小匹配部分会妹控掉，输出似乎也有时不大正常，我和他一起比对模板分别找出一些小瑕疵后他顺利地通过了G。期间sf学长跟我说了一下D和K的想法，D题的策略挺显然，但我们都觉得细节好多不大好处理；K题sf学长提出了一种很科学的、枚举16种情况的做法，跟他讨论完最终部分的处理就让他在G出来后上去写，最后因为时间不够没能写完。

sf学长写K时我想了一下B，考虑过分层的做法和转化成二维询问的做法，都没能想出来。

sfiction

开场依然是我从前往后看，jtjl从中间开始看，wxj学长从后面开始看。看了一下A题感觉非常的诡异，刚看完就被jtjl喊去给E题写LIS。写好之后我继续看题，中途wxj学长想出了I的解法，问我们熟不熟悉java的高精度。一番讨论之后准备让正在写E的jtjl用C++来写I（因为只需要读入和递增，时候发现有些的java超时了）。I1y34。我看完B之后wxj学长告诉了我C题的题意，我很快推出了C的公式。然而因为智商掉线没有意识到nC4y53。

下机之后我和wxj学长讨论题目。首先确认了J是FFT/NTT之类的姿势，但因为有些麻烦，E题也正在写，就打算延后。之后讨论H的相关策略，发现就是求树的直径。过了一会儿E又遇到了点问题，于是我上机开始写H，很快就写好了。H1y91。没几分钟E也写好了，一交超时。发现是有一处可能退化为O(n2)，改为二分之后就过了。E2y102。

通过E之前我和wxj学长讨论出了F的大致思路，之后wxj学长上机开始写J，我继续想F。J写好之后似乎出现了比较奇怪的问题，于是换我上机写F，写了约有半个小时。F1y154。这期间wxj学长和jtjl搞出了G的做法，似乎打算分别写一部分。之后wxj学长继续写J，中间间断由jtjl上机写G（在J通过之前G似乎也没有写多少，是还没有理清思路吗？）。J的NTT一直出问题，后来发现理论上NTT过不了极限数据，换成了FFT，努力修复之后终于通过了。J3y201。中间有次CE，可能是hdu编译器版本比较低。还有一次WA是因为我之前看错，把J的数组长度改小了。

wxj学长写J期间，我想到了D和K的做法，感觉都比较科学以及复杂。过了J之后我和wxj学长讨论了DK两题，综合了现在的ranklist，觉得还是K比较靠谱。之后我们两个就是在考虑其他题的做法和帮着抢救G。G又因为编译器的问题（命名冲突，本地编译通过）CE了一次，改好之后就过了。G2y259。之后我上机开始写K，然而因为码力不足，一开始姿势也不太对，到最后也没写完。

昨天刚说过要造数据，今天的C又……

JTJL

今天我还是从中间开始看题。先看了一眼E，感觉是用LIS就可以随意过的签到题，很激动，就让sf停下看题，先写了LIS的函数。然而我写剩下的代码时发现忽略了判重的问题，然后就gg了。成功背下了罚时的锅……

这时候刷榜发现有好多人过了I，因为之前sf写LIS的时候我和wxj学长讨论过I，有科学的做法，只是在纠结用JAVA还是C++。eclipse打开太慢，就果断用了C++，I1y34

我写I的时候sf找到了C的规律，就来写了C，之后又写了H。

期间每当机子空闲的时候我就上去调E。终于换了好几种姿势之后过了E。（囗囗囗）

之后学长们搞出了F科学的离线算法，sf去写，然后wxj学长做J的ntt（之后发现其实应该写fft），都顺利的过了

这时候发现没有人看过G我就去看了一下，以为是复杂的计算几何，因为好像当时并没有队伍过，后来发现其实计算几何只是幌子，Floyd+最小路径覆盖就可以解决。然后模版敲错了一个字母，查了好久……

总结

  • 提升码力，在复杂度允许的情况下可以采用更简单粗暴的做法提高编码速度。
  • 有多个坑可以跳的时候，要加强沟通选择编程复杂度相对较低的题。没有在写代码的人可以适当讨论一下接下来的安排，包括预估当前题目耗时。(from eternal reality)

补题

A B D K

sfiction

  • Unaccepted: K
附加文件