2020-2021:teams:mian:hdu_training:2016_multi-university_training_contest_1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:hdu_training:2016_multi-university_training_contest_1 [2020/05/24 23:02] withinlover |
2020-2021:teams:mian:hdu_training:2016_multi-university_training_contest_1 [2020/07/05 11:33] (当前版本) grapelemonade ↷ 页面2020-2021:teams:mian:hdutraining:2016_multi-university_training_contest_1被移动至2020-2021:teams:mian:hdu_training:2016_multi-university_training_contest_1 |
||
|---|---|---|---|
| 行 16: | 行 16: | ||
| * Solved 6 out of 11 problems | * Solved 6 out of 11 problems | ||
| * Rank 27/532 in official records | * Rank 27/532 in official records | ||
| - | * Solved 6 out of 11 afterwards | + | * Solved 8 out of 11 afterwards |
| ===== Virtual Participation ===== | ===== Virtual Participation ===== | ||
| 行 169: | 行 169: | ||
| ===== C: Game ===== | ===== C: Game ===== | ||
| + | * Idea by **//Gary//** | ||
| + | * Debug by **//Gary,Pantw//** | ||
| + | * Code by **//Gary//** | ||
| ==== 题意 ==== | ==== 题意 ==== | ||
| + | |||
| + | $n\times m$方格中有一些守卫，保证一个守卫同行同列以及以它为中心的九宫格内没有其他守卫，任意选方格中没有守卫的两点，求两点最短距离的期望 | ||
| + | |||
| + | $1\le n,m\le1000$ | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| + | 简单画图可以发现没有守卫时的最短距离即为曼哈顿距离，当被守卫隔开时最短距离即为曼哈顿距离+2 | ||
| + | |||
| + | 因而考虑将两种情况分开求解，先求的所有点对的曼哈顿距离，再求出隔开的点对额外的贡献，$\rm Ans=\frac{\sum dis}{\sum_{x,y\in没有守卫的点}1}$ | ||
| + | |||
| + | 曼哈顿距离可以通过遍历每行和每列来求解，如对于第i列，经过第i列的点对为$sum_{i左侧}\times sum_{i右侧}$，每一个点对都会对曼哈顿距离贡献1，求前缀和后扫描每行每列即可 | ||
| + | |||
| + | 对于守卫隔开的贡献，发现只有连续单调的守卫两边的点对会造成贡献，因为守卫个数极少，对每个守卫$O(n)$扫描来维护最长的连续单调守卫造成的贡献即可 | ||
| + | |||
| + | {{:2020-2021:teams:mian:hdutraining:4.png?400|}} | ||
| ===== D: GCD ===== | ===== D: GCD ===== | ||
| 行 192: | 行 208: | ||
| ===== E: Necklace ===== | ===== E: Necklace ===== | ||
| + | |||
| + | * Idea by **//Withinlover//** | ||
| + | * Code&Debug by **//Gary//** | ||
| ==== 题意 ==== | ==== 题意 ==== | ||
| + | |||
| + | 给标号的$n$个阴宝石和$n$阳宝石，相间放置围成圆，相邻的一对阴阳宝石匹配（仅能匹配一次）后可以产生价值，但有$m$对阴阳宝石不能产生价值，它们会变得暗淡，问暗淡的阴宝石最少为多少 | ||
| + | |||
| + | $0\le n\le 10,0\le m\le n\times n$ | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| + | |||
| + | 发现$n$较小，我们可以固定阳宝石，枚举阴宝石的排列，对每一种情况进行二分图匹配求得最大匹配$\rm Ans_i$，答案即为$n-\max\{\rm Ans_i\}$ | ||
| + | |||
| + | 需要注意由于是圆排列，枚举排列时固定一位只需要枚举剩余n-1位即可 | ||
| ===== F: PowMod ===== | ===== F: PowMod ===== | ||
| 行 221: | 行 248: | ||
| ===== G: Rigid Frameworks ===== | ===== G: Rigid Frameworks ===== | ||
| + | |||
| + | * Solved by **//Withinlover//**, **//Pantw//** | ||
| ==== 题意 ==== | ==== 题意 ==== | ||
| + | |||
| + | 给定 $n\times m$ 的一个网格，若无论外力如何作用，这个网格均不会变形，则称这个网格具有稳定性。显然初始的网格极易变形，是不具备稳定性的。如下图所示： | ||
| + | |||
| + | {{ :2020-2021:teams:mian:hdutraining:1.jpg?nolink&400 |}} | ||
| + | |||
| + | 你可以在每一个格子上任选一个对角线添加约束条件，也可以选择不加。询问有多少种增加约束条件的方法，使得添加约束条件后的网格具有稳定性。 | ||
| + | |||
| + | {{ :2020-2021:teams:mian:hdutraining:2.jpg?nolink&400 |}} | ||
| + | |||
| + | $2\times 3$ 的一个可能方案，此时网格不可变形。 | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| + | |||
| + | 选择两条对角线本质上并无区别，只是增加计数难度。 | ||
| + | |||
| + | 每一个位于 $(i, j)$ 的约束条件，本质上是固定了第 $i$ 行所有的竖边和第 $j$ 列所有的横边。如下图： | ||
| + | |||
| + | {{ :2020-2021:teams:mian:hdutraining:3.jpg?nolink&400 |}} | ||
| + | |||
| + | 建二分图，将每一行的竖边视为一个点，每一列的横边视为一个点。则左侧有 $n$ 个点，右侧有 $m$ 个点，每一个约束条件视为从左到右的一条连边。则原问题转化为 $(n + m)$ 个点的联通图计数问题。但是要注意由于可以在两条对角线中任意选择，每条边的贡献为 $2$。 | ||
| + | |||
| + | 裸的联通二分图计数可以参考blog：[[https://www.cnblogs.com/cenariusxz/p/5688549.html|连通二分图计数]] | ||
| + | |||
| + | 这里，记 $H[i][j] = 3^{ij}$，$F, G$ 递推式不变， 便可以得到答案。 | ||
| ===== H: Shell Necklace ===== | ===== H: Shell Necklace ===== | ||
| 行 245: | 行 296: | ||
| ===== K: tetrahedron ===== | ===== K: tetrahedron ===== | ||
| + | |||
| + | * Solved by **//Withinlover//** | ||
| ==== 题意 ==== | ==== 题意 ==== | ||
| + | |||
| + | 多组数据 | ||
| + | |||
| + | 给定空间中四点坐标，求组成的四面体的内接球半径以及球心坐标。 | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| + | |||
| + | 向量法可以计算出体积和表面积，进而得到半径 | ||
| + | |||
| + | 球心坐标太简单了，推推公式就行（狗头） | ||
2020-2021/teams/mian/hdu_training/2016_multi-university_training_contest_1.1590332558.txt.gz · 最后更改: 2020/05/24 23:02 由 withinlover
