======2020/06/20——2020/06/26周报======

=====团队训练=====

2020.6.26 [[germancollegiateprogrammingcontest2015|German Collegiate Programming Contest 2015]] ''prob:10/10/11'' ''rank:1/29''

=====林星涵=====

====专题====

无

=====陶吟翔=====

====专题====

本周无

=====郭衍培=====

====专题====

=====本周推荐=====

林星涵：[[https://nanti.jisuanke.com/t/A1408|A Journey to Greece]]

题意

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

数据范围

$ N\le 20000 $   $ P \le 15 $   $ M \le 1e5 $   $ G \le 1e5$

题解

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


陶吟翔：[[https://nanti.jisuanke.com/t/A1410|传送门]]

题意：给出一个有$N$个点的凸多边形，现在要把这个凸多边形的面积减少到它的$a$倍，减少的方法是在每一个角的两条边选择这个边的$\frac{1}{s}$组成三角形并把这个三角形切掉，现在给出凸多边形和$a$，求$s$。

解题思路：乍一看会想要二分，但是实际上可以直接把面积计算出来。首先在一个角切掉的面积是$S=\frac{e_1}{s} \times \frac{e_2}{s} \times sin\alpha$。我们发现总切掉的面积和$s^2$成反比，所以根据要切掉的面积可以直接计算出$s$。

郭衍培：

题意：给定一个有n个元素的集合A。给出m个数，判断每个数能否写成A中若干个数的和。$n\le 50000,m\le 50000$，A中最大元素小于50000