1100Div1+2#

Dashboard - Spectral::Cup 2026 Round 2 (Codeforces Round 1100, Div. 1 + Div. 2) - Codeforces

Easy；A，B，C1

Mid：C2

Hard：D(Gemini3.5Flash)

A-数学

题意：

给定一个序列，可进行如下若干次操作：

选择一个整数x，对于序列中的每个元素，若元素值小于x，则+1；大于则-1；等于则不变。

求使所有值都相同的最少的操作次数

假设y是最佳的,mn和mx分别表示序列中的最大值和最小值，那么需要执行的操作次数为max(y−mn,mx−y)

需要选择y值，使操作次数最小化，则y值应为mn和mx的中间位置，即 ⌈(mx−mn)//2⌉

1
for _ in range(int(input())):
2
    n = int(input())
3
    a = list(map(int, input().split()))
4
    mx = max(a)
5
    mn = min(a)
6
    ans = (mx - mn + 1) // 2
7
    print(ans)

B-贪心

比较莫名其妙的题目，感觉毫无意义，只要交换a中大于b中的值后，再加上max(a)即可

1
for _ in range(int(input())):
2
    n = int(input())
3
    a = list(map(int,input().split()))
4
    b = list(map(int,input().split()))
5
    for i in range(n):
6
        if a[i] > b[i]:
7
            a[i],b[i] = b[i],a[i]
8
    ans = sum(b) + max(a)
9
    print(ans)

C1-贪心+构造

题意：

给定序列a，选择一个索引i且ai>0，对于每个1≤j≤i的aj对其乘以-1

要求是求出最多n次操作后，使sum(a)最小的序列

题解：

从后向前遍历，对于遇到的每个数，都可以确保其变为负数，如果当前数是整数，则对其进行一次操作；反之继续

1
for _ in range(int(input())):
2
    n = int(input())
3
    a = list(map(int,input().split()))
4
    cnt = 0
5
    ans = []
6
    for i in range(n-1,-1,-1):
7
        val = a[i]
8
        if((cnt&1) == 0 and val > 0) or ((cnt&1) == 1 and val < 0):
9
            ans.append(i+1)
10
            cnt += 1
11
        print(len(ans))
12
        print(' '.join(map(str, ans)))

C2-前缀和+思维+构造

题意与C1相同，唯一不同点在于求的是操作后的最大值，值得注意的是，选择的索引必须满足ai>0才能进行反转操作，这就意味着不能像C1一样贪心的求解。

遍历每一个合法的最右侧切割点i，满足ai>0，则全局总和为：

\begin{aligned}\\& \underbrace{\text { pre }[i-1]}_{\text {左边全变正 }}-\underbrace{a_{i}}_{\text {自己变负 }}+\underbrace{\operatorname{suf}[i+1]}_{\text {右边保持原样 }}\\\end{aligned}

1
  pre = [0]*n
2
  pre[0] = abs(a[0])
3
  for i in range(1,n):
4
      pre[i] = pre[i-1] + abs(a[i])
5
  suf = [0]*(n+1)
6
  suf[n-1] = a[n-1]
7
  for i in range(n-2,-1,-1):
8
      suf[i] = suf[i+1] + a[i]

1
  best = suf[0]
2
  idx = -1
3
  for i in range(1,n):
4
      if a[i] > 0:
5
          s = pre[i-1] + suf[i+1] - a[i]
6
          if s > best:
7
              best = s
8
              idx = i

为什么左侧可以全部变成负数？

如果原本是负数，那么通过idx的操作，其会反转成正数

如果原本是正数，那么通过自己操作一次，就变成负数了，可以通过idx的操作变成负数

最后，通过逆序操作，找到需要进行操作的位置

1
  ans = []
2
  cur_a = list(a)
3
  for i in range(idx-1,-1,-1):
4
      if len(ans)%2 == 1:
5
          cur_a[i] = -cur_a[i]
6
      if cur_a[i] > 0:
7
          ans.append(i+1)
8
  ans.append(idx+1)

1
for _ in range(int(input())):
2
    n = int(input())
3
    a = list(map(int, input().split()))
4
    ans = []
5
    pre = [0]*n
6
    pre[0] = abs(a[0])
7
    for i in range(1,n):
8
        pre[i] = pre[i-1] + abs(a[i])
9
    suf = [0]*(n+1)
10
    suf[n-1] = a[n-1]
11
    for i in range(n-2,-1,-1):
12
        suf[i] = suf[i+1] + a[i]
13

14
    best = suf[0]
15
    idx = -1
16
    for i in range(1,n):
17
        if a[i] > 0:
18
            s = pre[i-1] + suf[i+1] - a[i]
19
            if s > best:
20
                best = s
21
                idx = i
22
    if idx == -1:
23
        print("0\n")
24
        continue
25
    ans = []
26
    cur_a = list(a)
27
    for i in range(idx-1,-1,-1):
28
        if len(ans)%2 == 1:
29
            cur_a[i] = -cur_a[i]
30
        if cur_a[i] > 0:
31
            ans.append(i+1)
32
    ans.append(idx+1)
33
    print(len(ans))
34
    print(*ans)

D-位运算+二分答案(Gemini3.5Flash)

给定两个长度均为 $n$ 的正整数数组 $a$ 和 $b$ 。可以将这两组数据视为一个 $2 \times n$ 的网格矩阵，其中每一列包含两个数 $(a_i, b_i)$ 。

现对该矩阵执行恰好 $n-1$ 次如下合并操作：

选择相邻的两列 $i$ 与 $i+1$ ，提取出这四项元素组成多重集 $S = \{a_i, a_{i+1}, b_i, b_{i+1}\}$ 。
将 $S$ 中的元素从小到大排序，记为 $s_1 \le s_2 \le s_3 \le s_4$ 。
用较小的中位数 $s_2$ 替换原 $a$ 数组的相邻两项，用较大的中位数 $s_3$ 替换原 $b$ 数组的相邻两项。这使得原来的两列坍缩并合并为独立的新列 $(s_2, s_3)$ 。

历经 $n-1$ 次操作后，整个矩阵将只剩下唯一的最后一列 $(a_1, b_1)$ 。要求通过优化合并的顺序与方案，最大化最终留存结果的 $\min(a_1, b_1)$ 。

1. 状态二值化（二分答案）

题目求的是“最大化的最小值”，此类问题的经典破局点在于二分答案 $X$ 。

假设我们期望最终的 $\min(a_1, b_1) \ge X$ ，这意味着最终留存的一列中，两个元素都必须大于或等于 $X$ 。

固定目标值 $X$ 后，元素的绝对数值便不再重要，可将矩阵中的所有元素进行0-1 符号化：

若数值 $\ge X$ ，记为1。
若数值 $< X$ ，记为0。

根据每一列中 $1$ 的数量，可将原始矩阵的每一列分类为以下三种状态：

状态 2（双 1 列）：两个元素均 $\ge X$ 。
状态 1（单 1 列）：一个元素 $\ge X$ ，另一个元素 $< X$ 。
状态 0（全 0 列）：两个元素均 $< X$ 。

2. 状态转移规律分析

当我们选择相邻两列进行合并时，这四格位置中 $1$ 的总数量（记为 $count$ ）将直接决定合并后新列的状态：

当 $count \le 1$ 时：排序后 $s_2 = 0, s_3 = 0$ ，新列转化为状态 0。
当 $count = 2$ 时：排序后 $s_2 = 0, s_3 = 1$ ，新列转化为状态 1。
当 $count \ge 3$ 时：排序后 $s_2 = 1, s_3 = 1$ ，新列转化为状态 2。

由此可导出三种基本状态两两合并的宏观规律：

状态组合	四格 1 总数 (count)	合并后新状态
状态 2 $+$ 状态 2	4	状态 2
状态 2 $+$ 状态 1	3	状态 2
状态 2 $+$ 状态 0	2	状态 1
状态 1 $+$ 状态 1	2	状态 1
状态 1 $+$ 状态 0	1	状态 0
状态 0 $+$ 状态 0	0	状态 0

3. “状态 1”的惰性净化

观察上述表格可以发现，状态 1 在合并链中充当了特殊的“催化剂”角色：

它与状态 2 合并时，会被状态 2 吸收且不破坏状态 2（结果仍为状态 2）。
它与状态 0 合并时，会被状态 0 湮灭（结果仍为状态 0）。
它与状态 1 自身合并时，状态保持不变。

这意味着，夹在状态 2 和状态 0 之间的连续状态 1 序列，可以通过合法的顺序被逐步吸收或湮灭，对最终全局的消去博弈不构成决定性性质。因此，在宏观判定时，我们可以直接无视所有的状态 1。

4. 消除策略与合法性判定（Check）

排除状态 1 后，序列仅由状态 2与状态 0 组成。分析它们的交锋规则：

两个状态 2 合并，数量减 1，保留状态 2。
状态 2 与状态 0 撞击，会产生一个状态 1。而此状态 1 随后可被相邻的状态 2 吸收。

这意味着，一个状态 2 能够完全抵消一个状态 0。更关键的是，由于状态 1 的惰性传递，一段连续的状态 0 区域（全 0 块），只需要耗费其一侧的一个状态 2 即可实现完全净化。

例如，对于序列[2, 0, 0, 0]：

2与第一个0合并转化为1 $\rightarrow$ 序列变为[1, 0, 0]。
状态1与接下来的0合并转化为0 $\rightarrow$ 序列变为[0, 0]。

根据此物理性质，我们可以得出二分判定的充分必要条件：

统计序列中独立的状态 2 的总个数（记为one），以及连续的状态 0 块的总个数（记为zero）。只要满足**one > zero**，状态 2 即可实现对所有状态 0 块的完全覆盖与清除，最终场上至少会保留一个状态 2，即证明 $\min(a_1, b_1) \ge X$ 具有可行性。

三、算法复杂度

时间复杂度：二分查找的范围为 $[0, 2n+5]$ ，判定函数check仅需单次 $O(n)$ 的线性扫描。总体时间复杂度为 $O(n \log n)$ ，在 2 秒的时限内表现极高。
空间复杂度：仅需存储原始输入的数组，空间复杂度为 $O(n)$ 。

1
import sys
2
def solve():
3
    # 快速读取全部输入
4
    input_data = sys.stdin.read().split()
5
    if not input_data:
6
        return
7

8
    iterator = iter(input_data)
9
    t = int(next(iterator))
10

11
    out = []
12

13
    for _ in range(t):
14
        n = int(next(iterator))
15
        a = [int(next(iterator)) for _ in range(n)]
16
        b = [int(next(iterator)) for _ in range(n)]
17

18
        # 二分答案的上下界
19
        # 答案必然在数组中出现过，最小可能为 1，最大为 2*n + 5
20
        l = 0
21
        r = 2 * n + 5
22

23
        while l < r:
24
            mid = (l + r) // 2
25

26
            one = 0  # 统计类型 2 的个数
27
            zero = 0  # 统计连续类型 0 块的个数
28
            prev = -1  # 记录上一个有效列的类型（0或1，无视类型1）
29

30
            for i in range(n):
31
                # 计算当前列有多少个元素 >= mid
32
                type_count = 0
33
                if a[i] >= mid:
34
                    type_count += 1
35
                if b[i] >= mid:
36
                    type_count += 1
37

38
                # 核心结论：类型 1 是催化剂，直接忽略，不影响块的分割
39
                if type_count == 1:
40
                    continue
41

42
                # 遭遇类型 2
43
                if type_count == 2:
44
                    one += 1
45
                    prev = 1
46

47
                # 遭遇类型 0
48
                elif type_count == 0:
49
                    # 如果前一个有效的列不是 0，说明这是一段新连续 0 块的开头
50
                    if prev != 0:
51
                        zero += 1
52
                    prev = 0
53

54
            # 判定：如果 2 的个数大于 0 块的个数，说明 2 足够充裕把 0 斩草除除根
55
            if one > zero:
56
                l = mid + 1  # 尝试更大的目标值
57
            else:
58
                r = mid  # 目标值过大，缩减范围
59

60
        # 二分结束时的 l 即为第一个失败的值，所以最大可行解是 l - 1
61
        out.append(str(l - 1))
62

63
    # 一次性批量输出
64
    sys.stdout.write("\n".join(out) + "\n")
65

66

67
if __name__ == "__main__":
68
    solve()

音乐

音乐

1100Div1+2#

音乐

目录

音乐

音乐

1100Div1+2-数学+贪心+前缀和/思维+位运算/二分答案

1100Div1+2#

音乐

目录