2020-2021:teams:hotpot:germancollegiateprogrammingcontest2015
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:germancollegiateprogrammingcontest2015 [2020/06/26 17:16] lotk |
2020-2021:teams:hotpot:germancollegiateprogrammingcontest2015 [2020/06/26 17:53] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| ===数据范围=== | ===数据范围=== | ||
| - | $ N\le 20000 $ | + | $ N\le 20000 $ $ P \le 15 $ $ M \le 1e5 $ $ G \le 1e5$ |
| - | + | ||
| - | $ P \le 15 $ | + | |
| - | + | ||
| - | $ M \le 1e5 $ | + | |
| - | + | ||
| - | $ G \le 1e5$ | + | |
| ===题解=== | ===题解=== | ||
| 行 49: | 行 43: | ||
| 已知最小路径覆盖=总点数-最大匹配数，所以只需要把原图转化为二分图然后求出最大匹配。<del>不过一开始写网络流T掉了，然后匈牙利算法过了，数据属实有点怪</del> | 已知最小路径覆盖=总点数-最大匹配数，所以只需要把原图转化为二分图然后求出最大匹配。<del>不过一开始写网络流T掉了，然后匈牙利算法过了，数据属实有点怪</del> | ||
| - | ====C - Cryptographer’s Conundrum==== | + | ====C - Cake==== |
| - | ===solved by tyx=== | + | ===solved by gyp=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给定n边形和一个r。要确定一个比例s，连结与每个顶点相邻的两条边上，靠近该顶点的s等分点，并切掉这两个s等分点与顶点构成的三角形。使得最终面积是原先的r倍。 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $n\le 100$，$0.25<r<1$，坐标小于等于$10^8$ | ||
| ===题解=== | ===题解=== | ||
| - | ====D - Carpets==== | + | 可以证明，所求的s一定大于2，即不会有两个被切掉的三角形有重合。算出总面积和所有顶点和相邻两个顶点构成的三角形面积之和。前者乘$1-r$等于后者除以$s^2$ |
| + | ====D - Carpets==== | ||
| ===solved by lxh,gyp=== | ===solved by lxh,gyp=== | ||
| 行 95: | 行 94: | ||
| 此题较为简单，我们只需要从 $1$ 开始做一遍最短路，再从 $N$ 做一遍，考虑怎么判断多条，我们显然可以轻松判断一条边在不在最短路上，若在，则给边的两点 $++d[x],++d[y]$ ，这徉处理之后，显然，如果有点$ d[x] > 2$，则一定有多条，如果两个端点 $d[1]==2||d[n]==2$ 则也存在多条。 | 此题较为简单，我们只需要从 $1$ 开始做一遍最短路，再从 $N$ 做一遍，考虑怎么判断多条，我们显然可以轻松判断一条边在不在最短路上，若在，则给边的两点 $++d[x],++d[y]$ ，这徉处理之后，显然，如果有点$ d[x] > 2$，则一定有多条，如果两个端点 $d[1]==2||d[n]==2$ 则也存在多条。 | ||
| - | ====F - Floppy Music==== | + | ====F - Divisions==== |
| - | ===solved by tyx,gyp=== | + | ===solved by gyp=== |
| - | + | ||
| - | ===written by tyx=== | + | |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给定N，求N的约数个数 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $N\le10^{18}$ | ||
| ===题解=== | ===题解=== | ||
| - | ====G - Goblin Garden Guards==== | + | 先筛出$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是质数。 |
| - | ===solved by tyx,gyp=== | + | ====G - Extreme Sort==== |
| - | ===written by lxh=== | + | ===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==== | ====K - Upside down primes==== | ||
| 行 139: | 行 172: | ||
| =====Replay===== | =====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但是没有看懂，最后没有做出 |
| =====总结===== | =====总结===== | ||
2020-2021/teams/hotpot/germancollegiateprogrammingcontest2015.1593162981.txt.gz · 最后更改: 2020/06/26 17:16 由 lotk
