小红书2023春招笔试

（Author：DH）

第一题

​ 小明学会了一种加密方式，他定义suc(x)为x再字母表中的后继，例如a的后继为b，b的后继为c…（即按字母表的顺序后一个）。特别的，z的后继为a。对于一个原字符串S，将其中每个字母x都替换成其三重后继，即suc(suc(suc(x)))的字母，即完成了加密。

​ 例如，abc加密后变成了def

​ 现在小明知道一个加密后的字符串S’，想请你找到他的原串S

输入描述

第一行一个正整数N，表示加密后的字符串长度
接下来一行是长度为N的字符串S‘，含义如上。保证仅包含小写英文字母。
对于所有数据：1<=N<=50000

输出描述

一行，一个长度为N的字符串S，表示答案

样例输入

3
def

样例输出

abc

题解

简单模拟即可

第二题

​ 在算法中，有各种各样的排序算法，例如归并排序，冒泡排序，快速排序等等。本题中，我们会使用一种新的排序算法：K排序。

​ K排序算法描述如下：首先，算法需要按照某种规则选择该数列上至多K个位置，将其对应的数抽出来，其他的数都往左对齐，之后这K个数排好序之后依次放在原数列末尾。以上过程算作一次操作。

​ 例如，对于数列[1,3,5,4,2]，当K=2时可以选择数字5和4，之后数列变成[1,3,2,4,5]。

​ 你的任务是：对于给定的序列，你需要计算出最少需要多少次上述操作，使得整个数列从小到大排好序？

输入描述

第一行一个正整数T，表示有T组数据。
对于每一组数据，第一行输入两个正整数n，k；第二行输入n个数a1,a2,...,an。该序列是一个1~n的排列。
对于所有数据，1<=k,n<=10^5,1<=ai<=n,ai!=aj,1<=T<=5

输出描述

对于每一组数据，输出一行一个整数，表示答案。

样例输入

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

样例输出

0
2

提示

样例解释
第一组数据，原数列已经排好序，则无需进行任何操作；
第二组数据，操作如下：
{1,3,5,4,2} -> {1,5,4,2,3}
{1,5,4,2,3} -> {1,2,3,4,5}

题解

本题等价于顺序找到一个从1开始每次增加1的最长递增序列

第三题

给出一个数组，你需要求出按顺序对其进行一系列区间操作后最终所得的数组。

操作有三种：

1.将下标在L到R之间的元素全部或上X；

2.将下标在L到R之间的元素全部与上X；

3.将下标在L到R之间的元素全部设为X；

输入描述

第一行有一个正整数N(1<=N<=100000)，代表数组的长度。
第二行有N个非负整数，范围在0到2^20-1之间，代表数组中的元素。
第三行有一个正整数M(1<=M<=100000)，代表操作次数。
第四行有M个正整数，代表M次操作中的区间左端点L。
第五行有M个正整数，代表M次操作中的区间右端点R。
第六行是一个长度为M的字符串，'|'代表操作1，'&'代表操作2，'='代表操作3.
第七行有M个正整数，代表M次操作中的参数X。

输出描述

在一行中输出N个数，代表所有操作按顺序完成后最终所得的数组。

样例输入

4
5 4 7 4
4 
1 2 3 2
4 3 4 2
= | & =
8 3 6 2

样例输出

8 2 2 0

题解

本题难度超纲了，正确做法是把每个数分解为二进制01串，然后每一位利用线段树进行区间更改操作（需要20个线段树）

可以利用暴力方法，简单的按照题目进行模拟，可以通过83%的样例。