💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍥 本次难度不大，大家要争取AK哦

1️⃣ 简单的统计二进制1的个数，

2️⃣ 思维+前缀和预处理，难度不大

3️⃣ 最短路模版的考查，用floyd/dijkstra都是OK滴～

🪙 01.神秘的字符变换 评测链接🔗

问题描述

LYA 是一位热爱密码学的高中生。一天，她发现了一种奇特的字符变换方法。这种方法是这样的：

给定一个只包含小写字母的字符串 。对于字符串中的每个字符，如果它的位置（从 1 开始计数）在二进制表示中有奇数个 1，就将该字符转换为对应的大写字母。

例如，对于字符串 "hello"：

• 第 1 个字符（h）的位置是 1，二进制是 1，有奇数个 1，所以变成 'H'。
• 第 2 个字符（e）的位置是 2，二进制是 10，有偶数个 1，保持小写。
• 第 3 个字符（l）的位置是 3，二进制是 11，有偶数个 1，保持小写。
• 第 4 个字符（l）的位置是 4，二进制是 100，有奇数个 1，所以变成 'L'。
• 第 5 个字符（o）的位置是 5，二进制是 101，有偶数个 1，保持小写。

变换后的字符串就变成了 "HelLo"。

LYA 觉得这种变换方法非常有趣，她想知道对于给定的字符串，变换后会是什么样子。你能帮她解决这个问题吗？

输入格式

第一行包含一个整数 ，表示测试用例的数量。

接下来 行，每行包含一个仅由小写字母组成的字符串 。

输出格式

对于每个测试用例，输出一行，表示经过变换后的字符串。

样例输入

1
abcdefg

样例输出

ABcDefG

样例输入

3
vwcvnwaomy
ovoxcfdtf
yynbve

样例输出

VWcVnwAOmy
OVoXcfDTf
YYnBve

数据范围

• 
• ，其中 表示字符串 的长度。

题解

按照题意模拟

简单的二进制转化，主要考查语法

参考代码

• Python

# 读取测试用例数量
T = int(input())

# 处理每个测试用例
for _ in range(T):
    # 读取输入的字符串
    s = input().strip()
    result = []
    
    # 遍历字符串中的每个字符
    for i, char in enumerate(s, start=1):
        # 如果位置的二进制表示中有奇数个1，则转换为大写
        if bin(i).count('1') % 2 == 1:
            result.append(char.upper())
        else:
            result.append(char)
    
    # 输出结果
    print(''.join(result))

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        scanner.nextLine();

        for (int i = 0; i < T; i++) {
            String s = scanner.nextLine();
            StringBuilder result = new StringBuilder();

            for (int j = 0; j < s.length(); j++) {
                int index = j + 1;
                if (Integer.bitCount(index) % 2 == 1) {
                    result.append(Character.toUpperCase(s.charAt(j)));
                } else {
                    result.append(s.charAt(j));
                }
            }

            System.out.println(result.toString());
        }

        scanner.close();
    }
}

• Cpp

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

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        string s;
        cin >> s;
        
        for (int i = 0; i < s.length(); ++i) {
            int index = i + 1;
            if (__builtin_popcount(index) % 2 == 1) {
                s[i] = toupper(s[i]);
            }
        }
        
        cout << s << endl;
    }
    
    return 0;
}

🍄 02.LYA的魔法花园 评测链接🔗

问题描述

LYA是一位热爱园艺的魔法师。她的花园里种植了各种奇妙的魔法植物，每株植物都有其独特的魔力值。一天，LYA决定对她的花园进行一些魔法实验。

花园里有 株植物，从左到右排列，每株植物的初始魔力值用一个整数表示。LYA计划进行 次魔法实验，每次实验她会选择两个区间 和 ，并按以下顺序施展魔法：

1. 对区间 内的所有植物施加"魔力倍增"咒语，使它们的魔力值翻倍。
2. 对区间 内的所有植物再次施加"魔力倍增"咒语，使它们的魔力值翻倍。

LYA想知道每次实验后，整个花园的总魔力值是多少。请注意，每次实验都是独立的，实验结束后花园会恢复到初始状态。

输入格式

第一行包含两个整数 和 ，分别表示植物的数量和魔法实验的次数。

第二行包含 个整数 ，表示每株植物的初始魔力值。

接下来的 行，每行包含四个整数 、、 和 ，表示每次魔法实验中选择的两个区间。

输出格式

输出包含 行，每行一个整数，表示每次魔法实验后花园的总魔力值。

样例输入

3 2
1 2 1
1 2 2 3
1 1 2 2

样例输出

12
7

数据范围

• 
• 
• 
• 

题解

前缀和预处理

首先，要理解每次魔法实验的影响：

1. 区间 内的植物魔力值翻倍
2. 区间 内的植物魔力值翻倍

实际上，可以将整个过程分解为以下几部分：

1. 原始总魔力值
2. 区间 的额外贡献（原值）
3. 区间 的额外贡献（原值）
4. 两个区间重叠部分的额外贡献（原值）

使用前缀和可以快速计算任意区间的和。预处理出前缀和数组，然后对于每次查询，可以在 时间内得到所需的区间和。

计算过程如下：

1. 计算原始总魔力值
2. 计算
3. 计算
4. 计算重叠部分 （如果存在）
5. 最终结果 =

这种方法的时间复杂度是 ，其中 用于预处理前缀和， 用于处理所有查询。这个复杂度对于给定的数据范围（）是完全可以接受的。

参考代码

• Python

# 读取输入
n, q = map(int, input().split())
a = [0] + list(map(int, input().split()))

# 计算前缀和
prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
    prefix_sum[i] = prefix_sum[i-1] + a[i]

S = prefix_sum[n]

# 处理查询
for _ in range(q):
    l1, r1, l2, r2 = map(int, input().split())
    
    sum1 = prefix_sum[r1] - prefix_sum[l1 - 1]
    sum2 = prefix_sum[r2] - prefix_sum[l2 - 1]
    
    overlap_l = max(l1, l2)
    overlap_r = min(r1, r2)
    sum_overlap = 0
    if overlap_l <= overlap_r:
        sum_overlap = prefix_sum[overlap_r] - prefix_sum[overlap_l - 1]
    
    total = S + sum1 + sum2 + sum_overlap
    print(total)

• Java

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        B