Practice.

A. Password

题意

给定 \([0, 9]\) 中的几个元素，按照升序排列给出。排除这些元素后，剩余的元素可作为密码的一部分。

其中，密码为 \(4\) 位数，只包含两种数字，且每种数字出现两次。

输出密码可行解的个数。

思路

首先，我们假设只包含数字 \(a, b\)，那么有 \(aabb, abba, bbaa, abab, baba\) 这 \(6\) 种可行解。

其次，我们统计出剩余 \(k\) 种数字，那么选两个的方案数就是 \(C^2_k\)。

因此，答案就是 \(6C^2_k\)。

不过，既然元素个数已经告诉我们了，那么 \(k = 10 - n\)。

因此我们完全不用管元素是什么。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

void solve(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int tmp;
        cin >> tmp; //啥用没有
    }
    cout << (10 - n) * (9 - n) / 2 * 6 << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --) solve();
}

Happy Happy Happy

B. Permutation Value

题意

给定一个整数 \(n\)，构造一个排列，满足其所有连续子序列中排列的个数最少。

思路1

很直接的思路就是让连续的数用其他元素隔开。

并且，为了尽可能不构造出排列，我们就最好先隔一位填按顺序上答案，然后在剩余的位置按顺序填上剩余的数。

如 \(4\ 1\ 5\ 2\ 6\ 3\)。

时间复杂度：\(O(n)\)

思路2

我们可能会想到倒着输出，这样确实可以让前面的那些取法都不是排列，但是我们只要选择右边界为右端点，那么我们会多出 \(n - 1\) 个排列，因为有 \(1\)。

那么，很直接的思路就是把 \(1\) 直接移到第一个，然后倒序输出即可，不难发现和思路 \(1\) 得到的数量是一致的。

如 \(1\ 6\ 5\ 4\ 3\ 2\)。

时间复杂度：\(O(n)\)

对应AC代码（思路1）

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

void solve(){
    int n;
    cin >> n;
    if(n % 2 == 1) cout << 1 << ' ';
    for(int i=0;i<n/2;i++){
        cout << n / 2 + i + 1 + n % 2 << ' ' << i + 1 + n % 2 << ' ';
    }
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --) solve();
}

思路2是题解做法（没想到居然这么简单

C. Save the Magazines

题意

给定一个长为 \(n\) 的二进制字符串 \(s\) 以及一个包含 \(n\) 个元素的序列 \(a\)。定义对于所有 \(i \in [2, n]\)，可进行下面的两个操作任选一：

若 \(s_{i - 1} = 0, s_i = 1\)，交换 \(a_{i - 1}\) 和 \(a_i\)（即传递 \(1\) 到前者）；
不进行操作

规定同一个 \(1\) 只能被传递一次。

遍历操作后的 \(s\)，若 \(s_i = 1\)，累计 \(ans += a_i\)。

输出 \(ans\) 的最大值。

思路

我们不妨遍历所有连续的 \(1\)，然后找出其中的最小值，将这个最小值剔除，用前面的 \(0\) 代替。

或者更容易实现地，我们遍历找出连续的 \(1\) 前面相邻的那个 \(0\)，并从这个 \(0\) 开始寻找最小值，并统计总和，最后这一段的价值就是 \(sum - min\)。

为了更加方便，我们不妨在第一个元素前插入 \(0\)，那么 \(0\) 一定是最小的，如果开头是 \(1\) 也不会影响答案。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

int a[N];

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = '0' + s;
    int ans = 0;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=0;i<=n;){
        int mn = a[i];
        int sum = a[i];
        int j = i + 1;
        while(j <= n && s[j] == '1'){
            mn = min(mn, a[j]);
            sum += a[j];
            j ++;
        }
        i = j;
        ans += sum - mn;
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --) solve();
}

有个大蠢比没看到只能向前交换然后一直在想 \(dp\)，我不说是谁（x