2019-team0x03-0011

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(Standings.png, 500px)]][[Image(Submissions.png, 500px)]]
== 概述 ==
八月集训第三场

== 流水账 ==

lcd开场写E，'''E1y37'''，然后sds上机写了I，'''I1y47'''。lmh上机写D，WA了一发后下来看代码。lcd看到榜上多人过G，胡乱分析了一下上了一个随机化，lmh觉得lcd肯定过不了，而lcd胸有成竹，于是两人赌了一杯奶茶。lcd等了10min+，返回了wa3，lcd bg++。lcd心想太亏，要把这杯奶茶赚回来，于是再次胡乱分析一波，先叉掉自己原来的随机化，接着上机写了个更不靠谱的假做法，lmh觉得这次他连test2都过不了，lcd又赌了一杯奶茶，结果wa2，lcd bg++。lmh翻出了字典，发现D是有向图，'''D2y101'''。lcd觉得G不适合他，扔给lmh，自己跑去看B。lmh也分析出了一个假做法并WA了一发，借鉴lcd的两发WA加上了随机化，大力艹过去了，'''G4y140'''。lcd看B发现费用流直接跑，心想sds这几天写了很多网络流，就丢给了sds，同时接下sds分析出的A题模型和打出来的表。lcd想了一会发现是个数位dp，因为状态设计太过辣鸡，把自己都恶心到了，还因为 & 打错 wa了一发，'''A2y186'''。sds写完B，本地测了一下过不了，优化了一下还是不太行，于是掏出校板，发现校板的费用流是dij写法的，学习了一发。写完后发现速度还是不太行，看榜上很多人过了，交了一发T掉了，于是陷入沉思。lmh得出了F的整体二分解法，但由于写得太丑，于是改为他喜欢的主席树。sds放弃了优化，开始尝试随机乱搞降低复杂度。lcd等到机位空出来后上机写了J，'''J1y278'''。最后sds大力过不去，lmh主席树被卡空间，于是凉凉。

== 总结 ==
=== SidneySun ===
 * 我感觉是时候开始整理一波模板了。
 * 网络流的问题要重视起来，还是要补充一下这方面的知识。
 * 我还是觉得三开的做法没有大的问题。三开带来的失败不是由于策略导致的，是由于个人水平不够。在这个问题上我倾向于加强个人能力试一下。

=== lichangdongtw ===

好像这场的参与度不错

 * A的状态设计有冗余（辣鸡状态），导致了写程序多花了些时间，肉眼debug也比较困难，还犯了个&打错的低级错误贡献了一发罚时
 * B我们都不会zkw费用流.......第一次遇到zkw能过其他不能过的题，缺失的技能点
 * F没过血亏，我应该去看一眼F，协助一下队友的

=== ntwbvdbl_oe ===
 * lmh今天要背大锅："
 * 真的是很久没有碰过这种套路了，自己的整体二分加了一大堆vector还被迫非递归版本，跑了4s。std只跑了1s，学习了一下，发现自己想复杂了，绕了几个弯。
 * 卡空间的技巧自己从来没有接触过，导致遇到问题时除了改数组大小束手无策。学习了ll改为int的写法。
 * 由于封榜后在三开(貌似和七月集训第三场差不多?)，没有与队友交流，导致自己的垃圾写法和思维误区没能有效地解决，自己其实对写出F题没有那么自信，只是非常清楚算法而已。
 * D题和G题自己的算法十分乱搞，但都大力艹过去了，于是对F题有一定影响
 * 遇到问题找队友帮忙就好(如果我也参与B题讨论可能就过了?)
 * (其实就算坚持写整体二分也不可能过，因为细节太差了，补题也是+12才过的
 * "lmh也很努力了，lmh就是菜而已

== 题解 ==
 * A: 数位dp
 * B: 最小费用最大流 or 最大流
 * C:
 * D: 反向操作，每次加边就从那一条边开始SPFA更新答案
 * E: dp
 * F: 二分+主席树(卡空间)或整体二分(模板题)
 * G: 随机化后每次选取能加到团里的点加进去，否则丢掉
 * H:
 * I: 堆 + 贪心
 * J: dp+找重心

[wiki:2019-team0x03 Back]

概述

八月集训第三场

流水账

lcd开场写E，E1y37，然后sds上机写了I，I1y47。lmh上机写D，WA了一发后下来看代码。lcd看到榜上多人过G，胡乱分析了一下上了一个随机化，lmh觉得lcd肯定过不了，而lcd胸有成竹，于是两人赌了一杯奶茶。lcd等了10min+，返回了wa3，lcd bg++。lcd心想太亏，要把这杯奶茶赚回来，于是再次胡乱分析一波，先叉掉自己原来的随机化，接着上机写了个更不靠谱的假做法，lmh觉得这次他连test2都过不了，lcd又赌了一杯奶茶，结果wa2，lcd bg++。lmh翻出了字典，发现D是有向图，D2y101。lcd觉得G不适合他，扔给lmh，自己跑去看B。lmh也分析出了一个假做法并WA了一发，借鉴lcd的两发WA加上了随机化，大力艹过去了，G4y140。lcd看B发现费用流直接跑，心想sds这几天写了很多网络流，就丢给了sds，同时接下sds分析出的A题模型和打出来的表。lcd想了一会发现是个数位dp，因为状态设计太过辣鸡，把自己都恶心到了，还因为 & 打错 wa了一发，A2y186。sds写完B，本地测了一下过不了，优化了一下还是不太行，于是掏出校板，发现校板的费用流是dij写法的，学习了一发。写完后发现速度还是不太行，看榜上很多人过了，交了一发T掉了，于是陷入沉思。lmh得出了F的整体二分解法，但由于写得太丑，于是改为他喜欢的主席树。sds放弃了优化，开始尝试随机乱搞降低复杂度。lcd等到机位空出来后上机写了J，J1y278。最后sds大力过不去，lmh主席树被卡空间，于是凉凉。

总结

SidneySun

• 我感觉是时候开始整理一波模板了。
• 网络流的问题要重视起来，还是要补充一下这方面的知识。
• 我还是觉得三开的做法没有大的问题。三开带来的失败不是由于策略导致的，是由于个人水平不够。在这个问题上我倾向于加强个人能力试一下。

lichangdongtw

好像这场的参与度不错

• A的状态设计有冗余（辣鸡状态），导致了写程序多花了些时间，肉眼debug也比较困难，还犯了个&打错的低级错误贡献了一发罚时
• B我们都不会zkw费用流.......第一次遇到zkw能过其他不能过的题，缺失的技能点
• F没过血亏，我应该去看一眼F，协助一下队友的

ntwbvdbl_oe

• lmh今天要背大锅："
• 真的是很久没有碰过这种套路了，自己的整体二分加了一大堆vector还被迫非递归版本，跑了4s。std只跑了1s，学习了一下，发现自己想复杂了，绕了几个弯。
• 卡空间的技巧自己从来没有接触过，导致遇到问题时除了改数组大小束手无策。学习了ll改为int的写法。
• 由于封榜后在三开(貌似和七月集训第三场差不多?)，没有与队友交流，导致自己的垃圾写法和思维误区没能有效地解决，自己其实对写出F题没有那么自信，只是非常清楚算法而已。
• D题和G题自己的算法十分乱搞，但都大力艹过去了，于是对F题有一定影响
• 遇到问题找队友帮忙就好(如果我也参与B题讨论可能就过了?)
• (其实就算坚持写整体二分也不可能过，因为细节太差了，补题也是+12才过的
• "lmh也很努力了，lmh就是菜而已

题解

• A: 数位dp
• B: 最小费用最大流 or 最大流
• C:
• D: 反向操作，每次加边就从那一条边开始SPFA更新答案
• E: dp
• F: 二分+主席树(卡空间)或整体二分(模板题)
• G: 随机化后每次选取能加到团里的点加进去，否则丢掉
• H:
• I: 堆 + 贪心
• J: dp+找重心

Back

附加文件

• rc11.png by lichangdongtw
• Standings.png by lichangdongtw
• Submissions.png by lichangdongtw