跳到主要内容

AtCoder Beginner Contest 179

Problem A - Plural Form​

直接实现逻辑即可。时间复杂度为O(∣S∣)O(|S|)。

参考代码 （Python 3）
s = input()
print(s + ('s' if s[-1] != 's' else 'es'))

Problem B - Go to Jail​

按要求计数即可。时间复杂度为O(N)O(N)。

参考代码 （Python 3）
n = int(input())
cnt = 0
ok = False
for _ in range(n):
    x, y = map(int, input().split())
    if x == y:
        cnt += 1
        if cnt >= 3:
            ok = True
    else:
        cnt = 0
print('Yes' if ok else 'No')

Problem C - A x B + C​

固定CC，符合条件的二元组(A,B)(A, B)的数目就等于N−CN-C的因子数，而一个正整数的因子数可以通过质因数分解求得。

设

n=p1a1p2a2…pkakn=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}

则其因子数为

∏i=1k(ai+1)\prod_{i=1}^k(a_i+1)

所以我们就计算1…N−11\dots N-1每个数的因子数，然后求和即可。

因为[1,x][1,x]范围内的质数个数近似为xln⁡x\frac{x}{\ln x}，总时间复杂度为O(NNlog⁡N)O(\frac{N\sqrt{N}}{\log N})。

参考代码 （C++）
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> primes = {2, 3, 5, 7, 11, 13};
  for (int i = 17; i <= n - 1; i += 2) {
    bool is_prime = true;
    for (int j = 0; primes[j] * primes[j] <= i; ++j) {
      if (i % primes[j] == 0) {
        is_prime = false;
        break;
      }
    }
    if (is_prime)
      primes.emplace_back(i);
  }
  int ans = 0;
  for (int i = 1; i < n; ++i) {
    int k = i;
    int fac = 1;
    for (int j = 0; primes[j] * primes[j] <= k; ++j) {
      if (k % primes[j] == 0) {
        int cnt = 0;
        while (k % primes[j] == 0)
          cnt++, k /= primes[j];
        fac *= (cnt + 1);
      }
    }
    if (k != 1)
      fac *= 2;
    ans += fac;
  }
  cout << ans;
}

Problem D - Leaping Tak​

考虑我们当前处在xx位置，我们上一步可能来自哪里？

我们需要检查所有的区间，然后找出对应的区间[l,r][l,r]（如果这样的区间存在的话），这一区间包含了所有能够利用原区间中的步长跳跃到当前位置的位置，也即上一步可能的位置。接下来我们将sum(l,r)sum(l,r)累加到dp[x]dp[x]上。

因为我们需要快速计算sum(l,r)sum(l,r)，所以实际上我们可以使用前缀和sum[i]sum[i]，而非dp[i]dp[i]。

时间复杂度为O(NK)O(NK)。

参考代码 （C++）
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
const ll MOD = 998244353;

int main() {
  int n, k;
  cin >> n >> k;
  vector<pair<int, int>> v(k);
  for (int i = 0; i < k; ++i)
    cin >> v[i].first >> v[i].second;
  vector<ll> sum(n + 1);
  sum[1] = 1;
  for (int i = 2; i <= n; ++i) {
    ll curr = 0;
    for (int j = 0; j < k; ++j) {
      if (v[j].first >= i)
        continue;
      int l = max(1, i - v[j].second);
      int r = i - v[j].first;
      curr += sum[r] - sum[l - 1];
    }
    curr %= MOD;
    if (curr < 0)
      curr += MOD;
    sum[i] = (sum[i - 1] + curr) % MOD;
  }
  ll ans = sum[n] - sum[n - 1];
  if (ans < 0)
    ans += MOD;
  cout << ans;
}

Problem E - Sequence Sum​

显然，操作足够多次后，一定会开始循环。因为M≤105M\leq10^5，所以循环的长度不超过10510^5，因此我们直接模拟找出循环节即可。

需要注意的是，循环节的起点未必是XX。

总时间复杂度为O(M)O(M)。

参考代码 （C++）
#include <iostream>
#include <map>
#include <vector>

using namespace std;
typedef long long ll;
int main() {
  ll n, x, m;
  cin >> n >> x >> m;
  map<ll, int> mp;
  int idx = 0;
  vector<ll> path;
  do {
    mp[x] = idx++;
    path.emplace_back(x);
    x = x * x % m;
  } while (!mp.count(x));
  int start = mp[x];
  int len = idx - start;
  ll sum = 0;
  for (int i = start; i < idx; ++i)
    sum += path[i];
  ll ans = 0;
  if (n < start) {
    for (int i = 0; i < n; ++i)
      ans += path[i];
  } else {
    for (int i = 0; i < start; ++i)
      ans += path[i];
    ll loop = (n - start) / len;
    ans += loop * sum;
    ll rem = (n - start) % len;
    for (int i = 0; i < rem; ++i)
      ans += path[start + i];
  }
  cout << ans;
}

Problem F - Simplified Reversi​

当我们放一个白石头的时候，会改变多少黑石头的颜色？

对于第一种操作，这是由该列最上面的白石头决定的；对于第二种操作，这是由该行最左边的白石头决定的。

而每种操作的影响是什么呢？第一种操作会影响1…X1\dots X行（XX是操作的列最上面的白石头所在的行），而第二种操作会影响1…X1\dots X列（XX是操作的行最左边的白石头所在的列）。

很自然地想到用线段树来处理。一个储存每行最上面的白石头，另一个储存每列最左边的白石头。对于非叶结点，我们存储区间的最大值。因为我们每次操作相当于一个切割，把所有大于XX的数都变为XX，因此，存储区间最大值，可以让我们很方便地判断当前的切割是否产生了影响。

时间复杂度为O(Qlog⁡N)O(Q\log N).

参考代码 （C++）
#include <iostream>
#include <vector>
#define MAXN 200005
#define lson (idx << 1)
#define rson (idx << 1 | 1)

using namespace std;
typedef long long ll;

struct Node {
  int l, r, hi, lazy = 0;
};

struct SegTree {
  Node s[MAXN << 2];
  void calc(int idx) { s[idx].hi = max(s[lson].hi, s[rson].hi); }

  void pushdown(int idx) {
    if (s[idx].lazy) {
      for (int i = lson; i <= rson; ++i) {
        if (s[i].hi > s[idx].lazy) {
          s[i].hi = s[idx].lazy;
          s[i].lazy = s[idx].lazy;
        }
      }
    }
    s[idx].lazy = 0;
  }

  void build(int idx, int l, int r, vector<int> &a) {
    s[idx].l = l, s[idx].r = r;
    if (l == r) {
      s[idx].hi = a[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid, a);
    build(rson, mid + 1, r, a);
    calc(idx);
  }

  void update(int idx, int l, int r, int x) {
    if (s[idx].hi <= x)
      return;
    if (s[idx].l >= l && s[idx].r <= r) {
      s[idx].hi = x;
      s[idx].lazy = x;
      return;
    }
    pushdown(idx);
    int mid = (s[idx].l + s[idx].r) >> 1;
    if (l <= mid)
      update(lson, l, r, x);
    if (mid + 1 <= r)
      update(rson, l, r, x);
    calc(idx);
  }

  int query(int idx, int l, int r) {
    if (s[idx].l >= l && s[idx].r <= r)
      return s[idx].hi;
    pushdown(idx);
    int ans = 0;
    int mid = (s[idx].l + s[idx].r) >> 1;
    if (l <= mid)
      ans = max(ans, query(lson, l, r));
    if (mid + 1 <= r)
      ans = max(ans, query(rson, l, r));
    return ans;
  }
};

int main() {
  int n, q;
  cin >> n >> q;
  vector<int> col(n + 1, n), row(n + 1, n);
  col[n] = 1, row[n] = 1;
  SegTree C, R;
  C.build(1, 1, n, col);
  R.build(1, 1, n, row);
  ll ans = (ll)(n - 2) * (n - 2);
  for (int i = 0; i < q; ++i) {
    int t, x;
    cin >> t >> x;
    if (t == 1) {
      int hi = C.query(1, x, x);
      ans -= hi - 2;
      R.update(1, 1, hi, x);
      C.update(1, x, x, 1);
    } else {
      int hi = R.query(1, x, x);
      ans -= hi - 2;
      C.update(1, 1, hi, x);
      R.update(1, x, x, 1);
    }
  }
  cout << ans;
}