下午刚打一场校赛，写完题解就灰头土脸的来打周赛了。

依旧alt

A. Nowcoder Weekly Contest

饿昏了，开局就唐了 alt

直接比较是否小于等于 ，是就 Rated，反之 Unrated。

B. ICPC Medal

设最终能额外合成的金牌数为 ，答案就是 。

要合成 个金牌，一共需要 个银牌。初始有 个银牌，所以还缺：

这些“缺的银牌”只能由铜牌合成，每个银牌需要 个铜牌。
在合成这 个金牌的过程中，最多能提前利用的掉落铜牌是 个（最后一次掉落已经来不及再参与当前这批 个金牌的构造）。

所以最多能补出的银牌数是：

可行条件为：

这个条件对 单调，因此二分最大可行 即可。

C. Unique Number

前缀加一操作决定了最终序列 一定满足：

目标是最大化不同数的个数。

把问题等价化之后，可以转成：构造一个“从右往左每次最多 +1”的非增序列，并满足上界。
先记前缀最小值：

然后从右往左贪心：

最终不同数个数就是：

整体复杂度 。

D. Balanced Array

平衡子数组条件是：

用双指针维护窗口 ，并用两个单调队列维护当前窗口最大值和最小值：

  • 递减队列维护最大值下标；
  • 递增队列维护最小值下标。

每次扩右端点后，如果不满足条件，就右移 并弹掉过期下标，直到重新合法。
此时以 结尾的合法子数组个数是：

累加即可。总复杂度 。

E. Maximize The Sum

操作定义为：

把三位二进制状态分类看：

  • 其余 6 种都会变成“两个 1、一个 0”

因此结论是：

  1. 若初始全 0，答案是 ；
  2. 若初始全 1，不操作最优，答案是 ；
  3. 其他情况（既有 0 又有 1）：
    • 全 1 不可达；
    • 但可以做到恰好只剩一个 0，所以最大和为 。

所以答案只和 1 的总数有关：

  • 否则

F. Palindromic Value

先预处理回文：

然后做 DP：

  • ：前 个字符的回文划分方案数
  • ：前 个字符所有划分方案价值和

若最后一段是 （且它是回文），长度为 ，则：

初始 ，答案是 。

复杂度：

  • 回文预处理
  • DP 转移