2017-Sp306-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
=== chenjb ===
继续是一套考验机时的题目，罚时控制做的还是不错的，最后这个D只差一点了，但是刚了1.5h没做出来还是比较可惜的，我和sub也出现了一些交流偏差。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：x，y显然独立。按顺序考虑坐标，如果更靠后就只就留着，否则和之前的点取加权平均。

 * B：越小的e尽量分配最大的i，在反图拓扑排序，用堆。

 * C：给每棵子树分配个角度，按照子树大小分配。

 * D：预处理起点到所有点的最短距离和所有点到终点的最短距离，然后考虑二分答案limit。对于一个点，如果满足d[1][i]<=A && d[1][i]+d[i][n]<=A+limit，那么这个点合法并且最迟要在A+limit-d[i][n]的时候到达(题目中提到可以在家里等着)；对于一条边(x,y,w)，如果x合法，且w+d[y][n]<=limit，则这条边也能做出即使反应，所以合法， y点也因此合法。对于抠出来的图，如果存在环，则必定有>=B的路径，因此合法；否则在dag上考虑一条加权最长链，除路径长度外，还要考虑在起点的最晚到达时间到达这段值，如果>=B则也合法。注意要预先判掉起点到终点的距离，如果d[1][n]<=limit则必定合法，如果d[1][n]>limit+A则必定不合法。
 * E：用vector套set，shuffle就是无序序列，塞成一个set。

 * F：最小树形图，注意要n^2^的。

 * G：每一步往前走2*i^2^+rand()%2，然后模拟。

 * H：最大构造显然是每个0前面1/0交替，奇数的话取头为1。

 * I：排序直接算。

 * J：最大值每log步会-1，然后所有人+log。模拟得到步数。

 * K：按题意模拟。

流水账

chenjb

继续是一套考验机时的题目，罚时控制做的还是不错的，最后这个D只差一点了，但是刚了1.5h没做出来还是比较可惜的，我和sub也出现了一些交流偏差。

oipotato

subconscious

题解

A：x，y显然独立。按顺序考虑坐标，如果更靠后就只就留着，否则和之前的点取加权平均。
B：越小的e尽量分配最大的i，在反图拓扑排序，用堆。
C：给每棵子树分配个角度，按照子树大小分配。
D：预处理起点到所有点的最短距离和所有点到终点的最短距离，然后考虑二分答案limit。对于一个点，如果满足d[1][i]<=A && d[1][i]+d[i][n]<=A+limit，那么这个点合法并且最迟要在A+limit-d[i][n]的时候到达(题目中提到可以在家里等着)；对于一条边(x,y,w)，如果x合法，且w+d[y][n]<=limit，则这条边也能做出即使反应，所以合法， y点也因此合法。对于抠出来的图，如果存在环，则必定有>=B的路径，因此合法；否则在dag上考虑一条加权最长链，除路径长度外，还要考虑在起点的最晚到达时间到达这段值，如果>=B则也合法。注意要预先判掉起点到终点的距离，如果d[1][n]<=limit则必定合法，如果d[1][n]>limit+A则必定不合法。
E：用vector套set，shuffle就是无序序列，塞成一个set。
F：最小树形图，注意要n²的。
G：每一步往前走2*i²+rand()%2，然后模拟。
H：最大构造显然是每个0前面1/0交替，奇数的话取头为1。
I：排序直接算。
J：最大值每log步会-1，然后所有人+log。模拟得到步数。
K：按题意模拟。

附加文件

1.png by chenjb