题目#

给爱丽丝和鲍勃一个二进制字符串 ∗ 。 s 长度为 n 。它包含至少一个 0 和至少一个 1 。

它们按照以下顺序各执行一次***操作：

• 首先，爱丽丝在 s 中选择 0 的一个出现点并将其删除。
• 然后，鲍勃在得到的字符串中选择 1 的一个出现点并删除它。

爱丽丝希望最终的字符串在 † 的词典中尽可能大，而鲍勃希望它在 † 的词典中尽可能小。如果双方都采取最优行动，请确定最终字符串。

∗ 一个二进制字符串是一个只由字符 0 和 1 组成的字符串。

† 对于两个长度相同的二进制字符串 a 和 b ，如果在它们不同的第一个位置上， a 的数字小于 b ，那么 a 在词法上小于 b 。

贪心#

两个人均删掉第一个0或1即可使得出现第一个1或0从而达到目的

1
for _ in range(int(input())):
2
    s = input().strip()
3
    pos0 = s.find('0')
4
    s = s[:pos0] + s[pos0 + 1:]
5
    pos1 = s.find('1')
6
    s = s[:pos1] + s[pos1 + 1:]
7
    print(s)

题目#

给你两个长度分别为 n 和 m 的数组 a 和 b 。这些数组中的所有 n+m 个整数都是不同的。

您可以对 a 执行以下操作，次数不限（可能为零）：

• 从 a 中选择两个元素，值分别为 x 和 y ，其中 x≤y 。
• 从 a 中删除这两个元素。
• 在 a 中插入一个整数 z ，使得 x≤z≤y .

完成所有操作后，可以任意排列 a 中的元素。

判断是否有可能使 a 等于 b 。

贪心#

要把a通过题述操作变成b显然的n ≥ 2*m

排序a和b，

排序后，用 a 中最小的 m 个数作为”左边界”，最大的 m 个数作为”右边界”。

对于b中的每个元素，在a中找配对须满足：

即b[i]应在a[i]左边能提供的最小值和a[n-m+i]右边能提供的最大值之间

1
import bisect
2
for _ in range(int(input())):
3
    n, m = map(int, input().split())
4
    a = list(map(int, input().split()))
5
    b = list(map(int, input().split()))
6
    a.sort()
7
    b.sort()
8
    ok = True
9
    if n < m*2:
10
        ok = False
11
    else:
12
        for i in range(m):
13
            if a[i] > b[i] or a[n-m+i] < b[i]:
14
                ok = False
15
                break
16
    print("YES" if ok else "NO")

题目#

给你一个长度为 $2n$ 的数组 $a$ 。从 $1$ 到 $n$ 的每个整数在 $a$ 中恰好出现两次。

最初，您的得分是 $0$ 。

当 $a$ 为非空时，您可以重复执行以下操作：

• 选择一个在 $a$ 中存在的整数 $x$ 。
• 设 $l$ 和 $r$ 分别是当前数组中出现 $x$ 的最左边和最右边的索引。如果 $x$ 只出现一次，那么就是 $l = r$ 。
• 将 $(r - l + 1)^2$ 加入您的得分。
• 从 $a$ 中删除 $a_l, a_{l + 1}, \ldots, a_r$ 元素。其余元素在不改变顺序的情况下进行连接，并从 $1$ 开始重新索引。

将数组清空后，求最大可能得分。

区间DP#

对于每个数字 x，它在数组中出现两次，记两个位置为：

如果选择 x 进行操作，会删除整个区间：

并获得：

的分数。

考虑多个数字对应的区间：

• 如果两个区间互不相交，那么它们可以分别执行操作。
• 如果两个区间存在交叉或包含关系，那么其中一个区间被删除后，另一个区间中的元素也会一起消失。

因此最终能够贡献完整分数的数字对应区间一定满足：

所有选择的区间两两不相交。

问题变成：

在所有区间中选择若干互不重叠的区间，使得收益最大。

这是经典的 加权区间调度问题。

假设选择一个区间：

长度：

如果不选择：

• 其中 len 个元素最终会单独删除。
• 每个元素贡献 1。

因此贡献为：

如果选择：

所以选择该区间产生的额外收益：

所有 2n 个元素无论如何都会被删除，因此基础贡献为：

只需要最大化：

最后答案：

将每个数字形成的区间记为：

其中：

按照右端点 r 从小到大排序。

定义：

表示考虑前 i 个区间时能够获得的最大额外收益。

对于第 i 个区间：

情况 1：不选择

直接继承：

情况 2：选择

需要找到最后一个与当前区间不冲突的区间：

那么：

综合：

由于区间已经按照右端点排序。

维护：

1
ends[i] = 第 i 个区间的右端点

对于当前区间左端点 l：

使用：

1
bisect_left(ends,l)

找到第一个：

的位置。

因此其前一个位置就是最后一个满足：

的不冲突区间。

遍历数组，记录每个数字出现的位置。

根据两个位置构造区间：

计算每个区间的额外收益：

按右端点排序。

使用加权区间 DP。

输出：

1
import bisect
2
for _ in range(int(input())):
3
    n = int(input())
4
    a = list(map(int, input().split()))
5
    pos = [[] for _ in range(n + 1)]
6
    for i, x in enumerate(a):
7
        pos[x].append(i)
8
    b = []
9
    for x in range(1, n + 1):
10
        l, r = pos[x]
11
        length = r - l + 1
12
        g = length * length - length
13
        b.append((l, r, g))
14
    b.sort(key=lambda x: x[1])
15
    en = [r for l, r, w in b]
16
    m = len(b)
17
    dp = [0] * (m + 1)
18
    for i in range(1, m + 1):
19
        l, r, w = b[i - 1]
20
        j = bisect.bisect_left(en, l, 0, i - 1)
21
        dp[i] = max(
22
            dp[i - 1],
23
            dp[j] + w
24
        )
25
    print(2 * n + dp[m])

将每个数字出现的位置看成一个带权区间，把原问题转化为最大权不相交区间选择问题，用dp[i]=max(dp[i-1],dp[pre[i]]+w[i])求最大额外收益，最后加上所有单点删除的基础贡献2n。

题目#

给你两个二进制字符串 $s$ 和 $t$ ，长度都是 $n$ 。

对于长度相同的两个二进制字符串 $a$ 和 $b$ ，如果执行下面的操作 0 次或 0 次以上就能使两个字符串变为空，那么这对字符串 $(a, b)$ 就叫做好字符串：

• 选择一组非空的位置 $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le |a|$ 和一个字符 $c \in \{\mathtt{0}, \mathtt{1}\}$ 。
• 让 $x = a_{i_1}a_{i_2}\ldots a_{i_k}$ 和 $y = b_{i_1}b_{i_2}\ldots b_{i_k}$ .
• 字符 $c$ 必须是 $x$ 和 $y$ 的模式 $^{\text{∗}}$ 。
• 从两个字符串中删除所选位置上的字符。其余字符将在不改变相对顺序的情况下进行连接。

二进制字符串的模式可以是 $\mathtt{0}$ 和 $\mathtt{1}$ 。

您需要回答 $q$ 个查询。每个查询都给出两个整数 $l$ 和 $r$ 。请判断一对子串 $(s_l s_{l+1} \ldots s_r, t_l t_{l+1} \ldots t_r)$ 是否合适。

这些查询是独立的。

$^{\text{∗}}$ 对于二进制字符串 $z$ ，如果字符 $c$ 在 $z$ 中至少出现 $\left\lceil \frac{|z|}{2} \right\rceil$ 次，则该字符 $c$ 是一个模式。这里， $\lceil x \rceil$ 表示大于或等于 $x$ 的最小整数。

对于每个位置 i，考虑：

共有四种情况：

对于一个查询区间，设：

一次操作需要选择若干位置，并选择一个字符 x。

要求：

• x 在第一个字符串选出的子序列中出现次数不少于一半。
• x 在第二个字符串选出的子序列中出现次数不少于一半。

情况1：选择字符 0

第一个字符串：

1
0 的数量 = a+b
2
1 的数量 = c+d

需要：

第二个字符串：

1
0 的数量 = a+c
2
1 的数量 = b+d

需要：

化简：

情况2：选择字符 1

同理：

因此一次操作合法条件：

3. 整个字符串可删除条件

考虑：

其中：

• 一个 01 和一个 10 可以互相抵消。
• 剩余的不平衡部分需要通过 00 或 11 提供贡献。

因此：

需要：

即：

这就是 good 的充要条件。

由于：

不能每次重新统计。

维护四个前缀数组：

1
pre00[i]
2
pre01[i]
3
pre10[i]
4
pre11[i]

表示前 i 个位置中四种类型出现次数。

对于查询：

有：

即可 O(1) 得到四个数量。

1. 遍历字符串。
2. 统计每个位置属于哪一种类型。
3. 建立四个前缀和数组。
4. 对每个查询：
   • 求 cnt00,cnt01,cnt10,cnt11
   • 判断：

1. 输出结果。

引理 1

一次操作可以删除一个非空集合，当且仅当：

证明：

选择 0 时：

选择 1 时：

两种情况合并：

引理 2

如果：

则整个字符串一定可以删除。

原因：

• 01 与 10 可以配对删除。
• 多余部分由 00 或 11 补偿。
• 每次操作至少删除一个字符。
• 最终可以删除全部位置。

定理

对于任意查询：

good 当且仅当：

因此算法正确。

1
import sys
2
input = sys.stdin.readline
3
T = int(input())
4
for _ in range(T):
5
    n, q = map(int, input().split())
6
    s = input().strip()
7
    t = input().strip()
8
    pre00 = [0] * (n + 1)
9
    pre01 = [0] * (n + 1)
10
    pre10 = [0] * (n + 1)
11
    pre11 = [0] * (n + 1)
12
    for i in range(n):
13
        pre00[i+1] = pre00[i]
14
        pre01[i+1] = pre01[i]
15
        pre10[i+1] = pre10[i]
16
        pre11[i+1] = pre11[i]
17
        if s[i] == '0' and t[i] == '0':
18
            pre00[i+1] += 1
19
        elif s[i] == '0' and t[i] == '1':
20
            pre01[i+1] += 1
21
        elif s[i] == '1' and t[i] == '0':
22
            pre10[i+1] += 1
23
        else:
24
            pre11[i+1] += 1
25
    for _ in range(q):
26
        l, r = map(int, input().split())
27
        c00 = pre00[r] - pre00[l-1]
28
        c01 = pre01[r] - pre01[l-1]
29
        c10 = pre10[r] - pre10[l-1]
30
        c11 = pre11[r] - pre11[l-1]
31
        if abs(c01 - c10) <= c00 + c11:
32
            print("YES")
33
        else:
34
            print("NO")