CF1691

ACgod · 2022-06-02 20:56:17 · 个人记录

A

任意相邻的两个数的和为偶数，必须满足整个数列必须奇偶性相同。否则必然存在一对(a_i,a_{i+1})满足a_i+a_{i+1}为奇数。

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::max;
using std::min;
using std::sort;

namespace myspace{
    int a[100005];
    void solve(int n) {
        int ans1 = 0, ans2 = 0;
        for(int i = 1; i <= n; i ++) {
            int a; cin >> a;
            if(a & 1) ans1 ++;
            else ans2 ++;
        }
        cout << min(ans1, ans2) << endl;
    }
    void Main() {
        int t; cin >> t;
        while(t--) {
            int n;
            cin >> n;
            solve(n);
        }
    }
}

int main() {
    myspace::Main();
    return 0;
}

B

很容易证明只能在值相等的数中交换。

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::max;
using std::min;
using std::sort;
using std::unordered_map;

#define umap unordered_map
#define rep(i,x,y) for(int i = x; i <= y; i ++)

namespace myspace{
    int a[100005];
    umap <int, int>last;
    void solve(int n){
        rep(i, 1, n) {
            cin >> a[i];
            last[a[i]] = i;
        }
        for(int i = 1; i <= n; i = last[a[i]] + 1) {
            if(last[a[i]] == i) {
                cout << -1 << endl;
                return;
            }
        }
        for(int i = 1; i <= n; i = last[a[i]] + 1) {
            cout << last[a[i]] << " ";
            for(int j = i + 1; j <= last[a[i]]; j ++) {
                cout << j - 1 << " ";
            }
        }
        cout << endl;
    }

    void Main() {
        int t; cin >> t;
        while(t--) {
            int n;
            cin >> n;
            for(int i = 0; i <= n; i ++) a[i] = 0;
            solve(n);
        }
    }
}

int main() {
    myspace::Main();
    return 0;
}

C

如果一个1不在整个字符串的两头，那么它对答案的贡献是一定的，为11(一次在十位，一次在个位)，判断能否移动到两头即可。

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int ones = 0, p1_first = n, p1_last = -1;
    for (int p = 0; p < n; p++) {
      if (s[p] != '1')
        continue;
      ones += 1;
      if (p1_first == n)
        p1_first = p;
      p1_last = p;
    }
    int add = 0;
    // moving the last one to last position
    if (ones > 0 and (n - 1 - p1_last) <= k) {
      k -= (n - 1 - p1_last);
      add += 1;
      ones -= 1;
    }
    // moving the first one to first position
    if (ones > 0 and p1_first <= k) {
      k -= (p1_first);
      add += 10;
      ones -= 1;
    }
    cout << 11 * ones + add << "\n";
  }
  return 0;
}

D

对于一个数，找出它能够成为最大值的最大区间，判断区间最大字段和是否满足题意即可。这可以线性时间内解决，也可以用数据结构，我这里用的是分块，很好解决。

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::min;
using std::max;
using std::sqrt;
using std::stack;

namespace myspace {
    #define rep(i,x,y) for(int i = x; i <= y; i ++)
    #define int long long
    struct block{
        int l, r;
        int sum;
        int lmax, rmax;
        int qmax;
        block() { l = r = 0; sum = 0;qmax = lmax = rmax = -2147483647;}
    }a[200001];
    int n, B;
    int e[200010];
    int pre[200010];
    int pos[200010];
    void init() {
        cin >> n;
        for(int i = 1; i <= n; i ++) {
            e[i] = 0;
            a[i].lmax = a[i].rmax = a[i].qmax = -2147483647;
        }
        rep(i, 1, n) cin >> e[i];
        int B = sqrt(n);
        rep(i, 1, B){
            a[i].l = a[i - 1].r + 1;
            a[i].r = i * B;
        }
        if(B * B < n) {
            B++;
            a[B].l = a[B - 1].r + 1;
            a[B].r = n;
        }
        rep(i, 1, B) {
            int s = 0;
            rep(j, a[i].l, a[i].r) {
                pos[j] = i;
                s += e[j];
                pre[j] = s;
                a[i].lmax = max(a[i].lmax, s);
            }
            a[i].sum = s;
            s = 0;
            for(int j = a[i].r; j >= a[i].l; j --) {
                s += e[j];
                a[i].rmax = max(a[i].rmax, s);
            }
            pre[a[i].l - 1] = 0;
            rep(j, a[i].l, a[i].r) {
                rep(k, j + 1, a[i].r) {
                    a[i].qmax = max(pre[k] - pre[j - 1], a[i].qmax);
                }
            }
        }
    }
    struct yzq {
        int no, s;
        yzq(int no, int s) : no(no), s(s) {}
    };
    stack<yzq> pr, suf;
    int pmax[200001], smax[200001];
    int query(int l, int r) {
        int p = pos[l], q = pos[r];
        if(p == q) {
            int f = e[l], ans = e[l];
            for(int i = l + 1; i <= r; i ++) {
                f = max(e[i],e[i] + f);
                ans = max(ans, f);
            }
            return ans;
        }
        else {
            int f = e[l], ans = e[l];
            for(int i = l + 1; i <= a[p].r; i ++) {
                f = max(e[i],e[i] + f);
                ans = max(ans, f);
            }
            f = e[a[q].l]; ans = max(ans, f);
            for(int i = a[q].l + 1; i <= r; i ++) {
                f = max(e[i], e[i] + f);
                ans = max(ans, f);
            }
            int lastans = -2147483647;
            int s = 0;
            for(int i = a[p].r; i >= l; i --) {
                s += e[i];
                lastans = max(lastans, s);
            }
            for(int i = p + 1; i <= q - 1; i ++) {
                ans = max(ans, lastans + a[i].lmax);
                ans = max(ans, a[i].qmax);
                lastans = max(a[i].rmax, lastans + a[i].sum);
            }
            f = e[a[q].l]; s = 0;
            for(int i = a[q].l; i <= r; i ++) {
                s += e[i];
                ans = max(ans, lastans + s);
            }
            return ans;
        }
    }
    void solve(void) {
        init();
        pr.push(yzq{0,2147483647});
        rep(i, 1, n) {
            if(e[i] < pr.top().s) {
                pmax[i] = pr.top().no;
            }
            else {
                while(pr.top().s <= e[i]) pr.pop();
                pmax[i] = pr.top().no;
            }
            pr.push(yzq{i,e[i]});
        }
        suf.push(yzq{0,2147483647});
        for(int i = n; i >= 1; i --) {
            if(e[i] < suf.top().s) {
                smax[i] = suf.top().no;
            }
            else {
                while(suf.top().s <= e[i]) suf.pop();
                smax[i] = suf.top().no;
            }
            suf.push(yzq{i,e[i]});
        }
        bool flag = false;
        for(int i = 1; i <= n; i ++) {
            if(e[i] < query(pmax[i]+1, smax[i]?smax[i]-1:n)) {
                flag = true;
                break;
            }
        }
        if(flag) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    void Main(void) {
        int t; cin >> t;
        while(t--) {
            solve();
        }
    }
}

signed main(void) {
    myspace::Main();
}