2019-team0x03-0024

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(Standings.png, 600px)]][[BR]][[Image(Submissions.png, 600px)]]
== 概述 ==
== 流水账 ==
lmh又双叒迟到了[[BR]]
开场sds开出K，找lcd验了解法，两人一致觉得这不是出门题，lcd试着想了想找不到什么优化的方法。sds开出J，找lcd验解，虽然两人都不太会做，但都觉得只有一个一个问这样的做法，看榜上过了很多，就试探性的交了一发过了，'''J1y23'''。接着跟榜看E，这时lmh来了，sds把K扔给lmh，lmh也得出一致的解法。lcd和sds讨论了一下出了E的解法，于是lcd上机写E，lmh想K的细节，E过了后lmh上机写过K，'''E1y67'''，'''K1y78'''。lcd下机后接下L的题意，想了很久做了一个非常复杂的转化，把字符串转到二维平面再映射到线段用线段树来维护，感觉用高于这题的思维复杂度出了解法...lcd上机写L，lmh和sds讨论B。L写完后由于非法和vector的问题WA了两发，'''L3y135'''。lmh得出了一个复杂的做法，sds听后帮他简化了一下，于是lmh上机写B。lcd下机后接下I的题意，出了个假做法，sds听了后帮忙推了一下柿子。两人一开始觉得很对，甚至准备上机写，后来突然意识到一个东西无法维护。于是lcd扔掉I，去看H，发现是个经典最小割模型，解了一下方程后出了解，找sds验过后因为sds写过很多次网络流，就把H题扔给他，自己跑去想F。lmh在B上WA了一发后冥思苦想了许久，写对拍找到了问题，PE两发后还交错到sds的H题上，'''B5y215'''。sds上机写H，两个队友在H和I之间挣扎，'''H1y239'''。封榜后，lcd觉得I不会做就是不会做了，继续想F，sds和lmh觉得F不如I可做，继续想I。lcd凭借直觉觉得F所有cut方案应该最后的价值和是一样的（题解第一个结论），但有了这个后仍然不太好做，于是他又大胆猜了一个结论（题解第二个结论），上机写了一下没过样例（其实是他写错了），此时剩下时间也不多了，于是三人弃疗。

== 总结 ==
=== SidneySun ===
 * 今日无事
 * I题真是个SB题。
=== lichangdongtw ===
 * 
=== ntwbvdbl_oe ===
 * I题应该是傻逼题结果三人都不会……需要好好补一补知识点
 * B题占用太多机时了(虽然不好写而且机位空着)，调试效率很低，对拍也写晚了，不够果断
 * 其他题不太能帮上忙
 * 20191001UPD:字典序LIS用单调栈就可以了

== 题解 ==
 * A:
 * B: 做(从左往右/从右往左)(字典序最大/最小)四次LIS，枚举交叉点更新答案。
 * C:
 * D:
 * E: dp，f(n)表示长度为n的序列，一个逆序对期望存在的轮数（贡献次数）
 * F:
 * G:
 * H: 经典最小割模型
 * I: 枚举所有回文串，判断是否双倍回文
 * J: 迷
 * K: 排序后答案必为连续三边，在主席树上从大到小枚举，枚举次数是log级别的
 * L: 对每个位置求个同颜色的前K-1个的位置作为y值，然后每个位置x带上y映射到二维平面，从左往右枚举右端点，只保留每种颜色最后一个位置的点，就是找一个y=x直线上最下的，右下方没有点的点，可以用反过来用点覆盖直线，线段树找没有被覆盖的最左边的位置

[wiki:2019-team0x03 Back]

概述

流水账

lmh又双叒迟到了

开场sds开出K，找lcd验了解法，两人一致觉得这不是出门题，lcd试着想了想找不到什么优化的方法。sds开出J，找lcd验解，虽然两人都不太会做，但都觉得只有一个一个问这样的做法，看榜上过了很多，就试探性的交了一发过了，J1y23。接着跟榜看E，这时lmh来了，sds把K扔给lmh，lmh也得出一致的解法。lcd和sds讨论了一下出了E的解法，于是lcd上机写E，lmh想K的细节，E过了后lmh上机写过K，E1y67，K1y78。lcd下机后接下L的题意，想了很久做了一个非常复杂的转化，把字符串转到二维平面再映射到线段用线段树来维护，感觉用高于这题的思维复杂度出了解法...lcd上机写L，lmh和sds讨论B。L写完后由于非法和vector的问题WA了两发，L3y135。lmh得出了一个复杂的做法，sds听后帮他简化了一下，于是lmh上机写B。lcd下机后接下I的题意，出了个假做法，sds听了后帮忙推了一下柿子。两人一开始觉得很对，甚至准备上机写，后来突然意识到一个东西无法维护。于是lcd扔掉I，去看H，发现是个经典最小割模型，解了一下方程后出了解，找sds验过后因为sds写过很多次网络流，就把H题扔给他，自己跑去想F。lmh在B上WA了一发后冥思苦想了许久，写对拍找到了问题，PE两发后还交错到sds的H题上，B5y215。sds上机写H，两个队友在H和I之间挣扎，H1y239。封榜后，lcd觉得I不会做就是不会做了，继续想F，sds和lmh觉得F不如I可做，继续想I。lcd凭借直觉觉得F所有cut方案应该最后的价值和是一样的（题解第一个结论），但有了这个后仍然不太好做，于是他又大胆猜了一个结论（题解第二个结论），上机写了一下没过样例（其实是他写错了），此时剩下时间也不多了，于是三人弃疗。

总结

SidneySun

• 今日无事
• I题真是个SB题。

lichangdongtw

ntwbvdbl_oe

• I题应该是傻逼题结果三人都不会……需要好好补一补知识点
• B题占用太多机时了(虽然不好写而且机位空着)，调试效率很低，对拍也写晚了，不够果断
• 其他题不太能帮上忙
• 20191001UPD:字典序LIS用单调栈就可以了

题解

• A:
• B: 做(从左往右/从右往左)(字典序最大/最小)四次LIS，枚举交叉点更新答案。
• C:
• D:
• E: dp，f(n)表示长度为n的序列，一个逆序对期望存在的轮数（贡献次数）
• F:
• G:
• H: 经典最小割模型
• I: 枚举所有回文串，判断是否双倍回文
• J: 迷
• K: 排序后答案必为连续三边，在主席树上从大到小枚举，枚举次数是log级别的
• L: 对每个位置求个同颜色的前K-1个的位置作为y值，然后每个位置x带上y映射到二维平面，从左往右枚举右端点，只保留每种颜色最后一个位置的点，就是找一个y=x直线上最下的，右下方没有点的点，可以用反过来用点覆盖直线，线段树找没有被覆盖的最左边的位置

Back

附加文件

• Standings.png by ntwbvdbl_oe
• Submissions.png by ntwbvdbl_oe