2019-team0x03-0008

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
像往常一样，sds发现了签到题。上机迅速地完成了b.cpp，此时榜上还没有多少提交。然后，sds把大前天的b.cpp交了上去，获得一个WA。换lmh上机签A，lmh迅速地完成了a.cpp，然后lmh把大前天的a.cpp交了上去，获得一个WA。此时已经过了一个小时，榜上几乎全部两题，我们垫底。随后lmh意识到代码交错了'''A2y63'''，但没有意识到sds代码也交错了。就这样，sds和lcd对着一份几乎完全正确的代码debug了60min。发现程序没有任何问题后决定换lcd重写'''B3y80'''。之后三小时'''G1y86'''，'''D1y114'''，'''C1y122'''，'''K1y213'''。lmh上机写F。比赛进行到最后一个小时，lcd告诉了sds一个错误的E题题意，sds听错了lcd说的H题的题意，sds和lmh告诉lcd一个错误的J题题意。就这样，我们一边感该zju的生源质量很高，一边讨论下来要加强训练。经过仔细讨论，我们觉得读错的这三个题都不可做，所以最后lmh全场唯一通过'''F9y265'''。

== 总结 ==
=== SidneySun ===
 * 带崩全场节奏 *1
 * 希望能在暑假达成 读错题十次 成就。
=== lichangdongtw ===
 * 读题错误真的不能再犯了，还是每道题都应当有至少两人分别读后再核对题意
=== ntwbvdbl_oe ===
 * lmh今天棒棒地写了F题!(真的不是因为队友开不出题才去写几何的)(lcd: 以后几何题都交给lmh写吧。lmh: ???)
 * lmh觉得几何题真的好难写，他写几何题太少了
 * lmh的错误题意又成功带崩队友(难道读对题他就会写了?)
== 题解 ==
 * A: 依题意模拟即可
 * B: 设(i,j)表示等差数列中相邻的两项，那么(i,j)的前驱和后继唯一，每条链算一下长度比较最长的
 * C: 对每个人算一下他单独走到门口要的时间，扔进时间队列里，相同时间的就往后挤，答案就是最大的时间
 * D: fi,j表示串A匹配到i，B匹配到j时继续匹配使得A,B都失配的最短长度，dp
 * E:
 * F: 长的一刀一定过某个点，枚举这个点另一端二分找一半的位置；短的一刀可能过两条边，枚举每条边，在这条边上三分一个点，另一端二分找一半的位置
 * G: 将序列中每个数和最大的数做差得绝对值ai，相当于每个位置的值选择ai或者-ai，使得序列的逆序对个数尽量少，从大到小考虑ai，贪心的决定选择ai还是-ai
 * H:
 * I:
 * J: 将相同颜色的点按照dfn排成'''环'''，答案为所有点的深度和减去相邻点lca的深度和，用set维护即可
 * K: 考虑如何O(n)判断当前最多能赢多少场，肯定是拿B中最小的几个去A中分别找大于自己的且没有被用过的数中最小的。基于这个，我们从左到右决定每场的马，假设剩余未决定的场次中我们要获胜K场，对于当前的第i场，我们先假设他获胜，从大到小找一个最大的值使得其大于B这场的值且取完后我们能获胜K-1场，如果不能获胜就找一个最大的值使得取完后我们能获胜K场，从大到小的枚举结合一下上面的判定可以做到合起来是一个O(n)，所以总复杂度是O(n^2^)的。（为啥大家K都是n^2^logn的，我们队出了两个n^2^的做法，但是其中我的做法因为太难写被扔掉了......）



[wiki:2019-team0x03 Back]

概述

七月集训第八场

流水账

像往常一样，sds发现了签到题。上机迅速地完成了b.cpp，此时榜上还没有多少提交。然后，sds把大前天的b.cpp交了上去，获得一个WA。换lmh上机签A，lmh迅速地完成了a.cpp，然后lmh把大前天的a.cpp交了上去，获得一个WA。此时已经过了一个小时，榜上几乎全部两题，我们垫底。随后lmh意识到代码交错了A2y63，但没有意识到sds代码也交错了。就这样，sds和lcd对着一份几乎完全正确的代码debug了60min。发现程序没有任何问题后决定换lcd重写B3y80。之后三小时G1y86，D1y114，C1y122，K1y213。lmh上机写F。比赛进行到最后一个小时，lcd告诉了sds一个错误的E题题意，sds听错了lcd说的H题的题意，sds和lmh告诉lcd一个错误的J题题意。就这样，我们一边感该zju的生源质量很高，一边讨论下来要加强训练。经过仔细讨论，我们觉得读错的这三个题都不可做，所以最后lmh全场唯一通过F9y265。

总结

SidneySun

• 带崩全场节奏 *1
• 希望能在暑假达成 读错题十次 成就。

lichangdongtw

• 读题错误真的不能再犯了，还是每道题都应当有至少两人分别读后再核对题意

ntwbvdbl_oe

• lmh今天棒棒地写了F题!(真的不是因为队友开不出题才去写几何的)(lcd: 以后几何题都交给lmh写吧。lmh: ???)
• lmh觉得几何题真的好难写，他写几何题太少了
• lmh的错误题意又成功带崩队友(难道读对题他就会写了?)

题解

• A: 依题意模拟即可
• B: 设(i,j)表示等差数列中相邻的两项，那么(i,j)的前驱和后继唯一，每条链算一下长度比较最长的
• C: 对每个人算一下他单独走到门口要的时间，扔进时间队列里，相同时间的就往后挤，答案就是最大的时间
• D: fi,j表示串A匹配到i，B匹配到j时继续匹配使得A,B都失配的最短长度，dp
• E:
• F: 长的一刀一定过某个点，枚举这个点另一端二分找一半的位置；短的一刀可能过两条边，枚举每条边，在这条边上三分一个点，另一端二分找一半的位置
• G: 将序列中每个数和最大的数做差得绝对值ai，相当于每个位置的值选择ai或者-ai，使得序列的逆序对个数尽量少，从大到小考虑ai，贪心的决定选择ai还是-ai
• H:
• I:
• J: 将相同颜色的点按照dfn排成环，答案为所有点的深度和减去相邻点lca的深度和，用set维护即可
• K: 考虑如何O(n)判断当前最多能赢多少场，肯定是拿B中最小的几个去A中分别找大于自己的且没有被用过的数中最小的。基于这个，我们从左到右决定每场的马，假设剩余未决定的场次中我们要获胜K场，对于当前的第i场，我们先假设他获胜，从大到小找一个最大的值使得其大于B这场的值且取完后我们能获胜K-1场，如果不能获胜就找一个最大的值使得取完后我们能获胜K场，从大到小的枚举结合一下上面的判定可以做到合起来是一个O(n)，所以总复杂度是O(n²)的。（为啥大家K都是n²logn的，我们队出了两个n²的做法，但是其中我的做法因为太难写被扔掉了......）

Back

附加文件

• Standings.png by ntwbvdbl_oe