题目#

如果一个整数 $n$ 的十进制表示中最多包含***两个不同的数字，那么这个整数 $n$ 就是好整数。例如，整数 $3$ 、 $8588$ 、 $67$ 是好整数，而整数 $123$ 、 $9447$ 则不是好整数。

给你一个整数 $x$ ( $1 \le x \lt 10^8$ )，它是好的。你的任务是找出一个满足以下两个条件的整数 $y$ ( $2 \le y \le 10^9$ )：

• $y$ 好。
• $x \times y$ 好。

构造#

**把 x 写两遍就是 x×y，而 y 就是 **100...001

1
for _ in range(int(input())):
2
    x = int(input())
3
    y = 10 ** len(str(x)) + 1
4
    print(y)

题目#

给你一个二进制字符串 $s$ ，其中只有字符 $\texttt{0}$ 和 $\texttt{1}$ 。

在一次操作中，您可以执行以下操作：

• 选择 $s$ 的子串 $^{\text{∗}}$ ，该子串是长度至少为 $2$ 的重码 $^{\text{†}}$ 。
• 从所选子串中恰好删除一个字符。

然后将字符串的其余部分连接起来，形成新字符串 $s$ 。

求任意多次（可能为零）进行此操作后，字符串 $s$ 可能达到的最小长度。

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

$^{\text{†}}$ 长度为 $m$ 的字符串 $a$ 如果在所有 $1 \le i \le m$ 中都有 $a_i = a_{m + 1 - i}$ ，则称该字符串为回文字符串。

贪心#

设 $c$ 是 $i$ 中 $s_i \ne s_{i+1}$ 的位置数。

如果 $c=0$ ，则所有字符都相等。整个字符串总是一个回文，因此我们可以反复删除字符，直到只剩下一个为止。

如果是 $c=1$ ，字符串正好由两个长度相等的连续字符块组成。任何长度至少为 $2$ 的回文字符串都必须完全包含在其中一个字符串块中，因此每次操作都只能缩短一个字符串块，而不可能完全删除它。因此，这两个区块仍然是非空的，而可能的最小长度是 $2$ 。

如果是 $c\ge 2$ ，那么字符串至少有三个数据块。首先，我们可以将每个字块的长度缩减为 $1$ ，因为只要其长度至少为 $2$ ，任何相等字符的字块本身都是长度至少为 $2$ 的回文。因此，我们可以假设字符串变成了交替字符串。

现在考虑一个长度至少为 $3$ 的交替字符串。它的最后三个字符总是以 $010$ 或 $101$ 的形式出现；因此，它们构成了一个回文字符串。删除这个回文字符串的最后一个字符可以将字符串缩短 $1$ ，剩下的字符串仍然是交替的。重复这一步骤，我们可以将字符串的长度减少到 $3$ 。那么整个字符串就是一个回文字符串，删除中间的字符可以得到两个相等的字符，再移动一步就可以将长度减至 $1$ 。

因此，如果是 $c=1$ ，答案为 $2$ ，否则为 $1$ 。

1
for _ in range(int(input())):
2
    n = int(input())
3
    s = input().strip()
4
    cnt = 1
5
    for i in range(1,n):
6
        if s[i] != s[i-1]:
7
            cnt += 1
8
    if cnt == 2:
9
        print(2)
10
    else:
11
        print(1)

题目#

给你两个数组 $a$ 和 $b$ ，每个数组的长度都是 $n$ 。您可以对数组 $a$ 执行以下操作任意多次（包括零次）：

1. 选择两个索引 $l$ 和 $r$ ，使得 $1 \le l \le r \le n$ ；
2. 对于从 $l$ 到 $r$ 的每个索引 $i$ （包括这两个索引）、
   • 设 $i - l$ 为奇数，则设 $a_i := a_i - 1$ 为奇数。
   • 如果 $i - l$ 是偶数，则设 $a_i := a_i + 1$ 为奇数。

判断是否可以通过执行任意次数的操作使数组 $a$ 等于数组 $b$ 。

贪心#

定义前缀和 p[i] = a[1] + a[2] + ... + a[i]

操作对前缀和的影响：

对于区间 [l, r]：

• 位置 l：+1 → p[l] 到 p[n] 都 +1
• 位置 l+1：-1 → p[l+1] 到 p[n] 都 -1
• 位置 l+2：+1 → p[l+2] 到 p[n] 都 +1
• …

最终效果：

• p[l-1] 及之前：不变
• p[l]：+1
• p[l+1]：+1-1=0
• p[l+2]：+1-1+1=+1
• …

某些前缀和 +1，某些不变，前缀和永远不会减少

操作 [i, i+1]：

• a[i] += 1，a[i+1] -= 1
• 只有 p[i] 增加 1，其他前缀和不变

操作 [n, n]：

• a[n] += 1
• 只有 p[n] 增加 1

每个前缀和都可以独立增加任意多次，但不能减少！

因此，a 能变成 b 的充要条件是：

$pi≤qi$对所有 i，$pi≤qi$对所有 i

其中 p[i] 是 a 的前缀和，q[i] 是 b 的前缀和。

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
    ok = True
6
    suma = sumb = 0
7
    for i in range(n):
8
        suma += a[i]
9
        sumb += b[i]
10
        if suma > sumb:
11
            ok = False
12
            break
13
    print("YES" if ok else "NO")

#