【题解】2020牛客NOIP赛前集训营-普及组（第六场）

写在前面

各位辛苦啦，感谢大家。

T1 七七七七

枚举几天可以完成，然后判断。

也可以用多个if解决问题。

注意到有些同学没有考虑的情况痛失分。

T2 平面旅行

直接从走到可以获得分。

从走到，并对唯一一个传送节点到达对应的点取min可以获得分。

简单建图求floyd最短路可以获得分。

预处理到达每个节点的距离，具体为所有传送门到其的距离和上一个点到其的距离的最小值，累计即可直接得到答案，可以得到分。

T3 小球下落

枚举每个小球的掉落情况，可以得到分。

模拟每个小球的掉落情况，可以得到分。

对于满分，显然从下往上贪心即可。

具体操作时每次贪心放到最下面可达的地方去，可不可达可以用规则判断。

可以发现只要有这三种情况之一就可以认为它们断开了：

xx

或者对于两层

x.
.x

或是

.x
x.

上述这三种情况会使上下区域断开，从而不可达。

可以用multiset或者其他方法动态维护最小值。

本题的时限比较宽松，复杂度小于的方法应该有很多。

T4 自由世界

简单写写if（可能不简单）可以获得分。

处理掉树上的情况+上面的特判可以获得分。

简单建图求floyd最短路可以获得分。

预处理到达每个节点的距离，具体为所有传送门到其的距离和上一个点到其的距离的最小值，累计即可直接得到答案，可以得到分。

具体的做法是以所有传送门为起点跑一次最短路（或者分开跑也行，但是控制一下常数），求每个点的最小值。

再以每个点为起点跑一次最短路，求到下一个点的最小值。

累计即可，原理上这样可以获得分，但可能因为常数原因会损失一定的分数。

下面是四题的标程：
T1: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45401125
T2: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45401131
T3: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45401136
T4: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45401148