Contest Info

date: 2019.03.07 16:25-21:25

practice link

Solutions

A. Self-Assembly

题目大意：给出一些正方形格子（每种都有无数个），正方形的每条边有 \(53\) 种，分别是 \(26\) 个字母拼接正负号或者是空。这些正方形可以任意旋转翻转，如果两个正方形某两条边的字母相同，正负相反，这两个正方形就可以通过这条边拼在一起，问是否可以拼出一个无穷大的连通块。

题解：等价于只能往上或者往右延伸得到一个环。以 \(53\) 种状态和是左边还是右边建点，以正方形作为边，一共有 \(106\) 个点，再枚举一个起点的左边或者下边，bfs 一次的复杂度是 \(106^2\) ，总的复杂度是 \(106^3\) 。

B. Hey, Better Bettor

题目大意：一个人赌博，每轮有 \(p\%\) 的概率赢，赢了加 \(1\) 元，输了减 \(1\) 元。他可以随时结束赌博，并且结束时如果输了钱，会返还其中的 \(x\%\) 给他。保证 \(p<50\)（黑心赌场）。问最优策略下他的期望收益。

题解：这个赌博是一个马尔可夫过程，某一轮之后的期望收益与之前的轮无关。因此我们是要找一个 \(L\) 和一个 \(R\)，如果当前输了 \(L\) 元或者赢了 \(R\) 元，那么就结束赌博。

下面我们称获得 \(R\) 元为赢得赌博。设 \(f(x)\) 表示当前有 \(x\) 元，赢得赌博的概率。显然有 \(f(L)=0,f(R)=1\)。另外有 \(f(x)=pf(x+1)+(1-p)f(x-1)(L<x<R)\)，即 \(f(x+1)=\frac{1}{p}f(x)-(\frac{1}{p}-1)f(x-1)\)。这个递推式的两个特征根为 \(1\) 和 \(\frac{1}{p}-1\)，记 \(\frac{1}{p}-1=t\)。不妨设 \(f(x)=\alpha+\beta\cdot t^{x}\)，可以解得 \(\displaystyle{\alpha=-\frac{t^{L}}{t^{R}-t^{L}},\beta=\frac{1}{t^{R}-t^{L}}}\)。我们要使 \(\displaystyle{f(0)=\frac{1-t^{L}}{t^{R}-t^{L}}}\) 最大。可以证明，这个函数固定 \(L,R\) 之一，对另一个变量都是先增后降的；对于其中一个取最大值，另一个变量的变化情况很复杂（我懒得算了），但是似乎也能证明是先增后降的。这题的数据范围保证我们能直接暴力枚举所有 \(L,R\)，直到函数开始单调下降为止，而三分反而是不可行的，因为这题相邻两项的差可能小于浮点数的精度范围。

C. Surely You Congest

题目大意：无向图上，初始有 \(c\) 辆车在一些位置。让你选择最多的车，使得它们一起从时刻 \(0\) 开始朝着 \(1\) 出发各自走某条最短路径，没有两辆车同时进入一条边。

题解：建出最短路径 DAG。可以发现，最短路长度不同的点互相独立，它们显然不可能同时进入同一条边。对于最短路径长度相同的点，如果它们的路径有边相交，显然也不行。所以对每种路径的点求一遍最大流。总流量最大为 \(c\)，所以复杂度 \(\mathcal{O}(c(n+m))\)。

D. Factors

签到题，暴搜即可。

E. Harvard

题目大意：一个内存中有 \(b\) 个字，每个字有 \(s\) 个字节。访问 \(0\) 号字的 \(s_{0}\) 字节，可以用一条指令 \(\text{lb}\;0, s_{0}\) 完成；访问其它字的 \(s_{0}\) 字节，可以用指令 \(\text{lb}\;1, s_{0}\) 完成，这条指令访问的字存储在寄存器 \(\text{BSR}\) 中，向 \(\text{BSR}\) 中写入值也需要一条指令。开始时 \(\text{BSR}\) 中存储的是一个 undefined 的值。

现在给你一段程序，其中需要依次访问若干变量，每种变量可出现若干次，但最多只有 \(13\) 种变量；程序有循环结构。现在要你把这些变量分配到内存中，使得这段程序编译后的总指令数最小。程序长度至多 \(10^{3}\)。

题解：编译部分用递归下降分析法很容易解决，这里就不赘述了。

假设我们分配好了变量，那么最优策略显然是：只在访问不同的非 \(0\) 号字之间时（切换字），才向 \(\text{BSR}\) 中写入值。

暴搜变量的分配方案，可以用如下策略剪枝：\(0\) 号字应当尽可能填满；非 \(0\) 号字之间互相没有区别；任意两个非空字中的变量个数之和应当大于 \(s\)（否则合并这两个字更优）。

这样最坏情况下状态大约有 \(2\cdot10^{6}\) 种，如果每种都重新编译，复杂度仍然较高。注意到，\(0\) 号字中的变量一旦确定，那么其它变量中每一对在程序中相邻的位置数也就确定了，我们可以在一次编译中预处理出所有这样的数量。之后搜索到每一个状态时，我们不必再次编译，利用预处理的值计算不同的非 \(0\) 号字之间的变量的答案即可。

F. Low Power

题目大意：有 \(n\) 个机器，每台机器有两块芯片，每块芯片需要 \(k\) 块电池供电。现在给出 \(2nk\) 块电池，求一种分配方案，使得所有机器的最大代价最小。每块芯片的代价为其 \(k\) 块电池的最小值，机器的代价是两块芯片代价差的绝对值。

题解：二分答案。将所有电池排序，考虑一台机器中分别作为两块芯片代价的两块电池，它们一定在排序后数组中是相邻的。并且满足其后面的电池数量，减掉后面已用的电池数量，要大于 \(2(k-1)\)（可以使得它们成为最小值）。贪心从后往前找到这样的 \(n\) 组即可。

H. Матрёшка

题目大意：给出了 \(n\) 个俄罗斯套娃的大小 \(a_i\)（\(a_i\) 大小与 \(n\) 同阶）。让你把它们合成若干个集合。最终每个集合里面的俄罗斯套娃从 \(1\) 连续到某个 \(m\)（不同集合的 \(m\) 相互独立）。操作的时候你只能合并相邻的两个集合。最小化打开套娃的总次数。

题解：考虑 \(dp_i\) 表示前 \(i\) 个套娃的答案。那么 \(dp_i = \min_{j=0}^{i-1} (dp_{j} + \text{cost}(j+1,i))\)。其中 \(dp_j\) 要合法，且区间 \((j, i]\) 是从 \(1\) 开始的连续数字。

考虑如何计算 \(\text{cost}(j+1,i)\)。我们区间 dp，合并两个区间的时候，计算打开套娃的次数。我们只考虑没有重复元素的合法区间，显然只有小于“两个区间最小值的最大值”的套娃才不用被打开。这个个数可以用类似计数排序的思想得到。复杂度 \(\mathcal{O}(n^3)\)。

I. Pirate Chest

题目大意：有一个面积为 \(m\times n\) 的池塘，每个位置有一个水的深度 \(d_{ij}\)。让你找到一个最大的长方体，其长和宽分别不超过 \(a,b\)（或者 \(b,a\)），高度任意，且满足在某个位置（池塘顶面和长方形顶面网格对网格）放下长方体之后（不倾斜），水面上升之后能严格高于长方体顶面。保证 \(ab \le nm\)。

题解：枚举长方体在 \(n\) 的这一维，假设其限制是 \(a\)。枚举 \(l, r\) 满足 \(x=r-l+1\le a\)。求出每一行在这些列 \([l, r]\) 之间的 min 值 \(g_1, \dots, g_m\)。假设我们选取了长度为 \(y(y\le b)\) 的一段，这一段的 min 值为 \(g_0\)。假设此时长方体的高为 \(h\)。满足条件等价于：

\[ \begin{aligned} &\frac{xyh}{nm} + g_0 > h\\ &h < \frac{nmg_0}{nm-xy} \end{aligned} \]

现在变量只有 \(g_0\) 和 \(y\)，要让 \(h\) 最大，发现在 \(g_0\) 固定的情况下，需要 \(y\) 尽可能大。显然这样 \(xyh\) 也最大。所以对于每个 \(g_i\) 我们用两次单调栈求出以它为最小值的区间长度，注意要与 \(b\) 取 min。这样我们可以得到：

\[ h = \lfloor \frac{nmg_0-1}{nm-xy} \rfloor \]

复杂度 \(\mathcal{O}(n^2m)\)。

J. Pollution Solution

题目大意：给你一个半圆和一个简单多边形，求它们交的面积。

题解：三角剖分一下即可。