2020-team10-002

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team10 返回]

== Rank和提交情况 ==
[[Image(Standing2.png,1000px)]] 

Solved: 7/11

== 流水账 ==
（written by lxy）



这一场感觉很流畅，前半部分就一直过过过，除开签到稍微慢了一点，基本就是写写就过了。在过了7题后，我们同时开了两个题，是正解，但调试失败，就很尴尬。不过比第一场进步了不少，希望大家能尽快进步！！！
== 个人小结 ==

lzh：A了四题。开场先看了E发现是个签到水题，正好lxy在写就接下去了，然而因为精度问题炸了很久，最后确定没有其他问题改用整数来写终于过了。期间lxy和我说了I题题意，也是签到题，就先把I过掉了。本来以为会做K题，但是K没人过，想了想细节发现有点难做弃了。听fr说A题有nlog^2做法回去看了A题（结果他说的其实是n^2log），本来想了一个nsqrt*log的做法，优化着就变成了线性了，轻松过掉。看了下J题发现是个常见套路DS，很快就调过了。最后主攻D题，思路正确但是不知道哪里炸了，也没空写对拍，最后也没调出来。

lxy：这场我躺的很舒服。在机上写了两个签到都被lzh赶了下来（不知道我在思考什么呜呜呜），然后趁空机时间写了个c，后面和fr讨论出了g把他赶去上机，做好了剩下的题一半的嘴题工作。感觉比第一场好很多，可能是数学题少了。

fr：开场先开了A，感觉是个大DS所以弃了。然后开F，很快发现就是一个简单模拟，上机15分钟切了。之后继续思考A然而还是不会。后来看榜发现G过的比较多，于是和lxy讨论然后上机过掉。然后lzh先后想出了A和J两道DS（其实A好像不是DS？？）并且切了。我跟lxy讨论H。大概剩1h的时候我想出了H的做法，但是lzh正在写D所以我没上机。剩30min时lzh调D调炸了，我上去写H，但是发现很多细节都没考虑，最后剩5min的时候弃了换lzh继续调D，最后也没过。。感觉如果最后盯着一道题做可能好一点？？

== 题解 ==
A:每次修改改变分数相同的数字，给每个分数一个lazy标记维护一下就可以了（lzh）

B:

C:按题意模拟即可（lxy）

D:最短路+凸包+拓扑排序（lzh）

E:签到题

F:就是求一个生成树。注意边是O(n^2)级别的，在加边过程中不要加完全图，只加n-1条边即可。（fr）

G:求出每个点对另一个点贡献的概率（简单的组合问题），利用期望定义求解即可。（fr）

H:先给整个图像减掉y=gx，则问题转化为求图像上两个纵坐标相等的点的最远距离。对于每个点，求出它右面最远的比它高的点，然后二分查找答案即可。（fr）

I:签到题

J:ddp 板子（lzh）

K: 

[/wiki/2020-team10 返回]

Rank和提交情况

Solved: 7/11

流水账

（written by lxy）

这一场感觉很流畅，前半部分就一直过过过，除开签到稍微慢了一点，基本就是写写就过了。在过了7题后，我们同时开了两个题，是正解，但调试失败，就很尴尬。不过比第一场进步了不少，希望大家能尽快进步！！！

个人小结

lzh：A了四题。开场先看了E发现是个签到水题，正好lxy在写就接下去了，然而因为精度问题炸了很久，最后确定没有其他问题改用整数来写终于过了。期间lxy和我说了I题题意，也是签到题，就先把I过掉了。本来以为会做K题，但是K没人过，想了想细节发现有点难做弃了。听fr说A题有nlog^{2做法回去看了A题（结果他说的其实是n}2log），本来想了一个nsqrt*log的做法，优化着就变成了线性了，轻松过掉。看了下J题发现是个常见套路DS，很快就调过了。最后主攻D题，思路正确但是不知道哪里炸了，也没空写对拍，最后也没调出来。

lxy：这场我躺的很舒服。在机上写了两个签到都被lzh赶了下来（不知道我在思考什么呜呜呜），然后趁空机时间写了个c，后面和fr讨论出了g把他赶去上机，做好了剩下的题一半的嘴题工作。感觉比第一场好很多，可能是数学题少了。

fr：开场先开了A，感觉是个大DS所以弃了。然后开F，很快发现就是一个简单模拟，上机15分钟切了。之后继续思考A然而还是不会。后来看榜发现G过的比较多，于是和lxy讨论然后上机过掉。然后lzh先后想出了A和J两道DS（其实A好像不是DS？？）并且切了。我跟lxy讨论H。大概剩1h的时候我想出了H的做法，但是lzh正在写D所以我没上机。剩30min时lzh调D调炸了，我上去写H，但是发现很多细节都没考虑，最后剩5min的时候弃了换lzh继续调D，最后也没过。。感觉如果最后盯着一道题做可能好一点？？

题解

A:每次修改改变分数相同的数字，给每个分数一个lazy标记维护一下就可以了（lzh）

B:

C:按题意模拟即可（lxy）

D:最短路+凸包+拓扑排序（lzh）

E:签到题

F:就是求一个生成树。注意边是O(n^2)级别的，在加边过程中不要加完全图，只加n-1条边即可。（fr）

G:求出每个点对另一个点贡献的概率（简单的组合问题），利用期望定义求解即可。（fr）

H:先给整个图像减掉y=gx，则问题转化为求图像上两个纵坐标相等的点的最远距离。对于每个点，求出它右面最远的比它高的点，然后二分查找答案即可。（fr）

I:签到题

J:ddp 板子（lzh）

K:

附加文件

• Standing2.png by longxy