以下仅为个人验题时所写，如果（现在无法通过/有bug/做法假了……）纯属本人菜。

  • 代码缺省，-std=gun++14 -O2可以通过。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>

#if defined(KENSHIN)
  #define DBG_MACRO_NO_WARNING
  #include "dbg/dbg.h"
#else
  #define dbg(...) (__VA_ARGS__)
#endif

using i64 = int64_t;

auto solve() -> void {
  
}

auto main() -> int {
  std::ios_base::sync_with_stdio(false);
  std::cin.exceptions(std::istream::failbit);
  std::cin.tie(nullptr);

  std::cout << std::fixed << std::setprecision(15);

  int TestCase = 1;
  // std::cin >> TestCase;
  while (TestCase--) solve();

  return 0;
}

A 牌堆 2

  • 模拟$\gcd$的过程即可。

B 子串查询 2

没看懂题，修改过题面了，还没看
好长，老年人就不折腾了~

C 彻底疯狂 2

  • 首先对rating桶排，如此保证rating不重复。
  • 枚举的过程中，选取当前题目$r_i,t_i$的情况下，分别在$r_i$的左右两侧选一个数。如此选择，显然可以保证不重不漏。

$$ \begin{aligned} numL &:= rating<r_i的题目个数 \newline numR &:= rating>r_i的题目个数 \newline cntL[x] &:= rating<r_i且tag=x的题目个数 \newline cntR[x] &:= rating>r_i且tag=x的题目个数 \end{aligned} $$

方案数为：$$(numL-cntL[t_i])\times(numR-cntR[t_i])-\sum_{x\neq t_i}cntL[x]\times cntR[x]$$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

auto solve() -> void {
  int n;
  std::cin >> n;

  std::vector<std::pair<int, int>> p(n);
  for (int i = 0; i < n; i++) {
    std::cin >> p[i].first >> p[i].second;
  }

  static constexpr int N = 200'000 + 1;
  std::array<int, N> cntL{}, cntR{};
  int numL = 0, numR = n;
  for (int i = 0; i < n; i++) cntR[p[i].second] += 1;

  std::sort(begin(p), end(p));
  i64 ans = 0, S = 0;
  for (int l = 0, r = l; l < n; l = r) {
    while (r < n and p[r].first == p[l].first) r += 1;
    for (int i = l; i < r; i++) {
      cntR[p[i].second] -= 1;
      S -= cntL[p[i].second];
      numR -= 1;
    }
    for (int i = l; i < r; i++) {
      ans += numL * 1LL * numR;
      ans -= cntL[p[i].second] * 1LL * (numR - cntR[p[i].second]);
      ans -= cntR[p[i].second] * 1LL * (numL - cntL[p[i].second]);
      ans -= S;
    }
    for (int i = l; i < r; i++) {
      cntL[p[i].second] += 1;
      S += cntR[p[i].second];
      numL += 1;
    }
  }
  std::cout << ans << "\n";
}

D 网格问题 2

  • 容易想到dp：
    • dpR[i][j]表示以$(i,j)$为阶梯的首个节点且下一个节点在其右侧。
    • dpD[i][j]表示以$(i,j)$为阶梯的首个节点且下一个节点在其下方。
  • 每次翻转操作仅影响$\mathcal{O}(n)$的节点的dp值，时间复杂度$\mathcal{O}(nq)$。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

auto solve() -> void {
  int n, m, q;
  std::cin >> n >> m >> q;

  std::vector<std::vector<int>> Mp(n + 2, std::vector<int>(m + 2));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) Mp[i][j] = 1;
  }

  std::vector<std::vector<i64>> dpR(n + 2, std::vector<i64>(m + 2));
  std::vector<std::vector<i64>> dpD(n + 2, std::vector<i64>(m + 2));
  const auto DP = [&](const int &i, const int &j) {
    if (Mp[i][j] == 0) {
      dpR[i][j] = dpD[i][j] = 0;
    } else {
      dpR[i][j] = dpD[i][j] = 1;
      if (Mp[i][j + 1] == 1) dpR[i][j] += dpD[i][j + 1];
      if (Mp[i + 1][j] == 1) dpD[i][j] += dpR[i + 1][j];
    }
  };

  i64 ans = 0;
  for (int i = n; i >= 1; i--) {
    for (int j = m; j >= 1; j--) {
      DP(i, j);
      ans += dpR[i][j] + dpD[i][j] - (Mp[i][j] == 1);
    }
  }

  const auto flip = [&](const int &i, const int &j) {
    const auto modify = [&](const int &x, const int &y) {
      if (x <= 0 or y <= 0) return;
      ans -= dpR[x][y] + dpD[x][y] - (Mp[x][y] == 1);
      if (x == i and y == j) Mp[x][y] ^= 1;
      DP(x, y);
      ans += dpR[x][y] + dpD[x][y] - (Mp[x][y] == 1);
    };
    for (int ii = i, jj = j; ii >= 1 and jj >= 1; ii--, jj--) {
      modify(ii, jj);
      modify(ii, jj - 1);
      modify(ii - 1, jj);
    }
  };

  while (q--) {
    int r, c;
    std::cin >> r >> c;
    flip(r, c);
    std::cout << ans << "\n";
  }
}

E 树の联结 2

  • 容易想到，按照树的外围节点$(\mathrm{degree}=1)$一层层删点，最终剩余一条链的时候即可连接首尾摧毁整颗树。
  • 判断链的方法为：有不超过$2$个节点的$\mathrm{degree}=1$。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

auto solve() -> void {
  int n;
  std::cin >> n;

  std::vector<std::vector<int>> tree(n);
  for (int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    --u, --v;
    tree[u].emplace_back(v);
    tree[v].emplace_back(u);
  }
  std::vector<int> deg(n), seq;
  for (int i = 0; i < n; i++) {
    deg[i] = (int)tree[i].size();
    if (deg[i] == 1) seq.emplace_back(i);
  }
  int ans = 0;
  while (true) {
    if ((int)seq.size() <= 2) {
      return std::cout << ans << "\n", void();
    }
    std::vector<int> nseq;
    for (const int &u : seq) {
      for (const int &v : tree[u]) {
        if (--deg[v] == 1) nseq.emplace_back(v);
      }
      deg[u] = 0;
    }
    ans += 1;
    seq = nseq;
  }
  assert(false);
}

F 彭彭和佳佳 2

  • 鼓励值的表达式很经典 $$\sum_{i=1}^{x-1}\sum_{j=i+1}^{x}v_{p_i}v_{p_j}=\frac{\left(\sum_{i=1}^{x}v_{p_i}\right)^2-\sum_{i=1}^{x}v_{p_i}^2}{2}$$
  • 由于$n,k$均不大，直接考虑背包维护： $$ \begin{aligned} way[i][S] &:= 前i个数，体积为S的方案数 \newline val[i][S] &:= 前i个数，体积为S时，\sum v^2的总和 \end{aligned} $$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

using mint = LazyMontgomeryModInt<998'244'353>;

auto solve() -> void {
  int n, k;
  std::cin >> n >> k;

  std::vector<int> snack(n);
  for (auto &&v : snack) std::cin >> v;

  std::vector<mint> way(k + 1);
  std::vector<mint> val(k + 1);
  way[0] = mint(1);

  for (const int &v : snack) {
    auto nway = way;
    auto nval = val;
    for (int s = 0; s <= k; s++) {
      if (s >= v) {
        nway[s] += way[s - v];
        nval[s] += (val[s - v] + way[s - v] * v * v);
      }
    }
    way = nway;
    val = nval;
  }

  mint ans = 0;
  for (int i = 1; i <= k; i++) {
    ans += (way[i] * i * i - val[i]) / 2;
    std::cout << ans << " \n"[i == k];
  }
}

G 辜辜的多项式 2

  • 素数筛求出$1$到$n$之间的素数。
  • 题目暗示，多项式。
  • 把素数作为指数。$a,b,c$成等差，$a+c=2b$在指数上如何体现？
  • 当然，本题直接打表也可以通过。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

using fps = FormalPowerSeries<mint>;

auto solve() -> void {
  int n;
  std::cin >> n;

  std::vector<bool> isPrime(n + 1, true);
  std::vector<int> prime;
  for (int x = 2; x <= n; x++) {
    if (isPrime[x]) {
      prime.emplace_back(x);
      for (int y = x * 2; y <= n; y += x) {
        isPrime[y] = false;
      }
    }
  }

  if (prime.size() <= 2) {
    std::cout << "0\n";
    return;
  }

  fps fp(prime.back() + 1);
  for (const int &p : prime) fp[p] = 1;
  auto fp2 = fp * fp;
  i64 ans  = 0;
  for (const int &p : prime) {
    if (2 * p < (int)fp2.size()) {
      ans += fp2[p * 2ULL].get() - 1LL * fp[p].get() * fp[p].get();
    }
  }
  std::cout << ans / 2 << "\n";
}

H Alice and Bob 2

  • 仅有$2^{16}$种状态（最后两个数不影响胜败结果），直接预处理即可。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

auto solve() -> void {
  static const auto buildSG = []() {
    constexpr int M = 16, MASK = (1 << M) - 1;
    std::bitset<MASK + 1> res;
    for (int s = 1; s <= MASK; s++) {
      for (int h = M - 1; h >= 0; h--) {
        if ((s >> h & 1) == 0) continue;
        auto t = s ^ (1 << h);

        if (res.test(t) == false) {
          res.set(s, true);
          goto NEXT;
        }

        for (int i = h - 1; i >= 0; i--) {
          if (res.test(t ^ (1 << i)) == false) {
            res.set(s, true);
            goto NEXT;
          }

          for (int j = i - 1; j >= 0; j--) {
            if (res.test(t ^ (1 << i) ^ (1 << j)) == false) {
              res.set(s, true);
              goto NEXT;
            }
          }
        }
      }
    NEXT:;
    }
    return res;
  };
  static auto SG = buildSG();

  int n;
  std::cin >> n;
  int state = 0;
  for (int i = n - 1; i >= 0; i--) {
    int bit;
    std::cin >> bit;
    state |= bit << i;
  }
  std::cout << (SG.test(state >> 2) ? "Alice" : "Bob") << "\n";
}

I 想找 chd44 玩 2

  • 计算几何，求点和线段的距离。HDU多校刚出过。

J 炼铜术士杜学长 2

  • 使用二分（之前也出过类似的，在超大具有单调性的矩阵中寻找第k大的题目）
  • Meet in the Middle
  • 把$n(\leq 32)$拆成两半，每一半均可使用二进制枚举出所有集合。
  • check: 由于体积很小，直接枚举即可。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

auto solve() -> void {
  int n, k;
  std::cin >> n >> k;

  std::vector<i64> w(n);
  for (auto &&wi : w) std::cin >> wi;

  if (static_cast<i64>(k) > (1LL << n)) {
    std::cout << "-1\n";
    return;
  }

  if (k == 1) {
    std::cout << "0\n";
    return;
  }

  const auto work = [&w](const int &M) {
    std::vector<std::vector<i64>> res(M + 1);
    std::vector<i64> S(1 << M);
    for (int i = 0; i < M; i++) S[1 << i] = w[i];
    for (int state = 1; state < (1 << M); state++) {
      S[state] = S[state ^ (state & -state)] + S[state & -state];
    }
    for (int i = 0; i < (1 << M); i++) {
      res[__builtin_popcount(i)].emplace_back(S[i]);
    }
    for (auto &&v : res) std::sort(begin(v), end(v));
    return res;
  };

  const auto A = work(n / 2);
  std::reverse(begin(w), end(w));
  const auto B = work(n - n / 2);

  const auto count = [&](const int &val) -> i64 {
    if (val == 0) return 1;
    i64 res = 1;
    for (int siz = 1; siz <= n; siz++) {
      const i64 LIM = val * 1LL * siz;
      for (int i = 0; i < (int)A.size(); i++) {
        int j = siz - i;
        if (j < 0 or j >= (int)B.size()) continue;
        int h = (int)B[j].size() - 1;
        for (const i64 &x : A[i]) {
          while (h >= 0 and B[j][h] + x > LIM) h -= 1;
          if (h == -1) break;
          res += h - 0 + 1;
        }
      }
    }
    return res;
  };

  int l = 1, r = int(1E9), ans = -1;
  while (l <= r) {
    int m = (l + r) >> 1;

    auto Leq = count(m);
    auto Eq  = Leq - count(m - 1);

    if (Leq >= k) {
      if (Leq - Eq >= k) {
        r = m - 1;
      } else {
        ans = m;
        break;
      }
    } else {
      l = m + 1;
    }
  }
  std::cout << ans << "\n";
}

K Sum of Subset XOR

  • 对于每个比特位可以分开考虑。
  • 考虑XOR的特性，选择奇数个1bit，0bit可以选任意个数。