Contest Info

date: 2017.07.28 10:00-15:00

practice link

Solutions

A. GPA

签到题

B. Poor Warehouse Keeper

题目大意：一个计价表可以显示两个整数 \(x\) 和 \(y\) ，分别表示物品的总数和它们的总价（任意两个物品的单价始终认为是相等的）的整数部分。计价表上有两个按钮，按钮 \(1\) 能使 \(x\) 增加 \(1\) ，并且总价 \(y\) 也同时增加使得物品的单价（按实际的价格计算，而并非屏幕显示的整数部分）不变；按钮 \(2\) 能使 \(y\) 增加 \(1\) ，这个操作将会改变物品的单价。一开始，物品的数量为 \(1\) ，价格恰好是 \(1\) ，给出一对 \(x \leq 10\) 和 \(y \leq 10^9\) ，问至少要操作多少次按钮才能使得计价表显示的两个数恰好是 \(x\) 和 \(y\) ，如果无解，则输出 \(-1\) .

题解：先假设有解，显然按钮 \(1\) 需要按的次数是确定的，为 \(x-1\) . 任意时刻我们只需要关心单价的变化，而我们最后需要得到的单价的范围是一个左闭右开的区间 \(\left[ \frac{y}{x},\frac{y+1}{x} \right)\)。只有使用按钮 \(2\) 才能改变单价，我们需要考虑如何使得使用按钮 \(2\) 的次数最少。枚举使用按钮 \(2\) 的时候 \(x\) 的值，则每使用一次按钮 \(2\) 会使单价增加 \(\frac{1}{x}\) 。 显然，在不超过最终单价上界的情况下，尽可能在 \(x\) 较小的时候使用按钮 \(2\) 是最优的，因此，我们可以使用除法和取整来实现浮点数的带余除法来计算每个 \(x\) 需要使用的按钮 \(2\) 的次数，然后判断是否在最终的单价区间中即可。无解的情况就是单价小于 \(1\) ，或者是枚举完所有 \(x\) 之后依然不能落在区间内的情况。

C. Campus Design

题目大意：给出一个 \(n \times m\) 的棋盘（\(n \leq 100\)，\(m \leq 10\)），棋盘上有一些坏点，要用一些 \(1 \times 1\) 和 \(1 \times 2\) 的骨牌去覆盖这个棋盘，所有没有坏点的格子都必须被覆盖，所有有坏点的格子都不能被覆盖，并且要求使用的 \(1 \times 1\) 的骨牌是数量不能少于 \(C\) 且不能多于 \(D\) （\(0 \leq C \leq D \leq 20\)），问一共有多少种不同的方案数，输出时对 \(1000000007\) 取模。

题解：因为 \(m\) 非常小，所以我们可以对轮廓线进行状态压缩，然后就可以逐格 \(dp\) 了，令 \(f[i][j][k][s]\) 表示当前在棋盘的 \((i,j)\) 位置，使用的 \(1\times 1\) 的骨牌数量为 \(k\) ，轮廓线的状态为 \(s\) 的方案数（\(s\) 是一个 \(m+1\) 位的二进制数，第 \(i\) 位为 \(1\) 表示轮廓线对应位置需要补全一个 \(1 \times 2\) 的骨牌）。使用滚动数组，时间复杂度为 \(O(nmk \cdot 2^{m+1})\) ，空间复杂度为 \(O(k \cdot 2^{m+1})\)，其中 \(k\) 为最多能使用的 \(1 \times 1\) 的骨牌数量。

D. Shoot

题目大意：在三维空间中，给你一条线段和 \(n\) 个三角形，现在等概率地从线段上选取一点，过这点沿给定方向引一条直线，问这条直线期望与多少个三角形相交？

题解：显然我们可以对每个三角形分别计算后把答案相加。对每个三角形我们分类讨论，设线段为 \(ST\) ，直线的方向为 \(\boldsymbol{r}\) ，三角形为 \(ABC\)：

• 若 \(\vec{ST}\parallel\boldsymbol{r}\)
  • 若 \(ST\) 与 \(\Delta ABC\) 相交，则答案 \(+1\)
  • 否则答案不变
• 否则，若 \(\boldsymbol{r}\parallel平面ABC\)
  • 若 \(ST\) 在平面 \(ABC\) 上，则将 \(\Delta ABC\) 投影到线段 \(ST\) 上，答案加投影所占 \(ST\) 比例
  • 否则答案不变
• 否则求出 \(ST\) 和 \(\boldsymbol{r}\) 组成的平面与 \(\Delta ABC\) 的交线段，将交线段投影到线段 \(ST\) 上，答案加投影所占 \(ST\) 比例

E. Circular Lamps

unsolved

F. Lunch Time

题目大意：有一个 \(n\) 个点，\(m\) 条边的有向图，每条边有一个容量 \(c\) ，表示每分钟能容纳 \(c\) 个人同时通行，假设每个人通过每条边的时间都是 \(1\) ，现在一共有 \(k\) 人，都想要从 \(0\) 号点去 \(n-1\) 号点，问最后到达的人最短需要用多少时间？

题解：我们考虑使用费用流来做，枚举只使用费用前 \(x\) 小的增广路（费用单调递增）来走的答案来更新最终的答案。我们需要记录：第 \(x\) 次增广路的费用（即走这条路到达的时间）\(\text{len}\) ，上一次增广路的费用 \(\text{last}\) ，当前增广路的流量 \(a\)，不超过时间 \(\text{last}\) 到达终点的最多人数 \(\text{cur}\)，第 \(x\) 次之前所有流的流量之和 \(\text{sum}\)。那么，可以算出，不超过时间 \(\text{len}\) 到达终点的最多人数 \(\text{cur}'= \text{cur} + (\text{len}-\text{last}) \times \text{sum} + a\) （每条增广路都可以把流量这么多的人全部堆在倒数第二个点，所以每一个额外的单位时间，可以贡献这么多人数），当前所有流的流量之和 \(\text{sum}'= \text{sum} + a\)，当前的答案为 \(\text{len} + \max (0,\lceil \, \frac{k-\text{cur}'}{\text{sum}'} \, \rceil)\)。

G. Drunk

题目大意：一个醉汉位于 \(n\) 维欧氏空间的原点，他走一步等概率移动到所有满足 \(0 \leq x_{i}, \sum_{i = 1}^{n}x^{2}_{i} \le R\) 的点，问他的期望坐标中最小的那一维是多少。

题解：显然根据对称性每一维坐标是相等的，不妨求 \(x_{1}\) 的值。设 \(V_{n}(R)\) 为半径为 \(R\) 的 \(n\) 维球的体积，答案即为： \[ \begin{aligned}\\ &\int_{0 \leq x_{i}, \sum_{i = 1}^{n}x^{2}_{i} \le R}x_{1}\mathrm{d}x_{1}\cdots\mathrm{d}x_{n}\\ =&\frac{\int_{0}^{R}x\frac{V_{n-1}(\sqrt{R^{2}-x^{2}})}{2^{n-1}}\mathrm{d}x}{\frac{V_{n}(R)}{2^{n}}}\\ =&2R\frac{\frac{\pi^{\frac{n}{2}}}{\Gamma(\frac{n}{2}+1)}}{\frac{\pi^{\frac{n+1}{2}}}{\Gamma(\frac{n+1}{2}+1)}}\int_{0}^{1}t(1-t^{2})^{\frac{n-1}{2}}\mathrm{d}t\\ =&\frac{2R\Gamma(\frac{n+1}{2}+1)}{\sqrt{\pi}(n+1)\Gamma(\frac{n}{2}+1)} \end{aligned}\\ \]

H. Cirno’s Present

题目大意：给一棵树上的每个点三染色，三种颜色机会均等。确定一种染色方案之后，删去端点异色的边，考虑一种颜色的贡献为 \(\mathrm{max}(0, X-Y)\)，其中 \(X\) 是该颜色点数为奇数的连通块个数， \(Y\) 是该颜色点数为偶数的连通块个数。求三种颜色的期望贡献之和。乘以 \(3^n\) 之后模 \(10^9+7\) 输出。

题解：三种颜色是对称的。我们只考虑一种颜色即可，最后答案乘以 \(3\)。对一种颜色进行 \(dp\)。状态函数为 dp[u][i][j] 表示以 \(u\) 为根的子树， \(i = 0, 1, 2\) 分别表示不选 \(u\)，选 \(u\) 且当前连通块点数为奇数，选 \(u\) 且当前连通块点数为偶数，\(j = X - Y\)。因为最后一维可能为负数，所以我们实现的时候需要加上偏移量。注意当前点的贡献不能计算，因为依赖于父亲是否选择，还不能确定他是否为一个连通块的根。

I. Wall Painting

题目大意：给你 \(n\) 个数，对所有的 \(1 \leq k \le n\) ，问 \(n\) 个数的所有 \(C_{n}^{k}\) 种组合的异或和之和是多少。

题解：容易发现，各个二进制位互不影响，答案即为 \(\sum_{i=0}^{29}2^{i}\sum_{j=1}^{n}C_{b_{i}}^{j}C_{n-b_{i}}^{k-j}[j\&1==1]\) ，其中 \(b_{i}\) 表示 \(n\) 个数中，有 \(b_{i}\) 个数第 \(i\) 位上为 \(1\) 。

J. Ball

题目大意：给你若干个红、黄、蓝色的球，依次将它们排成一行，每放入一个球得到的点数为放入位置左边不同颜色的数量 \(+\) 右边不同颜色的数量，问所能得到的最大点数。

题解：贪心。假设每种颜色的球都有两个以上，容易想到最优的方案是： \(R \to RY \to RYB \to RYBR \to RYBYR \to RYBBYR \to RYB?BYR \to RYB??BYR \to \cdots\) 。当然可能有些球不足两个，分类讨论即可，方法类似。

K. D tree

题目大意：一棵点上有权值的树，给你一个 \(K\)，让你求出字典序最小的点对 \((u, v)(u\leq v)\)，满足 \(u\) 到 \(v\) 的路径上所有点的权值之积模 \(10^6+3\) 同余 \(K\)。

题解：树上点分治。对于每个儿子 \(v\)，求出以 \(v\) 为根的子树中，每个点到 \(v\) 的链的乘积。然后考虑经过 \(u\) 的链，我们只需要算出逆来，在之前处理过的子树中查找值为该逆元的编号最小的点即可。注意处理 \(u\) 作为端点的情况。然后更新答案，以及每个值能取到的最小的点。需要用时间戳来优化清空数组。