题解-Educational Codeforces Round 182 (Div. 2)

忘记时间了，23:19才开始写，然后直接看B题，做不出来直接溜，结果还挺简单，做了三道，本来可以上大分的（悲）

题目链接

A

直接暴力

void solve() {
    int n; cin >> n;
    vi v(n);
    for(int i = 0; i < n; ++ i) cin >> v[i];
    for(int i = 0; i < n; ++ i) {
        for(int j = i + 1; j < n - 1; ++ j) {
            int a = 0, b = 0, c = 0;
            for(int k = 0; k <= i; ++ k) {
                a += v[k];
            }
            for(int k = i + 1; k <= j; ++ k) {
                b += v[k];
            }
            for(int k = j + 1; k < n; ++ k) {
                c += v[k];
            }
            if(a % 3 == b % 3 && b % 3 == c % 3) {
                cout << i + 1 << " " 
                << j + 1 << "\n";
                return;
            }
            if(a % 3 != b % 3 && b % 3 != c % 3 
            && c % 3 != a % 3) {
                cout << i + 1 << " " 
                << j + 1 << "\n";
                return;
            }
        }
    }
    cout << "0 0 \n";
}

B

将排列中没出现过的数从大到小填到0的位置，再左右两边向中间缩，排好序的就缩，直到第一个未排序的地方，输出差。

void solve() {
    int n; cin >> n;
    vi v(n);
    map<int, int> mp;
    for(int i = 0; i < n; ++ i) {
        cin >> v[i];
        mp[v[i]] ++;
    }
    vi nums;
    for(int i = n; i >= 1; -- i) {
        if(mp[i] == 0) nums.pb(i);
    }
    int pos = 0;
    for(int i = 0; i < n; ++ i) {
        if(v[i] == 0) v[i] = nums[pos ++];
    }

    int l = 0, r = n - 1;
    for(int i = 0; i < n; ++ i) {
        if(v[i] == i + 1) l ++;
        else break;
    }
    for(int i = n - 1; i > 0; -- i) {
        if(v[i] == i + 1) r --;
        else break;
    }
    if(r - l + 1 <= 0) cout << 0 << "\n";
    else  cout << r - l + 1 << '\n';
}

C

dp，只有四种可能的转移

void solve() {
    int n; cin >> n;
    vi a(n), b(n);
    for(int i = 0; i < n; ++ i) cin >> a[i];
    for(int i = 0; i < n; ++ i) cin >> b[i];

    vi dp(2, 0), cur(2, 0);
    dp[0] = 1; dp[1] = 1; 
    for(int i = 1; i < n; ++ i){
        cur[0] = cur[1] = 0;
        for(int j = 0; j <= 1; ++ j){
            for(int k = 0; k <= 1; ++ k){
                int p = (j == 0 ? a[i-1] : b[i-1]);
                int pp = (j == 0 ? b[i-1] : a[i-1]);
                int c = (k == 0 ? a[i] : b[i]);
                int cc = (k == 0 ? b[i] : a[i]);
                if(p <= c && pp <= cc){
                    cur[k] += dp[j];
                    if(cur[k] >= MOD) 
	                    cur[k] -= MOD;
                }
            }
        }
        dp = cur;
    }
    int ans = 0;
    if(n == 1) ans += 2 % MOD; 
    else {
        dp[0] += dp[1];
        if(dp[0] >= MOD) dp[0] -= MOD;
        ans += dp[0];
    }
    cout << ans << '\n';
}