A - Antimedian Deletion

除了 n=1n=1 时答案为 11，其余情况答案均为 22．考虑值 vv，对于其左侧，只要有多于 22 个元素，就一定可以选三个（不选 vv）然后删除一个；当左侧只剩下两个时，如果 vv 大于另外两个，则可以删除最小值，否则可以删除最大值．

于是左右两侧都最多只有一个元素，此时可以同时选这三个数，并删去一个．于是最终答案为 22．

Problem A
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
#include <bits/stdc++.h>

void work() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (auto &x : a)
    std::cin >> x;

  if (n <= 2) {
    for (int i = 0; i < n; i++)
      std::cout << n << " \n"[i == n - 1];
    return;
  }

  for (int i = 0; i < n; i++)
    std::cout << 2 << " \n"[i == n - 1];
}

int main() {
  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0);
  int t;
  std::cin >> t;
  while (t--)
    work();
}

B - Mickey Mouse Constructive

首先当 x=yx=y 时，我们肯定是先全部放 11 然后全部放 −1-1，这样就只有 11 种分隔方案．

接着不妨考虑 x>yx\gt y．按上面的摆法，方案数为 ϕ(x−y)\phi(x-y)，即 (x−y)(x-y) 的因子个数．这个也是最小的．

Problem B
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
#include <bits/stdc++.h>

void work() {
  int x, y;
  std::cin >> x >> y;

  int v = std::abs(x - y);

  int ans = 0;
  if (v != 0) {
    for (int i = 1; i * i <= v; i++)
      if (v % i == 0)
        ans += i * i == v ? 1 : 2;
  } else
    ans = 1;

  std::cout << ans << "\n";
  for (int i = 0; i < x; i++)
    std::cout << 1 << " ";
  for (int i = 0; i < y; i++)
    std::cout << -1 << " ";
  std::cout << "\n";
}

int main() {
  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0);
  int t;
  std::cin >> t;
  while (t--)
    work();
}

C1 - Equal Multisets (Easy Version)

考虑元素 vv 在 aa 数组里的下标为 pp，即 ap=va_p=v．要想满足题目的要求，设 vv 在 b[]b[] 里的下标为 qq，那么对于 b[]b[] 中每一个可以覆盖 pp 的区间，vv 都必须包含在其中．所以，qq 应该是这样的区间的交集，即

q∈⋂l∈[1,n−k+1]p∈[l,r][l,r]q\in \bigcap_{\scriptsize{\begin{aligned}l&\in [1,n-k+1]\\ p&\in [l,r]\end{aligned}}} [l,r]

令 L=n−k+1,R=kL=n-k+1,R=k

  • 如果 L≤RL\le R，对于 p∈[L,R]p\in[L,R] 的元素 apa_p，他们就只能在这个 [L,R][L,R] 区间里重排．对于 [L,R][L,R] 之外的元素，则必须一一对应
  • 如果 L>RL\gt R，说明不是所有的区间都重叠，这个情况下，p=qp=q，即 a,ba,b 必须一一对应．
Problem C1
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
#include <bits/stdc++.h>

void work() {
  int n, k;
  std::cin >> n >> k;

  std::vector<int> a(n + 1), b(n + 1);
  for (int i = 1; i <= n; i++)
    std::cin >> a[i];
  for (int i = 1; i <= n; i++)
    std::cin >> b[i];

  int left = n - k + 1, right = k;
  if (left <= right) {
    bool fixed = true;
    for (int i = 1; i < left; i++)
      fixed &= b[i] == -1 or a[i] == b[i];
    for (int i = right + 1; i <= n; i++)
      fixed &= b[i] == -1 or a[i] == b[i];

    bool same = true;
    std::set<int> f;
    for (int i = left; i <= right; i++)
      f.insert(a[i]);

    int cnt = 0;
    for (int i = left; i <= right; i++) {
      if (b[i] == -1)
        cnt++;
      else if (!f.count(b[i])) {
        fixed = false;
        break;
      } else {
        f.erase(b[i]);
      }
    }
    fixed &= cnt == f.size();
    std::cout << (fixed ? "YES" : "NO") << "\n";
  } else {
    bool fixed = true;
    for (int i = 1; i <= n; i++) {
      fixed &= b[i] == -1 or a[i] == b[i];
    }
    std::cout << (fixed ? "YES" : "NO") << "\n";
  }
}

int main() {
  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0);
  int t;
  std::cin >> t;
  while (t--)
    work();
}

C2 - Equal Multisets (Hard Version)

我们用 WraW_r^a 表示区间 a[r−k+1,r]a[r-k+1,r] 对应的 multiset，因为 Wra=Wrb,Wr−1a=Wr−1bW_r^a=W_r^b,W_{r-1}^a=W_{r-1}^b，所以有

Wra−Wr−1a=Wrb−Wr−1bW_r^a-W_{r-1}^a=W_r^b-W_{r-1}^b

我们考虑把 multiset 看成是代表频率统计的 nn 维向量，用 ex∈Nne_x \in \mathbb{N}^n 表示 cnt[x]=1,cnt[y]=0,y≠xcnt[x]=1,cnt[y]=0,y\ne x．那么 multiset 相减就可以看作向量相减，那么

ear−ear−k=ebr−ebr−k  ⟹  ear−ebr=ear−k−ebr−ke_{a_{r}} - e_{a_{r-k}}=e_{b_r}-e_{b_{r-k}} \\ \implies e_{a_{r}} - e_{b_r}=e_{a_{r-k}}-e_{b_{r-k}}

于是我们可以按下标 mod kk 进行分组处理．在每一组中可以分类讨论：

  1. 如果这一组中，a[]a[] 全相等，那么 b[]b[] 也必须全相等
    1. 如果已有的 b[]b[] 有 ≥2\ge 2 个不同元素，直接不可能
    2. 否则，如果 b[]b[] 有一个元素，那么所有 b[]b[] 就只能是这个元素
    3. 否则 b[]b[] 可以随便填
  2. 否则若 a[]a[] 有不同元素，那么就必须满足 ai=bia_i=b_i，这样所有 ear−ebr=0⃗e_{a_r}-e_{b_r}=\vec{0}．

第一种情况里还有额外需要考虑的：我们现在只考虑第一个窗口 [1,k][1,k]．在 “b[]b[] 被强制填数” 这个情况下，b[]b[] 填的数不受 a[]a[] 控制，于是在第一个窗口里，有可能出现虽然要求的是 aia_i 但是填的是 bi≠aib_i\ne a_i，尽管通过了 eai−ebie_{a_i}-e_{b_i} 全相等的判断，但却是错误的．所以，需要判断一下第一个窗口里填 bib_i 的数量不会超过 aia_i.

Problem C2
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
#include <bits/stdc++.h>

void work() {
  int n, k;
  std::cin >> n >> k;
  std::vector<int> a(n + 1), b(n + 1);

  std::vector<int> src(n + 1, 0), req(n + 1, 0);

  for (int i = 1; i <= n; i++)
    std::cin >> a[i];
  for (int i = 1; i <= n; i++)
    std::cin >> b[i];

  bool ok = true;
  int spare = 0;
  for (int r = 0; r < k; r++) {
    std::multiset<int> d;
    std::vector<int> idx;
    for (int i = 1 + r; i <= n; i += k) {
      d.insert(a[i]);
      idx.push_back(i);
    }

    if (*d.begin() != *d.rbegin()) { // b[i] == a[i] for all i in idx[]
      for (auto i : idx) {
        if (b[i] != -1 and a[i] != b[i]) {
          std::cout << "NO\n";
          return;
        }
      }
    } else {
      src[a[idx[0]]]++;

      std::multiset<int> db;
      for (auto i : idx)
        if (b[i] != -1)
          db.insert(b[i]);

      if (!db.empty() and
          *db.begin() != *db.rbegin()) { // impossible, >= 2 values
        std::cout << "NO\n";
        return;
      }

      if (!db.empty())
        req[*db.begin()]++;
    }
  }

  for (int i = 1; i <= n; i++)
    if (req[i] > src[i]) {
      std::cout << "NO\n";
      return;
    }

  std::cout << "YES\n";
}

int main() {
  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0);
  int t;
  std::cin >> t;
  while (t--)
    work();
}

D - AND-array

思路很好想．看到位运算想拆位拆贡献的做法．假设这 nn 个数在第 pp 位有 cpc_p 个数是 11，那么如果 subsequence 的长度为 kk，这一位的贡献为

(cpk)2p\binom{c_p}{k}2^p

所以答案便是 sum over pp

bk=∑p=0292p(cpk)b_k=\sum_{p=0}^{29} 2^p\binom{c_p}{k}

然而这个 cpc_p 并不好计算．我们换一个思路：把 cpc_p 相同的 pp 提出来，这样就可以 sum over cpc_p 从而消去这个不好枚举的东西：

bk=∑t=0n(tk)(∑p:cp=t2p)=∑t=0n(tk)mt\begin{aligned} b_k&=\sum_{t=0}^n \binom{t}{k} \Big( \sum_{p:c_p=t}2^p \Big)\\ &=\sum_{t=0}^n \binom{t}{k} m_t \end{aligned}

所以，我们倒着枚举 kk，就可以一步一步解出 mn,mn−1,…,m1,m0m_n, m_{n-1},\dots, m_1, m_0．知道 {mt,t}\{m_t,t\} pair 后，就可以构造解了．

Problem D
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>

constexpr int Mod = 1e9 + 7;
constexpr int N = 1e5 + 5;
constexpr int B = 29;

using i64 = long long;

struct mint {
  int v;
  mint() : v(0) {}
  mint(long long _v) : v(_v % Mod) {}
  static mint fpow(mint b, int p) {
    mint res = 1;
    while (p) {
      if (p & 1)
        res *= b;
      b *= b;
      p >>= 1;
    }
    return res;
  }
  static mint inv(mint s) { return fpow(s, Mod - 2); }
  mint operator+(mint r) { return v + r.v >= Mod ? v + r.v - Mod : v + r.v; }
  mint operator+=(mint r) { return *this = *this + r; }
  mint operator-(mint r) { return v < r.v ? v + Mod - r.v : v - r.v; }
  mint operator-=(mint r) { return *this = *this - r; }
  mint operator*(mint r) { return 1ll * v * r.v % Mod; }
  mint operator*=(mint r) { return *this = *this * r; }
  mint operator/(mint r) { return *this * inv(r); }
  mint operator/=(mint r) { return *this = *this / r; }
  friend std::istream &operator>>(std::istream &is, mint &c) {
    return is >> c.v;
  }
  friend std::ostream &operator<<(std::ostream &os, mint c) {
    return os << c.v;
  }
};

std::vector<mint> fac(N, 1), ifac(N, 1);

mint C(int n, int k) {
  if (k < 0 || k > n)
    return 0;
  return fac[n] * ifac[k] * ifac[n - k];
}

void work() {
  int n;
  std::cin >> n;
  std::vector<mint> v(n + 1);
  for (int i = 1; i <= n; i++)
    std::cin >> v[i];

  std::vector<std::pair<int, mint>> have; // {t, m_t}
  std::vector<int> cnt(50, 0);
  for (int k = n; k >= 1; k--) {
    mint sub{0};

    for (auto &[t, mt] : have)
      sub += mt * C(t, k);

    mint mk = v[k] - sub;

    if (mk.v != 0) {
      have.push_back({k, mk});

      for (int p = 0; p < B; p++)
        if (mk.v >> p & 1)
          cnt[p] = k;
    }
  }

  std::vector<int> a(n, 0);
  for (int p = 0; p < B; p++) {
    for (int i = 0; i < cnt[p]; i++)
      a[i] |= 1 << p;
  }

  for (auto x : a)
    std::cout << x << " ";
  std::cout << "\n";
}

int main() {
  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0);
  int t;
  std::cin >> t;

  for (int i = 1; i < N; i++)
    fac[i] = fac[i - 1] * i;
  ifac[N - 1] = mint::inv(fac[N - 1]);
  for (int i = N - 2; i >= 0; i--)
    ifac[i] = ifac[i + 1] * (i + 1);

  while (t--)
    work();
}

E - Minimum Path Cover

我们假设 dp[i]dp[i] 表示覆盖 S(i)S(i) 的最少路径数，且其中恰好有一条经过 ii．对于 good path，我们只需要知道其 gcd 即可．

此外，我们记录 lcm[i]lcm[i] 表示所有达到 dp[i]dp[i] 的方案中，经过 ii 的 good paths 的 gcd 值的 LCM

考虑怎么转移．对于读入的 ax,chx[]a_x, ch_x[]，我们首先判断能不能从某个子节点转移上来，即存在 j∈chx[]j\in ch_x[]，满足 gcd⁡(ax,lcm[j])>1\gcd(a_x, lcm[j])\gt 1．如果存在，那么

dp[x]←∑j∈chx[]dp[j]dp[x]\gets \sum_{j\in ch_x[]} dp[j]\\

lcm[x]lcm[x] 需要记录所有可以达到 dp[x]dp[x] 的方案里，good paths 的 gcd 值的 LCM．所以先求出所有的 lcm[j]lcm[j] 使得 gcd⁡(lcm[j],ax)>1\gcd(lcm[j], a_x)\gt 1，再对这些 lcm[j]lcm[j] 求一个 LCM

lcm[x]←lcmj:gcd⁡(lcm[j],ax)>1(lcm[j])lcm[x]\gets \mathop{\texttt{lcm}}\limits_{j:\gcd(lcm[j],a_x)\gt 1}(lcm[j])

否则，如果不能从子节点转移上来，那么 xx 自己就必须是单独一条 good path，于是

dp[x]←1+∑j∈chx[]dp[j]lcm[x]←axdp[x]\gets 1+ \sum_{j\in ch_x[]} dp[j]\\ lcm[x]\gets a_x

Problem E
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
#include <bits/stdc++.h>

using i64 = long long;

void work() {
  int n;
  std::cin >> n;

  std::vector<i64> dp(n + 1, 0), lcm(n + 1, 0), ans(n + 1, 0);
  for (int i = n; i >= 1; i--) {
    i64 a;
    int k;
    std::cin >> a >> k;

    i64 sum = 0, curlcm = 1;
    for (int t = 0, c; t < k; t++) {
      std::cin >> c;
      sum += dp[c];

      i64 g = std::gcd(a, lcm[c]);
      if (g > 1)
        curlcm = std::lcm(curlcm, g);
    }

    if (curlcm == 1) {
      dp[i] = 1 + sum;
      lcm[i] = a;
    } else {
      dp[i] = sum;
      lcm[i] = curlcm;
    }

    ans[i] = dp[i];
    std::cout << ans[i] << std::endl;
  }
}

int main() {
  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0);
  int t;
  std::cin >> t;
  while (t--)
    work();
}
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。