Codeforces Round 940 (Div. 2) and CodeCraft-23

Luckyblock / 2024-04-22 / 原文

写在前面
A
B
C
D
E
写在最后

写在前面

比赛地址：https://codeforces.com/contest/1957。

大病场妈的

A

签到。

尽可能凑三角形。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    int n; std::cin >> n;
    int cnt[110] = {0};
    for (int i = 1; i <= n; ++ i) {
      int a; std::cin >> a;
      ++ cnt[a];
    }

    int ans = 0;
    for (int i = 1; i <= 100; ++ i) {
      if (cnt[i] >= 3) ans += cnt[i] / 3;
    }
    std::cout << ans << "\n";
  }
  return 0;
}

B

构造。

首先特判 $n=1$。

对于 $n\ge 2$，仅需构造：

\[\begin{cases} a_1 &= 2^{\left\lfloor\log_2 k\right\rfloor} - 1\\ a_2 &= k - a_1\\ a_i &= 0 (3\le i\le n) \end{cases}\]

此时 $a_1 | a_2 | \cdots | a_n$ 中 1 的个数取到上界 $\log_2 k$。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int ans[kN];
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    int n, k; std::cin >> n >> k;

    if (n == 1) std::cout << k << "\n";
    else {
      int l = log2(k);
      std::cout << (1 << l) - 1 << " " << k - (1 << l) + 1 << " ";
      for (int i = 3; i <= n; ++ i) std::cout << 0 << " ";
      std::cout << "\n";
    }
    
  }
  return 0;
}

C

组合数学。

妈的 DP 假了。

放棋子等价于删去矩阵中棋子所在的一行一列。于是根据读入的 $k$ 步先预处理出矩阵还剩下几行几列可填。然后考虑如何求得 $n\times n$ 的空矩阵的方案数 $f_n$。

直觉是考虑每步白棋放在什么位置，然后通过 $f_{n - 1}$ 与 $f_{n - 2}$ 递推求解。然而发现方案数与放置顺序无关，若直接 DP 会难以处理重复的局面。但是发现仅有白棋可能会出现在 $r=c$ 的位置，考虑白棋每步放置的位置，则最终局面可看做选出 $x$ 个 $r=c$ 的位置，再选出 $\frac{n-x}{2}(2 | n-x)$ 个位置来放置白棋的方案数。于是考虑组合意义：

对于 $0\le x\le n, 2 | n - x$，可看做先从矩阵中选出 $x$ 个 $r=c$ 的位置，然后依次从 $(n-x)\times (n - x), (n - x -2)\times (n - x - 2), \cdots, 2\times 2$ 的矩阵中选出一个 $r\not=c$ 的位置，操作之间是无序的，则其对答案的贡献为：

\[{{n}\choose{x}}\times \frac{(n - x)(n-x-1)\times (n - x-2)(n-x-3)\times \cdots }{\left(\frac{n-x}{2}\right)!} \]

递推求上式右侧即可。

又本题钦定了 $\sum n\le 3\times 10^5$，于是对每组数据都直接套用上述组合意义式大力枚举求解 $f_n$ 即可。

总时间复杂度 $O(\sum (n + k))$ 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
const int lim = 3e5;
const LL p = 1e9 + 7;
//=============================================================
LL fac[kN];
//=============================================================
void Init() {
  fac[0] = fac[1] = 1;
  for (int i = 2; i <= lim; ++ i) {
    fac[i] = fac[i - 1] * i % p;
  }
}
LL qpow(LL x_, LL y_) {
  LL ret = 1;
  while (y_) {
    if (y_ & 1) ret = ret * x_ % p;
    x_ = x_ * x_ % p, y_ >>= 1ll;
  }
  return ret;
}
LL C(LL n_, LL m_) {
  if (m_ > n_) return 0;
  return fac[n_] * qpow(fac[m_], p - 2) % p * qpow(fac[n_ - m_], p - 2) % p;
}
LL Solve(int n_) {
  LL ret = 1, s = 1;
  for (int i = 2; i <= n_; i += 2) {
    s = 1ll * (1ll * i * i - i) % p * s % p; 
    LL delta = C(n_, n_ - i) * s % p * qpow(fac[i / 2], p - 2) % p;
    ret += delta, ret %= p;
  }
  return ret;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  Init();

  int T; std::cin >> T;
  while (T --) {
    int n, k; std::cin >> n >> k;
    for (int i = 1; i <= k; ++ i) {
      int x, y; std::cin >> x >> y;
      if (x != y) n -= 2;
      else n -= 1;
    }
    std::cout << Solve(n) << "\n";
  }
  return 0;
}

D

位运算。

感觉比 C 简单呃呃，可能太套路了。

拆一下这个式子，等价于求三元组 $(x, y, z)(x\le y\le z)$ 满足：

\[\left(\bigoplus_{x\le i\le z} a_i \right)\oplus a_y > \left(\bigoplus_{x\le i\le z} a_i \right) \]

异或等价于选择一些位置将它们翻转，则上式成立等价于 $a_y$ 二进制中最高位的 1（即 $\left\lfloor \log_2 a_y \right\rfloor$ 位）在 $\left(\bigoplus_{x\le i\le z} a_i \right)$ 中为 0，则只需检查 $a_x\sim a_z$ 所有数二进制该位为 1 的数的数量是否为偶数。考虑枚举位置 $y$，求合法三元组的数量即求满足条件的区间 $[x, z]$ 的数量。考虑将区间转化为整个数列删去一个前缀删去一个后缀，则仅需考虑整个数列，以及选择的前后缀中该位为 1 的数的奇偶性即可。

考虑预处理 $\operatorname{pre}_{i, j, 0/1}$ 表示前缀 $0 \sim 0, 0\sim 1, 0\sim 2, \cdots 0\sim i$ 中，它们的第 $j$ 位中 1 的个数为偶数/奇数的前缀的个数，同理可预处理 $\operatorname{suf}_{i, j, 0/1}$ 表示后缀 $n + 1\sim n + 1, n\sim n + 1, \cdots i\sim n + 1$ 中，它们的第 $j$ 位中 1 的个数为偶数/奇数的后缀的个数。则有：

若整个数列第 $k = \left\lfloor \log_2 a_y \right\rfloor$ 位为 1 的数量为奇数，则贡献为 $\operatorname{pre}_{y - 1, k, 0}\times \operatorname{suf}_{y + 1, k, 1} + \operatorname{pre}_{y - 1, k, 1}\times \operatorname{suf}_{y + 1, k, 0}$。
若整个数列第 $k = \left\lfloor \log_2 a_y \right\rfloor$ 位为 1 的数量为偶数，则贡献为 $\operatorname{pre}_{y - 1, k, 0}\times \operatorname{suf}_{y + 1, k, 0} + \operatorname{pre}_{y - 1, k, 1}\times \operatorname{suf}_{y + 1, k, 1}$。

枚举每位预处理 $\operatorname{pre}$ 与 $\operatorname{suf}$，然后枚举 $1\le y\le n$ 通过上式计算贡献即可。

总时间复杂度 $O\left(\sum n\log v\right)$ 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, a[kN];
int cntpre[40][kN];
int pre[40][kN][2], suf[40][kN][2];
LL ans;
//=============================================================
void Init() {
  for (int i = 0; i <= 30; ++ i) {
    int s = (1 << i);
    pre[i][0][0] = suf[i][n + 1][0] = 1;
    pre[i][0][1] = suf[i][n + 1][1] = 0;

    for (int j = 1, c = 0; j <= n; ++ j) {
      c += ((a[j] & s) != 0);
      cntpre[i][j] = c;
      pre[i][j][0] = pre[i][j - 1][0] + (c % 2 == 0);
      pre[i][j][1] = pre[i][j - 1][1] + (c % 2 == 1);
    }
    for (int j = n, c = 0; j >= 1; -- j) {
      c += ((a[j] & s) != 0);
      suf[i][j][0] = suf[i][j + 1][0] + (c % 2 == 0);
      suf[i][j][1] = suf[i][j + 1][1] + (c % 2 == 1);
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n;
    for (int i = 1; i <= n; ++ i) std::cin >> a[i];
    Init();

    ans = 0;
    for (int y = 1; y <= n; ++ y) {
      int bit = log2(a[y]);
      int c = cntpre[bit][n];
      int cpre[2] = {pre[bit][y - 1][0], pre[bit][y - 1][1]};
      int csuf[2] = {suf[bit][y + 1][0], suf[bit][y + 1][1]};
      if (c % 2 == 0) {
        ans += 1ll * cpre[0] * csuf[0];
        ans += 1ll * cpre[1] * csuf[1];
      } else {
        ans += 1ll * cpre[0] * csuf[1];
        ans += 1ll * cpre[1] * csuf[0];
      }
    }
    std::cout << ans << "\n";
  }
  return 0;
}