2017-C08-team4

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||
||947||4:51:36||2160||B||g++||Time-limit exceeded||
||945||4:50:38||2161||B||g++||Time-limit exceeded||
||939||4:43:26||1209||B||g++||Wrong answer||
||930||4:28:42||2534||J||g++||OK||
||928||4:28:27||367||J||g++||Presentation error||
||923||4:17:33||2404||J||g++||Time-limit exceeded||
||919||4:10:39||2404||J||g++||Time-limit exceeded||
||916||3:59:04||2358||J||g++||Wrong answer||
||903||3:21:02||1210||H||g++||OK||
||852||0:51:34||1120||D||g++||OK||
||846||0:39:58||427||G||g++||OK||
||842||0:28:06||538||G||g++||Wrong answer||
||839||0:24:14||516||G||g++||Time-limit exceeded||

== 流水账 by JYW ==
今天惨败。
首发签到出问题，姜学长看错E题上去码，码到一半发现不对，然后发现大部分人过G题，换黄学长码G。
黄学长考虑有问题，两发罚时后过G。
然后期间张学长和姜学长讨论出D，换姜学长码D，张学长继续推J。
姜学长一A，换张学长码J，姜学长和黄学长讨论H，张学长中途思路卡壳，换姜学长码可能超时的H，然后竟然过了。
最后两小时，张学长安心码J，姜学长和黄学长试图讨论出一题，但最终没有结果。
最后半小时，张学长终于过J。换姜学长写随机贪心B，张学长和黄学长讨论E。
姜学长果然WA了两次，然后张学长想出了E，时间不够。
果然名次开始不停下降了，QAQ，GG。
最后第五名，只做了四题。
== 总结 ==
  * 需要多交流。
== 补题 ==
A(√)[[BR]]
B(√)[[BR]]
C()[[BR]]
E(√)研究各种做法后想到此题确实存在O(n*m^2^)做法，首先dp用矩阵维护，利用team8题解中的平移区间的做法，维护前缀积和后缀积时每次乘的矩阵每行每列最多只有两个元素，所以可以O(m^2^)做矩乘；当合并两个积时并不需要求出整个积，只要求乘积矩阵中一个元素即可，这部分O(m)。整个算法O(n*m^2^)
[[BR]]
F()[[BR]]
I()[[BR]]

Run ID	Time	Size	Problem	Language	Result
947	4:51:36	2160	B	g++	Time-limit exceeded
945	4:50:38	2161	B	g++	Time-limit exceeded
939	4:43:26	1209	B	g++	Wrong answer
930	4:28:42	2534	J	g++	OK
928	4:28:27	367	J	g++	Presentation error
923	4:17:33	2404	J	g++	Time-limit exceeded
919	4:10:39	2404	J	g++	Time-limit exceeded
916	3:59:04	2358	J	g++	Wrong answer
903	3:21:02	1210	H	g++	OK
852	0:51:34	1120	D	g++	OK
846	0:39:58	427	G	g++	OK
842	0:28:06	538	G	g++	Wrong answer
839	0:24:14	516	G	g++	Time-limit exceeded

流水账 by JYW

今天惨败。

首发签到出问题，姜学长看错E题上去码，码到一半发现不对，然后发现大部分人过G题，换黄学长码G。

黄学长考虑有问题，两发罚时后过G。

然后期间张学长和姜学长讨论出D，换姜学长码D，张学长继续推J。

姜学长一A，换张学长码J，姜学长和黄学长讨论H，张学长中途思路卡壳，换姜学长码可能超时的H，然后竟然过了。

最后两小时，张学长安心码J，姜学长和黄学长试图讨论出一题，但最终没有结果。

最后半小时，张学长终于过J。换姜学长写随机贪心B，张学长和黄学长讨论E。

姜学长果然WA了两次，然后张学长想出了E，时间不够。

果然名次开始不停下降了，QAQ，GG。

最后第五名，只做了四题。

总结

需要多交流。

补题

A(√)

B(√)

C()

E(√)研究各种做法后想到此题确实存在O(n*m²)做法，首先dp用矩阵维护，利用team8题解中的平移区间的做法，维护前缀积和后缀积时每次乘的矩阵每行每列最多只有两个元素，所以可以O(m²)做矩乘；当合并两个积时并不需要求出整个积，只要求乘积矩阵中一个元素即可，这部分O(m)。整个算法O(n*m²)

F()

I()