Contest Info

date: 2019.01.12 15:10-20:10

practice link

Solutions

A. Altruistic Amphibians

题目大意：深为 \(d\) 的井底有 \(n\) 只青蛙，每只青蛙有一个身高 \(h_{i}\)，重量 \(w_{i}\)，跳跃高度 \(l_{i}\)。青蛙们可以叠起来跳出井，设从上到下依次是青蛙 \(t_{1},\cdots,t_{m}\)，那么首先对每个 \(2\le i\le m\) 要满足 \(\sum_{j=1}^{i-1}w_{t_{j}}<w_{t_{i}}\)。如果 \(l_{t_{1}}+\sum_{i=2}^{m}h_{t_{i}}>d\)，那么青蛙 \(t_{1}\) 可以跳出井。问最优策略下最多能有多少只青蛙跳出井？保证 \(\sum w_{i}\le10^{8}\)。

题解：显然每只青蛙能否跳出井是相互独立的。设 \(dp[i]\) 表示当前已经摆放了一些青蛙，并且在它们上面再叠放总重量 \(i-1\) 的青蛙时不会违反规则，最多摆放的高度是多少。对于每只青蛙 \(i\)，考虑它如何转移 \(dp\)。我们有 \[ \begin{cases} &dp[w_{i}]:=\max(dp[w_{i}],dp[j]+h_{i})&(j=2w_{i})\\ &dp[j-w_{i}]:=\max(dp[j-w_{i}],dp[j]+h_{i})&(w_{i}+1\le j<2w_{i}) \end{cases} \]

转移时要注意不断做后缀最大值。

时间复杂度 \(\mathcal{O}(n+\sum w_{i})\)，空间复杂度 \(\mathcal{O}(\sum w_{i})\)。

B. Baby Bites

签到题。

C. Code Cleanups

签到题。

D. Delivery Delays

题目大意：无向图的 \(1\) 号点有一个披萨店，他会依此接到若干个订单 \((s_i,u_i,t_i)\)，分别表示接到订单的时间，需要送达的节点，披萨准备好可以送出的时间。保证 \(s,t\) 分别递增。骑手可以携带任意数量的披萨，但是必须按照订单顺序送货。求最小的最大等待时间。

题解：二分答案。dp 验证。设 \(\text{dp}[i]\) 表示前 \(i\) 个订单送达之后的最小时间。用 Dijkstra 预处理任意两点的最短路。预处理 \(\text{cost}[i][j]\) 表示订单 \([i,j]\) 的配送时间。 \(\text{pre}[i][j]=\max_{k=i}^j \text{cost}[i][k] - s_k\)。

转移的时候，枚举 \(j\) 到 \(i\) 一起送。令 \(s=\max(\text{dp}[j-1],t_i)\)，如果 \(s+\text{dis}[1][u_j]+\text{pre}[j][i]>mid\)，那么不合法，否则用 \(s+\text{dis}[1][u_j]+\text{cost}[j][i]+\text{dis}[u_i][1]\) 更新 \(\text{dp}[i]\)。

E. Explosion Exploit

暴搜。注意状态内部不需要有序，即可缩减大量状态。

G. Game Scheduling

题目大意：有 \(m\) 支队伍，每支队有 \(n\) 个人。现在任意两只队的每两个人都要打一场比赛，要求你安排至多 \((m-1)n+1\) 轮比赛，每人每轮至多参加一场比赛（相当于每人至多轮空一轮）。

题解：若 \(n=1\)，那么就是经典的 round robin问题。我们以此为基础进行构造。

首先安排编号不同的人之间的比赛。若 \(n\) 为偶数，那么我们按照 \(n\) 个人的 round robin 安排比赛，队伍之间则循环比赛，即队伍 \(i\) 在第 \(j\) 轮和队伍 \((i+j)\mod{m}\) 比赛。最后所有编号相同的人再按照 \(m\) 个人的 round robin 比赛即可。

若 \(n\) 为奇数，每一轮会有一个编号轮空，那么我们把这个编号的“内战”插入每一轮即可。若 \(m\) 也是奇数，那么这样还会多出一些人，很容易再用一轮解决。

给出一些例子：

4 4
A1-B3 A2-B4 B1-C3 B2-C4 C1-D3 C2-D4 D1-A3 D2-A4 
A1-C3 A2-C4 B1-D3 B2-D4 C1-A3 C2-A4 D1-B3 D2-B4 
A1-D3 A2-D4 B1-A3 B2-A4 C1-B3 C2-B4 D1-C3 D2-C4 
A1-B4 A3-B2 B1-C4 B3-C2 C1-D4 C3-D2 D1-A4 D3-A2 
A1-C4 A3-C2 B1-D4 B3-D2 C1-A4 C3-A2 D1-B4 D3-B2 
A1-D4 A3-D2 B1-A4 B3-A2 C1-B4 C3-B2 D1-C4 D3-C2 
A1-B2 A4-B3 B1-C2 B4-C3 C1-D2 C4-D3 D1-A2 D4-A3 
A1-C2 A4-C3 B1-D2 B4-D3 C1-A2 C4-A3 D1-B2 D4-B3 
A1-D2 A4-D3 B1-A2 B4-A3 C1-B2 C4-B3 D1-C2 D4-C3 
A1-C1 B1-D1 A2-C2 B2-D2 A3-C3 B3-D3 A4-C4 B4-D4 
A1-D1 C1-B1 A2-D2 C2-B2 A3-D3 C3-B3 A4-D4 C4-B4 
A1-B1 D1-C1 A2-B2 D2-C2 A3-B3 D3-C3 A4-B4 D4-C4 

4 5
A1-B3 A2-B4 B1-C3 B2-C4 C1-D3 C2-D4 D1-E3 D2-E4 E1-A3 E2-A4 
A1-C3 A2-C4 B1-D3 B2-D4 C1-E3 C2-E4 D1-A3 D2-A4 E1-B3 E2-B4 
A1-D3 A2-D4 B1-E3 B2-E4 C1-A3 C2-A4 D1-B3 D2-B4 E1-C3 E2-C4 
A1-E3 A2-E4 B1-A3 B2-A4 C1-B3 C2-B4 D1-C3 D2-C4 E1-D3 E2-D4 
A1-B4 A3-B2 B1-C4 B3-C2 C1-D4 C3-D2 D1-E4 D3-E2 E1-A4 E3-A2 
A1-C4 A3-C2 B1-D4 B3-D2 C1-E4 C3-E2 D1-A4 D3-A2 E1-B4 E3-B2 
A1-D4 A3-D2 B1-E4 B3-E2 C1-A4 C3-A2 D1-B4 D3-B2 E1-C4 E3-C2 
A1-E4 A3-E2 B1-A4 B3-A2 C1-B4 C3-B2 D1-C4 D3-C2 E1-D4 E3-D2 
A1-B2 A4-B3 B1-C2 B4-C3 C1-D2 C4-D3 D1-E2 D4-E3 E1-A2 E4-A3 
A1-C2 A4-C3 B1-D2 B4-D3 C1-E2 C4-E3 D1-A2 D4-A3 E1-B2 E4-B3 
A1-D2 A4-D3 B1-E2 B4-E3 C1-A2 C4-A3 D1-B2 D4-B3 E1-C2 E4-C3 
A1-E2 A4-E3 B1-A2 B4-A3 C1-B2 C4-B3 D1-C2 D4-C3 E1-D2 E4-D3 
B1-C1 E1-D1 B2-C2 E2-D2 B3-C3 E3-D3 B4-C4 E4-D4 
E1-A1 D1-C1 E2-A2 D2-C2 E3-A3 D3-C3 E4-A4 D4-C4 
A1-D1 B1-E1 A2-D2 B2-E2 A3-D3 B3-E3 A4-D4 B4-E4 
C1-E1 A1-B1 C2-E2 A2-B2 C3-E3 A3-B3 C4-E4 A4-B4 
D1-B1 C1-A1 D2-B2 C2-A2 D3-B3 C3-A3 D4-B4 C4-A4 

5 4
A2-B3 A5-B4 B2-C3 B5-C4 C2-D3 C5-D4 D2-A3 D5-A4 A1-C1 B1-D1 
A2-C3 A5-C4 B2-D3 B5-D4 C2-A3 C5-A4 D2-B3 D5-B4 A1-D1 C1-B1 
A2-D3 A5-D4 B2-A3 B5-A4 C2-B3 C5-B4 D2-C3 D5-C4 A1-B1 D1-C1 
A5-B1 A4-B3 B5-C1 B4-C3 C5-D1 C4-D3 D5-A1 D4-A3 A2-C2 B2-D2 
A5-C1 A4-C3 B5-D1 B4-D3 C5-A1 C4-A3 D5-B1 D4-B3 A2-D2 C2-B2 
A5-D1 A4-D3 B5-A1 B4-A3 C5-B1 C4-B3 D5-C1 D4-C3 A2-B2 D2-C2 
A1-B4 A2-B5 B1-C4 B2-C5 C1-D4 C2-D5 D1-A4 D2-A5 A3-C3 B3-D3 
A1-C4 A2-C5 B1-D4 B2-D5 C1-A4 C2-A5 D1-B4 D2-B5 A3-D3 C3-B3 
A1-D4 A2-D5 B1-A4 B2-A5 C1-B4 C2-B5 D1-C4 D2-C5 A3-B3 D3-C3 
A3-B5 A1-B2 B3-C5 B1-C2 C3-D5 C1-D2 D3-A5 D1-A2 A4-C4 B4-D4 
A3-C5 A1-C2 B3-D5 B1-D2 C3-A5 C1-A2 D3-B5 D1-B2 A4-D4 C4-B4 
A3-D5 A1-D2 B3-A5 B1-A2 C3-B5 C1-B2 D3-C5 D1-C2 A4-B4 D4-C4 
A4-B2 A3-B1 B4-C2 B3-C1 C4-D2 C3-D1 D4-A2 D3-A1 A5-C5 B5-D5 
A4-C2 A3-C1 B4-D2 B3-D1 C4-A2 C3-A1 D4-B2 D3-B1 A5-D5 C5-B5 
A4-D2 A3-D1 B4-A2 B3-A1 C4-B2 C3-B1 D4-C2 D3-C1 A5-B5 D5-C5 

5 5
A2-B3 A5-B4 B2-C3 B5-C4 C2-D3 C5-D4 D2-E3 D5-E4 E2-A3 E5-A4 E1-A1 D1-C1 
A2-C3 A5-C4 B2-D3 B5-D4 C2-E3 C5-E4 D2-A3 D5-A4 E2-B3 E5-B4 A1-D1 B1-E1 
A2-D3 A5-D4 B2-E3 B5-E4 C2-A3 C5-A4 D2-B3 D5-B4 E2-C3 E5-C4 C1-E1 A1-B1 
A2-E3 A5-E4 B2-A3 B5-A4 C2-B3 C5-B4 D2-C3 D5-C4 E2-D3 E5-D4 D1-B1 C1-A1 
A5-B1 A4-B3 B5-C1 B4-C3 C5-D1 C4-D3 D5-E1 D4-E3 E5-A1 E4-A3 E2-A2 D2-C2 
A5-C1 A4-C3 B5-D1 B4-D3 C5-E1 C4-E3 D5-A1 D4-A3 E5-B1 E4-B3 A2-D2 B2-E2 
A5-D1 A4-D3 B5-E1 B4-E3 C5-A1 C4-A3 D5-B1 D4-B3 E5-C1 E4-C3 C2-E2 A2-B2 
A5-E1 A4-E3 B5-A1 B4-A3 C5-B1 C4-B3 D5-C1 D4-C3 E5-D1 E4-D3 D2-B2 C2-A2 
A1-B4 A2-B5 B1-C4 B2-C5 C1-D4 C2-D5 D1-E4 D2-E5 E1-A4 E2-A5 E3-A3 D3-C3 
A1-C4 A2-C5 B1-D4 B2-D5 C1-E4 C2-E5 D1-A4 D2-A5 E1-B4 E2-B5 A3-D3 B3-E3 
A1-D4 A2-D5 B1-E4 B2-E5 C1-A4 C2-A5 D1-B4 D2-B5 E1-C4 E2-C5 C3-E3 A3-B3 
A1-E4 A2-E5 B1-A4 B2-A5 C1-B4 C2-B5 D1-C4 D2-C5 E1-D4 E2-D5 D3-B3 C3-A3 
A3-B5 A1-B2 B3-C5 B1-C2 C3-D5 C1-D2 D3-E5 D1-E2 E3-A5 E1-A2 E4-A4 D4-C4 
A3-C5 A1-C2 B3-D5 B1-D2 C3-E5 C1-E2 D3-A5 D1-A2 E3-B5 E1-B2 A4-D4 B4-E4 
A3-D5 A1-D2 B3-E5 B1-E2 C3-A5 C1-A2 D3-B5 D1-B2 E3-C5 E1-C2 C4-E4 A4-B4 
A3-E5 A1-E2 B3-A5 B1-A2 C3-B5 C1-B2 D3-C5 D1-C2 E3-D5 E1-D2 D4-B4 C4-A4 
A4-B2 A3-B1 B4-C2 B3-C1 C4-D2 C3-D1 D4-E2 D3-E1 E4-A2 E3-A1 E5-A5 D5-C5 
A4-C2 A3-C1 B4-D2 B3-D1 C4-E2 C3-E1 D4-A2 D3-A1 E4-B2 E3-B1 A5-D5 B5-E5 
A4-D2 A3-D1 B4-E2 B3-E1 C4-A2 C3-A1 D4-B2 D3-B1 E4-C2 E3-C1 C5-E5 A5-B5 
A4-E2 A3-E1 B4-A2 B3-A1 C4-B2 C3-B1 D4-C2 D3-C1 E4-D2 E3-D1 D5-B5 C5-A5 
B1-C1 B2-C2 B3-C3 B4-C4 B5-C5 E1-D1 E2-D2 E3-D3 E4-D4 E5-D5 

H. House Lawn

签到题。

I. Intergalactic Bidding

签到题。

J. Jumbled String

题目大意：让你构造一个 0/1 串，使得 00,01,10,11 作为子序列出现各 \(a,b,c,d\) 次。

题解：通过 \(a,d\) 可以解出 0 和 1 的个数。对于 000…001111…111 这个串，我们考虑从左往右把每个 1 往左边移动，移动一次 01 的个数少一个，并且 10 的个数多一个。注意 \(a,d\) 等于 0/1 的时候有多个解。

K. King’s Colors

题目大意：给你一棵 \(n\) 个点的树，问你恰用 \(k\) 种颜色染色，使得相邻边颜色不同的方案数。

题解：显然对 \(\forall j\in[1,k]\) 分别计算使用不超过 \(j\) 种颜色染色的方案数，然后容斥。

对每种颜色计算时，朴素的想法是记 \(dp[u][i]\) 表示 \(u\) 的子树，\(u\) 涂颜色 \(i\) 的方案数。另外注意到每种颜色是无差别的，因此可省去第二维。

时间复杂度 \(\mathcal{O}(nk)\)。