题目#

尤塞夫位于坐标 $(0, 0)$ 处，想要到达位于 $(x, y)$ 处的 Koshary 板块。

为了到达那里，尤塞夫需要迈很长的步子。从任意一点 $(a, b)$ 出发，迈出长长的一步，他就会到达：

• $(a + 2, b)$ 或 $(a, b + 2)$ 。

然而，尤塞夫在整个旅程中最多只能迈出***步。一小步移动到

• $(a + 1, b)$ 或 $(a, b + 1)$ 。

尤塞夫能到达科沙里板块的准确坐标 $(x, y)$ 吗？

数学#

可以发现，只能向左或向右走一次，则x和y不能同时为奇数

1
for _ in range(int(input())):
2
    x,y = map(int,input().split())
3
    if x % 2 == 1 and y % 2 == 1:
4
        print("NO")
5
    else:
6
        print("YES")

题目#

优素福给了你一个长度为 $n$ 的序列 $s$ ，其中只有字符” $\texttt{(}$ “和” $\texttt{)}$ “。您最多**次可以执行以下操作：

• 选择 $s$ 的子串 $^{\text{∗}}$ 并将其删除。然后，您可以将删除的字符逐个重新插入剩余的字符串中。每个字符都可以放在任意位置，与其他字符无关。

优素福想让你判断是否有可能在执行最多一次操作后得到一个正则括号序列 $^{\text{†}}$ 。

$^{\text{∗}}$ 子串是字符串的连续子段。例如，“acab “是 “abacaba “的子串（从位置 $3$ 开始，到位置 $6$ 结束），但 “aa “或 “d “不是这个字符串的子串。因此，从位置 $l$ 到位置 $r$ 的字符串 $s$ 的子串是 $s[l, r]= s_l s_{l+1} \dots s_r$ 。

$^{\text{†}}$ 正则括号序列是指可以通过在序列的原始字符之间插入字符 $1$ 和 $+$ 将其转换为正确算术表达式的括号序列。例如

• 括号序列 $\texttt{()()}$ 和 $\texttt{(())}$ 是正则表达式（得到的表达式为： $\texttt{(1)+(1)}$ 和 $\texttt{((1+1)+1)}$ ）；
• 括号序列 $\texttt{)(}$ 、 $\texttt{(}$ 和 $\texttt{)}$ 则不是。

贪心#

直接选择整个字符串是无害的

那么显然只需要统计字符串中”(“的数量是否等于”)“即可

1
from collections import Counter
2
for _ in range(int(input())):
3
    n = int(input())
4
    s = input().strip()
5
    cnt = Counter(s)
6
    ok = 1
7
    if cnt['('] != cnt[')']:
8
        ok = 0
9
    if ok:
10
        print("YES")
11
    else:
12
        print("NO")

题目#

Yousef 给了你一个由 $n$ 个正整数组成的数组 $a$ 。

让 $f(a)$ 表示 $a$ 的子数组 $^{\text{∗}}$ 的积能被 $6$ 整除的个数。

更正式地说，对于 $l$ 和 $r$ 中的每一对索引 $1 \le l \le r \le n$ ，考虑子数组 $a_l, a_{l+1}, \dots, a_r$ 。如果这个子数组的元素乘积能被 $6$ 整除，那么这个子数组就被计算在内。

例如，如果 $a = [1, 6, 2]$ ，那么乘积能被 $6$ 整除的子数组有 $[6]$ 、 $[1, 6]$ 、 $[6, 2]$ 和 $[1, 6, 2]$ ，所以是 $f(a) = 4$ 。

你的任务是对数组 $a$ 中的元素重新排序，使 $f(a)$ 最小。如果有多种方法可以做到这一点，你可以输出其中任何一种。

$^{\text{∗}}$ 如果从数组 $a$ 中删除开头的几个（可能是零个或全部）元素和结尾的几个（可能是零个或全部）元素，就可以得到数组 $b$ ，那么数组 $b$ 就是数组 $a$ 的子数组。

构造#

如果一个子数组同时包含 $2$ 和 $3$ 这两个质因数，那么它的积就能被 $6$ 整除。因此，每个元素都属于 $4$ 组：

• $S_6$ :能被 $6$ 整除的元素
• $S_2$ :能被 $2$ 整除但不能被 $3$ 整除的元素
• $S_3$ :能被 $3$ 除尽但不能被 $2$ 除尽的元素
• $S_1$ :既不能被 $2$ 也不能被 $3$ 整除的元素

$S_6$ 中的元素已经使任何子数组都能被 $6$ 整除，因此我们希望将这些元素集中在一个末尾，以尽量减少它们包含在子数组中的个数。在接下来的两段中，我们先不讨论 $S_6$ 。

对于其余的元素，如果我们将所有的 $S_2$ 放在所有的 $S_3$ 之前，那么唯一可分割的子数组就是以 $S_2$ 开始、以 $S_3$ 结束的数组。任何其他顺序都只会产生更多这样的子数组。

我们该如何处理 $S_1$ 中的元素呢？将它们放置在任何位置都不会减少可整除子数组的数量，但是我们可以将它们放置在 $S_2$ 和 $S_3$ 之间，从而避免增加可整除子数组的数量。可被 $6$ 整除的子数组仍然是以 $S_2$ 为起点，以 $S_3$ 为终点的数组，因此可整除的子数组数仍然尽可能少。

因此，最佳的构造是

$[S_6] + [S_2] + [S_1] + [S_3]$

1
for _ in range(int(input())):
2
    n = int(input())
3
    a = list(map(int,input().split()))
4
    x = []
5
    y = []
6
    z = []
7
    p = []
8
    for c in a:
9
        if c % 6 == 0:
10
            x.append(c)
11
        elif c % 2 == 0:
12
            y.append(c)
13
        elif c % 3 == 0:
14
            z.append(c)
15
        else:
16
            p.append(c)
17
    ans = x + y + p + z
18
    print(*ans)

题意#

优素福给了你一个由 $2n$ 个整数组成的数组 $a$ 。在数组中，每个整数 $x \in [0, n - 1]$ 都会出现**次。

你的任务是找到一个子数组 $a_l, a_{l + 1}, \dots, a_r$ ，它是一个回文数组 $^{\text{∗}}$ ，使得它的 $\operatorname{mex}(a_l, a_{l + 1}, \dots, a_r)$ $^{\text{†}}$ 最大。输出这个最大可能值。

{例如，字符串 “z”、“aaa”、“aba”、“abccba “是回文字符串，但字符串 “codeforces”、“reality”、“ab “不是回文字符串。

$^{\text{†}}$ 整数数组的 $\operatorname{mex}$ （最小排除数）定义为数组中不出现的最小非负整数。例如

• $[2,2,1]$ 的 $\operatorname{mex}$ 是 $0$ ，因为 $0$ 不属于数组。
• $[3,1,0,1]$ 的 $\operatorname{mex}$ 是 $2$ ，因为 $0$ 和 $1$ 属于数组，而 $2$ 不属于数组。
• $[0,3,1,2]$ 的 $\operatorname{mex}$ 是 $4$ ，因为 $0$ 、 $1$ 、 $2$ 和 $3$ 属于数组，而 $4$ 不属于数组。

贪心+构造#

最优子数组总是包含 $0$ 元素。这是因为，如果它不包含 $0$ ，那么就是 $\operatorname{mex} = 0$ 。但是 $\operatorname{mex} = 1$ 可以通过将 $0$ 元素视为自己的子数组来实现。因此，最佳子数组必须始终包含 $0$ 元素。

这样，我们就只有 $3$ 个候选中心可以展开回文。假设 $x$ 是数组中第一个 $0$ 的位置， $y$ 是第二个 $0$ 的位置：

• $x$ 可以是最佳宫位的中心。
• $y$ 可以是最佳宫位的中心。
• $x$ 和 $y$ 可以位于首尾对应的两边。例如， $[\dots, 0, \dots, j, k, j, \dots, 0, \dots]$ 为奇数宫位， $[\dots, 0, \dots, j, k, k, j, \dots, 0, \dots]$ 为偶数宫位。

我们可以尝试上述每一种选择，只要子数组仍然是回文数组，就从候选中心开始扩展，同时跟踪 $\operatorname{mex}$ 。答案就是所有 $3$ 候选数中最大的 $\operatorname{mex}$ 。

1
def f(l,r,n,v):
2
    s = set(range(n+1))
3
    while l >= 0 and r < 2 * n and v[l] == v[r]:
4
        if v[l] in s:
5
            s.discard(v[l])
6
        l -= 1
7
        r += 1
8
    return min(s)
9
for _ in range(int(input())):
10
    n = int(input())
11
    v = list(map(int,input().split()))
12
    x = y = -1
13
    for i in range(2*n):
14
        if v[i] == 0:
15
            if x == -1:
16
                x = i
17
            else:
18
                y = i
19
    ans = max(f(x,x,n,v),f(y,y,n,v),f((x + y)//2,(x + y + 1)//2,n,v))
20
    print(ans)

问题#

优素福有 $n$ 列并排的立方体。第 $i$ 列中有 $a_i$ 个相同的单位立方体垂直堆叠在一起。最初，重力将立方体向下拉，因此每列 $i$ 中都有 $a_i$ 个立方体，高度为 $1, 2, \dots, a_i$ 。

突然，重力向右移动。每个立方体都尽可能向右水平滑动。一个立方体不能穿过其他立方体，也不能与其他立方体重叠，它必须保持原来的高度。最终的配置是由初始高度唯一决定的。

在重力移动之前，优素福最多可以进行***次操作：选择索引 $i$ 并将 $a_i$ 减少 $1$ （即从该列中移除一个立方体）。他也可以选择什么都不做。

如果一个立方体在重力移动后的列索引与原来的列索引不同，则称该立方体移动了。

假设尤塞夫最优化地使用了单次减少（或选择不使用），求重力移动后移动的立方体的最大可能数量。

AI题解#

1
t = int(input())
2
for _ in range(t):
3
    n = int(input())
4
    v = list(map(int, input().split()))
5

6
    total = sum(v)
7

8
    # 后缀最小值
9
    suf_mn = [0] * n
10
    suf_mn[n - 1] = v[n - 1]
11
    total -= suf_mn[n - 1]
12

13
    for i in range(n - 2, -1, -1):
14
        suf_mn[i] = min(suf_mn[i + 1], v[i])
15
        total -= suf_mn[i]
16

17
    # 统计最长的连续相等段
18
    mx = -1
19
    cur = 1
20
    for i in range(1, n):
21
        if suf_mn[i] == suf_mn[i - 1]:
22
            cur += 1
23
        else:
24
            mx = max(mx, cur)
25
            cur = 1
26
    mx = max(mx, cur)
27

28
    print(total + mx - 1)

一、问题理解#

• n 列立方体，第 i 列有 a[i] 个
• 重力向右移动：每个立方体尽量向右滑动，保持高度不变，不能重叠
• 可以至多一次减少某列的一个立方体
• 求移动的立方体的最大数量

二、重力向右后的形态#

重力向右移动后，立方体会形成”台阶”状：

• 高度从右往左非递减
• 最终每列的高度 = 后缀最小值

1
原始：[5, 3, 4, 2, 1]
2
后缀最小值：[1, 1, 1, 1, 1]（太极端）
3

4
实际：每个位置最多能保留 min(原始高度, 右侧的最小高度)

三、核心公式#

重力移动后，第 i 列的高度 = min(v[i], v[i+1], ..., v[n-1]) = 后缀最小值

不动立方体总数 = 所有列后缀最小值之和

移动立方体数 = 总立方体 - 不动立方体

四、操作：减少一个立方体#

可以选择某列减少 1。减少哪一列能让移动数最大？

• 减少某列，可能降低该列的后缀最小值
• 如果该列的后缀最小值等于它自己，减少它会让后缀最小值减 1，从而让更多立方体移动

五、代码逻辑#

1
total = sum(v)  # 总立方体数
2

3
# 计算后缀最小值之和
4
suf_mn[i] = min(suf_mn[i+1], v[i])
5
total -= suf_mn[i]  # 减去不动立方体

total 现在 = 不操作时的移动立方体数

1
# 统计最长连续相等段
2
mx = -1
3
cur = 1
4
for i in range(1, n):
5
    if suf_mn[i] == suf_mn[i-1]:
6
        cur += 1
7
    else:
8
        mx = max(mx, cur)
9
        cur = 1

为什么统计连续相等段？

如果 suf_mn[i] = suf_mn[i+1] = ... = suf_mn[j]，说明这些列的后缀最小值相同，且等于某列的实际值。

减少那个”卡住”的列（即 v[k] == suf_mn[k] 的那一列），可以让整个连续段的后缀最小值减 1，从而让这段所有列的立方体多移动 1 个。

六、最终答案#

1
print(total + mx - 1)

• total：不操作的移动数
• mx - 1：操作一次能让多少个额外立方体移动
• 合起来就是最大移动数

七、图解#

1
v = [5, 3, 4, 2, 1]
2

3
后缀最小值：
4
suf_mn = [1, 1, 1, 1, 1]
5

6
不动的 = 1+1+1+1+1 = 5
7
移动的 = (5+3+4+2+1) - 5 = 10
8

9
连续相等段：5个1连续，mx = 5
10
操作：减少 v[0] 5→4，后缀最小值变成 [1,1,1,1,1]（不变？）
11
等等...

实际上，如果 v[4]=1 且 suf_mn[4]=1，减少它：

• suf_mn 变成 [0,0,0,0,0]
• 不动的 = 0，移动的 = 全部

但一次操作只能减少 1，所以移动数增加 连续相等段长度 - 1。

八、总结#