2017-Sp14-team3

从 Trac 迁移的文章

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

原文章内容如下：

reku：感觉好久没有训练，然后签到题F三个人就卡了很久...不知道为什么我们队伍老是爱卡签到题，真的是智力低下吗QAQ。然后后面的M超级不顺，wyh几乎卡了大半场。最后K也没出，也不太清楚正确的做法...不过7题还算还行吧...虽然被zucc打飞了。另外怎么回事啊，怎么没有人写训练小结了啊...看看对面一队二队写的多丰富...

lzw:这场的L感觉并不难，但是过的队伍不多，感觉有些奇怪。几何题卡了很久，可能是猛犸的板子的原因，后来换成杭电的板子就过了。K题以为是水题，想到一个2个log的做法，看了看时限有10s，以为可以随便艹，结果TLE到死，赛后发现我的DP姿势正确性也是有问题的。最后johhan手撸出了J题，非常厉害，不愧是江苏省自招第一！ 

Johann:这场的M的锅非常奇怪。因为前期一直返回TLE，我就没有想到会是求外心的板子错了。其实因为我是一直随机直到找到解为止，因此所有的WA都会变成T。导致前期一直在改些有的没的，浪费了很多罚时。后期终于开始发现错误，改了好多。包括对eps的使用感觉又有了新的理解。最后改成了正确的求外心板子，终于保住了脑袋。最后手撕J题可能是每个高中生的基本功吧。( ~~gtmlzw~~ )







补题：
K：分数规划 + DP,将所有区间按左端点从左到右排序，dp[i][j]表示用了前i个区间, 覆盖了1...j的最小代价。 转移的时候 dp[i][j] = dp[i - 1][j], dp[i][Right[i]] = min{dp[i][Right[i]], dp[i - 1][i - 1...Right[i]] + value[i]}. 实际上可以把i - 1...Right[i]改成 i - 1 ...t  这样就是一个后缀最小值，可以把线段树换成树状数组。（线段树会TLE）。 实际做的时候需要把value为负数的区间都先取过来，然后把value设为0再DP. 否则会出错。

reku：感觉好久没有训练，然后签到题F三个人就卡了很久...不知道为什么我们队伍老是爱卡签到题，真的是智力低下吗QAQ。然后后面的M超级不顺，wyh几乎卡了大半场。最后K也没出，也不太清楚正确的做法...不过7题还算还行吧...虽然被zucc打飞了。另外怎么回事啊，怎么没有人写训练小结了啊...看看对面一队二队写的多丰富...

lzw:这场的L感觉并不难，但是过的队伍不多，感觉有些奇怪。几何题卡了很久，可能是猛犸的板子的原因，后来换成杭电的板子就过了。K题以为是水题，想到一个2个log的做法，看了看时限有10s，以为可以随便艹，结果TLE到死，赛后发现我的DP姿势正确性也是有问题的。最后johhan手撸出了J题，非常厉害，不愧是江苏省自招第一！

Johann:这场的M的锅非常奇怪。因为前期一直返回TLE，我就没有想到会是求外心的板子错了。其实因为我是一直随机直到找到解为止，因此所有的WA都会变成T。导致前期一直在改些有的没的，浪费了很多罚时。后期终于开始发现错误，改了好多。包括对eps的使用感觉又有了新的理解。最后改成了正确的求外心板子，终于保住了脑袋。最后手撕J题可能是每个高中生的基本功吧。( gtmlzw )

补题：

K：分数规划 + DP,将所有区间按左端点从左到右排序，dp[i][j]表示用了前i个区间, 覆盖了1...j的最小代价。 转移的时候 dp[i][j] = dp[i - 1][j], dp[i][Right[i]] = min{dp[i][Right[i]], dp[i - 1][i - 1...Right[i]] + value[i]}. 实际上可以把i - 1...Right[i]改成 i - 1 ...t 这样就是一个后缀最小值，可以把线段树换成树状数组。（线段树会TLE）。 实际做的时候需要把value为负数的区间都先取过来，然后把value设为0再DP. 否则会出错。