携程 秋招 2023.10.10 编程题目与题解

发表于 分类于 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

1、游游修改01串

游游拿到了一个01串，她最多可以修改字符串中的一个位置(即'0'变'1'，或'1'变'0')。游游希望修改后字符串包含尽可能多的长度为\(3\)的回文子串。你能帮帮她吗？

输入

一个仅包含'0'和'1'的字符串，长度不超过\(10^5\)。

输出

一个整数，代表修改后的回文子串数量。

样例

1
2
3
4
5
输入：
01101

输出：
2

解答

一个长度为\(3\)的字符串\(t=t_1t_2t_3\)是回文串当且仅当\(t_1=t_3\)。

因此，首先统计当前输入的字符串\(s\)有多少个长度为\(3\)的回文串，并记录其值为\(v\)。如果要修改字符\(s[i]\)，那么只会影响子串\(s[i-2:i]\)和\(s[i:i+2]\)是否为回文串这个状态发生变化。因此改变\(s[i]\)后，重新统计受影响的位置中的变化即可，最终取最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
s = input()
n = len(s)
v = 0
for i in range(1, n - 1):
    if s[i - 1] == s[i + 1]:
        v += 1
mx = v
s = list(int(x) for x in s)
for i in range(n):
    k = i - 1
    w = v
    for k in [i - 1, i + 1]:
        if 1 <= k < n - 1 and s[k - 1] == s[k + 1]:
            w -= 1
    s[i] ^= 1
    for k in [i - 1, i + 1]:
        if 1 <= k < n - 1 and s[k - 1] == s[k + 1]:
            w += 1
    mx = max(mx, w)
    s[i] ^= 1
print(mx)

2、游游的分治

二维平面上有\(n\)个点。游游准备用以下的分治手段查找出某个点。

  1. 按横坐标从小到大排序，横坐标相等的按纵坐标从小到大排序。将排好序的点数组分成数量尽可能接近的两部分（如果此时共有奇数个点，那么第一部分的数量比第二部分少\(1\)）。查找指定点在第一部分还是第二部分。

  2. 按纵坐标从小到大排序，纵坐标相等的按横坐标从小到大排序。将排好序的点数组分成数量尽可能接近的两部分（如果此时共有奇数个点，那么第一部分的数量比第二部分少\(1\)）。查找指定点在第一部分还是第二部分。

  3. 回到第一步重复下去。直到最终只剩一个点时跳出。

请你模拟游游的分治过程。

输入

第一行输入两个正整数\(n,x\)，代表点的数量、以及需要查找第几个点。

接下来的\(n\)行，每行输入两个整数\(x_i,y_i\)，代表点的坐标。

  • \(1 \le n \le 1000\)
  • \(-10^9\le x_i,y_i\le 10^9\)

输出

输出一个字符串，代表每次查找的结果。

  1. 如果该次查到的在第一部分，输出'L'。
  2. 如果该次查到的在第二部分，输出'R'。
  3. 如果该次查找仅包含一个点，输出'O'。

样例

1
2
3
4
5
6
7
8
9
输入：
4 2
-1 3
3 5
2 6
4 3

输出：
RRO

解答

按照题目的要求进行即可。第\(i\)次的搜索使用的排序规则为第\(i\bmod 2\)条，并舍弃另一半未被搜索的点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n, x = map(int, input().split())
a = []
f = [lambda t: t, lambda t: (t[1], t[0])]
for _ in range(n):
    a.append(tuple(map(int, input().split())))
t = a[x - 1]
s = ""
for k in range(100):
    a.sort(key=f[k & 1])
    m = len(a)
    if m == 1:
        s += "O"
        break
    l, r = a[:m >> 1], a[m >> 1:]
    if t in l:
        s += "L"
        a = l
    else:
        s += "R"
        a = r
print(s)

3、游游的字符串

游游拿到了一个字符申，她每次接作可以梅一个字裤修改为其字母表上相邻的字母，例如'a'修改为'b'，'e'修改为'd'等。

游游希望最终字符串每个相邻字符都不相等，她想知道最终最少操作多少次？请你给出任意一个修改后的方案。

输入

输入仅包含一行由英文小写字母组成的字符串，长度不超过\(10^5\)。

输出

第一行输出一个整数，代表最少的修改次数。

第二行输出一个字符串，代表修改后的字符串。有多解时输出任意即 可。

样例

1
2
3
4
5
6
输入：
aabcc

输出：
2
babcb

解答

一个字符可以改成它字母表上相邻的字符，我们可以将第\(i\)个字符最终变成另一个字符视为是一种决策，这些决策集合用\(O_i\)来表示，\(o_{i,j}\)表示选择的是第\(j\)种决策表示的字符。

由于当前字母的决策只取决于前一个字母，因此这题我们使用动态规划不难解决。令\(s\)表示输入的字符串，状态\(f(i,j)(1\le i\le n,1\le j\le |O_i|)\)表示保证前\(i\)个字符已经不相同的情况下，第\(i\)个字符为\(o_{i,j}\)所需要的最小操作次数。那么可以写出如下状态转移方程：

\(f(i,j)= \left \{\begin{aligned} &[o_{i,j}\neq s_i] & & \text{if}\quad i=1 \\ &\min_{\substack{1\le k\le |O_{i-1}|\\o_{i-1,k}\neq o_{i,j}}}\{f(i-1,k)+[o_{i,j}\neq s_i]\} & & \text{if}\quad i>1 \\ \end{aligned}\right.\)

其中，示性函数\([b]\)表示布尔表达式\(b\)如果成立，那么其值为\(1\)，否则为\(0\)。为了记录最优决策，我们还要记录当前状态是由\(f(i-1,\cdot)\)的哪个状态转移而来，在最后构造方案时，根据记录情况，从后往前进行构造即可。

因此，最终答案为\(\displaystyle{\min_{j=1}^{|O_n|}\{f(n,j)\}}\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
s = input()
n = len(s)

op = ["" for _ in range(n)]
for i in range(n):
    if s[i] == 'a':
        op[i] = 'ab'
    elif s[i] == 'z':
        op[i] = 'yz'
    else:
        k = ord(s[i])
        op[i] = chr(k - 1) + chr(k) + chr(k + 1)

f = [[0 for _ in range(len(op[i]))] for i in range(n)]
pre = [[0 for _ in range(len(op[i]))] for i in range(n)]
for j in range(len(op[0])):
    f[0][j] = int(op[0][j] != s[0])
for i in range(1, n):
    for j in range(len(op[i])):
        f[i][j] = 10 ** 10
        for k in range(len(op[i - 1])):
            if op[i - 1][k] != op[i][j]:
                v = f[i - 1][k] + int(op[i][j] != s[i])
                if v < f[i][j]:
                    f[i][j] = v
                    pre[i][j] = k

k = 0
for j in range(len(op[-1])):
    if f[-1][j] < f[-1][k]:
        k = j
print(f[-1][k])
ans = ["" for _ in range(n)]
for i in range(n - 1, -1, -1):
    ans[i] = op[i][k]
    k = pre[i][k]
print("".join(ans))

4、游游的树

游游拿到了一棵树，其中每个节点被染成了红色(r) 、绿色(g)或蓝色(b)。

游游想选择一条长度为\(3\)的简单路径，满足该路径上的四个点恰好共有\(3\)种颜色。

游游想知道，可以选择多少不同的路径？我们认为，点\(p\)到点\(q\)，点\(q\)到点\(p\)这两条路径为同一条。

注：树指不含重边和自环的无向连通图。

输入

第一行输入一个正整数\(n\)，代表树的节点数量。

第二行输入一个长度为\(n\)的、仅包含'r'、'g'、'b'三种字符的字符串，第\(i\)个字符表示节点\(i\)的颜色。

接下来的\(n-1\)行，每行输入两个正整数\(u\)和\(v\)，代表点\(u\)和点\(v\)有一条无向边连接。

  • \(3\le n\le 10^5\)
  • \(1\le u,v\le n\)

输出

一个整数，代表不同路径的数量。

样例

1
2
3
4
5
6
7
8
9
10
11
12
输入：
4
rgbg
1 2
2 3
3 4

输出：
1

提示：
只有一种选择：选择1-2-3-4路径

解答

由于长度的路径只有\(3\)，因此我们可以用贡献法进行解决，枚举每一边作为路径的中间那条边，计算路径数，并添加到答案中。

为了表达上和编码上的方便，我们分别将三种颜色映射成三个数字\(0,1,2\)。令\(a_u\)表示节点\(u\)的颜色，令\(c_{u,k}\)表示节点\(u\)有多少个相邻节点的颜色是\(k\)，令\(d_u\)表示节点\(u\)的度数。接下来对每条边\(u,v\)分两种情况进行讨论：

  • 如果\(a_u=a_v\)，那么说明\(u\)的另一个邻居\(x\)和\(v\)的另一个邻居\(y\)必须是剩下的两种颜色。设这两种颜色分别为\(c_1\)和\(c_2\)，那么要么\(x\)的颜色为\(c_1\)，\(y\)的颜色为\(c_2\)；要么\(x\)的颜色为\(c_2\)，\(y\)的颜色为\(c_1\)，因此这条边总共做出的贡献为\(c_{u,c_1}\times c_{v,c_2}+c_{u,c_2}\times c_{v,c_1}\)。

  • 如果\(a_u\neq a_v\)，令\(c_0\)是除去\(a_u\)和\(a_v\)的剩下的第三种颜色，那么\(x\)和\(y\)中必定有一个颜色是\(c_0\)，另一个节点颜色随意，那么可以看出这部分做出的贡献为\(c_{u,c_0}\times(d_v-1)+c_{v,c_0}\times (d_u-1)-c_{u,c_0}\times c_{v,c_0}\)，其中，前两项里面的\(-1\)在于避免这条路径又回到这条边的另一个节点，从而避免把有重复节点的路径统计进去。第三项在于前面的一项将两端都是颜色c_0的情况重复计算了，需要减回去。

因此直接累计答案即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n = int(input())
s = input()
cnt = [[0, 0, 0] for _ in range(n)]
g = [[] for _ in range(n)]
mp = {'r': 0, 'g': 1, 'b': 2}
col = [mp[c] for c in s]

edge = []
for i in range(1, n):
    x, y = map(lambda x: int(x) - 1, input().split())
    g[x].append(y)
    g[y].append(x)
    edge.append((x, y))
for i in range(n):
    for j in g[i]:
        cnt[i][col[j]] += 1
ans = 0
for u, v in edge:
    if col[u] == col[v]:
        c1 = 1 if col[u] == 0 else 0
        c2 = 3 - c1 - col[u]
        ans += cnt[u][c1] * cnt[v][c2] + cnt[u][c2] * cnt[v][c1]
    else:
        c = 3 - col[u] - col[v]
        ans += cnt[u][c] * (len(g[v]) - 1) + cnt[v][c] * (len(g[u]) - 1) - cnt[u][c] * cnt[v][c]
print(ans)

如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝