CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
<HTML>
<!-- omit in toc -->
</HTML>
====== 2016 Multi-University Training Contest 1 ======

Virtual Participated on May 24, 2020.

VP available here: [[https://vjudge.net/contest/122988|Virtual Judge]]

Practice available on [[http://acm.hdu.edu.cn/search.php?field=problem&key=2016+Multi-University+Training+Contest+1&source=1&searchmode=sources|HDOJ]].

====== Results ======

===== Summary =====

  * Solved 6 out of 11 problems
  * Rank 27/532 in official records
  * Solved 8 out of 11 afterwards

===== Virtual Participation =====

<HTML>
<table>
<style>
td, th {text-align: center;}
.cell-accepted {color: #0a0;font-weight: bold;}
.cell-rejected {color: #00a;}
.cell-time {font-size: 1.0rem;display: block;}
.contest-name {font-size: 1.5em;color: #445f9d;}
.successfulChallengeCount {color: green;}
.unsuccessfulChallengeCount {color: gray;}
</style>
<tr>
<th style="width:2em;" class="top left">
#
</th>
<th style="width:2em;" class="top">
=
</th>
<code>
<th style="width:4em;" class="top">Penalty</th>
<th style="width:4em;" class="top">
        <a>A</a>
</th>
<th style="width:4em;" class="top">
        <a>B</a>
</th>
<th style="width:4em;" class="top">
        <a>C</a>
</th>
<th style="width:4em;" class="top">
        <a>D</a>
</th>
<th style="width:4em;" class="top">
        <a>E</a>
</th>
<th style="width:4em;" class="top">
        <a>F</a>
</th>
<th style="width:4em;" class="top">
        <a>G</a>
</th>
<th style="width:4em;" class="top">
        <a>H</a>
</th>
<th style="width:4em;" class="top">
        <a>I</a>
</th>
<th style="width:4em;" class="top">
        <a>J</a>
</th>
<th style="width:4em;" class="top right">
        <a>K</a>
</th>
</code>
</tr>
<tr c="375061" u="316241" class="this myself">
<td class="rank meta same" data-original-title title>
33
</td>
<td class="solved meta same" data-original-title title>
6
</td>
<td class="penalty meta same" data-original-title title>
1223 20:23:41
</td>
<td class="cell-accepted">
00:43:29<br> (-1)
</td>
<td class="cell-accepted">
04:32:18<br> (-3)
</td>
<td class="cell-rejected">
(-1)
</td>
<td class="cell-accepted">
02:03:26<br> (-1)
</td>
<td class="cell-accepted">
02:34:44<br> (-4)
</td>
<td class="prob ">
</td>
<td class="cell-accepted">
04:28:51<br>
</td>
<td class="prob ">
</td>
<td class="prob ">
</td>
<td class="prob ">
</td>
<td class="cell-accepted">
03:00:53<br>
</td>
</tr>
</table>
</HTML>

===== Submit Distribution in Members =====

^    Solved     ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^  G  ^  H  ^  I  ^  J  ^  K  ^
|     Pantw     |  √  |  √  |     |     |     |     |     |     |     |     |     |
|  Withinlover  |     |     |     |  √  |     |  O  |  √  |     |     |     |  √  |
|     Gary      |     |     |  O  |     |  √  |     |     |     |     |     |     |

(√ for solved during VP, ○ for after VP, - for tried but not solved)


----

====== Solutions ======

===== A: Abandoned country =====

  * Solved by **//Pantw//**

==== 题意 ====

给一个边权两两不同的无向图。求最小生成树，以及最小生成树中使得所有点对最短路平均值的最小值。

$n\le 10^5, m\le 10^6$。

==== 解法 ====

由于边权不同我们可以直接知道最小生成树是唯一的，那么求出来之后 DP 一下即可。

===== B: Chess =====

  * Idea by **//Pantw, Withinlover, Gary//**
  * Debug by **//Pantw, Withinlover, Gary//**
  * Code by **//Pantw//**

==== 题意 ====

$n\times 20$ 的棋盘，有若干相同的棋子，每个格子上至多有一个棋子，移动方式是：

  * 若一个棋子右边是空格子，那么它可以移动到该格子；
  * 若一个棋子隔着连续的一堆棋子，那么它可以跳过这些棋子，达到右边的第一个空格。
  * 棋子不能超出右边界。

给定初始状态，问先手必胜还是先手必败。

==== 解法 ====

由于 $20\times 2^{20}$ 不大，可以直接预处理出 SG 函数值。

然后就是经典的 Nim 游戏了。

===== 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 =====

  * Idea by **//Pantw//**
  * Code by **//Withinlover//**

==== 题意 ====

给定一个数列，每次查询一个区间 $[l, r]$。输出区间的最大公约数 $x$，同时输出满足最大公约数为 $x$ 的区间 $[l', r']$ 的个数。

==== 解法 ====

区间公约数查询是裸的ST表。预处理后直接回答。

针对第二问，可以发现最大公约数的取值不会太多。且固定 $l$ 时，$\gcd(a_l,a_{l+1},\dots,a_r)$单调递减，可以二分确定出每一次 $\gcd$ 变化的位置，然后用一个 $map$ 存一下。就做完了。

简易证明：考虑将 $a_l$ 质因数分解，易知当 $r$ 变化时， $\gcd$ 的值最多会下降其质因数个数次。

===== 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 =====

  * Idea by **//Withinlover//**, **//Pantw//**
  * Code in practice by **//Withinlover//**

==== 题意 ====

已知三个正整数 $n, m, p$，其中 $n$ 不含平方因子。

设 $k=\sum_{i=1}^{m}\varphi(i*m) \bmod {1000000007}$；

计算 $ans = k^{k^{k^{k\dots}}}\bmod p$，$k$ 有无限个。

==== 题解 ====

大力推公式，设 $F(n, m) = \sum_{i=1}^m\varphi(i*n)$

$$F(n,m)=\sum_{i=1,i\%p!=0}^m\varphi(i*n)+\sum_{i=1,i\%p==0}^m\varphi(i*n)$$ $$=\varphi(p)\sum_{i=1,i\%p!=0}^m\varphi\left(i*\frac{n}{p}\right)+p\sum_{i=1,i\%p==0}^m\varphi\left(i*\frac{n}{p}\right)$$ $$=\varphi(p)\sum_{i=1}^m\varphi\left(i*\frac{n}{p}\right)+\sum_{i=1,i\%p==0}^m\varphi\left(\frac{i}{p}*n\right)$$ $$=\varphi(p)\sum_{i=1}^m\varphi\left(i*\frac{n}{p}\right)+\sum_{i=1}^{m/p}\varphi\left(i*n\right)$$ $$=\varphi(p)F\left(\frac{n}{p},m\right) + F\left(n,\frac{m}{p}\right)$$

第一个难题解决，注意下递归的边界就可以做了。

计算 $ans$ 时，迭代使用欧拉定理，$A^B\bmod C=A^{B\%\varphi(C)+\varphi(C)}\bmod C$，显然会很快收敛为 $0$，后面的无限多个 $k$ 就没有意义了。迭代计算即可。

===== 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 =====

==== 题意 ====

==== 解法 ====

===== I: Solid Dominoes Tilings =====

==== 题意 ====

==== 解法 ====

===== J: Subway =====

==== 题意 ====

==== 解法 ====

===== K: tetrahedron =====

  * Solved by **//Withinlover//**

==== 题意 ====

多组数据

给定空间中四点坐标，求组成的四面体的内接球半径以及球心坐标。

==== 解法 ====

向量法可以计算出体积和表面积，进而得到半径

球心坐标太简单了，推推公式就行（狗头）


----

====== Timeline ======

^  Time  ^Action  ^
|   0    |Start   |
|  300   |End     |


----

====== Reflections ======
CVBB ACM Team

用户工具

站点工具

页面工具
