【春招笔试】2024-05-06-携程-三语言题解

✨ 笔试合集传送们

🧷春秋招笔试合集

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新携程近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试

👏 感谢大家的订阅➕ 和 喜欢💗

🥇 01.可爱的棋盘

问题描述

LYA 小姐最近迷上了国际象棋，但普通的国际象棋棋盘她已经玩腻了。为了增加趣味性，她想设计一种由 和 两种字符组成的 行 列的字符矩阵作为棋盘，并且希望相邻的字符都不相同（定义上下、左右都是相邻的）。你能帮帮 LYA 小姐设计这样一个棋盘吗？

输入格式

第一行输入两个正整数 和 ，代表矩阵的行数和列数。

第二行输入两个字符 和 。

输出格式

输出 行，每行 个字符，表示矩阵。有多解时输出任意解即可。

样例输入

3 4
0 ?

样例输出

0?0?
?0?0
0?0?

数据范围

和 为 ASCII 可见字符

题解

本题的思路是按照棋盘的规则，依次填充每个位置的字符。我们可以发现，对于 位置的字符，如果 的奇偶性为奇数，就填充 ，否则填充 ，这样可以保证相邻的字符一定不同。按照这个规则依次填充整个矩阵即可得到答案。

时间复杂度 ，空间复杂度 。

参考代码

• Python

n, m = map(int, input().split())
c1, c2 = input().split()

for i in range(n):
    s = ""
    for j in range(m):
        if (i + j) % 2 == 1:
            s += c1
        else:
            s += c2
    print(s)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char c1 = sc.next().charAt(0);
        char c2 = sc.next().charAt(0);
        
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < m; j++) {
                if ((i + j) % 2 == 1) {
                    sb.append(c1);
                } else {
                    sb.append(c2);
                }
            }
            System.out.println(sb.toString());
        }
    }
}

• Cpp

#include <iostream>
using namespace std;

int main() {
    int n, m;
    char c1, c2;
    cin >> n >> m >> c1 >> c2;
    
    for (int i = 0; i < n; i++) {
        string row = "";
        for (int j = 0; j < m; j++) {
            if ((i + j) % 2 == 1) {
                row += c1;
            } else {
                row += c2;
            }
        }
        cout << row << endl;
    }
    
    return 0;
}

🥈 02.最大数字串

问题描述

A 先生有一个很长的数字串，他希望从中截取一段长度为 的子串（可以包含前导零），使得截取出的这个数尽可能大。你能帮帮 A 先生找出这个最大的数吗？为了避免数字太大，你只需要输出这个数模 的值。

输入格式

第一行输入一个字符串，表示 A 先生的数字串。

第二行输入两个正整数 和 ，用空格隔开。

输出格式

输出一个整数，表示最大数模 的值。

样例输入

12332
3 12

样例输出

8

数据范围

题解

这题建议直接上python，内置大整数模拟就很舒服，其他语言题解待补充ing...

跟新：其他语言可以采用手写高精度取模

参考代码

• Python

s = input()
k, p = map(int, input().split())
num = int(s[:k])
ans = num
n = len(s)
pow10 = 10 ** (k - 1)

for i in range(k, n):
    num = (num % pow10) * 10 + int(s[i])
    ans = max(ans, num)

print(ans % p)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int k = scanner.nextInt();
        int p = scanner.nextInt();
        
        String cur = s.substring(0, k);
        int n = s.length();
        for (int i = k; i < n; i++) {
            String t = s.substring(i - k + 1, i + 1);
            if (t.compareTo(cur) > 0) {
                cur = t;
            }
        }
		// 高精度取模
        long sum = 0;
        for (int i = 0; i < k; i++) {
            sum = (sum * 10 + (cur.charAt(i) - '0')) % p;
        }
        
        System.out.println(sum);
    }
}

• Cpp

#include<bits/stdc++.h>

using namespace std;


int main (){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
	string s; cin >> s;
	int k, p; cin >> k >> p;
	string cur = s.substr(0, k);
	int n = s.size();
	for(int i = k; i < n; i ++)
	{
		string t = s.substr(i - k + 1, k);
		if(t > cur)
			cur = t;
	}	
	long long t = 0;
	// 高精度取模
	for(int i = 0; i < k; i ++)
		t = (t * 10 + cur[i] - '0') % p;
	cout << t << "\n";
    return 0;
}

🥉 03.区间乘积模 6

问题描述

LYA 有一个长度为 的数组，她想知道对于给定的若干个区间，区间内所有元素的乘积模 的值是多少。你能帮帮她吗？

输入格式

第一行输入两个正整数 和 ，分别表示数组的长度以及询问的次数。

第二行输入 个正整数 ，表示数组中的元素。

接下来的 行，每行输入两个正整数 和 ，表示一次询问的区间为第 个数到第 个数（包括第 和第 个数）。

输出格式

输出共 行，第 行表示第 次询问的结果。

样例输入

5 3
1 2 3 4 5
2 4
4 5
1 2

样例输出

0
2
2

数据范围

题解

这道题可以使用前缀和的思想来解决。可以预处理出每个前缀中 、、、 和 的个数，然后对于每次询问，可以通过前缀和的差值得到区间内每个数的个数，然后用快速幂计算出区间内所有数的乘积模 的结果。

用一个二维数组 来存储前缀和，其中 表示前 个数中 和 的个数之和， 表示前 个数中 的个数， 表示前 个数中 的个数， 表示前 个数中 的个数。

对于每次询问 ，可以通过 得到区间内每个数的个数，然后用快速幂计算出区间内所有数的乘积模 的结果。需要注意的是，如果区间内存在 ，那么整个区间的乘积就是 。

时间复杂度 ，其中 表示数组中的最大值。空间复杂度 。

参考代码

• Python

def qmi(a, b, mod):
    res = 1 % mod
    while b > 0:
        if b & 1 == 1:
            res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res

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

s = [[0] * 4 for _ in range(n + 1)]
for i in range(n):
    s[i + 1] = s[i][:]
    if a[i] == 2:
        s[i + 1][0] += 1
    if a[i] == 4:
        s[i + 1][0] += 2
    if a[i] == 3:
        s[i + 1][1] += 1
    if a[i] == 5:
        s[i + 1][2] += 1
    if a[i] == 0:
        s[i + 1][3] += 1

for _ in range(q):
    l, r = map(int, input().split())
    cnt = [s[r][j] - s[l - 1][j] for j in range(4)]
    t = qmi(2, cnt[0], 6)
    t = t * qmi(3, cnt[1], 6) % 6
    t = t * qmi(5, cnt[2], 6) % 6
    t = t * qmi(0, cnt[3], 6)
    print(t)

• Java

import java.util.Scanner;

public class Main {
    static long qmi(long a, long b, long mod) {
        long res = 1 % mod;
        while (b > 0) {
            if ((b & 1) == 1)
                res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in