EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)

比赛链接

Problems	AC
A. Upload More RAM	○
B. K-Sort	○
C. Basil’s Garden	○
D. World is Mine	○
E. Wonderful Tree!	○
F1. Interesting Problem (Easy Version)	⊕
F2. Interesting Problem (Hard Version)	⊕
G1. Spinning Round (Easy Version)
G2. Spinning Round (Hard Version)
H. Fumo Temple

A

Code

B

给定一个长度为 $ n $ 的整数数组 $ a $。

你可以进行以下操作任意次（可以为零次）：

• 首先，选择一个整数 $ k $，使得 $ 1 \le k \le n $，并支付 $ k + 1 $ 个硬币。
• 然后，选择恰好 $ k $ 个索引，使得 $ 1 \le i_1 < i_2 < \ldots < i_k \le n $。
• 然后，对于从 $ 1 $ 到 $ k $ 的每个 $ x $，将 $ a_{i_x} $ 增加 1。

找出使数组 $ a $ 非递减（即 $ a_1 \le a_2 \le \ldots \le a_n $）所需的最少硬币数。

呃呃呃，这个题实现的时候脑瘫了，改来改去花了半个小时才过。导致后面心态一度很崩

Code

C

有 $ n $ 朵花排成一行，第 $ i $ 朵花的初始高度为 $ h_i $ 米。

每秒钟，风会从左边吹过来，导致一些花的高度降低。

具体来说，每秒钟，对于从 $ 1 $ 到 $ n $ 的每个 $ i $，按以下顺序发生：

• 如果 $ i = n $ 或 $ h_i > h_{i+1} $，则 $ h_i $ 的值变为 $ \max(0, h_i - 1) $。

第一次所有花的高度 $ h_i = 0 $（对于所有 $ 1 \le i \le n $）需要经过多少秒？

感觉是究极无敌脑电波题

a[n] 变成 0 的时间是 a[n]。a[n - 1] 变成 0 的时间取决于 a[n]。

• 如果 a[n - 1] >= a[n] 的话，那么至少需要 a[n - 1] 的时间
• 如果 a[n - 1] < a[n] 的话，先要等 a[n] 变到 a[n - 1] 的大小，然后转化为上面那种情况。一共是 a[n] + 1 的时间。

Code

D

Alice 和 Bob 正在玩游戏。最初，有 $n$ 个蛋糕，其中第 $i$ 个蛋糕的美味值为 $a_i$ 。

Alice 和 Bob 轮流吃蛋糕，Alice 先吃：

• 轮到 Alice 选择并吃掉任何剩余的蛋糕，其美味度严格大于她之前吃过的任何蛋糕的最大美味度。请注意，在第一轮，她可以选择任何蛋糕。
• 轮到 Bob 选择并吃掉任何剩余的蛋糕。

当当前玩家吃不到合适的蛋糕时，游戏结束。让 $x$ 为 Alice 吃的蛋糕数量。然后，Alice 想要最大化 $x$ ，而 Bob 想要最小化 $x$ 。

如果两个玩家都发挥最佳水平，找出 Alice 会吃多少蛋糕。

想一下你会发现，Alice 是没有决策可言的，每次吃最小的一定是最优的。Bob 要拿一个数的话就要在 Alice 拿到这个数之前全部拿干净。

f[i][j] 表示 Bob 在前 i 种数里选完了 j 种的时候需要进行的操作次数

• 如果不取第 i 种的话， f[i][j] = f[i - 1][j]
• 如果要取第 i 种，需要满足 dp[i - 1][j - 1] + 第 i 种数字的个数 <= i - j，不等式右边的是 Alice 的操作次数，不等式左边是 Bob 的操作次数，Alice 的操作次数应当 >= Bob 的操作次数。dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 第 i 种数字的个数

Code

E

给定一棵树，有 $n$ 个顶点，根节点为 $1$ 。第 $i$ 个顶点上写有一个整数 $a_i$ 。

让 $L$ 成为 $v$ 的所有直接子节点的集合。如果对于所有 $L$ 不为空的顶点 $v$ ，满足：

$$ a_v \le \sum_{u \in L}{a_u}$$

则称一棵树为 wonderful。

在一个操作中，您可以选择任意顶点 $v$ 并将 $a_v$ 增加 $1$ 。

找到使给定的树变得 wonderful 所需的最少操作数！($2 \le n \le 5000$)

算是一个实现题吧，思维难度其实不大。一开始以为是一个直接的贪心，写了一发发现错了。想了一下自己错的原因是向上合并子树信息的时候没有考虑到特定代价下的操作次数是有限的，换句话说是代价是会变的。

具体实现方面，维护 f[i][j] 表示 当前在 i 点，深度为 j 的剩余可操作次数。因为代价是和深度挂钩的，是 j - dep[i]，即两点的深度差。

Code

F1

$1 \le n \le 100$

您将获得一个长度为 $n$ 的整数数组 $a$ 。

在一个操作中，您将执行以下两步过程：

1. 选择一个索引 $i$ ，使得 $1 \le i < |a|$ 和 $a_i = i$ 。

2. 从数组中删除 $a_i$ 和 $a_{i+1}$ ，并连接剩余部分。

找出您可以执行上述操作的最大次数。

如果希望 $a_i$ 最终被删掉，需要满足以下条件：

• $a_i \le i$，显然 $a_i$ 应该在的位置必须不在当前位置的后方。
• $a_i$ 和 $i$ 奇偶性相同，因为每次操作都是删 2 个，不改变奇偶性。
• 需要在 $[1, i - 1]$ 中恰好删去 $\frac{i - a_i}{2}$ 个数，使得 $a_i = i$。

所以我们可以设计出一个区间 dp：设 $g_{l, r}$ 表示要将 $[l, r]$ 删干净，最少要在 $[1, l - 1]$ 操作的次数。