携程笔试 - 0905

第一题

题面

游游有两个整数 $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$ 是字典序最小的，因此直接模拟即可。

#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";
}

第二题

题面

一个长度为 $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$ 结尾的长度为偶数的权值为奇数的子字符串的数量，以此类推。

dp数组的转移如代码所示：

#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";
}

第三题

题面

游游喜欢数数，他想知道由 $0-n$ 这些数字组成的 $m$ 位数中（每个数最多使用一次），有多少个是大于 $k$ 的。

输入描述：
第一行，输入 $n,m,k$ $(1 \le n \le 7, 1 \le m \le n + 1, 0 \le k \le 10^8)$

输出描述：
输出大于 $k$ 的数量

示例：

输入：5 1 0
输出：5
解释：大于 0 的是 1,2,3,4,5 这 5 个数

思路与代码

首先选择 $m$ 个数位，然后求这些数位的全排列，组合在一起。要注意 $0$ 在有多个数位的情况下不能开头。

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> ans;
    int n = nums.size();
    auto dfs = [&](auto self, vector<int> cur, int mask) {
        if(mask == (1 << n) - 1) {
            vector<int> add = cur;
            ans.push_back(add);
            return;
        }
        for(int i = 0;i < n;i++) {
            if((mask >> i & 1) == 0) {
                mask ^= (1 << i);
                cur.push_back(nums[i]);
                self(self,cur,mask);
                cur.pop_back();
                mask ^= (1 << i);
            }
        }
    };
    dfs(dfs,{},0);
    return ans;
}
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    n++;
    int ans = 0;
    for (int i = 0; i < (1 << n); i++) {
        if (__builtin_popcount(i) == m) {
            vector<int> nums;
            for (int j = 0; j < n; j++) {
                if (i >> j & 1) {
                    nums.push_back(j);
                }
            }
            vector<vector<int>> pers = permute(nums);
            for (vector<int> p : pers) {
                int sum = 0;
                if (p.size() > 1 && p[0] == 0) {
                    continue;
                }
                for (int x : p) {
                    sum = sum * 10 + x;
                }
                if (sum > k) {
                    ans++;
                }
            }
        }
    }

    cout << ans << "\n";
}

第四题

题面

游游有一个长度为 $n$ 的数组 $a$，下标从 $1$ 开始，一个好数组要求任意连续的 $k$ 个元素的总和不超过 $sum$。
现在可以执行任意次修改，每次修改选择一个下标 $i(1 \le i \le n)$，令 $a_i = a_i - 1$，注意 $a_i$ 不能为负数。最少执行多少次操作可以满足 $a$ 是一个好数组？

输入描述：
第一行，输入 $n,k,sum$ $(1 \le k \le n \le 2×10^5, 1 \le sum \le 10^{13})$
第二行输入 $n$ 个数 $a_i$ $(0 \le a_i \le 10^9)$

输出描述：
输出最少操作次数

示例：

输入：5 3 10
      9 7 3 6 5
输出：10
解释：修改为 [9,1,0,5,5]，只需要操作 10 次

思路与代码

可以想到每次贪心的对窗口中的最后一个数进行操作，可以使得答案最优。

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
#define ll long long
int main() {
    int n, k;
    ll sum;
    cin >> n >> k >> sum;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    deque<pair<int, int>> dq;
    ll cur = 0;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front().first < i - k + 1) {
            pair<int, int> p = dq.front();
            cur -= p.second;
            dq.pop_front();
        }
        cur += a[i];
        dq.push_back({i, a[i]});
        while (cur > sum) {
            ll diff = cur - sum;
            int sub = min((ll)dq.back().second, diff);
            cur -= sub;
            dq.back().second -= sub;
            ans += sub;
            if (dq.back().second == 0) {
                dq.pop_back();
            }
        }
    }
    cout << ans << "\n";
}