2021-04-11 度小满金融 笔试

时间：2021-04-11 16:00-17:30 (90min)

题型：

一。选择题（25道）60分

大多数是考察的是图的题目

二。编程题（2道）40分

1. 100%

开关电灯
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小A在宾馆打工。一日，小A需要把宾馆一个走廊上n个灯全部关掉。走廊上的灯编号为1~n。宾馆的电路有设计缺陷。宾馆的走廊上有n个开关，第i个开关只可以改变i~n号电灯的状态，即亮的熄灭，熄灭的变亮。 小A一秒按一次开关，一共按了m次。给出小A每次按下的开关编号，请问每一盏灯第一次关掉的时间。一开始，所有灯都是亮着的。
输入描述
输入第一行包含两个数，n,m 接下来一行m个数，代表小A每次按下的开关编号
（n,m≤100000,最后一次按下的开关一定是1号开关。）
输出描述
输出一行n个数，代表每盏电灯最后关掉的时间。
样例输入
4 2
2 1
样例输出
2 1 1 1

import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] nm = sc.nextLine().split("\\s+");
        int n = Integer.parseInt(nm[0]);//灯数
        int m = Integer.parseInt(nm[1]);//按下的开关数
        String[] mNum = sc.nextLine().split("\\s+");//每次开关
        int[] k = new int[n];//初始化一个灯的数组
        int count = 1;//次数
        for (String i : mNum) {//模拟开关并记录
            for (int j = Integer.parseInt(i) - 1; j < n; j++) {
                if (k[j] == 0) {
                    k[j] = count;
                }
            }
            count++;
        }
        for (int i : k) {
            System.out.print(i + " ");
        }
    }
}

2. 值有45%的通过了（另外复杂度也比较高），求大佬指教！！

消消乐
时间限制： 3000MS
内存限制： 589824KB
题目描述：
给定一个长度为n的字符串，每个位置表示一种颜色。你有一次机会可以消掉一堆颜色相同并且连续的序列，并且得到这个序列的长度的得分。比如对于字符串aaabbccccc，你可以消掉aaa，可以得到3分，你也可以消掉cccc，得到4分。现在你有k次作弊的机会，每次作弊可以改变字符串中任意一个位置的颜色，比如aaabaac，你可以把第四个位置的b改成a，这样就能从1消到6，当然你也可以不改变任意位置。现在你需要输出最大的得分。
为了方便，每种颜色我们用小写的字母来表示，也就是至多有26种颜色。
输入描述
第一行一个整数n表示字符串的长度和一个整数k表示作弊的次数。(1≤k≤n≤1e6)
第二行一个长度为n并且只包含小写字母的字符串。
输出描述
最大的得分。
样例输入
5 1
aaaba
样例输出
5

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] nk = sc.nextLine().split("\\s+");
        int n = Integer.parseInt(nk[0]);//字符串长度
        int k = Integer.parseInt(nk[1]);//作弊次数
        String s = sc.nextLine();
        int score = 0;//最终得分
        for (int i = 0; i < n - 1; i++) {
            String str = s;
            int scoreTmp = 1;//临时得分
            int K = 0;//作弊次数
            int tmp = i + 1;//记录未作弊位置时候的最大
            for (int j = i + 1; j < n; j++) {
                if (str.charAt(i) == str.charAt(j)) {
                    scoreTmp++;
                } else if (K < k) {//还能作弊
                    if (tmp == i + 1) {
                        tmp++;
                    }
                    K++;
                    str = str.replaceFirst(str.charAt(j) + "", str.charAt(i) + "");
                    scoreTmp++;
                } else {
                    break;
                }
            }
            if (score < scoreTmp) {
                score = scoreTmp;
            }
            i = tmp;
        }
        System.out.println(score);
    }
}