=====比赛信息=====

  * **日期：2020.6.26**

  * **比赛地址：** [[https://www.jisuanke.com/contest/10792/rank?page=1|传送门]]

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

=====题解=====

====A -  A Journey to Greece====

===solved by lxh===

===written by lxh===

===题意===

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

===数据范围===

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

===题解===

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

====B - Bounty Hunter II====

===solved by tyx===

===题意===

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

===数据范围===

$N \le 10^3$

===题解===

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

====C - Cake====

===solved by gyp===

===题意===

给定n边形和一个r。要确定一个比例s，连结与每个顶点相邻的两条边上，靠近该顶点的s等分点，并切掉这两个s等分点与顶点构成的三角形。使得最终面积是原先的r倍。

===数据范围===

$n\le 100$，$0.25<r<1$，坐标小于等于$10^8$

===题解===

可以证明，所求的s一定大于2，即不会有两个被切掉的三角形有重合。算出总面积和所有顶点和相邻两个顶点构成的三角形面积之和。前者乘$1-r$等于后者除以$s^2$

====D - Carpets====
===solved by lxh,gyp===

===written by lxh===

===题意===

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

===数据范围===

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

===题解===

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

====E -  Change of Scenery====

===solved by lxh===

===written by lxh===

===题意===

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

===数据范围===

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

===题解===

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

====F - Divisions====

===solved by gyp===

===题意===

给定N，求N的约数个数

===数据范围===

$N\le10^{18}$

===题解===

先筛出$10^7$以内质数，并除去N中10^7以内质数的约数。剩下的部分若不为1，则要么是一个大质数，要么是两个大质数的乘积，要么是一个大质数的平方。开根再平方，可以很容易判断是否是最后一种情况。那么接下来就只需判断是否是大质数了。这时，可以使用Rabin-Miller测试法，选2,3,5,7,11,13,17,19,23，进行费马小定理计算。若都$a^{p-1}\equiv 1\pmod p$，则p是质数。

====G - Extreme Sort====

===solved by gyp===

===题意===

其实就是问一组序列是不是不减的

===数据范围===

$n\le 1024$

===题解===

略

====I - Milling machines====

===solved by gyp===

===题意===

模拟一下，有点复杂，略了

===题解===

水题，略

====J - Souvenirs====

===solved by gyp===

===题意===

最开始有c个金币，一个金币可以换g个银币。n个商人，每个人能卖一个纪念品。每个纪念品的价格不同，用银币标出。不同商人对金币的找零方式也有所不同（分为三种）。购买纪念品必须按顺序。

===数据范围===

$g,c,n\le 100$，纪念品价格小于100

===思路===

dp[i][j]表示有i个金币，j个纪念品时最多的银币个数。如果不存在满足要求的情况就是-1。初始时，只有dp[c][0]=0。针对不同的商人，dp方程有三种情况。稍微推一推即可。

====K - Upside down primes====

===solved by tyx===

===题意===

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

===数据范围===

$N \le 10^{16}$

===题解===

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

=====Replay=====

第一小时：tyx和lxh想出A，lxh开始写A，gyp想F、E，tyx想B想出，然后tyx和gyp开始想C并想出，lxh写出A，tyx开始写K但是一直WA

第二小时：tyx发现了问题过了K，gyp开始写F发现longlong不够用，改用__int128后成功通过，tyx开始写B但是WA了，gyp开始写G并通过，然后lxh开始写E并通过，gyp开始写C但是WA

第三小时：gyp发现C没开longlong，开后通过，tyxB题无法调出于是换了方法后通过，lxh开始写D，写到一半发现比较麻烦于是暂停，gyp开始写I，tyx和lxh开始想J并想出

第四小时：gyp写出I后开始写J，J错了两次发现有一个细节错误，通过J后lxh把D完善后通过

第五小时：三个人一起看H但是没有看懂，最后没有做出

=====总结=====

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