Increase/Decrease/Copy

我们可以先将 \(a_i\) 变为 \(b_i\),统计在变化的过程中与 \(b_{i + 1}\)的最少差值即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 5;

int t, n, a[N], b[N];

void Solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n + 1; i++) {
    cin >> b[i];
  }
  int mini = 1e9, ans = 0;
  for (int i = 1; i <= n; i++) {
    if ((a[i] <= b[n + 1] && b[n + 1] <= b[i]) || (b[i] <= b[n + 1] && b[n + 1] <= a[i])) {
      mini = 0;
    }
    mini = min(mini, abs(a[i] - b[n + 1]));
    mini = min(mini, abs(b[i] - b[n + 1]));
    ans += abs(a[i] - b[i]);
  }
  cout << ans + mini + 1 << "\n";
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> t;
  while (t--) {
    Solve();
  }
  return 0;
}

Job Interview

大模拟,维护 \(4\) 个前缀和然后二分

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 4e5 + 5;

int t, n, m, a[N], b[N], sum[3][N], cnt[3][N], arr[3][N], tot[3], cur;

void Solve() {
  cin >> n >> m;
  for (int i = 1; i <= n + m + 1; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n + m + 1; i++) {
    cin >> b[i];
  }
  for (int i = 1; i <= n + m + 1; i++) {
    sum[1][i] = sum[1][i - 1] + (a[i] > b[i]) * a[i];
    sum[2][i] = sum[2][i - 1] + (b[i] > a[i]) * b[i];
    cnt[1][i] = cnt[1][i - 1] + (a[i] > b[i]);
    cnt[2][i] = cnt[2][i - 1] + (b[i] > a[i]);
    arr[1][i] = arr[1][i - 1] + a[i];
    arr[2][i] = arr[2][i - 1] + b[i];
  }
  for (int i = 1; i <= n + m + 1; i++) {
    if (i == n + m + 1) {
      cout << cur << "\n";
      break;
    }
    int tmp = n + m + 1;
    for (auto op : {1, 2}) {
      int l = i, r = n + m + 1;
      while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (cnt[op][mid] - cnt[op][i] <= n * (op == 1) + m * (op == 2) - tot[op]) {
          l = mid;
        }
        else r = mid - 1;
      }
     // cout << l << " ";
      tmp = min(tmp, l);
    }
   // cout << "\n";
    int now = sum[1][tmp] - sum[1][i] + sum[2][tmp] - sum[2][i];
    if (cnt[1][tmp] - cnt[1][i] == n - tot[1]) {
      cout << cur + now + arr[2][n + m + 1] - arr[2][tmp] << " ";
    }
    else {
      cout << cur + now + arr[1][n + m + 1] - arr[1][tmp] << " ";
    }
    if (tot[2] == m || (a[i] > b[i] && tot[1] < n)) {
      tot[1]++, cur += a[i];
    }
    else {
     tot[2]++, cur += b[i];
    }
  }
  tot[1] = tot[2] = cur = 0;
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> t;
  while (t--) {
    Solve();
  }
  return 0;
}

Invertible Bracket Sequences

用一个小根堆,考虑如果当前的和为 \(sum\) 那么之前的 \(sum1 * 2 < sum\) 的都不可以,我们开一个堆,每次统计为\(sum\)有多少个即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 4e5 + 5;

int t, n, a[N], ans, cnt[N];

string s;

void Solve() {
  priority_queue<int, vector<int>, greater<int> > q;
  cin >> s;
  n = s.size();
  s = " " + s;
  for (int i = 1; i <= n + 1; i++) {
    cnt[i] = 0;
  }
  cnt[0] = 1;
  ans = 0;
  q.push(0);
  for (int i = 1; i <= n; i++) {
    if (s[i] == '(') {
      a[i] = 1;
    }
    else a[i] = -1;
  }
  for (int i = 1, sum = 0; i <= n; i++) {
    sum += a[i];
    while (!q.empty() && q.top() * 2 < sum) {
      cnt[q.top()]--;
      q.pop();
    }
    ans += cnt[sum];
    q.push(sum);
    cnt[sum]++;
  }
  cout << ans << "\n";
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> t;
  while (t--) {
    Solve();
  }
  return 0;
}