Contest Info

date: 2019.04.04 19:00-24:00(UTC+8)

practice link

Solutions

B. Beautiful Bridges

题目大意：有一座山，它的形状用一条有 \(n\) 个点的折线段表示，折线段下方到海平面是山的组成部分。现在要修建一座分段的拱桥，桥面高度为 \(h\)，每一段的桥柱只能建在折线段的端点上，且拱桥不能和山相交，但是可以相切（详见题图）。修桥的代价是 \(\alpha\sum_{i=1}^{m}(h-y_{t_{i}})+\beta\sum_{i=1}^{m-1}(x_{t_{i+1}}-x_{t_{i}})\)，求最小代价。

题解：显然 \(\mathcal{O}(n^{2})\) dp。问题在于如何 check 每个区间修桥是否会和山相切。我们把拱桥拆成左右两个 \(\frac{1}{4}\) 圆，不妨考虑左 \(\frac{1}{4}\) 圆，固定左端点，容易发现半径小的 \(\frac{1}{4}\) 圆是严格被大的 \(\frac{1}{4}\) 圆包含的。因此我们很容易 \(\mathcal{O}(n^{2})\) 地预处理出每个区间是否合法。

I. Karel the Robot

题目大意：有一个机器人在一个有障碍的 \(r\times c\) 网格中移动。现在给出 \(e\) 段代码和对应的起始位置及方向，代码有如下几种指令：

• 向前移动一格

• 方向向左转 \(90^{\circ}\)

• 执行一个无参 void 函数

• 条件语句

• 循环语句

其中条件和循环语句的判断有 \(5\) 种，n w s e 分别表示当前方向为 n w s e 时条件为真，b 表示当前方向前面一格为障碍时条件为真。循环语句只有 while (!cond){body;} 型。问执行完代码后的位置及方向，或判断代码为死循环。每段代码长度至多 \(100\)。

题解：一道编译题。

如果不考虑循环，那么直接 dfs，如果搜到了 dfs 栈中的位置，那么这整个栈中的位置都是死循环。对于循环，我们把它拆成一个新函数 \(A\)，定义

A{
    if (cond){
    }
    else{
        body;
        A;
    }
}

即可。

时间复杂度 \(\mathcal{O}(100rce)\)，主要难点在于编译器的编写。

K. Traffic Blights

题目大意：一条路上有 \(n\le500\) 个红绿灯，它们的位置是非负整数 \(x_{1},\cdots,x_{n}\)，且 \(x\) 严格递增。每个红绿灯从 \(t=0\) 开始，有 \(r_{i}\) 秒红，\(g_{i}\) 秒绿，一直循环下去（即红的时间为 \([0,r_{i}),[r_{i}+g_{i},2r_{i}+g_{i}),\cdots\)）。现在一个人从 \(x=0\) 出发，以单位速度匀速向右走，出发的时间服从 \(U([0,INF])\)（\(INF\) 是一个充分大的数）。对每个红绿灯求出它是这个人碰到的第一个红绿灯的概率，以及不碰到任何红绿灯的概率。\(r_{i}+g_{i}\le100\)。

题解：显然是个数论题。设 \(t_{i}=r_{i}+g_{i}\)，那么出发时间以 \(\text{lcm}(t_{1},\cdots,t_{n})\) 为周期。

设出发时间为 \(t\)，那么第 \(i\) 个红绿灯是第一个的概率即为所有满足 \(r_{j}\le u_{j}<t_{j}(1\le j<i),0\le u_{i}<r_{i}\) 的下列同余方程组中，有解的方程组的数量： \[ \begin{cases} t+x_{1}&\equiv u_{1}\pmod{t_{1}}\\ &\vdots\\ t+x_{i}&\equiv u_{i}\pmod{t_{i}}\\ \end{cases} \] 如果所有的 \(t_{i}\) 两两互质，那么显然这个同余方程组一定有解，那么数量就是 \(\prod_{j=1}^{i-1}g_{j}\cdot r_{i}\)，从概率论的角度来说，就是每个红绿灯是红还是绿相互独立，我们很容易在 \(\mathcal{O}(n)\) 的时间内得到答案。

考虑稍微坏一些的情况，如果不互质，那么这两个 \(t_{i}\) 必然相等。这种情况也不难，我们很容易把相等的 \(t_{i}\) 一起处理，不过复杂度要下降到 \(\mathcal{O}(100n)\)。

再坏一些的情况是，如果不互质，那么这两个 \(t_{i}\) 必然有一个是另一个的约数。这种情况下，我们把较小的 \(t_{i}\) 延长若干倍直到相等即可。

但是，这样的情况也不容易达到，例如 \(6\) 和 \(10\) 既不互质，也互不为约数。

我们尝试枚举 \(t\) 模一个 \(T\)（常数）的余数，对每个余数分别计算。这样带来的好处是，所有的 \(t_{i}\) 都减小到了 \(\frac{t_{i}}{\gcd(t_{i},T)}\)。如果所有的 \(t_{i}\) 都是质数的幂，那么就满足要求了。很容易证明，\(T=\prod_{p\text{ is prime}}p^{\lfloor\frac{\log_{p}100}{2}\rfloor}=2520\) 时即满足要求。我们用反证法：假如某个 \(t_{i}\) 有两种以上质因子，那么这两种质因子分别都大于等于 \(p^{\lfloor\frac{\log_{p}100}{2}\rfloor+1}>p^{\frac{\log_{p}100}{2}}=\sqrt{100}\)，与 \(t_{i}\le100\) 矛盾。

时间复杂度 \(\mathcal{O}(2520\cdot100\cdot n)\)。实际上还可以压个位，但是巨难写。