团子2025.03.15题目集

题目一：神秘解密器

1️⃣：使用字符串模拟，按照规则处理每个字符

2️⃣：需要记录上一步操作，以便处理'Z'撤销操作

3️⃣：时间复杂度 ，空间复杂度

难度：简单

题目二：倍数关系统计

1️⃣：利用整除分块技术优化求和过程

2️⃣：对于每个 ，计算区间 中是 倍数的数字个数

3️⃣：时间复杂度 ，远优于暴力枚举的

难度：中等

题目三：最小权值生成树

1️⃣：使用扩展欧几里得算法和模逆元计算方程解的个数

2️⃣：构建图并使用并查集找出最大连通块

3️⃣：应用 Kruskal 算法求解最小生成树

难度：困难

01. 神秘解密器

题目内容

小基发现了一个古老的解密装置，这个装置可以将一段加密字符串 转换成原始信息 。初始时，原始信息 为空字符串，解密装置会按照以下规则逐个处理加密字符串中的每个字符 ：

• 如果当前字符是 ''（保证在整个字符串中至多出现一次），则将当前的原始信息 反转；
• 如果当前字符是 ''（保证在整个字符串中至多出现一次），则撤销上一步操作：
  • 如果上一步是 ''，则取消反转；
  • 如果上一步是添加其他字符，则删除这个字符；
  • 如果上一步为空（即这是第一个操作），则跳过这一操作；
• 对于其他任何字符，直接将其添加到原始信息 的末尾。

小基想知道，给定一个加密字符串 ，解密后得到的原始信息 是什么。

输入描述

第一行输入一个整数 ，表示测试用例的数量。 接下来的 行，每行输入一个字符串 ，表示加密字符串。 保证单个测试文件中所有字符串的长度之和不超过 。

输出描述

对于每个测试用例，输出一行，表示解密后得到的原始信息 。数据保证解密后的字符串长度不为 。

样例1

输入：

2
meRDZ
DameDame

输出：

em
DameDame

解释：

1. 样例1解密过程：

   • 添加'm'，t="m"
   • 添加'e'，t="me"
   • 遇到'R'，反转字符串，t="em"
   • 添加'D'，t="emD"
   • 遇到'Z'，撤销上一步，t="em"

2. 样例2解密过程：

   • 直接将所有字符添加到t中，没有特殊操作，t="DameDame"

题解

这道题目要求模拟一个字符串解密过程，按照给定的规则处理每个字符。

解题思路很直接：按顺序处理加密字符串中的每个字符，并根据规则更新原始信息 。关键是要正确处理 'R' 和 'Z' 这两个特殊字符。

为了处理 'Z' 撤销操作，需要记录上一步的操作类型。可以使用一个变量来标记上一步是什么操作：

• 如果上一步是添加字符，记录添加的是哪个字符
• 如果上一步是反转操作，标记为特殊值（如 'R'）
• 如果没有上一步操作，标记为空

具体实现步骤：

1. 初始化原始信息 为空字符串
2. 初始化上一步操作 prev 为空
3. 遍历加密字符串 中的每个字符 ：
   • 如果 是 'R'，反转 ，并将 prev 设为 'R'
   • 如果 是 'Z'，根据 prev 撤销上一步操作：
     • 如果 prev 是 'R'，再次反转
     • 如果 prev 是其他字符，从 末尾删除该字符
     • 如果 prev 为空，不做任何操作
     • 将 prev 设为空
   • 对于其他字符，将其添加到 末尾，并将 prev 设为该字符
4. 返回最终的原始信息

时间复杂度：，其中 是加密字符串的长度。在最坏情况下，需要处理每个字符，并可能需要反转字符串（反转操作的时间复杂度也是 ）。 空间复杂度：，用于存储原始信息 。

三语言参考代码

• Cpp

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string solve(const string& s) {
    string res;  // 原始信息
    char prev = 0;  // 记录上一步操作，0表示无操作
    
    for (char ch : s) {
        if (ch == 'R') {
            // 反转字符串
            reverse(res.begin(), res.end());
            prev = 'R';
        } else if (ch == 'Z') {
            // 撤销上一步操作
            if (prev == 'R') {
                // 如果上一步是反转，再次反转恢复
                reverse(res.begin(), res.end());
            } else if (prev != 0) {
                // 如果上一步是添加字符，删除最后一个字符
                if (!res.empty()) {
                    res.pop_back();
                }
            }
            // 上一步操作被撤销，重置prev
            prev = 0;
        } else {
            // 添加字符到末尾
            res.push_back(ch);
            prev = ch;
        }
    }
    
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    while (n--) {
        string s;
        cin >> s;
        cout << solve(s) << endl;
    }
    
    return 0;
}

• Python

import sys
input_str = lambda:sys.stdin.readline().strip()

def solve(s):
    buf = []  # 使用列表存储字符，方便操作
    prev = None  # 记录上一步操作
    
    for ch in s:
        if ch == 'R':
            # 反转字符串
            buf.reverse()
            prev = 'R'
        elif ch == 'Z':
            # 撤销上一步操作
            if prev == 'R':
                # 如果上一步是反转，再次反转恢复
                buf.reverse()
            elif prev is not None:
                # 如果上一步是添加字符，删除最后一个字符
                if buf:  # 确保buf不为空
                    buf.pop()
            # 上一步操作被撤销，重置prev
            prev = None
        else:
            # 添加字符到末尾
            buf.append(ch)
            prev = ch
    
    return ''.join(buf)

def main():
    t = int(input_str())
    for _ in range(t):
        s = input_str()
        print(solve(s))

if __name__ == "__main__":
    main()

• Java

import java.util.Scanner;

public class Main {
    public static String solveStr(String s) {
        StringBuilder result = new StringBuilder();  // 原始信息
        Character prevOp = null;  // 记录上一步操作
        
        for (int i = 0; i < s.length(); i++) {
            char currCh = s.charAt(i);
            
            if (currCh == 'R') {
                // 反转字符串
                result.reverse();
                prevOp = 'R';
            } else if (currCh == 'Z') {
                // 撤销上一步操作
                if (prevOp != null) {
                    if (prevOp == 'R') {
                        // 如果上一步是反转，再次反转恢复
                        result.reverse();
                    } else {
                        // 如果上一步是添加字符，删除最后一个字符
                        if (result.length() > 0) {
                            result.deleteCharAt(result.length() - 1);
                        }
                    }
                }
                // 上一步操作被撤销，重置prevOp
                prevOp = null;
            } else {
                // 添加字符到末尾
                result.append(currCh);
                prevOp = currCh;
            }
        }
        
        return result.toString();
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testNum = scanner.nextInt();
        scanner.nextLine();  // 消耗换行符
        
        for (int i = 0; i < testNum; i++) {
            String inputS = scanner.nextLine();
            System.out.println(solveStr(inputS));
        }
        
        scanner.close();
    }
}

02. 倍数关系统计

题目内容

小柯正在研究一种特殊的数学关系。她定义了一个函数 ，规则如下：

• 如果 是 的倍数，则
• 否则

现在，小柯想要计算在给定范围内所有数对的函数值之和，即：

请你帮她解决这个问题。

输入描述

一行包含四个正整数 ，用空格分隔。

输出描述

一个整数，表示所有满足条件的数对函数值之和。

样例1

输入：

3 4 1 2

输出：

3

解释： 需要计算的数对有：(3,1), (3,2), (4,1), (4,2)

• ，因为 3 是 1 的倍数
• ，因为 3 不是 2 的倍数
• ，因为 4 是 1 的倍数
• ，因为 4 是 2 的倍数 所以总和为

数据范围

• 
• 

题解

这道题目要求计算在给定范围内所有数对的函数值之和。函数 的定义是：如果 是 的倍数，则值为 1，否则为 0。

暴力枚举所有数对并计算函数值是不可行的，因为数据范围高达 ，会导致时间复杂度为 ，这显然会超时。

关键观察是：对于固定的 ，可以快速计算出区间 中有多少个数是 的倍数。

具体来说，对于任意 ，区间 中 的倍数的个数为：

其中 表示不超过 的最大整数（向下取整）。

这样，可以遍历 从 到 ，对每个 计算上述公式，然后将所有结果相加。

但是，直接遍历 的时间复杂度仍然是 ，当 很大时仍然会超时。可以使用整除分块技术进一步优化。

整除分块的核心思想是：对于函数 ，当 变化时，函数值的变化是有规律的。具体来说，当 增大时， 的值会减小或保持不变。而且，对于连续的一段 值， 的值可能是相同的。

利用这一特性，可以将 的范围分成若干块，每块内 和 的值保持不变。这样，就可以一次性处理一整块，而不需要逐个计算。

具体算法步骤：

1. 初始化答案 ans = 0
2. 从 开始遍历：
   • 计算 和
   • 计算 ，这是区间 中 的倍数的个数
   • 找出最大的 ，使得对于所有 ， 和 的值保持不变
   • 将 加到答案中
   • 更新 ，继续遍历
3. 返回最终答案

这种方法的时间复杂度为 ，远优于暴力枚举的方法。

三语言参考代码

• Cpp

#include <iostream>
#include <algorithm>
using namespace std;

long long calc(long long a, long long b, long long c, long long d) {
    long long ret = 0;
    long long idx = c;
    
    while (idx <= d) {
        // 计算区间[a, b]中idx的倍数的个数
        long long v1 = b / idx;
        long long v2 = (a - 1) / idx;
        long long gap = v1 - v2;
        
        // 找出最大的idx_end，使得对于所有idx <= idx_end，
        // floor(b/idx)和floor((a-1)/idx)的值保持不变
        long long e1 = (v1 == 0) ? d : b / v1;
        long long e2 = (v2 == 0) ? d : (a - 1) / v2;
        long long idx_end = min({d, e1, e2});
        
        // 将gap * (idx_end - idx + 1)加到答案中
        ret += gap * (idx_end - idx + 1);
        
        // 更新idx，继续遍历
        idx = idx_end + 1;
    }
    
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    
    cout << calc(a, b, c, d) << "\n";
    
    return 0;
}

• Python

import sys
input_str = lambda:sys.stdin.readline().strip()

def calc(a, b, c, d):
    res = 0
    idx = c
    
    while idx <= d:
        # 计算区间[a, b]中idx的倍数的个数
        v1 = b // idx
        v2 = (a - 1) // idx
        gap = v1 - v2
        
        # 找出最大的idx_end，使得对于所有idx <= idx_end，
        # floor(b/idx)和floor((a-1)/idx)的值保持不变
        e1 = d if v1 == 0 else b // v1
        e2 = d if v2 == 0 else (a - 1) // v2
        idx_end = min(d, e1, e2)
        
        # 将gap * (idx_end - idx + 1)加到答案中
        res += gap * (idx_end - idx + 1)
        
        # 更新idx，继续遍历
        idx = idx_end + 1
    
    return res

def main():
    a, b, c, d = map(int, input_str().split())
    print(calc(a, b, c, d))

if __name__ == "__main__":
    main()

• Java

import java.util.Scanner;

public class Main {
    public static long calcSum(long left1, long right1, long left2, long right2) {
        long result = 0;
        long currJ = left2;
        
        while (currJ <= right2) {
            // 计算区间[left1, right1]中currJ的倍数的个数
            long val1 = right1 / currJ;
            long val2 = (left1 - 1) / currJ;
            long diff = val1 - val2;
            
            // 找出最大的maxJ，使得对于所有currJ <= maxJ，
            // floor(right1/currJ)和floor((left1-1)/currJ)的值保持不变
            long end1 = (val1 == 0) ? right2 : right1 / val1;
            long end2 = (val2 == 0) ? right2 : (left1 - 1) / val2;
            long maxJ = Math.min(right2, Math.min(end1, end2));
            
            // 将diff * (maxJ - currJ + 1)加到答案中
            result += diff * (maxJ - currJ + 1);
            
            // 更新currJ，继续遍历
            currJ = maxJ + 1;
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        Scanner sc