Contest Info

date: 2017.07.30 10:00-15:00

practice link

Solutions

A. Hard Code

签到题

B. Golden Radio Base

题目大意：令 \(\phi = \frac{1+\sqrt{5}}{2}\)，求 \(n\) 的 \(\phi\) 进制表达式（每一位只能是 \(01\)），且表达式中不能含有 \(11\)。

题解：

法一：观察到有 \(\phi + 1 = \phi^2\)，以及 \(2\phi^2 = \phi^3 + 1\)。所以有 \(\phi^n = \phi^{n-1}+\phi^{n-2}\)，以及 \(2\phi^n = \phi^{n+1}+\phi^{n-2}\)。稍微分析可以发现不会超过 \(100\) 位，所以直接暴力用上面的式子展开即可，每次循环 \(100\) 为验证条件，直到符合条件为止。

法二：设数列 \(a_{0}=1, a_{1}=3, a_{n}=3a_{n-1}-a_{n-2}\) ，易证 \(a_{0}=\phi^{0}, a_{i}=\phi^{2i}+\phi^{-2i}(i\ge 1)\) ，我们尝试用尽可能少的 \(a_{i}\) 中的项来表示 \(n\) ，也就是每次贪心地选择 \(a_{i}\) 中最大的小于等于 \(n\) 的项减去，直到 \(n\) 为 \(0\) 。

显然有 \(3a_{i} \ge a_{i+1}\) ，因此 \(a_{i}\) 中每一项会用到不超过两次。这样我们就得到一个数列 \(\cdots?0?0?.0?0?\cdots\) ，其中 \(?\) 为 \(0, 1, 2\) 。我们从高位到低位把 \(2\) 消掉，再从低位到高位把连续的 \(1\) 消掉——我没有想到怎么证明这样做一次就能保证满足题目要求，不过能 AC ，而且显然的是，即使这样不正确，那么用 W 的方法再做几次，需要的次数也会非常少。

C. Little Tiger vs. Deep Monkey

题目大意：有 \(n\) 道题目，每道题目都有 \(\frac{1}{2}\) 的概率正确，每道题目都有一个对应的分数 \(sc_i \leq 1000\)，如果正确，就能得到该题目对应的分数。给出一个浮点数 \(P\) ，问至少得多少分才能使得分不超过这个分数的概率不小于 \(P\)。

题解：直接 dp，令 \(f[i][j]\) 为前 \(i\) 道题目得分为 \(j\) 的概率，最后枚举分数 \(j\) 判断 \(\sum\limits_{i=0}^{j} f[n][i]\) 是否不小于 \(P\) 即可。

D. Bathysphere

题目大意：给你一段 \([0, L]\) 上的折线，折线在 \(x\) 轴的上方，再给你一个长度 \(d\) ，求 \([x-d,x+d](d \leq x \leq L-d)\) 这段区间上折线的期望高度关于 \(x\) 的最大值。

题解：设折线方程为 \(f(x)\) 。 \(E(x)=\int_{x-d}^{x+d}f(t)dt\) ，故 \(E'(x)=f(x+d)-f(x-d)\) ，而且 \(f\) 是个连续函数，所以要求最大值我们只需要找 \(x=d,x=L-d\) 和 \(f(x+d)=f(x-d)\) 的地方就好了。

E. Min-max-multiply

unsolved

F. RP problem

题目大意：给你一个无自环的有向图，保证每个点的出度大于 \(0\) ，每个点有一个 RP 值，所有点的 RP 值之和为 \(1\) ，每天每个点把自己的 RP 等分给它指向的结点，问有多少种 RP 分配方案使得每个点的 RP 永远不变，若有唯一一种，问是否能通过给 \(n-1\) 多连一条出边，使 \(n-1\) 的 RP 变大，若能，求出使 RP 最大的连边方案，若有多种方案，输出编号最小的点。

题解：列出线性方程组然后高斯消元（容易发现没有必要列出 \(n-1\) 的 RP 守恒方程）： \[ \left\{ \begin{aligned}\\ &x_{0}-\frac{[1 \to 0]}{deg^{+}(1)}x_{1}-\cdots-\frac{[n-1\to0]}{deg^{+}(n-1)}x_{n-1}=0\\ &\vdots\\ &-\frac{[0 \to n-2]}{deg^{+}(0)}x_{0}-\frac{[1 \to n-2]}{deg^{+}(1)}x_{1}-\cdots+x_{n-2}-\frac{[n-1\to n-2]}{deg^{+}(n-1)}x_{n-1}=0\\ &x_{0}+x_{1}+\cdots+x_{n-1}=0 \end{aligned}\\ \right. \]

高斯消元以后，若 \(mat[n-1][n-1]\) 为 \(0\)，则有无穷多组解，否则恰有一组解（容易证明不可能无解）。对于第二个问题，如果暴力枚举新连的边并且每次都重新高斯消元会 TLE 。我们发现新连一条边只改变矩阵的最后一列，而对前 \(n-1\) 列高斯消元时，与最后一列无关，于是就可以愉快地利用这个性质加速了，复杂度 \(\mathcal{O}(n^{3})\) 。

G. Mosaic

题目大意：给出一个 \(n \times n\)（\(n \leq 800\)） 的矩阵，初始时矩阵的每个位置都是一个不超过 \(10^9\) 的非负整数。有 \(q\) 次询问，每次给出一个位置 \((x,y)\) ，和一个长度 \(L\) （\(L \leq 1000\) 且为奇数），问以 \((x,y)\) 为中心的子矩阵的最大值和最小值的平均值是多少，并把 \((x,y)\) 这个位置修改为这个值。

题解：用二维线段树维护，奇数层按 \(x\) 划分区间，偶数层按 \(y\) 划分区间。

H. Tower

unsolved

I. String

题目大意：给你一个字符串 \(S\)，和两个整数 \(L,M\)。我们认为 \(S\) 的一个子串是“可取”的，当且仅当：

• 子串长度为 \(M\times L\)
• 子串可以被分成 \(M\) 个串的连接，每个串长为 \(L\)，并且这 \(M\) 个串互不相等

求 \(S\) 的“可取”的子串个数。

题解：字符串hash。令 \(S = s_0s_1\dots s_{n-1}\)，定义hash函数 \(H(x) = \sum \limits_{i = x}^{n-1} s_i\cdot base^{i-x}\)。那么子串 \(S[i, i + L - 1]\) 的hash值为 \(H(i) - H(i + L)\cdot base^L\)。我们只需要枚举 \(i\in [0, L)\) 为子串的开头，用一个 map 来维护hash值即可。放入 \(m\) 个串之后如果 map 的大小等于 \(m\)，那么答案加一，然后每次从后面加入一个串，从前面删掉一个串。

J. Tri-war

题目大意：给你一棵树，\(m\) 次询问。每次询问给出三个不同的关键点 \(a, b, c\)。一个点被某个关键点占据，当且仅当另外两个关键点到它的距离，严格大于该关键点到它的距离。求每个关键点占据的点个数。

题解：考虑两个关键点的情况。显然我们只需要找到关键点 \(u, v\) 上的分界点（或者分界边），将它们分开即可。分开的两部分分别属于一个关键点。那么三个关键点的时候，我们先单独考虑被关键点 \(a\) 占据的点的个数。我们求出 \(a,b\) 的分界点，\(a,c\) 的分界点。通过讨论两个分界点分别在 \(a \rightarrow lca(a, b) \rightarrow b\) 和 \(a \rightarrow lca(a, c) \rightarrow c\) 两条链上的位置，和它们之间的相互关系，就可以求得被关键点 \(a\) 占据的点的个数。对 \(b,c\) 同理。