CVBB ACM Team

• 日期：2020.6.26

• 比赛地址： 传送门

• 做题情况：lxh(ADE)，tyx(BK)，gyp(CFGIJ)

一共有 $ N $ 个点，其中有 $ P $ 个是要观看的，有 $M$ 条边，有 $G$ 的时间，给出走每条边的时间，和每个点观看所需的时间，还有一个只能使用一次的特殊操作， 从一点到任意另外一点花费 $T$ 的时间，问是否存在一种方案，在 $G$ 内从 $0$ 开始访问每个需要观看的点再返回 $0$。

$ N\le 20000 $

$ P \le 15 $

$ M \le 1e5 $

$ G \le 1e5$

由于关联到的点只有最多15个，因此我们只需要求出这15个点到每个点的最短距离，再利状压 $DP$ 处理出回到0点并且访问了每个点的最短时间即可。

给出一个有$N$个点的DAG，问最小路径覆盖。

$N \le 10^3$

已知最小路径覆盖=总点数-最大匹配数，所以只需要把原图转化为二分图然后求出最大匹配。不过一开始写网络流T掉了，然后匈牙利算法过了，数据属实有点怪

给出一个区域 $(W × H)$ ，给出 N个地毯和其长宽 $wi,hi$，问能否完全覆盖区域。

$ W, H \le 100 $ $ N \le 7$

由于 $N$ 的范围实在太小，所以我们直接暴力从右上到左下搜索，遇到没覆盖的就尝试覆盖即可。

求图中有没有大于等于两条从 $1$ 到 $N$ 的最短路

$N \le 10000$ $M \le 1000000$

此题较为简单，我们只需要从 $1$ 开始做一遍最短路，再从 $N$ 做一遍，考虑怎么判断多条，我们显然可以轻松判断一条边在不在最短路上，若在，则给边的两点 $++d[x],++d[y]$ ，这徉处理之后，显然，如果有点$ d[x] > 2$，则一定有多条，如果两个端点 $d[1]==2||d[n]==2$ 则也存在多条。

在一个平面给出一些点，再给出一些圆，问有多少点没有被覆盖。（一个坐标上可以有多个点）

给出一个正整数$N$，现在这个数显示在一个每个数字用七段二极管显示的屏幕上，问如果把这个屏幕转180度显示的数还是不是质数。

$N \le 10^{16}$

按照题意做即可，不过要注意1不是质数。

第一小时：

第二小时：

第三小时：

第四小时：

第五小时：

• 判断质数的时候要注意1不是质数。
• 一定要注意题目的数据范围。