题目#

给你一个长度为 $n$ $^{\text{∗}}$ 的排列 $a$ 。

您可以执行以下任意次数（可能为零）的操作：

• 选择索引 $i$ ( $1 \le i \le \frac{n}{2}$ ) $1 \le i \le \frac{n}{2}$ ），然后交换 $a_i$ 和 $a_{2i}$ 。

例如，当 $a=[1,4,2,3,5]$ 时，可以交换 $a_2$ 和 $a_4$ ，使其成为 $[1,3,2,4,5]$ ，但不能交换 $a_2$ 和 $a_3$ 。

请判断序列 $a$ 能否按递增顺序排序。

$^{\text{∗}}$ 长度为 $n$ 的排列是由 $n$ 个不同的整数组成的数组，这些整数从 $1$ 到 $n$ 按任意顺序排列。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（ $2$ 在数组中出现了两次）， $[1,3,4]$ 也不是一个排列（ $n=3$ ，但数组中有 $4$ ）。

排序#

实际上这不是一般的树，而是多条独立的链：

text

链1: 1 → 2 → 4 → 8 → 16 → …链3: 3 → 6 → 12 → 24 → …链5: 5 → 10 → 20 → …链7: 7 → 14 → 28 → …

每个奇数 k 对应一条链：k, 2k, 4k, 8k, ...

• 操作只能交换同一链上相邻的两个元素
• 不同链之间的元素永远无法交换

通过多次相邻交换（冒泡），链内元素可以任意排列。

1
t = int(input())
2
for _ in range(t):
3
    n = int(input())
4
    a = [0] + list(map(int, input().split()))  # 1-indexed
5
    # 对每条链（起点为奇数）排序
6
    for start in range(1, n + 1, 2):
7
        # 收集链上的值和位置
8
        vals = []
9
        pos = []
10
        x = start
11
        while x <= n:
12
            pos.append(x)
13
            vals.append(a[x])
14
            x *= 2
15
        # 排序
16
        vals.sort()
17
        # 放回
18
        for p, v in zip(pos, vals):
19
            a[p] = v
20
    # 检查是否递增
21
    ok = True
22
    for i in range(2, n + 1):
23
        if a[i] < a[i - 1]:
24
            ok = False
25
            break
26
    print("YES" if ok else "NO")

题目#

考虑下面的立方体 $D$ ，其中的数字 $x$ 和 $7-x$位于相对的边上。位于对边：

从 $1$ 到 $6$ 的整数序列 $b$如果满足以下条件，则称为掷骰子序列：

• 所有相邻元素对都位于立方体的相邻 $^{\text{∗}}$ 面上。

例如， $[1,4,2]$是一个掷骰子序列，而 $[3,4,6,3]$ 不是，因为 $3$ 和 $4$不在骰子的相邻面上。此外， $[2,2,4]$ 也不是掷骰子序列，因为 $2$ 和 $2$ 位于骰子的同一面（不相邻）。

给定一个从 $1$ 到 $6$ 的由 $n$个整数组成的序列 $a$，可以进行任意次数（可能为零）的以下运算。

• 选择索引 $1 \le i \le n$ 和整数 $1 \le x \le 6$。然后，将 $a i$ 的值更改为 $x$ 。

请计算使 $a$ 成为掷骰子序列所需的最少次运算。

贪心#

掷骰子序列的非法情况只有两种：

1. 相同面相邻：a[i] == a[i-1]
2. 对面相邻：a[i] + a[i-1] == 7（对面：1-6, 2-5, 3-4）

遇到非法对 (a[i-1], a[i]) 时，必须修改其中一个。

最优策略：修改 a[i]（而不是 a[i-1]），并且跳过 a[i]，让它和后面重新匹配。

为什么修改 a[i] 更好？

• a[i-1] 已经和 a[i-2] 匹配好了
• 修改 a[i] 只影响当前和下一对
• 跳过 a[i] 意味着把 a[i] 改成某个值，然后继续检查 a[i+1] 和 a[i+2]

修改 a[i] 后，a[i] 可以变成任意值：

• 可以让 (a[i-1], a[i]') 合法
• 可以让 (a[i]', a[i+1]) 也合法（因为 a[i]' 可以选 4 种相邻面）

跳过 a[i] 后，检查 (a[i+1], a[i+2])，它们原本可能合法也可能不合法，互不影响。

1
for _ in range(int(input())):
2
    n = int(input())
3
    a = list(map(int,input().split()))
4
    ans = 0
5
    i = 1
6
    while i < n:
7
        if a[i] + a[i-1] == 7 or a[i] == a[i-1]:
8
            ans += 1
9
            i += 2
10
        else:
11
            i += 1
12
    print(ans)

状态机DP#

每个面的相邻面 = 除了自己和对面外的 4 个面

1
dp[i][j] = 使前 i 个元素成为掷骰子序列，且第 i 个元素等于 j 的最小修改次数

1
for j in range(1, 7):
2
    dp[1][j] = 1 if a[1] != j else 0

1
for i in range(2, n + 1):           # 遍历每个位置
2
    for j in range(1, 7):           # 当前元素取值 j
3
        for k in adj[j]:            # 前一个元素取值 k（必须与 j 相邻）
4
            cost = 1 if a[i] != j else 0
5
            dp[i][j] = min(dp[i][j], dp[i-1][k] + cost)

1
for _ in range(int(input())):
2
    n = int(input())
3
    a = [0] + list(map(int, input().split()))
4
    adj = {
5
        1: [2, 3, 4, 5],
6
        2: [1, 3, 4, 6],
7
        3: [1, 2, 5, 6],
8
        4: [1, 2, 5, 6],
9
        5: [1, 3, 4, 6],
10
        6: [2, 3, 4, 5]
11
    }
12
    INF = 10 ** 9
13
    dp = [[INF] * 7 for _ in range(n + 1)]
14
    for j in range(1, 7):
15
        dp[1][j] = 1 if a[1] != j else 0
16
    for i in range(2, n + 1):
17
        for j in range(1, 7):
18
            for k in adj[j]:
19
                cost = 1 if a[i] != j else 0
20
                dp[i][j] = min(dp[i][j], dp[i - 1][k] + cost)
21
    ans = min(dp[n][1:])
22
    print(ans)

题目#

有一个由 $n$ 组成的隐藏序列 $a_1,a_2,\ldots,a_n$ 。整数（ $n \ge 2$ ）。保证所有 $1 \le i \le n$ 都是 $|a_i| \le 1000$ 。

让我们定义一个函数 $f(x)$ 如下：

已知 $n$ 的值为 $f(1),f(2),\ldots,f(n)$ ，请确定 $a_1,a_2,\ldots,a_n$ 的值。

保证可以唯一确定 $a_1,a_2,\ldots,a_n$ 的值。

数学#

让我们绘制 $y=f(x)=\sum_{i=1}^n a_i \cdot |i-x|$ 的曲线图并观察斜率。 $a_i \cdot |i-x|$ 项与其他项有何不同？

在函数 $f(x)$ 中，唯一在 $x=i$ 处改变斜率的是 $a_i \cdot |i-x|$ 项。换句话说， $x=i$ 附近的斜率差与 $a_i$ 有关。让我们来计算一下这些斜率。

• $x=i$ 左侧的斜率为 $f(i)-f(i-1)$ ；
• 到 $x=i$ 右边的斜率是 $f(i+1)-f(i)$ ；
• 我们知道 $x=i$ 附近的斜率变化了 $2a_i$ ；
• 因此，当 $1 \lt i \lt n$ 时， $a_i = \frac{(f(i+1)-f(i))-(f(i)-f(i-1))}{2} = \frac{f(i+1)+f(i-1)-2f(i)}{2}$ 。

现在我们知道了 $a_2,a_3,\ldots,a_{n-1}$ 。那么 $a_1$ 和 $a_n$ 呢？让我们定义一个新函数如下。

从 $f(x)$ 中减去 $n-2$ 项，可以在 $\mathcal{O}(n)$ 时间内求出 $g(x)$ 的一个值。

现在请注意以下几点：

• $g(1) = (n-1) \cdot a_n$ ;
• $g(n) = (n-1) \cdot a_1$ .

因此， $a_1$ 和 $a_n$ 可以在 $\mathcal{O}(n)$ 时间内从 $g(1)$ 和 $g(n)$ 找到。

1
def solve(n, f):
2
    vec = [0] * n
3

4
    # 计算中间元素 a[1] 到 a[n-2]
5
    for i in range(1, n - 1):
6
        val = f[i + 1] + f[i - 1] - 2 * f[i]
7
        if val % 2 != 0:
8
            return []
9
        vec[i] = val // 2
10
        if abs(vec[i]) > 1000:
11
            return []
12

13
    # 计算 f(0) 和 f(n-1) 对应的值
14
    def g(j):
15
        w = f[j]
16
        for i in range(1, n - 1):
17
            w -= vec[i] * abs(i - j)
18
        return w
19

20
    g1 = g(0)
21
    gn = g(n - 1)
22

23
    if gn % (n - 1) != 0:
24
        return []
25
    if g1 % (n - 1) != 0:
26
        return []
27

28
    vec[0] = gn // (n - 1)
29
    vec[n - 1] = g1 // (n - 1)
30

31
    if abs(vec[0]) > 1000 or abs(vec[n - 1]) > 1000:
32
        return []
33

34
    return vec
35

36

37
t = int(input())
38
for _ in range(t):
39
    n = int(input())
40
    f = list(map(int, input().split()))
41
    a = solve(n, f)
42
    print(*a)