CSES Sorting and Searching

这些是寒假集训新做的题，之前做过的不会再专门写一遍题解了，如果需要代码可以看仓库。

Distinct Values Subarrays#

很经典的滑动窗口问题，我们只需要维护以每一个位置为结尾往左延伸的最长长度，这个滑动窗口随着右端点的右移左端点一定不会左移。做法是记录一个左端点 $j$ 初始化成 1，右端点 $i$ 从 $1$ 到 $n$ 枚举，每次往右走时， $j = \max\left\{j, x_i\text{上次出现的位置} + 1\right\}$ ，区间长度相加就是答案。

1
#include <iostream>
2
#include <map>
3

4
using namespace std;
5

6
map<int, int> mp;
7

8
int main() {
9
    ios::sync_with_stdio(0);
10
    cin.tie(0), cout.tie(0);
11
    int n;
12
    long long res = 0;
13
    cin >> n;
14
    for (int i = 1, j = 1; i <= n; ++i) {
15
        int t;
16
        cin >> t;
17
        j = max(j, mp[t] + 1);
18
        mp[t] = i;
19
        res += i - j + 1;
20
    }
21
    cout << res << endl;
22
    return 0;
23
}

Distinct Values Subsequences#

每个数只能出现一次或者不出现，统计一下每个数出现的个数，然后+1累乘就是答案。

1
#include <iostream>
2
#include <map>
3

4
using namespace std;
5
const int MOD = 1000000007, N = 200010;
6
typedef long long LL;
7
map<int, int> mp;
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    int n, tot = 1;
13
    LL res = 1;
14
    cin >> n;
15
    for (int i = 1; i <= n; ++i) {
16
        int t;
17
        cin >> t;
18
        mp[t]++;
19
    }
20
    for (auto [k, v] : mp) res = (res * (v + 1)) % MOD;
21
    cout << (res - 1 + MOD) % MOD << endl;
22
    return 0;
23
}

Star's Blog

Distinct Values Subarrays#

Distinct Values Subsequences#