蚂蚁集团 秋招 2023.09.05 机试题目与题解

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

1、小红判断相等

小红现在有一个长度为\(n\)的字符串\(s\)和长度为\(n\)的数组 \(a\)，如果满足对于\(a_i=a_j\)，都有\(s_i=s_j\)，并且对于\(a_i\neq a_j\)，都有 \(s_i\neq s_j\)，则字符串和数组相等。

请你告诉小红她的字符串和数组是否相等。

输入

一行一个整数\(t\)，表示有\(t\)组数据，对于每组数据：

一行一个整数\(n\)，表示字符串和数组的长度。

一行一个数组\(a\)，表示小红的数组。

一行一个字符串\(s\)，表示小红的字符串，字符串只包含小写字母。

  • \(1\le t\le 100\)
  • \(1\le n\le 1000\)
  • \(1\le a_i\le 50\)

输出

如果字符串和数组相等，输出"YES"，否则输出"NO"

样例

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

输出：
YES
NO

解答

这里需要判定的是\(a_i =a_j\)当且仅当\(s_i=s_j\)，因此我们分两个方向进行判断：

  1. \(s_i=s_j\Rightarrow a_i=a_j\)
  2. \(a_i=a_j\Rightarrow s_i=s_j\)

这两种判断方式是对称的，不失一般性，我们选择第1个方向进行解说。首先将\(s_i\)所有相同的下标都汇聚到一个集合中，然后再判断这个集合中所有下标在数组\(a\)中是否相等即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import defaultdict


def check(u, v):
    g = defaultdict(list)
    for i, x in enumerate(v):
        g[x].append(i)
    for v in g.values():
        st = set(u[x] for x in v)
        if len(st) > 1:
            return False
    return True


T = int(input())
for _ in range(T):
    input()
    a = list(map(int, input().split()))
    s = input()
    print("YES" if check(s, a) and check(a, s) else "NO")

2、小红的文具

小红有\(n\)支笔和\(m\)个本子，每支笔的颜色为\(a_i\)，本子的颜色为\(b_i\)，小红要拿走一支笔和一本本子，使得笔的颜色和本子的颜色可以匹配，颜色相同可以匹配。

颜色用\(0\)到\(10^9\)之间的整数表示。如果颜色为\(-1\)，则表示是彩色的，彩色可以匹配任何颜色。

请你帮助小红最多可以匹配多少对笔和本子。

输入

第一行两个整数\(n\)和\(m\)，表示笔的数量和本子的数量。

第二行\(n\)个整数\(a_i\)，表示每支笔的颜色。 第三行\(m\)个整数\(b_i\)，表示每个本子的颜色。

  • \(1\le n,m\le 10^5\)
  • \(-1\le a_i,b_i\le 10^9\)

输出

输出一个整数，表示最多可以匹配的对数。

样例

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

输出：
3

提示：
可以匹配的拿法有(1, 4), (2, 1), (3, 3)。

解答

分三个步骤来进行贪心：

  1. 先让单色的笔和单色的本子进行匹配。
  2. 如果有剩下的单色物品未被匹配，那么让彩色的笔和单色的笔记本匹配，或者是让单色的笔和彩色的笔记本匹配。
  3. 如果仍然剩下彩色的笔记本和笔，那么就让它们直接匹配。

由此分三步统计匹配个数即为答案。

代码

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
from collections import Counter

input()
a = map(int, input().split())
b = map(int, input().split())
ma = Counter(a)
mb = Counter(b)
na = ma.get(-1, 0)
nb = mb.get(-1, 0)
ma[-1] = mb[-1] = 0
ans = 0
for k, v in ma.items():
    if k in mb.keys():
        d = min(v, mb[k])
        ma[k] -= d
        mb[k] -= d
        ans += d
sa = sum(ma.values())
sb = sum(mb.values())
da = min(na, sb)
db = min(nb, sa)
ans += da + db
na -= da
nb -= db
ans += min(na, nb)
print(ans)

3、小红的red权值

小红定义一个字符串的权值为: 所有字符'e'的权值和。对于每个字符'e'，它前面的'r'和后面的'd'都会贡献\(1\)的权值。例如，"reded"的权值是\(5\)，因为第一个'e'贡献了\(3\)的权值(前面\(1\)个'r'和后面\(2\)个'd')，第二个'e'贡献了\(2\)的权值 (前面\(1\)个'r'和后面1个'd')。

现在小红拿到了一个仅由'r', 'e', 'd', '?'四种字符组成的字符串，小红可以将每个'?'修改为'r', 'e', 'd'中的任意一个字符（假设共有\(k\)个'?'，最终显然有\(3^k\)种方案）。

小红想知道，对于所有修改方案的权值之和是多少？由于答案过大，请对\(10^9+7\)取模。

输入

一个仅包含'r', 'e', 'd', '?'的字符串，长度不超过\(200000\)。

输出

所有方案的权值之和对\(10^9+7\)取模的答案。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：
re?ed

输出：
16

提示：
共有三种方案："rered"的权值为5，"reeed"的权值为6，"reded"的权值为5。总权值为16。

输入：
rrre

输出：
3

解答

这道题的基本思想是，对于每一对不同的下标\((i,j)\)，其中\(1\le i< j\le n\)，考虑它在这\(3^k\)个字符串中的贡献次数。

我们从前往后枚举每个字符\(c\)。假设\(c\)前面有\(r\)个字符'r'，后面有\(r\)个字符'd'。我们只讨论\(c\)是'e'或者是'?'的情况，因为有\(c\)意味着可以直接算贡献。

  • 如果\(c\)是字符'e'，那么\(c\)前面的每一个'r'都可以算作一次贡献。由于这个字符串可以生成\(3^k\)个不同的字符串，因此这一对可以产生\(3^k\)的贡献，这意味着这\(r\)个字符'r'一共产生了\(c\cdot 3^k\)的贡献；对于\(c\)后面的\(d\)个'd'也同理，产生了总共\(d\cdot 3^k\)的贡献。对于\(c\)左边的'?'，如果这个'?'为'r'，那么这一对可以产生\(3^{k-1}\)的贡献（因为其它'?'都可以随意填充字符）；类似的，对于\(c\)右边的'?'，如果这个'?'为'd'，那么这一对同样也可以产生\(3^{k-1}\)的贡献。由于字符串中有\(k\)个问号，因此这些问号总共会产生\(k\cdot 3^{k-1}\)的贡献。因此，这一种情况总共产生\((r+d)\cdot 3^k+k\cdot 3^{k-1}\)的贡献。

  • 如果\(c\)是字符'?'，那么现在假设\(c\)是一个'?'。和上面的分析非常类似，一对'r'和'?'可以产生\(3^{k-1}\)的贡献（因为这里的'?'已经被假设成'e'），因此这\(r\)个字符'r'一共产生了\(c\cdot 3^{k-1}\)的贡献；对于\(c\)后面的\(d\)个'd'也类似，产生了总共\(d\cdot 3^{k-1}\)的贡献。对于\(c\)左边的'?'，如果这个'?'为'r'，那么这一对可以产生\(3^{k-2}\)的贡献（因为除了填入'r'的'?'，和当前已经填入'e'的'?'，其它'?'都可以随意填充字符）；类似的，对于\(c\)右边的'?'，如果这个'?'为'd'，那么这一对同样也可以产生\(3^{k-2}\)的贡献。由于字符串中有\(k\)个问号，并且\(c\)已经是'e'，因此这些问号总共会产生\((k-1) \cdot 3^{k-2}\)的贡献。因因此，这一种情况总共产生\((r+d)\cdot 3^{k-1}+(k-1)\cdot 3^{k-2}\)的贡献。

因此，直接从前往后，暴力求出每一个'e'和'?'作为'e'时产生的贡献即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
s = input()
n = len(s)
mod = 10 ** 9 + 7
q = s.count('?')
cr = cq = 0
cd = s.count('d')
ans = 0
for ch in s:
    if ch == 'r':
        cr += 1
    elif ch == 'd':
        cd -= 1
    elif ch == 'e':
        ans += (cr + cd) * pow(3, q, mod)
        if q > 0:
            ans += q * pow(3, q - 1, mod)
    else:
        ans += (cr + cd) * pow(3, q - 1, mod)
        if q > 1:
            ans += (q - 1) * pow(3, q - 2, mod)
    ans %= mod
print(ans)

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