ABC179-AK记

vp 赛时 AK！

A - Plural Form

考虑直接判断字符串结尾

// BLuemoon
#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using DB = double;

const int kMaxN = 2e5 + 5;

string s;

void pr(bool pr) {
  cout << (pr ? "Yes" : "No") << '\n';
}

int main() {
  cin >> s;
  cout << s << (s[s.size() - 1] == 's' ? "es" : "s") << '\n';
  return 0;
}

B - Go to Jail

考虑直接暴力判断

// BLuemoon
#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using DB = double;

const int kMaxN = 1e2 + 5;

int n, a[kMaxN], b[kMaxN];
bool ans;

void pr(bool pr) {
  cout << (pr ? "Yes" : "No") << '\n';
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
  }
  for (int i = 2; i < n; i++) {
    if (a[i - 1] == b[i - 1] && a[i] == b[i] && a[i + 1] == b[i + 1]) {
      ans = 1;
      break;
    }
  }
  pr(ans);
  return 0;
}

C - A x B + C

考虑只要 \(A \times B < N\)，就可以找到唯一存在的 \(C\)。

枚举 \(A\)，找满足条件的 \(B\) 的数量。

// BLuemoon
#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using DB = double;

const int kMaxN = 2e5 + 5;

int n;
LL ans;

void pr(bool pr) {
  cout << (pr ? "Yes" : "No") << '\n';
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    ans += (n - 1) / i;
  }
  cout << ans << '\n';
  return 0;
}

D - Leaping Tak

考虑 dp。

令 \(dp_i\) 为到 \(i\) 个点的方案数。因为 \(k \le 10\)，我们可以存下 \(dp\) 数组的前缀和，对于每个区间直接调用前缀和计算和即可

// BLuemoon
#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using DB = double;

const int kMaxN = 2e5 + 5;
const LL kP = 998244353;

int n, k, l[kMaxN], r[kMaxN];
LL s[kMaxN], dp[kMaxN];
bitset<kMaxN> v;

void pr(bool pr) {
  cout << (pr ? "Yes" : "No") << '\n';
}

int main() {
  cin >> n >> k;
  for (int i = 1; i <= k; i++) {
    cin >> l[i] >> r[i];
  }
  dp[1] = s[1] = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      (dp[i] += s[max(0, i - l[j])] - s[max(0, i - r[j] - 1)]) %= kP;
      (dp[i] += kP) %= kP;
    }
    s[i] = (s[i - 1] + dp[i]) % kP;
  }
  cout << dp[n] << '\n';
  return 0;
}

E - Sequence Sum

This

F - Simplified Reversi

考虑人类智慧

我们存下当前行/列会改到哪个点，直接更改答案即可，因为只有需要更新时才会进行 fill，所以时间复杂度为 \(O(n+q)\)

// BLuemoon
#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using DB = double;

const int kMaxN = 2e5 + 5;

int n, q, r[kMaxN], c[kMaxN], f, L, R, op, g;
LL ans;

void pr(bool pr) {
  cout << (pr ? "Yes" : "No") << '\n';
}

int main() {
  for (cin >> n >> q, ans = 1ll * (n - 2) * (n - 2); q; q--) {
    (f == 0) && (fill(r + 1, r + n + 1, n), fill(c + 1, c + n + 1, n), f = 1, L = R = n);
    cin >> op >> g;
    if (op == 1) {
      (g < L) && (fill(r + g, r + L + 1, R), L = g), ans -= r[g] - 2;
    } else {
      (g < R) && (fill(c + g, c + R + 1, L), R = g), ans -= c[g] - 2;
    }
  }
  cout << ans << '\n';
  return 0;
}