第十七届北京信息科技大学程序设计竞赛（校外同步赛）

所有代码均以现代化C++实现 拥有非常强的可读性的同时保证了代码简洁短小 可以放心食用 有不够详细的题目也可以评论 我会修改解题报告

A接雨水 贪心

用最高的板子放在最左和最右就可以接最多的雨水 
void A() {
  int t;
  cin >> t;
  while (t --) {
    int n;
    cin >> n;
    vector<int> w(n);
    for (int &x : w) cin >> x;
    ranges::sort(w);
    long long ans = (long long)w[n - 2] * (n - 1);
    cout << ans << '\n';
  }
}

B小芳与残骸 DP/组合数学

一个数组中的元素 因为元素只可能是 0 或 1
所以abs(a - b)可以表示为a ^ b
想要[a, b]能成为目标数组 则有 a != b
即 b = !a

初始状态:[1] 即可以达成的唯一数组,也是题目描述的目标数组
目标数组可以从 其他目标数组转移来 即:
newtarget = target[x ... a] -> target[x ... a, !a]
如 [1] -> [1, !1] = [1, 0]

或从其他不满足的数组中转移来:
newtarget = num[x ... a] -> target[x ... a, !a]
如 [0] -> [0, !0] = [0, 1]

可以发现对于任意数组 只要加上最后一个数的否定版 一定能创造出一个新的目标数组
构造 n = 1 的目标数组时 可以从 n = 0 的任意数组转移来 [] -> [1] (空的视为0)
构造 n = 2 时 可以从 n = 1的任意数组转移来 [0] -> [0, 1], [1] -> [1, 0]
可以发现 构造任意 n 的数组时 可以从 长度为 n - 1 的数组转移而来
而 n - 1 长度的数组 一共有2^{n - 1}种
即构造长度为 n 的目标数组一共有2^{n - 1}种

注意计算2^{n - 1}时记得取模 防止溢出 
void B() {
  int t;
  cin >> t;
  while (t --) {
    int n, ans = 1;
    cin >> n;
    for (int i = 1; i < n; i ++) {
      (ans *= 2) %= mod;
    }
    cout << ans << '\n';
  }
}

C小苯的棋盘游戏 贪心

只要长或宽是奇数就可以转移 
void C() {
  int t;
  cin >> t;
  while (t --) {
    int x, y;
    cin >> x >> y;
    if (x & 1 || y & 1) cout << "YES" << '\n';
    else cout << "NO" << '\n';
  }
}

D暴暴龙的防奶龙要塞 贪心

n<=4时可证明是无解的
n>4时 让1连接所有的点 使1成为关键房间
再把剩下的点分成两份 每份点之间互相连接 即使断开也能保持连通 
void D() {
  int n;
  cin >> n;
  if (n <= 4) cout << -1 << '\n';
  else {
    cout << 2 * n - 4 << '\n';
    for (int i = 2; i <= n; i ++) {
      cout << 1 << ' ' << i << '\n';
    }
    for (int i = 2; i <= n / 2; i ++) {
      cout << i << ' ' << i + 1 << '\n';
    }
    for (int i = n / 2 + 2; i < n; i ++) {
      cout << i << ' ' << i + 1 << '\n';
    }
  }
}

E奶龙与奥利奥自动机 DP

用set模拟后发现其实是个斐波那契数列-1的结果 答案是A[2 * (n + 1)] - 1
从DP角度来看 DP[i] = DP[i - 1] * 3 - DP[i - 2] + 1
可以分解为斐波那契数列的第2n项 -1 由于一直在取模 可能答案正好是0 
为了防止0 - 1变为负数 所以取模前先加一个模数在减一
void E() {
  int n;
  cin >> n;
  vector<int> dp(2, 1);
  for (int i = 1; i <= 2 * (n + 1); i ++) {
    (dp[i & 1] += dp[~i & 1]) %= mod;
  }
  cout << (dp[1] + mod - 1) % mod << '\n';
}

F奶龙智斗暴暴龙 概率论/贪心

让一个桶里只有鲱鱼罐头 其他都放进另一个罐头 可以证明是最大的 
void F() {
  double n;
  cin >> n;
  double ans = 0.5;
  ans += (n - 1) / (2 * n - 1) / 2;
  cout << fixed << setprecision(6) << ans << '\n';
}

G小红的抛物线 数学

对三个点排序后求两个点之间的斜率 即对求导的结果比大小 
void G() {
  int t;
  cin >> t;
  while (t --) {
    vector<pair<double, double>> p(3);
    for (auto &[x, y] : p) cin >> x >> y;
    ranges::sort(p);
    double a = (p[1].second - p[0].second) / (p[1].first - p[0].first);
    double b = (p[2].second - p[1].second) / (p[2].first - p[1].first);
    if (a > b) cout << "DOWN" << '\n';
    else cout << "UP" << '\n';
  }
}

H小苯的序列染色 模拟+贪心

由于目标线段的要求是端点的最大值而非区间最大值 所以我们可以遍历每个点i
如果 i - w[i] + 1存在 即可能有一条目标线段 [i - w[i] + 1, i] 判断是否成立即可
右边也是同理 [i, i + w[i] - 1]
最后对所有线段贪心即可 
void H() {
  int t;
  cin >> t;
  while (t --) {
    int n;
    cin >> n;
    vector<int> w(n);
    for (int &x : w) cin >> x;
    vector<int> seg(n, -1);
    for (int i = 0; i < n; i ++) {
      if (i - w[i] + 1 >= 0 && w[i - w[i] + 1] <= w[i]) seg[i - w[i] + 1] = max(seg[i - w[i] + 1], i);
      if (i + w[i] - 1 < n && w[i + w[i] - 1] <= w[i]) seg[i] = max(seg[i], i + w[i] - 1);
    }
    for (int i = 1; i < n; i ++) seg[i] = max(seg[i], seg[i - 1]);
    int needcolor = 0, cnt = 0;
    while (needcolor < seg[needcolor] + 1) {
      cnt ++;
      needcolor = seg[needcolor] + 1;
      if (needcolor == n) break;
    }
    if (needcolor == n) cout << cnt << '\n';
    else cout << -1 << '\n';
  }
}

I小苯的字符串构造 贪心

其实最多只要2个字母
如果字符串是基数 那可以直接令他全是a 所有长度为奇数的子串:a aaa aaaaa的个数为n - lth + 1 一定是奇数 满足条件
如果字符串是偶数 那就可以令他又n - 1个a和一个b组成 刚才证明了n - 1个a一定成立 而ab和b的数量又只有1 一定满足条件 
void I() {
  int t;
  cin >> t;
  while (t --) {
    int n;
    cin >> n;
    if (n & 1) cout << string(n, 'a') << '\n';
    else cout << string(n - 1, 'a') << 'b' << '\n';
  }
}

J小苯的运算式 DP

可以用DP来解 DP[i][0]表示长度为偶数的最大值 DP[i][1]表示长度为基数的最大值
由于DP[i]只与DP[i - 1]有关 所以我们可以直接使用滚动数组来解决 
DP[i][0] = max(DP[i - 1][0] + a, a, DP[i - 1][1])
DP[i][1] = max(DP[i - 1][0] - a, DP[i - 1][0]) 
void J() {
  long long t, inf = LLONG_MIN / 2;
  cin >> t;
  while (t --) {
    long long n, a;
    cin >> n;
    vector<vector<long long>> dp(2, vector<long long>(2, inf));
    cin >> dp[0][0];
    for (int i = 1; i < n; i ++) {
      vector<long long> &cur = dp[i & 1], &pre = dp[~i & 1];
      cin >> a;
      cur[0] = max({pre[1] + a, a, pre[0]});
      cur[1] = max(pre[1], pre[0] - a);
    }
    cout << ranges::max(dp[~n & 1]) << '\n';
  }
}

K小苯的闯关游戏 二分

二分初始战斗力 暴力测试是否能通关 
void K() {
  int t;
  cin >> t;
  while (t --) {
    int n;
    cin >> n;
    vector<int> w(n);
    for (int &x : w) cin >> x;
    int l = *min_element(w.begin(), w.end()), r = *max_element(w.begin(), w.end());
    while (l <= r) {
      int mid = l + (r - l) / 2;
      auto check = [&](int health) {
        int h = health;
        for (int &x : w) {
          if (h > x) h ++;
          else if (h < x) h --;
        }
        return h > health;
      };
      if (check(mid)) {
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    cout << l << '\n';
  }
}

L小苯的序列还原 模拟

打草稿发现数组之间的关系:
原数组从前往后是数组从后往前跳着选再从前往后的结果 
void L() {
  int t;
  cin >> t;
  while (t --) {
    int n;
    cin >> n;
    vector<int> w(n);
    for (int &x : w) cin >> x;
    vector<int> ans(n);
    int i;
    for (i = 0; n - 1 - 2 * i >= 0; i ++) {
      ans[n - 1 - 2 * i] = w[i];
    }
    for (int j = n & 1; i < n; j += 2, i ++) {
      ans[j] = w[i];
    }
    for (int x : ans) cout << x << ' ';
    cout << '\n';
  }
}

MGPA Calculator 模拟

本场最简单的题 直接写关系式即可 
void M() {
  double score, ans;
  cin >> score;
  if (score < 60) ans = 0;
  else ans = 1 + (score - 60) / 10;
  cout << fixed << setprecision(2) << ans << '\n';
}