笔试时间：2024年09月05日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

游游有两个整数n,k, 他希望构造出一个1~n的排列p, 需要p的最长上升子序列长度为k, 并且p是所有满足要求的排列中字典序最小的。最长上升子序列是一个序列中最长的严格单调递增的子序列。

输入描述

两个正整数n,k，用空格隔开。

输出描述

输出n个正整数，代表构造的排列。

样例输入

5 3

样例输出

1 2 5 4 3

参考题解

模拟。由于字典序要求最小，因此要贪心的考虑。容易想到首先构造出1, 2, 3, ..., k - 1，n, n - 1, ..., k是字典序最小的。

C++：[此代码未进行大量数据的测试，仅供参考]

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < k - 1; i++) {
        a[i] = i + 1;
    }
    a[k - 1] = n;
    for (int i = k, x = n - 1; i < n; i++, x--) {
        a[i] = x;
    }
    for (int x : a) {
        cout << x << " ";
    }
    cout << "\n";
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        Vector<Integer> a = new Vector<>(n);

        for (int i = 0; i < k - 1; i++) {
            a.add(i + 1);
        }
        a.add(n);

        for (int i = k, x = n - 1; i < n; i++, x--) {
            a.add(x);
        }

        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n, k = map(int, input().split())
a = [0] * n

for i in range(k - 1):
    a[i] = i + 1
a[k - 1] = n

x = n - 1
for i in range(k, n):
    a[i] = x
    x -= 1

print(" ".join(map(str, a)))

第二题

题目

一个长度为k的二进制字符串(下标从1开始)的权值定义如下：每次操作可以选择一个下标i(1 ≤ i ≤ k)，将[1, i]中的字符全部取反(0变成1，1变成0)，字符串的权值为将字符串变成全1所需要的最小操作次数。给定一个长度为n的01字符串，问：有多少个长度为奇数并且权值为奇数的子字符串？

输入描述

第一行输入一个正整数n，代表字符串的长度。第二行输入字符串S。

输出描述

输出包含一行一个整数，表示长度和权值都是奇数的非空子串数量。

样例输入

5

01010

样例输出

6

参考题解

动态规划。定义三维dp数组，第一个维度表示下标，第二个维度表示长度是奇数还是偶数，第三个维度表示权值是奇数还是偶数

例如：dp[i][0][0]就表示以下标i结尾的长度为偶数并且权值为偶数的子字符串的数量，dp[i][0][1]表示以下标i结尾的长度为偶数的权值为奇数的子字符串的数量，以此类推。

C++：[此代码未进行大量数据的测试，仅供参考]

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(2, vector<int>(2, 0)));
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            dp[i][1][0]++;
            if (i > 0) {
                dp[i][0][0] += dp[i - 1][1][0];
                dp[i][0][1] += dp[i - 1][1][1];
                dp[i][1][0] += dp[i - 1][0][0];
                dp[i][1][1] += dp[i - 1][0][1];
            }
        }else {
            dp[i][1][1]++;
            if (i > 0) {
                 if (s[i - 1] == s[i]) {
                    dp[i][0][0] += dp[i - 1][1][0];
                    dp[i][0][1] += dp[i - 1][1][1];
                    dp[i][1][0] += dp[i - 1][0][0];
                    dp[i][1][1] += dp[i - 1][0][1];
                 } else {
                    dp[i][0][0] += dp[i - 1][1][0];
                    dp[i][0][1] += dp[i - 1][1][1];
                    dp[i][1][0] += dp[i - 1][0][0];
                    dp[i][1][1] += dp[i - 1][0][1];
                 }
            }
        }
        ans += dp[i][1][1];
    }
    cout << ans << "\n";
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String s = scanner.next();
        int[][][] dp = new int[n][2][2];
        long ans = 0;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                dp[i][1][0]++;
                if (i > 0) {
                    dp[i][0][0] += dp[i - 1][1][0];
                    dp[i][0][1] += dp[i - 1][1][1];
                    dp[i][1][0] += dp[i - 1][0][0];
                    dp[i][1][1] += dp[i - 1][0][1];
                }
            } else {
                dp[i][1][1]++;
                if (i > 0) {
                    if (s.charAt(i - 1) == s.charAt(i)) {
                        dp[i][0][0] += dp[i - 1][1][0];
                        dp[i][0][1] += dp[i - 1][1][1];
                        dp[i][1][0] += dp[i - 1][0][0];
                        dp[i][1][1] += dp[i - 1][0][1];
                    } else {
                        dp[i][0][0] += dp[i - 1][1][0];
                        dp[i][0][1] += dp[i - 1][1][1];
                        dp[i][1][0] += dp[i - 1][0][0];
                        dp[i][1][1] += dp[i - 1][0][1];
                    }
                }
            }
            ans += dp[i][1][1];
        }

        System.out.println(ans);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
s = input()
dp = [[[0, 0] for _ in range(2)] for _ in range(n)]
ans = 0

for i in range(n):
    if s[i] == '1':
        dp[i][1][0] += 1
        if i > 0:
            dp[i][0][0] += dp[i - 1][1][0]
            dp[i][0][1] += dp[i - 1][1][1]
            dp[i][1][0] += dp[i - 1][0][0]
            dp[i][1][1] += dp[i - 1][0][1]
    else:
        dp[i][1][1] += 1
        if i > 0:
            if s[i - 1] == s[i]:
                dp[i][0][0] += dp[i - 1][1][0]
                dp[i][0][1] += dp[i - 1][1][1]
                dp[i][1][0] += dp[i - 1][0][0]
                dp[i][1][1] += dp[i - 1][0][1]
            else:
                dp[i][0][0] += dp[i - 1][1][0]
                dp[i][0][1] += dp[i - 1][1][1]