浙江省第十五届大学生程序设计竞赛部分题解

A B C D E F G H I J K L M
O O O O Ø Ø . . Ø O O O O

O: 当场通过 Ø: 赛后通过 .: 尚未通过

A. Peak

solved by ybmj

ybmj’s solution
找到最大值后判断左边是否都小于最大值,右边是否都大于最大值。

Trick:最大值出现在第一个或者最后一个。

B. King of Karaoke

solved by Moira

Moira’s solution
将两个序列作差之后对差值计数,最大得分即为出现最多的差值的次数。

C. Magic 12 Months

solved by Moira

Moira’s solution
组合数学+概率论爆炸推公式。
$A$的概率一定是$1$撇开不说,记总共剩下$m$张牌,还剩下$a$张$A$,其他的牌若剩下$k$张,其概率为:
$$\frac{\sum_\limits{i=k} ^ {m-a} C_{a+i-1} ^ {a-1} P_i ^ k}{C_m ^ a P_{m-a} ^ k}$$

D. Sequence Swapping

solved by ybmj

ybmj’s solution
$dp[i][j]$表示第$i$个左括号向右至多交换$j$个右括号所得到的最大价值。
预处理一下每个左括号后面的右括号的数量以及位置和权值,然后DP就好了。

E. LIS

upsolved by CSL

CSL’s solution

  • $f_j = f_i (j < i)→a_j ≥ a_i$
  • $f_j + 1 = f_i (j < i) → a_j < a_i$

考虑差分约束建图。对于每个数的范围的限制,新增附加结点即可。
从附加结点出发跑个SPFA,输出答案就好了。

F. Now Loading!!!

upsolved by CSL

CSL’s solution
注意到$\lceil \log_p ^ {a_i} \rceil$的取值不超过$28$种,于是我们将$a_i$排序后,预处理出$\sum_\limits{i=1} ^ j \lfloor \frac{a_i}{x} \rfloor$。
对于每个询问,二分得到每个$x$对应的区间即可。时间复杂度$O(28n + 28m \log n)$。

G. JUMPin’ JUMP UP!!!

unsolved

H. Game on a Tree

unsolved

I. Magic Points

upsolved by Moira

Moira’s solution
手玩后发现:前$n-1$条线可以轻松构造。$i$->$n+i$连即可;关键在于最后一条线。
如果$i$不能被$n$整除,则$n-1$->$2 \times n - 3 + i$连线。

  • 令$i$等于$n - 1$,即$n-1$->>$3 \times n - 4$即可。
  • 注意特判$n = 2$的情况。

J. CONTINUE…?

solved by ybmj

ybmj’s solution
枚举其中一个集合的人数,并检查答案是否合法即可。

K. Mahjong Sorting

sovled by CSL

CSL’s solution
首先将二维的麻将牌变成一维。
爆炸分类讨论一波:

  • 如果第一张牌个大于第二张牌,那么只有第一张牌能作为幸运牌;
  • 如果第一张牌是白板,那么说明幸运牌不在排序的集合中,此时幸运牌可能取到小于第二张牌的所有牌;
  • 如果第二张牌是白板,那么幸运牌可以取$[a_1,a_3)$;
  • 如果其他牌是白板(位置记作$i$),那么幸运牌可以取$(a_{i-1}, a_{i+1})$;
  • 如果没有白板,那么幸运牌可以是任何一张未出现的数字牌。

Trick:$n$ 等于1,以及白板在最后一张牌的时候。

L. Doki Doki Literature Club

solved by CSL

CSL’s solution
结构体排序直接贪心即可。

M. Lucky 7

solved by CSL

CSL’s solution
扫一遍判断是否$\exists i, a_i + b ≡ 0 \pmod 7$即可。

捐助作者