🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员
✨ 本系列打算持续跟新携程近期的春秋招笔试题汇总～
💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。
文章目录
- 🥇 01.可爱的棋盘
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 数据范围
- 题解
- 参考代码
- 🥈 02.最大数字串
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 数据范围
- 题解
- 参考代码
- 🥉 03.区间乘积模 6
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 数据范围
- 题解
- 参考代码
- 🎖 04.卢小姐的树上游戏
- 题目描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例输入
- 样例输出
- 数据范围
- 题解
- 参考代码
- 写在最后
- 📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。
🥇 01.可爱的棋盘
问题描述
LYA 小姐最近迷上了国际象棋，但普通的国际象棋棋盘她已经玩腻了。为了增加趣味性，她想设计一种由 c 1 c_1 c1 和 c 2 c_2 c2 两种字符组成的 n n n 行 m m m 列的字符矩阵作为棋盘，并且希望相邻的字符都不相同（定义上下、左右都是相邻的）。你能帮帮 LYA 小姐设计这样一个棋盘吗？
输入格式
第一行输入两个正整数 n n n 和 m m m，代表矩阵的行数和列数。
第二行输入两个字符 c 1 c_1 c1 和 c 2 c_2 c2。
输出格式
输出 n n n 行，每行 m m m 个字符，表示矩阵。有多解时输出任意解即可。
样例输入
3 4
0 ?
样例输出
0?0?
?0?0
0?0?
数据范围
1 ≤ n , m ≤ 1000 1 \le n, m \le 1000 1≤n,m≤1000
c 1 c_1 c1 和 c 2 c_2 c2 为 ASCII 可见字符
题解
本题的思路是按照棋盘的规则，依次填充每个位置的字符。我们可以发现，对于 ( i , j ) (i, j) (i,j) 位置的字符，如果 i + j i+j i+j 的奇偶性为奇数，就填充 c 1 c_1 c1，否则填充 c 2 c_2 c2，这样可以保证相邻的字符一定不同。按照这个规则依次填充整个矩阵即可得到答案。
时间复杂度 O ( n m ) O(nm) O(nm)，空间复杂度 O ( n m ) O(nm) O(nm)。
参考代码
- 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 先生有一个很长的数字串，他希望从中截取一段长度为 k k k 的子串（可以包含前导零），使得截取出的这个数尽可能大。你能帮帮 A 先生找出这个最大的数吗？为了避免数字太大，你只需要输出这个数模 p p p 的值。
输入格式
第一行输入一个字符串，表示 A 先生的数字串。
第二行输入两个正整数 k k k 和 p p p，用空格隔开。
输出格式
输出一个整数，表示最大数模 p p p 的值。
样例输入
12332
3 12
样例输出
8
数据范围
1 ≤ 字符串长度 ≤ 1 0 5 1 \le \text{字符串长度} \le 10^{5} 1≤字符串长度≤105
1 ≤ p ≤ 1 0 9 1 \le p \le 10^9 1≤p≤109
1 ≤ k ≤ log 10 ( 字符串长度 ) 1 \le k \le \log_{10}(\text{字符串长度}) 1≤k≤log10(字符串长度)
题解
这题建议直接上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)
其他题解待补充ing…
🥉 03.区间乘积模 6
问题描述
LYA 有一个长度为 n n n 的数组，她想知道对于给定的若干个区间，区间内所有元素的乘积模 6 6 6 的值是多少。你能帮帮她吗？
输入格式
第一行输入两个正整数 n n n 和 q q q，分别表示数组的长度以及询问的次数。
第二行输入 n n n 个正整数 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an，表示数组中的元素。
接下来的 q q q 行，每行输入两个正整数 l l l 和 r r r，表示一次询问的区间为第 l l l 个数到第 r r r 个数（包括第 l l l 和第 r r r 个数）。
输出格式
输出共 q q q 行，第 i i i 行表示第 i i i 次询问的结果。
样例输入
5 3
1 2 3 4 5
2 4
4 5
1 2
样例输出
0
2
2
数据范围
1 ≤ n , q ≤ 1 0 5 1 \le n, q \le 10^5 1≤n,q≤105
1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai≤109
1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1≤l≤r≤n
题解
这道题可以使用前缀和的思想来解决。可以预处理出每个前缀中 2 2 2、 3 3 3、 4 4 4、 5 5 5 和 0 0 0 的个数，然后对于每次询问，可以通过前缀和的差值得到区间内每个数的个数，然后用快速幂计算出区间内所有数的乘积模 6 6 6 的结果。
用一个二维数组 s s s 来存储前缀和，其中 s [ i ] [ 0 ] s[i][0] s[i][0] 表示前 i i i 个数中 2 2 2 和 4 4 4 的个数之和， s [ i ] [ 1 ] s[i][1] s[i][1] 表示前 i i i 个数中 3 3 3 的个数， s [ i ] [ 2 ] s[i][2] s[i][2] 表示前 i i i 个数中 5 5 5 的个数， s [ i ] [ 3 ] s[i][3] s[i][3] 表示前 i i i 个数中 0 0 0 的个数。
对于每次询问 [ l , r ] [l, r] [l,r]，可以通过 s [ r ] [ j ] − s [ l − 1 ] [ j ] s[r][j] - s[l-1][j] s[r][j]−s[l−1][j] 得到区间内每个数的个数，然后用快速幂计算出区间内所有数的乘积模 6 6 6 的结果。需要注意的是，如果区间内存在 0 0 0，那么整个区间的乘积就是 0 0 0。
时间复杂度 O ( n + q log m ) O(n + q \log m) O(n+qlogm)，其中 m m m 表示数组中的最大值。空间复杂度 O ( n ) O(n) O(n)。
参考代码
- 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);
int n = scanner.nextInt();
int q = scanner.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextLong() % 6;
}
long[][] s = new long[n + 1][4];
for (int i = 0; i < n; i++) {
System.arraycopy(s[i], 0, s[i + 1], 0, 4);
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;
}
while (q-- > 0) {
int l = scanner.nextInt();
int r = scanner.nextInt();
long[] cnt = new long[4];
for (int j = 0; j < 4; j++) {
cnt[j] = s[r][j] - s[l - 1][j];
}
long 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);
System.out.println(t);
}
}
}
- Cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int qmi(int a, int b, int mod){
int res = 1 % mod;
while(b)
{
if(b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
signed main (){
int n, q; cin >> n >> q;
vector<int> a(n);
for(int i = 0; i < n; i ++) cin >> a[i], a[i] %= 6;
vector<vector<int>> s(n + 1, vector<int>(4));
for(int i = 0; i < n; i ++)
{
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;
}
while(q --)
{
int l, r; cin >> l >> r;
vector<int> cnt(4);
for(int j = 0; j < 4; j ++)
{
cnt[j] = s[r][j] - s[l - 1][j];
}
int 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);
cout << t << "\n";
}
return 0;
}
🎖 04.卢小姐的树上游戏
题目描述
卢小姐拿到了一棵 n n n 个节点的树，每个节点上都有一个数字（ 0 0 0 到 9 9 9 之间）。
现在卢小姐定义 f ( i ) f(i) f(i) 为：以 i i i 号节点为起点时，选择一条路径，使得路径上的数字拼接起来能被 3 3 3 整除的方案数。注意前导零也是合法的。
现在卢小姐希望你能帮她求出 f ( 1 ) f(1) f(1) 到 f ( n ) f(n) f(n) 的值。
输入格式
第一行包含一个正整数 n n n，表示树的节点数。
第二行包含 n n n 个整数，第 i i i 个数 a i a_i ai 表示 i i i 号节点上的数字。
接下来 n − 1 n-1 n−1 行，每行包含两个正整数 u u u 和 v v v，表示 u u u 号节点和 v v v 号节点之间有一条边。
输出格式
输出共 n n n 行，第 i i i 行输出 f ( i ) f(i) f(i) 的值。
样例输入
3
1 2 3
1 2
2 3
样例输出
2
1
2
样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
样例输出
1
3
2
1
0
数据范围
- 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105
- 0 ≤ a i ≤ 9 0 \leq a_i \leq 9 0≤ai≤9
题解
考虑对这棵树进行 DFS。设 c n t u [ i ] cnt_u[i] cntu[i] 表示以 u u u 为根的子树中，从 u u u 出发，路径上的数字拼接起来对 3 3 3 取模为 i i i 的方案数。
我们可以通过 DFS 求出每个节点的 c n t cnt cnt 数组。对于节点 u u u，初始时 c n t u [ a [ u ] m o d 3 ] = 1 cnt_u[a[u] \bmod 3] = 1 cntu[a[u]mod3]=1，然后对于 u u u 的每个子节点 v v v，我们已经求出了 c n t v cnt_v cntv，则有：
c n t u [ ( j + a [ u ] ) m o d 3 ] + = c n t v [ j ] , j = 0 , 1 , 2 cnt_u[(j + a[u]) \bmod 3] += cnt_v[j], \quad j = 0, 1, 2 cntu[(j+a[u])mod3]+=cntv[j],j=0,1,2
这样，我们就可以求出每个节点的 c n t cnt cnt 数组。而 f ( i ) f(i) f(i) 就等于 c n t i [ 0 ] cnt_i[0] cnti[0]。
但是，这样做有一个问题：当我们求 f ( i ) f(i) f(i) 时， c n t cnt cnt 数组已经被子节点的贡献所影响，不再是以 i i i 为根的子树的情况了。
为了解决这个问题，我们可以再进行一次 DFS。设 t u [ i ] t_u[i] tu[i] 表示除了以 u u u 为根的子树之外，其他部分对 u u u 的 c n t cnt cnt 数组的贡献。在第二次 DFS 中，对于节点 u u u 的子节点 v v v，我们先计算出 t v t_v tv：
t v [ i ] = c n t u [ i ] − c n t v [ ( i − a [ u ] + 3 ) m o d 3 ] , i = 0 , 1 , 2 t_v[i] = cnt_u[i] - cnt_v[(i - a[u] + 3) \bmod 3], \quad i = 0, 1, 2 tv[i]=cntu[i]−cntv[(i−a[u]+3)mod3],i=0,1,2
然后，我们可以更新 c n t v cnt_v cntv：
c n t v [ ( j + a [ v ] ) m o d 3 ] + = t v [ j ] , j = 0 , 1 , 2 cnt_v[(j + a[v]) \bmod 3] += t_v[j], \quad j = 0, 1, 2 cntv[(j+a[v])mod3]+=tv[j],j=0,1,2
这样， c n t v cnt_v cntv 就变成了以 v v v 为根的子树的情况，我们就可以求出 f ( v ) = c n t v [ 0 ] f(v) = cnt_v[0] f(v)=cntv[0]。
总时间复杂度 O ( n ) O(n) O(n)。
参考代码
- Python
n = int(input())
a = [0] + list(map(int, input().split()))
a = [x % 3 for x in a]
g = [[] for _ in range(n+1)]
for _ in range(n-1):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
mp = {}
def dfs1(u, pre):
cnt = [0] * 3
cnt[a[u]] = 1
for i in g[u]:
if i != pre:
t = dfs1(i, u)
for j in range(3):
cnt[(j + a[u]) % 3] += t[j]
mp[u] = cnt
return cnt
dfs1(1, -1)
f = [0] * (n+1)
f[1] = mp[1][0]
def dfs2(u, pre):
cur = a[u]
for i in g[u]:
if i != pre:
t, k, z = [0] * 3, [0] * 3, [0] * 3
for j in range(3):
z[j] = mp[i][(j - cur + 3) % 3]
t[j] = mp[u][j] - z[j]
k[(j + a[i]) % 3] = t[j]
for j in range(3):
mp[i][j] += k[j]
f[i] = mp[i][0]
dfs2(i, u)
dfs2(1, -1)
for i in range(1, n+1):
print(f[i])
- Java
import java.util.*;
public class Main {
static List<List<Integer>> tree;
static int[] a;
static int n;
static long[] f;
static int[][] dp;
static Map<Integer, int[]> mp = new HashMap<>();
private static int[] dfs(int node, int parent) {
int[] cnt = new int[3];
cnt[a[node] % 3] = 1;
for (int child : tree.get(node)) {
if (child != parent) {
int[] t = dfs(child, node);
for (int j = 0; j < 3; j++) {
cnt[(j + a[node] % 3) % 3] += t[j];
}
}
}
mp.put(node, cnt);
return cnt;
}
private static void reroot(int node, int parent) {
f[node] = mp.get(node)[0];
for (int child : tree.get(node)) {
if (child != parent) {
int[] t = new int[3];
int[] k = new int[3];
int[] z = new int[3];
int[] childCnt = mp.get(child);
int[] nodeCnt = mp.get(node);
for (int j = 0; j < 3; j++) {
z[j] = childCnt[(j - a[node] + 3) % 3];
t[j] = nodeCnt[j] - z[j];
k[(j + a[child] % 3) % 3] = t[j];
}
for (int j = 0; j < 3; j++) {
childCnt[j] += k[j];
}
mp.put(child, childCnt);
reroot(child, node);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
tree = new ArrayList<>();
a = new int[n + 1];
f = new long[n + 1];
dp = new int[n + 1][3];
for (int i = 0; i <= n; i++) {
tree.add(new ArrayList<>());
}
for (int i = 1; i <= n; i++) {
a[i] = scanner.nextInt() % 3;
}
for (int i = 0; i < n - 1; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
tree.get(u).add(v);
tree.get(v).add(u);
}
dfs(1, -1);
reroot(1, -1);
for (int i = 1; i <= n; i++) {
System.out.println(f[i]);
}
scanner.close();
}
}
- Cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
int a[N];
vector<int> g[N];
unordered_map<int, vector<int>> mp;
int f[N];
vector<int> dfs1(int u, int pre) {
vector<int> cnt(3);
cnt[a[u]] = 1;
for (int i : g[u]) {
if (i != pre) {
auto t = dfs1(i, u);
for (int j = 0; j < 3; j++) {
cnt[(j + a[u]) % 3] += t[j];
}
}
}
mp[u] = cnt;
return cnt;
}
void dfs2(int u, int pre) {
int cur = a[u];
for (int i : g[u]) {
if (i != pre) {
vector<int> t(3), k(3), z(3);
for (int j = 0; j < 3; j++) {
z[j] = mp[i][(j - cur + 3) % 3];
t[j] = mp[u][j] - z[j];
k[(j + a[i]) % 3] = t[j];
}
for (int j = 0; j < 3; j++) {
mp[i][j] += k[j];
}
f[i] = mp[i][0];
dfs2(i, u);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i] %= 3;
}
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1, -1);
f[1] = mp[1][0];
dfs2(1, -1);
for (int i = 1; i <= n; i++) {
printf("%d\n", f[i]);
}
return 0;
}
写在最后
📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。
![[redis] redis为什么快](https://img-blog.csdnimg.cn/img_convert/e080a9d78b36a00810820ff9165eff95.png)
