2017-team1-ex30

从 Trac 迁移的文章

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

原文章内容如下：

== Contest Information ==

'''XVII Open Cup - Eastern Grand Prix'''

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

== 流水账 ==


== 总结 ==


=== shb ===


=== jsb ===

这场听说二队打的很好？有点紧张。
前期也还算行？后来又是到最后两题C和K的时候卡了。我先看的K，想到了一个很不好写的DP做法，考虑了一下细节就弃了；后来丢给了颜学长，他花了一些时间，修正出了一种相对好写的做法。回去看C，是基于随机大数据的MST相关题。以前见过这种“只向前五个点连边“的MST模型（当时N都比较小），显然状压DP是能搞的。这里N=10^7^，还有T=20组数据，明显有很大风险。我口胡了一下，觉得没有更优的做法，就上机去写了。开始写的状态数是几百的做法，明显过不去，后来各种优化，剪枝成了50种左右，然后处理O(1)转移。其实这里我应该停下来好好想想复杂度。T=20确实不知道大数据有多少，但是本题是带LL的DP，若T=1的话，效率也是上亿，已经不太可能跑出了。

最后lsmll学长压哨写K。交了一发绝杀，可惜好像被卡常数了？就崩了。问了问二队，他们K采取了一种叉不掉（应该是对的）但挺好写的DP姿势。C的话，sub快速找到了一个循环节！然后让cjb随便写了个mst暴力就过了。。。哎，以后要算清复杂度，有时间的话多搞搞这种规律、循环节什么的。要是N=10^9^,肯定早过了。


=== lsmll ===
这场很崩，比二队少了两题。不过K题应该优化常数就能过的，感觉我可能要学习下常数小一点的线段树（我的线段树一直很慢）...?但二队使用了更优的做法好像。另外C题似乎有些题目看错..（虽然影响可能不大）?要注意

== 补题 ==

C []

J []

K []

Contest Information

XVII Open Cup - Eastern Grand Prix

Opentrains

流水账

总结

shb

jsb

这场听说二队打的很好？有点紧张。

前期也还算行？后来又是到最后两题C和K的时候卡了。我先看的K，想到了一个很不好写的DP做法，考虑了一下细节就弃了；后来丢给了颜学长，他花了一些时间，修正出了一种相对好写的做法。回去看C，是基于随机大数据的MST相关题。以前见过这种“只向前五个点连边“的MST模型（当时N都比较小），显然状压DP是能搞的。这里N=10⁷，还有T=20组数据，明显有很大风险。我口胡了一下，觉得没有更优的做法，就上机去写了。开始写的状态数是几百的做法，明显过不去，后来各种优化，剪枝成了50种左右，然后处理O(1)转移。其实这里我应该停下来好好想想复杂度。T=20确实不知道大数据有多少，但是本题是带LL的DP，若T=1的话，效率也是上亿，已经不太可能跑出了。

最后lsmll学长压哨写K。交了一发绝杀，可惜好像被卡常数了？就崩了。问了问二队，他们K采取了一种叉不掉（应该是对的）但挺好写的DP姿势。C的话，sub快速找到了一个循环节！然后让cjb随便写了个mst暴力就过了。。。哎，以后要算清复杂度，有时间的话多搞搞这种规律、循环节什么的。要是N=10⁹,肯定早过了。

lsmll

这场很崩，比二队少了两题。不过K题应该优化常数就能过的，感觉我可能要学习下常数小一点的线段树（我的线段树一直很慢）...?但二队使用了更优的做法好像。另外C题似乎有些题目看错..（虽然影响可能不大）?要注意

补题

C []

J []

K []