第一题：加密
小明学会了一种加密方式。他定义suc(x)为x在字母表中的后继，例如a的后继为b，b的后继为c… （即按字母表的顺序后一个）。特别的，z的后继为a。对于一个原字符串S，将其中每个字母x都替换成其三重后继，即suc(suc(suc(x)))的字母，即完成了加密。例如，abc加密后变成def （suc(suc(suc(a)))=d suc(suc(suc(b)))=e, suc(suc(suc©))=f）。 现在小明知道一个加密后的字符串S’，想请你找出他的原串S。
输入数据
3
def
输出数据
abc
直接模拟完成
Class solution{
public static String findString(String s){
int n = s.length();
String ans = "";
for(int i = 0; i < n; i ++){
if(s.charAt(i)=='a' || s.charAt(i)=='b' || s.charAt(i)=='c'){
ans += (char) (s.charAt(i) - 3 + 26);
}else{
ans += (char)(s.charAt(i) - 3);
}
}
return ans;
}
}
public main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入字符串的长度：");
int n = scanner.nextInt();
System.out.print("请输入字符串：");
String input = scanner.next();
Solution s = new Solution();
System.out.println(s.findString(input));
scanner.close();
}
}
第二题：K排序
在算法中，有各种各样的排序算法，例如归并排序，冒泡排序，快速排序等等。本题中，我们会使用一种新的排序算法：K排序。
K排序算法描述如下：首先，算法需要按照某种规则选择该数列上至多K个位置，将其对应的数抽出来，其他的数都往左对齐，之后这K个数排好序之后依次放在原数列末尾。以上过程算作一次操作。
例如，对于数列[1,3,5,4,2]，当K=2时可以选择数字5和4，之后数列变成[1,3,2,4,5]。
你的任务是：对于给定的数列，你需要计算出最少需要多少次上述操作，使得整个数列从小到大排好序？
样例输入
2
5 1
1 2 3 4 5
5 2
1 3 5 4 2
样例输出
0
2
主要思路是贪心，每次找到当前未排序部分的最小值，将其移动到正确的位置，如果需要移动的距离超过了k，则需要进行一次K排序操作。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int n = sc.nextInt();
int k = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
int ans = 0;
int cur = 0;
while (cur < n) {
int minIndex = cur;
for (int i = cur + 1; i < Math.min(cur + k + 1, n); i++) {
if (nums[i] < nums[minIndex]) {
minIndex = i;
}
}
if (minIndex == cur) {
cur++;
} else {
int temp = nums[minIndex];
for (int i = minIndex; i > cur; i--) {
nums[i] = nums[i - 1];
}
nums[cur] = temp;
ans++;
}
}
System.out.println(ans);
}
}
}
第三题: 涂色
给出一个数组。你需要求出按顺序对其进行一系列区间操作后最终所得的数组。
操作有三种：
将下标在L到R之间的元素全部或上X。
将下标在L到R之间的元素全部与上X。
将下标在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