Codeforces Round #804 (Div. 2)-C. The Third Problem

C. The Third Problem

链接跳转

感觉当时思路与正解就差一点了(还得加油啊)
思路:
a[x] 表示 x所在的位置

1.考虑(0) , 那么 pos = a[0] 的位置 mex(pos) = 1, 如果将0与其他数交换肯定会导致mex(pos) = 0,所以0肯定不能换
2.考虑(1), 0 与 1 组成的区间记f1, mex(f1) = 2, 如果将1 与其他数交换位置 那么 mex(f1) = 1, 所以 1 也是不能换的
我们可以发现:
①.对于i而言，如果 0 ~ (i - 1) 都在 i 左边：
那么可以发现 此时分成了 … 0 … (i - 1) … i … 分成了 4个区间分别记 f1, f2, f3, f4，
当i交换的位置为 f1, f2, f3区间内, 那么设包含 0 ~ i的区间 t1 mex(t1) = i + 1，
而对于原序列t1区间，mex(t1) != i + 1(因为不可能包含i)。
②.考虑分在f4区间, 更加不行, 因为原序列包含0 ~ i区间 mex() = i + 1, 换了位置肯定为 i;
右边同理。
所以放在左右边都不行， 那么就考虑 i 放在中间的情况:
你可以发现除了区间两头以外 其他数都可以交换，因为无论怎样交换 区间内的任意子区间mex() = j (j <= i) ，而包含外面的数的区间mex() = j(j > i), 所以都不会对mex产生影响

此时需要注意，需要从小到大依次枚举: 因为交换数字的情况必须要满足(交换的数字也能在此区间交换：必须要满足区间两头比它小), 从而计算每个数能交换的次数相乘就行了 (r - l + 1 - i)
r - l + 1: 区间的个数，
i : 前面计算过得数字(因为前面枚举了这些数字 减去他们即可)

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

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

int n, m;
int a[N];

void solve(){
    cin >> n;
    
    for(int i = 1; i <= n; ++ i){
        int x;
        cin >> x;
        a[x] = i;
    }
    
    LL ans = 1;
    
    int l, r;
    l = r = a[0];
       
    for(int i = 1; i < n; ++ i){
        if(a[i] < l) l = a[i];
        
        if(a[i] > r) r = a[i];
        
        if(a[i] > l && a[i] < r){
            ans = ((ans * (r - l + 1 - i) % mod) + mod) % mod;
        }
        
    } 
    
    cout << ans << endl;
    
}

int main(){
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    //t = 1;
    while(t --){
        solve();
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52