AtCoder Regular Contest 148（ARC148）C、D 题解

C - Lights Out on Tree

#题型/构造

分析

• 看到每次给一个点集然后保证点集大小总和的形式还以为是虚树。
• 如果一个子树内乱七八糟的颜色不统一那不管怎么翻根节点都翻不成一个颜色吧？
• 所以得先统一一个子树内的颜色弄成和根节点一样再翻根节点。
• 手玩发现其实只有两种情况。考虑某个黑色的根节点，如果根节点的某一个儿子本身就是黑色，那就等这个儿子的子树全变黑了再操作；如果某一个儿子是白色，得等这个儿子的子树全变白了再翻一次这个儿子。

• 子树变白或者变黑的操作就放到子树那里计数，对于根节点需要新增的操作数量就是白点儿子数量 + 1（最后自己再翻一次）。
• 整个过程都可以换成 DP，所以这么做肯定操作次数最少。

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int n, Q, a[N], p[N], cnt[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> Q;
  for(int i = 2; i <= n; i++) {
    cin >> p[i];
    ++cnt[p[i]];
  }
  for(int i = 1, m; i <= Q; i++) {
    cin >> m;
    vector<int> arr;
    int ans = 0;
    for(int j = 1, v; j <= m; j++) {
      cin >> v;
      a[v] = 1;
      arr.emplace_back(v);
      ans += cnt[v] + 1;
    }
    for(int x : arr)
      if(a[p[x]]) ans -= 2;
    cout << ans << '\n';
    for(int x : arr) a[x] = 0;
  }
 
 return 0;
}

D - Mod M Game

#题型/博弈游戏

分析

• 容易发现如果对于每一个不同的数，出现的次数为偶数，那么肯定 Bob 胜。
• 然后就没思路了。

看题解后分析

• 考虑缩小问题结构，设 Alice 和 Bob 已经选的数和分别为 ，还剩下两个数 。如果 Alice 获胜则有 且 。那么 Alice 获胜的必要条件是 （注意是必要条件，也就是说满足这个性质不一定 Alice 必胜，但是不满足 Alice 一定不胜，在我们没思路的情况下可以考虑猜测必要条件后面可以证明转化成充要条件）。
• 由 推出 ，也就是 或 。
• 猜想整个序列除了 的 pair 就是 的 pair，而 的 pair 还一定是偶数对？
• 这竟然是对的。
• 要证明的话只需在不满足上述条件的情况为 Alice 构造必胜策略，因为 Bob 在满足条件的情况显然必胜。称 和 这两种为配对上的 pair，那么 Alice 只需最开始在没配对的 pair 里选一个数，然后根据 Bob 的选择进行选择。如果 Bob 选择了配对上的 pair 里面的数，那 Alice 也选配对上的；如果 Bob 选没配对上的，那么 Alice 也选没配上的。如果总共就只有一对没配对上的数，也就是 ，那么 Alice 最开始不管选择 中的那个数肯定都能赢。如果没配对上的数至少有两对，那么在按照上述策略选择到还剩下 1 对没配对上的数时，除了这对数 Alice 选择的和 以及 Bob 选择的和 是可以算出的。那么选择这对数中不会输的那个即可。

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int n, D, a[2 * N];
multiset<int> s;

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> D;
  for(int i = 1; i <= 2 * n; i++) {
    cin >> a[i];
    s.insert(a[i]);
  }
  int cnt1 = 0, cnt2 = 0, k = (D + 1) / 2;
  for(int i = 1; i <= 2 * n; i++) {
    if(s.find(a[i]) == s.end()) continue;
    s.erase(s.find(a[i]));
    if(s.find(a[i]) != s.end()) {
      s.erase(s.find(a[i]));
      ++cnt1;
    } else if(s.find((a[i] + k) % D) != s.end()) {
      s.erase(s.find((a[i] + k) % D));
      ++cnt2;
    }
  }
  if(cnt2 % 2 == 0 && cnt1 + cnt2 == n) cout << "Bob\n";
  else cout << "Alice\n";
 
 return 0;
}

E - ≥ K

#题型/计数 #数学/组合数学/圆排列

做法

• 先加一个数 变成圆排列，最后钦定这个 右边的数是序列的开头即可。
• 考虑给最小的数 两边放上钦定的数来满足条件。记使得 成立的 的数量为 ，那么选择方案数显然是 。
• 然后把 删去，放入新数 ，因为把这 3 个数绑定在一起后放在圆上的哪个位置都可以。
• 可重集排列要除掉 ，但注意人为放进去的多个 不能视作同一个数。

代码

非常的丑陋，为了求 rank 把 pb_ds 的比较策略改成了 less_equal<int>，但这样 lower_bound 找到的就是大于 key 的第一个元素了。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <atcoder/modint.hpp>

using namespace std;
using namespace __gnu_pbds;
const int N = 2e5 + 5;
int n, k, a[N];
typedef atcoder::modint998244353 mint;
tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> s;
tree<int, int> cnt;
mint fac[N], ans = 1;

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> k;
  fac[0] = 1;
  for(int i = 1; i <= n + 1; i++) fac[i] = fac[i - 1] * i;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    s.insert(a[i]);
    ++cnt[a[i]];
  }
  s.insert(INT_MAX);
  while(!s.empty()) {
    int u = *s.begin();
    if(u >= (k + 1) / 2) break;
    int c = s.size() - s.order_of_key(k - u);
    // 只剩两个数了也是可以的
    if(s.size() > 2) ans *= c, ans *= c - 1;
    s.erase(s.begin());
    auto it = s.lower_bound(k - u);
    // 用 less_equal 作为比较规则会导致 lower_bound 找到的实际是大于 key 的第一个元素
    if(it != s.begin() && *prev(it) >= k - u) it = prev(it);
    if(it != s.end()) s.erase(it);
    it = s.lower_bound(k - u);
    if(it != s.begin() && *prev(it) >= k - u) it = prev(it);
    if(it != s.end()) s.erase(it);
    s.insert(INT_MAX);
  }
  ans = ans * fac[s.size()] / s.size();
  for(auto [u, c] : cnt) ans /= fac[c];
  cout << ans.val() << endl;
 
  return 0;
}