FZU ACM 联合训练 Day4总结

题解

A

题意:
给定一个原始平面点集和一个询问平面点集,统计平面上有且仅有一个顶点在询问点集中的直角三角形的个数。两个点集大小不超过 (2000)

题解:
Day 2原题来着?
连我都会,极角排序,双指针扫一遍统计答案,注意精度。

感受:
口胡的,打题还是要靠基础扎实的公主。

D

题意:
给定一个大小适当的正整数,问它的倒数在十进制下是不是有限小数。

感受:
不说了,说了读者只会觉得我很傻。

E

题意:
很复杂,试着概括一下。
给定一个网格图,有两种格子,一种可以通过,反之则不然。
网格图第一行有若干个机器人,机器人会尝试向下移动,直到遇见一个转换器改变它的方向。
这样的转换器有四种,它们能把从某两个方向来的机器人调转到另一个方向去,但是没有转换器能支持调头,机器人转弯后会继续移动,直到碰见下一个转换器。
转换器只可以放在可以通过的格子上,且不能被放在同一个格子上。
网格图底部有若干出口,每个机器人只有抵达某个出口才算逃离了网格图,出口与机器人不必有确定的对应关系,但一个出口不可以容纳多个机器人。
任何时刻机器人可以处在同一个格子而不发生冲突(除了出口而外)。
求一种放转换器的方案,使得机器人可以全部逃离网格图。

题解:
发现每个格子最多被横/纵着通过一次,因为机器人的路径不可能重复(否则它们一定会走到同一个出口),也不可能反向重复(这样只会让逆行的机器人走回被逆行者的出发点)。
由于机器人之间是等价的,所以我们搞一个网络流,源点向机器人连边,每个格子向四周连边,出口向汇点连边,所有边的流量都是1。
容易发现会有很多不合法的情况(但是不包括路径重复和逆行的情况)。

  • 一个格子先被上->左了一次,又被下->右了一次。

容易发现这样是不优的,因为这两条路径若是要存在,则它们在别处一定还会有交(要么自己和自己相交,要么相互之间有两个交点),我们可以在这里直接把答案优化掉。

  • 一个格子先被上->左了一次,又被右->下了一次。

机器人之间是等价的。这种情况相当于没有放转换器。

还有两种情况是对称的,不说了。
做完了。

感受:
考场上没想,能有什么感受?

F

题意:
给定一个仙人掌森林,问有多少种删边方案让它变为一个树森林。沙漠化防治研究

题解:
这还用说?直接跑环,环边至少删一条,树边删不删根本无所谓。

Others

咕咕咕中,等待补档。

全场感受

Marser不在的第一天,想她(雾)。

原文地址:https://www.cnblogs.com/JiuPleber/p/FZUACMday4.html