Contestant'. Rank 1390. Rating +9(+109 -100).

A. Divisible Array

题意

给定整数 \(n\)，构造一个长度为 \(n\) 的数组 \(a\)，满足 \(a_i \bmod i = 0\)，且总和 \(sum\) 满足 \(sum \bmod n = 0\)。

思路

构造一个 \(2, 4, \ldots, 2n\) 的数组，\(sum = \frac{(2 + 2n)n}{2} = n(n + 1)\)。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10;

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

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

倒也有其他思路，这个最好写

B. Permutation Swap

题意

给定一个未排序的排列，输出最大的 \(k\)，满足按照 "\(a_i\) 和 \(a_{i + k}\)" 之间可交换的方式进行排序后，可将排列升序。

思路

如果一个数 \(x\) 位于 \(y\) 位置，他想要到 \(x\) 位置，那么 \(abs(y - x) \bmod k = 0\)。

那么，如果所有数都要满足这个条件，我们只需求 \(gcd\) 即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10;

void solve(){
    int n;
    cin >> n;
    int ans = -1;
    for(int i=1;i<=n;i++){
        int cur;
        cin >> cur;
        cur = abs(cur - i);
        if(cur == 0) continue;
        if(ans == -1) ans = cur;
        else ans = gcd(ans, cur);
    }
    cout << ans << '\n';
}

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

瞎猜就完事了

C. Counting Orders

题意

给定两个长度相等的序列 \(a, b\)，其中 \(a\) 中无重复元素，输出满足所有 \(a_i\) 均大于 \(b_i\) 的 \(a\) 的所有排列的个数。

思路

我们将 \(a, b\) 升序排序，那么，对于每一个 \(a_i\)，我们找出 \(b\) 中满足 \(a_i > b_i\) 的个数 \(cnt\)，这个个数就是 \(a_i\) 能放的位置。

因而，答案就是 \(cnt_1 \cdot(cnt_2 - 1) \cdot(cnt_3 - 2) \cdots (cnt_n - (n - 1))\) （考虑前面几个数已经放了，而且前几个数能放的区间一定在当前能放的区间里面）。

找位置可以线性也可以二分。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 1e9 + 7;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> b[i];
    sort(all(a)), sort(all(b));
    int ans = 0, cnt = 0;
    for(int i=n-1;i>=0;i--){
        int pos = n - (upper_bound(all(a), b[i]) - a.begin());
        if(pos <= cnt){
            cout << 0 << '\n';
            return;
        }
        if(ans == 0) ans = pos - cnt;
        else ans = (ans * (pos - cnt)) % mod;
        cnt ++;
    }
    cout << ans << '\n';
}

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

乱猜即可

D1. Range Sorting (Easy Version)

题意

给定一个序列 \(p\)，定义操作为选定一个区间 \([l, r]\)，并将里面的数排序，代价为 \(r - l\)。

输出对于序列的 所有连续子序列，任意次操作后，使其升序所需的最小代价的总和。

思路

首先，我们固定子序列的头，然后依次枚举尾。

不难发现，如果一段区间不需要参与排序，那么他一定是单调的，并且，除去这段区间后，没有比区间内的数小的数。

当然，这个区间内也不能包含比剩余数小的数。

我们维护一个单调栈，在弹出元素的时候，将元素和当前元素取最大值，最后放入栈中的是这个最大值。

这样即可满足上述的所有条件（比较抽象）。

取最大值是为了满足最后一个条件，而单调栈的维护满足了剩下的条件。

对于一段枚举的区间 \([i, j]\)，最小代价就是 \(j - i - size\)，其中 \(size\) 是单调栈的大小。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 1e9 + 7;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    int ans = 0;
    for(int i=0;i<n;i++){
        stack<int> st;
        for(int j=i;j<n;j++){
            int mx = a[j];
            while(!st.empty() && a[j] < st.top()){
                mx = max(mx, st.top()), st.pop();
            }
            st.emplace(mx);
            ans += j - i + 1 - st.size();
        }
    }
    cout << ans << '\n';
}

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

太妙了！