2019-team666-0005
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2019-team666 返回]
== 概述 ==
[[Image(Submissions.png,1000px)]]
七月集训第5场
== 流水账 ==
/*今天全程自闭调J不知道发生了啥 你们看到了补一下鸭*/
开场tjc看出K题可做写了10分钟发现看错题了，改了一会才过，'''K1y22'''，hyw秒出H并上机花了2分钟写了一发，wa了，这时候榜上一堆人过I题，tjc去码了一下，'''I1y27'''，hyw继续改H，tjc和yyc讨论B解法，当hyw再次wa的时候yyc上机写了一发B，'''B1y48'''，写B的时候hyw看出哪里写错了，上机改了一下，'''H3y53'''。这时没题可写了，三人分别开题，tjc看C、yyc看G、hyw看J，tjc最先想出来，讨论了一下解法就上机写了，'''C1y74'''，tjc去想E，yyc上机写G，'''G1y150'''，期间E和J都想出来了，由于榜上J题没人过，tjc先去写了E，'''E1y187'''，接下来hyw写J，tjc看A，yyc看F，yyc先想出F是个最小树形图问题，对着板子分析了一下感觉由于边权有特殊性可以直接跑过去，于是趁J题wa的时候写了一下，交上去T了，调了一会以后hyw发现J题比较函数没开long long，改了一下交上去就过了'''J3y275'''，最后25分钟尝试调F、写A的乱搞、写F的乱搞，都没有AC。
== 总结 ==
A题想到了离正解很近的地方，最后又跑偏了
F题最小树形图板子是n^3^的，需要准备一个mlogn和一个n^2^+m的板子（当然，nlogn+m更好）
=== yyc ===
为什么我一直都觉得最小树形图是n^2^的...
=== tjc ===
=== hyw ===
再忘写longlong我是狗
=== 题解 ===
官方题解 http://2018.nwerc.eu/files/nwerc2018slides-handout.pdf
A：两维独立，对于每一维合并顶点逆序的二次函数，直到不能合并为止（注意精度！推式子可能会导致精度爆炸，要用含有尽量少乘除法操作的式子计算最终结果）
B：反着贪心，使得序列反向后字典序最小 例题：hnoi2015 菜肴制作
C：以重心为根后按dfs序平均分配角度（相当于与子树大小有关），将边平移至合适位置即可
D：求出每个点到起点和终点的距离，二分答案w，将到起点+终点距离<=a+w的点标记为好的，如果一条边(u,v)中u是好的，且这条边长度+v到终点距离<=w，将v和这条边标记成好的，然后考虑所有好的边，如果这个图有环则合法，否则如果在图中停留时间长度>=b合法，否则不合法。
求图中停留时间长度：latest[i]表示在i点时的停留时间长度，初始时latest[i]=a+w-到终点距离，然后在新图中dp即可，latest[v]=max(latest[v],latest[u]+len)。
处理在家停留情况，需要在原图中加一条从1到1长度为0的边。
E：concat没用，sorted可以覆盖掉里面的所有操作，相当于直接给区间排序，shuffle同理，如果shuffle控制的区间里面的数不全相同，那么需要sort一下并标记shuffle的区间，最后比较两个序列是否完全相同&&标记的区间是否完全相同即可
代码细节：思想是把相同操作封装起来，readgroup读入int、忽略其他字符直到小括号匹配为止，readlist读入int、忽略其他字符直到右中括号为止（好像写麻烦了，readgroup和readlist本质相同），readint就是正常的读入优化
F：最短路/复杂度优秀的最小树形图
G：每次走到边界外两格
H：签到，分奇偶贪心填数
I：sort完了for一遍
J：注意到多个相同的最高点数变化会循环，利用这个性质，先将后n-1个数排序，递推得到每个数和名次在它前一位的数相等所需要的时间以及相等时的点数，可以求得后n-1个人点数最大值达到julia的点数之前有几个人的点数相等，然后求一个循环节模拟即可。
K：反着暴力[/wiki/2019-team666 返回]
概述
七月集训第5场
流水账
/*今天全程自闭调J不知道发生了啥 你们看到了补一下鸭*/
开场tjc看出K题可做写了10分钟发现看错题了，改了一会才过，K1y22，hyw秒出H并上机花了2分钟写了一发，wa了，这时候榜上一堆人过I题，tjc去码了一下，I1y27，hyw继续改H，tjc和yyc讨论B解法，当hyw再次wa的时候yyc上机写了一发B，B1y48，写B的时候hyw看出哪里写错了，上机改了一下，H3y53。这时没题可写了，三人分别开题，tjc看C、yyc看G、hyw看J，tjc最先想出来，讨论了一下解法就上机写了，C1y74，tjc去想E，yyc上机写G，G1y150，期间E和J都想出来了，由于榜上J题没人过，tjc先去写了E，E1y187，接下来hyw写J，tjc看A，yyc看F，yyc先想出F是个最小树形图问题，对着板子分析了一下感觉由于边权有特殊性可以直接跑过去，于是趁J题wa的时候写了一下，交上去T了，调了一会以后hyw发现J题比较函数没开long long，改了一下交上去就过了J3y275，最后25分钟尝试调F、写A的乱搞、写F的乱搞，都没有AC。
总结
A题想到了离正解很近的地方，最后又跑偏了
F题最小树形图板子是n3的，需要准备一个mlogn和一个n2+m的板子（当然，nlogn+m更好）
yyc
为什么我一直都觉得最小树形图是n2的...
tjc
hyw
再忘写longlong我是狗
题解
官方题解 http://2018.nwerc.eu/files/nwerc2018slides-handout.pdf
A：两维独立，对于每一维合并顶点逆序的二次函数，直到不能合并为止（注意精度！推式子可能会导致精度爆炸，要用含有尽量少乘除法操作的式子计算最终结果）
B：反着贪心，使得序列反向后字典序最小 例题：hnoi2015 菜肴制作
C：以重心为根后按dfs序平均分配角度（相当于与子树大小有关），将边平移至合适位置即可
D：求出每个点到起点和终点的距离，二分答案w，将到起点+终点距离<=a+w的点标记为好的，如果一条边(u,v)中u是好的，且这条边长度+v到终点距离<=w，将v和这条边标记成好的，然后考虑所有好的边，如果这个图有环则合法，否则如果在图中停留时间长度>=b合法，否则不合法。
求图中停留时间长度：latest[i]表示在i点时的停留时间长度，初始时latest[i]=a+w-到终点距离，然后在新图中dp即可，latest[v]=max(latest[v],latest[u]+len)。
处理在家停留情况，需要在原图中加一条从1到1长度为0的边。
E：concat没用，sorted可以覆盖掉里面的所有操作，相当于直接给区间排序，shuffle同理，如果shuffle控制的区间里面的数不全相同，那么需要sort一下并标记shuffle的区间，最后比较两个序列是否完全相同&&标记的区间是否完全相同即可
代码细节：思想是把相同操作封装起来，readgroup读入int、忽略其他字符直到小括号匹配为止，readlist读入int、忽略其他字符直到右中括号为止（好像写麻烦了，readgroup和readlist本质相同），readint就是正常的读入优化
F：最短路/复杂度优秀的最小树形图
G：每次走到边界外两格
H：签到，分奇偶贪心填数
I：sort完了for一遍
J：注意到多个相同的最高点数变化会循环，利用这个性质，先将后n-1个数排序，递推得到每个数和名次在它前一位的数相等所需要的时间以及相等时的点数，可以求得后n-1个人点数最大值达到julia的点数之前有几个人的点数相等，然后求一个循环节模拟即可。
K：反着暴力
附加文件
- Submissions.png by aison