记录下 2024-03-09 团子的第一次笔试

时间：2024-03-09 10:00 - 12:00

战况：3.5 / 5

小美的MT

题目

MT 是美团的缩写，因此小美很喜欢这两个字母。

现在小美拿到了一个仅由大写字母组成字符串，她可以最多操作k次，每次可以修改任意一个字符。小美想知道，操作结束后最多共有多少个'M'和'T'字符？

输入描述

第一行输入两个正整数，代表字符串长度和操作次数。第二行输入一个长度为的、仅由大写字母组成的字符串。

1<=k<=n<=10⁵

输出描述

输出操作结束后最多共有多少个'M'和'T'字符。

示例 1

输入

5 2
MTUAN

输出

说明

修改第三个和第五个字符，形成的字符串为 MTTAM，这样共有 4 个'M'和'T'。

思路 && 代码

基础字符串处理题，找到字符串原本包含"M"和"T"的数量，然后k的贡献就是最多产生k个MT，然后只需要和剩余的字符取个最小值即可。

Java
Python

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        String s = sc.next();
        solve(n, k, s);
        sc.close();
    }

    static void solve(int n, int k, String s) {

        int cnt = 0;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (ch == 'M' || ch == 'T')
                cnt++;
        }
        System.out.println(cnt + Math.min(k, n - cnt));
    }

}

n, k = map(int, input().split())
s = input()

cnt = s.count("M") + s.count("T")
print(cnt + min(k, n - cnt))

小美的数组询问

题目

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。

现在小美想知道，如果那些未知的元素在区间[l,r]范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？共有q次询问。

输入描述

第一行输入两个正整数n,q，代表数组大小和询问次数。

第二行输入n个整数a_i，其中如果输入ai的为 0，那么说明ai是未知的。

接下来的q行，每行输入两个正整数l,r，代表一次询问。

1<=n,q<=10⁵

0<=a_i<=10⁹

1<=l<=r<=10⁹

输出描述

输出q行，每行输出两个正整数，代表所有元素之和的最小值和最大值。

示例 1

输入

输出

5 6
8 8

说明

只有第二个元素是未知的。第一次询问，数组最小的和是 1+1=3=5，最大的和是 1+2+3=6。第二次询问，显然数组的元素和必然为 8。

思路 && 代码

首先统计总和，然后统计0的数量，最小值就是0的数量 * 区间左值，反之最大值就是0的数量 * 区间右值。

📢注意：Java、C++这类语言需要注意溢出问题。

Java
Python

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), q = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }
        long sum = 0;
        int cnt0 = 0;
        for (long x : arr) {
            if (x == 0)
                cnt0++;
            sum += x;
        }
        for (int i = 0; i < q; i++) {
            long l = sc.nextLong(), r = sc.nextLong();
            long mn = sum + l * cnt0;
            long mx = sum + r * cnt0;
            System.out.println(mn + " " + mx);
        }
        sc.close();
    }

}

n, q = map(int, input().split())
arr = [int(x) for x in input().split()]

cnt0 = arr.count(0)
s = sum(arr)

for _ in range(q):
    l, r = map(int, input().split())
    mn, mx = s + l * cnt0, s + r * cnt0
    print(mn, mx)

小美的平衡矩阵

题目

小美拿到了一个n*n 的矩阵，其中每个元素是 0 或者 1。

小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。

现在，小美希望你回答有多少个i*i的完美矩形区域。你需要回答1<=i<=n的所有答案。

输入描述

第一行输入一个正整数n，代表矩阵大小。

接下来的n行，每行输入一个长度为n的01 串，用来表示矩阵。

输出描述

输出n行，第i行输出的i * i 完美矩形区域的数量。

示例 1

输入

输出

思路 && 代码

二维前缀和。枚举所有的边长 i 的正方形，判断正方形的和是否为 i\*i / 2 。

参考资料：【图解】二维前缀和（附模板代码 Python/Java/C++/Go/JS）

Java
Python

import java.util.*;

public class Main {

    static int[][] preSum;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            String line = sc.next();
            for (int j = 0; j < n; j++) {
                matrix[i][j] = line.charAt(j) - '0';
            }
        }
        // 计算前缀和
        preSum = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                preSum[i + 1][j + 1] = preSum[i + 1][j] + preSum[i][j + 1] - preSum[i][j] + matrix[i][j];
            }
        }

        for (int size = 1; size <= n; size++) {
            System.out.println(solve(n, matrix, size));
        }
        sc.close();
    }

    static int solve(int n, int[][] matrix, int size) {
        int cnt = 0;
        for (int r1 = 0; r1 <= n - size; r1++) {
            for (int c1 = 0; c1 <= n - size; c1++) {
                int r2 = r1 + size - 1;
                int c2 = c1 + size - 1;
                int cnt1 = query(r1, c1, r2, c2);
                if (cnt1 * 2 == size * size)
                    cnt++;
            }
        }
        return cnt;
    }

    /* 返回左上角在 (r1,c1) 右下角在 (r2,c2) 的子矩阵元素和 */
    static int query(int r1, int c1, int r2, int c2) {
        return preSum[r2 + 1][c2 + 1] - preSum[r2 + 1][c1] - preSum[r1][c2 + 1] + preSum[r1][c1];
    }

}

def query(r1: int, c1: int, r2: int, c2: int) -> int:
    return (
        pre_sum[r2 + 1][c2 + 1]
        - pre_sum[r2 + 1][c1]
        - pre_sum[r1][c2 + 1]
        + pre_sum[r1][c1]
    )


def solve(size: int) -> int:
    cnt = 0
    for r1 in range(n - size + 1):
        for c1 in range(n - size + 1):
            r2, c2 = r1 + size - 1, c1 + size - 1
            cnt1 = query(r1, c1, r2, c2)
            if cnt1 * 2 == size * size:
                cnt += 1
    return cnt


n = int(input())
matrix = []

for _ in range(n):
    matrix.append([int(x) for x in input()])

pre_sum = [[0] * (n + 1) for _ in range(n + 1)]
for i, row in enumerate(matrix):
    for j, x in enumerate(row):
        pre_sum[i + 1][j + 1] = (
            pre_sum[i + 1][j] + pre_sum[i][j + 1] - pre_sum[i][j] + x
        )

for size in range(1, n + 1):
    print(solve(size))

小美的区间删除

题目

小美拿到了一个大小为 n 的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有 k 个 0。小美想知道，一共有多少种不同的删除方案？

输入描述

第一行输入两个正整数n，k。第二行输入n个正整数a_i，代表小美拿到的数组。

1<=n,k<=10⁵

1<=a_i<=10⁹

输出描述

一个整数，代表删除的方案数。

示例 1

输入

5 2
2 5 3 4 20

输出

说明

第一个方案，删除[3]。
第二个方案，删除[4]。
第三个方案，删除[3,4]。
第四个方案，删除[2]。

思路 && 代码

乘积末尾0的数量取决于2和5的因子数量中较小的值。

假设数组中因子 2 的个数为 x，因子 5 的个数的个数为 y，构成末尾 0 的个数就是 min(x, y)。假设某区间因子 2 和 5 的个数分别为 x1 和 y1 ，那么如果删除该区间，剩余因子 2 的个数为 x-x1 ，剩余因子 5 的个数为 y-y1 ，如果 min(x-x1, y-y1) >= k，那么该区间可以删除。

技巧：先计算因子 2 和 5 的前缀和，然后枚举可以删除的区间。

Java
Python

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        solve(n, k, arr);
        sc.close();
    }

    static void solve(int n, int k, int[] arr) {
        int fac2TotalNum = 0, fac5TotalNum = 0;
        int[] pre2Sum = new int[n + 1], pre5Sum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int fac2 = getFactor(arr[i], 2);
            int fac5 = getFactor(arr[i], 5);
            fac2TotalNum += fac2;
            fac5TotalNum += fac5;
            pre2Sum[i + 1] = pre2Sum[i] + fac2;
            pre5Sum[i + 1] = pre5Sum[i] + fac5;
        }
        int cnt = 0;
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n) {
                int fac2 = pre2Sum[j + 1] - pre2Sum[i]; // [i, j] 之间的 2 的因子数
                int fac5 = pre5Sum[j + 1] - pre5Sum[i]; // [i, j] 之间的 5 的因子数
                int left2 = fac2TotalNum - fac2, left5 = fac5TotalNum - fac5;
                if (Math.min(left2, left5) >= k) // 当前 j 位置可以删除
                    j++;
                else
                    break;
            }
            cnt += Math.max(j - i, 0);
        }
        System.out.println(cnt);
    }

    static int getFactor(int num, int factor) {
        int cnt = 0;
        while (num != 0 && num % factor == 0) {
            cnt++;
            num /= factor;
        }
        return cnt;
    }

}

def getFactor(x: int, mod: int):
    cnt = 0
    while x != 0 and not x % mod:
        cnt += 1
        x //= mod
    return cnt


n, k = map(int, input().split())
arr = [int(x) for x in input().split()]

pre2_sum, pre5_sum = [0] * (n + 1), [0] * (n + 1)
fac2_total_num, fac5_total_num = 0, 0
for i, x in enumerate(arr):
    fac2, fac5 = getFactor(x, 2), getFactor(x, 5)
    fac2_total_num += fac2
    fac5_total_num += fac5
    pre2_sum[i + 1] = pre2_sum[i] + fac2
    pre5_sum[i + 1] = pre5_sum[i] + fac5


cnt, j = 0, 0
for i in range(n):
    while j < n:
        fac2 = pre2_sum[j + 1] - pre2_sum[i]
        fac5 = pre5_sum[j + 1] - pre5_sum[i]
        left2, left5 = fac2_total_num - fac2, fac5_total_num - fac5
        if min(left2, left5) >= k:
            cnt += 1
            j += 1
        else:
            break

print(cnt)

小美的朋友关系

题目

小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。

现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？

事件共有 2 种：

1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。

2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。

注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。

输入描述

第一行输入三个正整数n,m,q，代表总人数，初始的朋友关系数量，发生的事件数量。接下来的m行，每行输入两个正整数u,v，代表初始编号u的人和编号v的人是朋友关系。接下来的q行，每行输入三个正整数op,u,v，含义如题目描述所述。

1 < n < 10⁹

1< m,q < 10⁵

1< u,v < n

1< op < 2

保证至少存在一次查询操作

输出描述

对于每次 2 号操作，输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"No"。

示例 1

输入

输出

Yes
No
No

说明

第一次事件，1 号和 5 号本来就不是朋友，所以无事发生。

第二次事件是询问，1 号和 3 号可以通过 2 号的介绍认识。

第三次事件是询问，显然 1 号和 4 号无法互相认识。

第四次事件，1 号和 2 号淡忘了。

第五次事件，此时 1 号无法再经过 2 号和 3 号互相认识了。

思路 && 代码

并查集 + 逆向

简单的连接问题使用并查集求解是非常方便的，但是这里涉及到删除边的操作。

不妨做如下假设：

找出所有可能要删除的边，然后假设所有边都删除了，构建一个最终的并查集；
逆向遍历所有的 q 次操作，如果是查询，使用并查集直接查出即可；如果是删除，则往并查集添加边。

Java
Python

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Set<int[]> edge = new HashSet<>();
        Set<int[]> delEdge = new HashSet<>();
        int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            edge.add(new int[] { u, v });
        }
        List<int[]> ops = new ArrayList<>();
        for (int i = 0; i < q; i++) {
            int op = sc.nextInt(), u = sc.nextInt(), v = sc.nextInt();
            if (op == 1) {
                delEdge.add(new int[] { u, v });
                delEdge.add(new int[] { v, u });
            }
            ops.add(new int[] { op, u, v });
        }

        solve(n, edge, delEdge, ops);

        sc.close();
    }

    static void solve(int n, Set<int[]> edge, Set<int[]> delEdge, List<int[]> ops) {
        UnionFind uf = new UnionFind(n + 1);
        // 并查集建边（最终的并查集）
        for (int[] e : edge) {
            boolean flag = false;
            for (int[] de : delEdge) {
                if (e[0] == de[0] && e[1] == de[1]) {
                    flag = true;
                    break;
                }
            }
            if (flag)
                continue;
            uf.join(e[0], e[1]);
        }

        // 倒序遍历指令
        int q = ops.size();
        List<String> ans = new ArrayList<>();
        for (int i = q - 1; i >= 0; i--) {
            int[] op = ops.get(i);
            int u = op[1], v = op[2];
            if (op[0] == 1) {
                // 加边
                uf.join(u, v);
            } else {
                if (uf.isSame(u, v)) {
                    ans.add("Yes");
                } else {
                    ans.add("No");
                }
            }
        }
        for (int i = ans.size() - 1; i >= 0; i--) {
            System.out.println(ans.get(i));
        }
    }

}

class UnionFind {
    int[] father;
    int n = 1005;

    public UnionFind() {
        this.father = new int[n];
        init();
    }

    public UnionFind(int n) {
        this.n = n;
        this.father = new int[n];
        init();
    }

    /**
     * 并查集初始化
     */
    public void init() {
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }

    /**
     * 寻找根节点（路径压缩）
     * 
     * @param u 节点
     * @return u 的根节点
     */
    public int find(int u) {
        if (u == father[u])
            return u;
        else
            return father[u] = find(father[u]);
    }

    /**
     * 判断u和v是否能找到同一个根节点
     * 
     * @param u u 节点
     * @param v v 节点
     * @return u v 是否同根
     */
    public boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    /**
     * 将 v -> u 这条边加入并查集
     * 
     * @param u u 节点
     * @param v v 节点
     */
    public void join(int u, int v) {
        // 寻根
        u = find(u);
        v = find(v);
        // 若根相同，说明在同一个集合内，不用将两个节点相连，直接返回
        if (u == v)
            return;
        father[v] = u;
    }

}

class UnionFind:
    def __init__(self, n=1005):
        self.n = n
        self.father = [i for i in range(n)]

    def find(self, u: int):
        if u == self.father[u]:
            return u
        else:
            self.father[u] = self.find(self.father[u])
            return self.father[u]

    def isSame(self, u: int, v: int):
        u = self.find(u)
        v = self.find(v)
        return u == v

    def join(self, u: int, v: int):
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        self.father[v] = u


def solve(n: int, edge: list, delEdge: list, ops: list) -> None:
    uf = UnionFind(n + 1)
    for e in edge:
        flag = False
        for de in delEdge:
            if e[0] == de[0] and e[1] == de[1]:
                flag = True
                break
        if flag:
            continue
        uf.join(e[0], e[1])

    ans = []
    for op in reversed(ops):
        u = op[1]
        v = op[2]
        if op[0] == 1:
            uf.join(u, v)
        else:
            if uf.isSame(u, v):
                ans.append("Yes")
            else:
                ans.append("No")

    for a in reversed(ans):
        print(a)


n, m, q = map(int, input().split())
edge, delEdge, ops = [], [], []
for _ in range(m):
    u, v = map(int, input().split())
    edge.append((u, v))
for _ in range(q):
    op, u, v = map(int, input().split())
    if op == 1:
        delEdge.append((u, v))
        delEdge.append((v, u))
    ops.append((op, u, v))

solve(n, edge, delEdge, ops)