蚂蚁集团秋招 2023.09.14 编程题目与题解

发表于 2023-09-17 分类于笔试阅读次数：本文字数： 2.6k 阅读时长 ≈ 2 分钟

1、小红的逆序对

小红现在有一个长度为\(n\)的数组\(a_1,a_2,\dots,a_n\)，她希望这个数组出现至少一个逆序对。每一次她可以进行如下两种操作之一：

选择一个元素\(a_i\)，对\(a_i\)加上\(x\)。
选择一个元素\(a_i\)，对\(a_i\)减去\(y\)。

至少需要多少次操作才能够保证数组出现了至少一个逆序对？

这里的一个逆序对是指，存在一个下标对\((i,j)\)，同时满足\(1\le i<j\le n\)和\(a_i>a_j\)。

输入

第一行三个整数\(n,x,y\)，表示数组的大小和\(x,y\)的值。

第二行\(n\)个整数，表示数组\(a_1,a_2,\dots,a_n\)。

\(2\le n\le 10^5\)
\(-10^9\le a_i\le 10^9\)
\(1\le x,y\le 10^9\)

输出

输出一个整数表示答案。

样例

输入：
3 1 2
1 3 5

输出：
2

输入：
4 5 7
4 6 10 9

输出：
2

解答

首先，如果这个数组本身已经存在逆序对，那么什么操作都不需要进行，直接输出\(0\)即可。

如果不存在逆序对，那么说明这个数组已经是有序的。因此，为了使操作次数最少，我们选择相邻最近的两个数\(a_{i},a_{i+1}(1\le i<n)\)进行操作。为了使这两个数是一个逆序对，我们要么把\(a_i\)添加\(x\)，要么把\(a_{i+1}\)减少\(y\)，选择速度最快的操作使得最终满足\(a_{i}>a_{i+1}\)即可。这里需要至少进行\(\left\lceil\dfrac{a_{i+1}-a_i+1}{\max\{x,y\}}\right\rceil\)次操作。可以发现，这个值和\(\left\lfloor\dfrac{a_{i+1}-a_i}{\max\{x,y\}}\right\rfloor+1\)相等。

因此，对于一个已经有序的数组\(a\)，这题的最终答案为：

\[\left\lfloor\dfrac{\min_{i=1}^{n-1}\{a_{i+1}-a_i\}}{\max\{x,y\}}\right\rfloor+1\]

代码

n, x, y = map(int, input().split())
o = max(x, y)
a = list(map(int, input().split()))
d = min(a[i] - a[i - 1] for i in range(1, n))
ans = 0 if d < 0 else d // o + 1
print(ans)

2、小红的匹配

小红有\(1\)到\(n\)这\(n\)个数字，\(n\)是偶数。

她想将这\(n\)个数字两两匹配，比如将\(a_i\)和\(a_j\)匹配，\(i\neq j\)，需要保证\((a_i+k)\times a_j\)是\(4\)的倍数，即\((a_i+k)\times a_j\%4 =0\)，其中\(k\)是一个整数，每个数字只能匹配一次。

请问小红能否完成匹配，如果可以，输出匹配的方案。

输入

第一行两个整数\(n\)和\(k\)，表示数字的个数和\(k\)的值，保证\(n\)是一个偶数。

\(1\le n,k\le 10^5\)

输出

如果能完成匹配，输出YES，然输出\(n/2\)行，每行两个整数\(a_i\)和\(a_j\)，表示匹配的两个数字。

如果不能完成匹配，输出NO。

样例

输入：
4 2

输出：
YES
2 1
3 4

提示：
(2 + 2) * 1 = 4是4的倍数，(3 + 2) * 4 = 20是4的倍数。

解答

本题进行分类讨论。令\(m=n/2\)，可以知道\(1\sim n\)中有\(m\)个奇数，\(m\)个偶数（即一半一半）。

我们将\(1\sim n\)这\(n\)个整数划分成\(3\)类：

奇数，记为\(A_n\)。
偶数，但不是\(4\)的倍数，记为\(B_n\)。
\(4\)的倍数，记录为\(C_n\)。

接下来进行分类讨论：

\(k\)是奇数。这时只需要将\(A_n\)中的所有书放在\(a_i\)一侧，将\(B_n\)和\(C_n\)放在\(a_j\)一侧。这时放在\(a_i\)一侧的真实值为\(a_i+k\)，它们都是偶数。因此\(a_i\)和\(b_i\)一侧的数任意组合，都是答案。
\(k\)是\(2\)的倍数，但不是\(4\)的倍数。那么对于\(A_n\)中的所有数，它们加上\(k\)之后仍然是奇数，因此无论将它们放在\(a_i\)还是\(a_j\)一侧，它们不会对乘积\((a_i+k)\times a_j\)贡献出任何因子\(2\)。对于\(B_n\)和\(C_n\)，我们将\(B_n\)所有整数都放在\(a_i\)一侧，这样它们就贡献了\(2\)个因子\(2\)（因为新值是\(a_i+k\)）；将\(C_n\)所有整数都放在其余匹配\(a_j\)一侧，那么它们也贡献了\(2\)个因子\(2\)。未被摆放的\(A_n\)随意摆放到其余空位即可，答案必然正确。
\(k\)是\(4\)的倍数，这时无论放在\(a_i\)一侧还是\(a_j\)一侧都是一样的，可以抛弃\(k\)的具体值直接进行讨论。由于\(|A_n|=m\)，因此这\(m\)个奇数必定处在不同匹配中。对于\(B_n\)和\(C_n\)，由于\(B_n\neq \varnothing\)必定成立，因此\(B_n\)中的一个元素必定被填入其中一个匹配中，但是另一个数必定来自\(A_n\)，它没有\(2\)的因子。因此，这种情况必然无解。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100004;
int a[N],b[N],n,k;
int main(){
    scanf("%d %d",&n,&k);
    int m=n/2;
    int flag=0;
    if(k%2==1){
        flag=1;
        for(int i=1;i<=m;i++){
            a[i]=2*i-1;b[i]=2*i;
        }
    }
    else if(k%4==2){
        int x=1,pos=0;
        for(int i=2;i<=n;i+=4){
            a[++pos]=i;b[pos]=x;
            x+=2;
        }
        for(int i=4;i<=n;i+=4){
            b[++pos]=i;a[pos]=x;
            x+=2;
        }
    }
    puts(flag?"YES":"NO");
    if(flag){
        for(int i=1;i<=m;i++)
            printf("%d %d\n",a[i],b[i]);
    }
}

3、小红的路径

小红拿到了一棵树，已知树上有\(3\)种节点: 红色、绿色或者蓝色。小红可以经过红色节点，小紫可以经过红色或者绿色节点。小红想知道，有多少条路径是小紫能走但小红不能走的？注：树上任意两点之间都存在且仅存在一条路径。

输入

第一行输入一个整数\(n(1\le n\le 10^5)\)表示树的大小。

第二行输入一个长度为\(n\)，且仅包含'r', 'g', 'b'三种字母的字符串表示每个结点的颜色，其中'r'代表红色，'g'代表绿色，'b'代表蓝色。

接下来\(n-1\)行，每行输入两个整数\(u,v(1<u,v\le n)\)表示树上的边。

输出

输出一个整数表示答案。

样例

输入：
3
rgb
1 2
1 3

输出：
1

提示：
只有路径1-2是小紫可走，但小红不可走的。

解答

首先可以知道的是，小红能走的路径小紫必定也能走，因此只需要将小紫能够走的路径数减去小红能够走的路径数即可。

不失一般性，我们这里只求取其中一个人能够走的路径数。由于原图是一棵树，因此我们去除这个人所有不能走的节点后，可以发现这个图变成了一个森林，其中每个连通块都是一棵树。同一连通块下的任意一对节点都可达，因此我们统计每个连通块的节点数\(c\)后，可以知道这里面一共有\(\dfrac{c(c-1)}{2}\)条路径可以添加到答案中。

这里使用了并查集来求取每个连通块中的节点数。

代码

import sys

sys.setrecursionlimit(10 ** 5 + 4)
n = int(input())
s = input()
e = []
for _ in range(1, n):
    x, y = map(lambda x: int(x) - 1, input().split())
    e.append((x, y))


def solve(t):
    def find(x):
        if x == fa[x]:
            return x
        else:
            fa[x] = find(fa[x])
            return fa[x]

    def merge(x, y):
        u, v = find(x), find(y)
        if u != v:
            fa[v] = u
            sz[u] += sz[v]

    fa = list(range(n))
    sz = [1 for _ in range(n)]
    for x, y in e:
        if s[x] in t and s[y] in t:
            merge(x, y)
    val = 0
    for i in range(n):
        if i == find(i) and s[i] in t:
            val += sz[i] * (sz[i] - 1) // 2
    return val


ans = solve('rg') - solve('r')
print(ans)