csp2024赛前集训

caoshurui / 2024-09-25 / 原文

2024-09-22

开题顺序：ABDC

时间分配:A:20min，B:30min，C:1.5h，D:30min，其余时间打摆。

主观难度：绿/1600，蓝/1900，紫/2400，蓝/2100

set

设 $f_{i,j}$ 表示前 $i$ 个数和为 $j$ 的方案数，然后直接 01 背包，最后用快速幂把每种和的数量次方乘起来就行了。由于 $f$ 最后要当指数，所以要 $mod (kM-1)$。

code:

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 205, kM = 998244353;

LL f[kMaxN * kMaxN], n, ans = 1;

LL P(LL x, LL y) {
  LL ans = 1;
  for (LL i = 1; i <= y; i <<= 1, x = x * x % kM) {
    (y & i) && (ans = ans * x % kM);
  }
  return ans;
}

int main() {
  freopen("set.in", "r", stdin);
  freopen("set.out", "w", stdout);
  ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  f[0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = n * n; j >= i; j--) {
      f[j] = (f[j] + f[j - i]) % (kM - 1);
    }
  }
  for (int i = 1; i <= n * n; i++) {
    f[i] && (ans = ans * P(i, f[i]) % kM);
  }
  cout << ans;
  return 0;
}

hire

设当前 $i$ 位置上的人有 $a_i$ 个，考虑到在合法时一定会有一些性质：

\[\forall l,r\in [1,n],l\le r, \sum_{i=l}^{r}a_i\le(r-l+1+d)\times k \]

将其拆开：

\[\sum_{i=l}^{r}a_i\le r\times k-l\times k+k+d\times k \]

\[\sum_{i=l}^{r} (a_i-k)\le k\times d \]

然后直接用线段树维护每个位置的权值为 $a_i-k$ 的序列的全局最大子段和就行。

code:

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 5e5 + 5;

struct T {
  LL s, l, r, ans;

  T() {
    s = l = r = ans = 0;
  }
} w[kMaxN << 2];

LL n, m, k, d;

T Merge(T x, T y) {
  T v;
  v.s = x.s + y.s;
  v.l = max(x.l, x.s + y.l);
  v.r = max(y.r, x.r + y.s);
  v.ans = max({x.ans, y.ans, x.r + y.l});
  return v;
}

void Update(int u, int l, int r, int x, LL y) {
  if (l == r && l == x) {
    w[u].s += y;
    w[u].l = w[u].r = w[u].ans = max(0LL, w[u].s);
  } else if (l > x || r < x) {
    return;
  } else {
    int mid = l + r >> 1;
    Update(u << 1, l, mid, x, y);
    Update(u << 1 | 1, mid + 1, r, x, y);
    w[u] = Merge(w[u << 1], w[u << 1 | 1]);
  }
}

T Query(int u, int l, int r, int L, int R) {
  if (l > R || r < L) {
    T v;
    v.s = v.l = v.r = v.ans = 0;
    return v;
  } else if (L <= l && r <= R) {
    return w[u];
  } else {
    int mid = l + r >> 1;
    return Merge(Query(u << 1, l, mid, L, R), Query(u << 1 | 1, mid + 1, r, L, R));
  }
}

int main() {
  freopen("hire.in", "r", stdin);
  freopen("hire.out", "w", stdout);
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> k >> d;
  for (int i = 1; i <= n; i++) {
    Update(1, 1, n, i, -k);
  }
  for (LL x, y; m; m--) {
    cin >> x >> y;
    Update(1, 1, n, x, y);
    cout << (Query(1, 1, n, 1, n).ans <= k * d ? "YES" : "NO") << "\n";
  }
  return 0;
}

block

这个题状态设计本质和 P6773 的状态设计一样，但赛时并没有看出来。

设 $f_{i,j}$ 表示以 $i$ 为根的子树中选择了的连通块中有限制的点的 $dfn$ 最大值为 $j$ (如果不存在有限制的点在连通块内 $j$ 为 0)，转移找到前一个子树内 $dfn$ 最大的点，然后与当前子树内的 $dfn$ 最大的有限制点判断是否被限制到，没有就算上。

code:

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using Pii = pair<int, int>;

const int kMaxN = 1e5 + 5, kMaxM = 55;
const LL kInf = 1e18;

LL f[kMaxN][kMaxM], a[kMaxN], vis[kMaxN], p[kMaxN], id[kMaxN], c, ans, n, m;
vector<int> g[kMaxN];
set<Pii> s;

void Dfs(int u, int fa) {
  f[u][p[u]] = a[u];
  for (int i : g[u]) {
    if (i != fa) {
      Dfs(i, u);
      LL val = -kInf;
      for (int j = 0; j <= c; j++) {
        !s.count({i, id[j]}) && (val = max(val, f[u][j]));
      }
      for (int j = 0; j <= c; j++) {
        f[u][j] = max(f[u][j], f[i][j] + val);
      }
    }
  }
  for (int i = 0; i <= c; i++) {
    ans = max(ans, f[u][i]);
  }
}

int main() {
  freopen("block.in", "r", stdin);
  freopen("block.out", "w", stdout);
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1, x, y; i <= n; i++) {
    for (cin >> x; x; x--) {
      cin >> y;
      g[i].push_back(y), g[y].push_back(i);
    }
  }
  fill(f[0], f[n + 1], -kInf);
  for (int i = 1, x, y; i <= m; i++) {
    cin >> x >> y;
    vis[x] = vis[y] = 1;
    s.insert({x, y}), s.insert({y, x});
  }
  for (int i = 1; i <= n; i++) {
    vis[i] && (p[i] = ++c, id[c] = i);
  }
  Dfs(1, 0);
  cout << ans;
  return 0;
}

checkers

一开始看见是个数数题感觉是神仙题不太敢做，但看完题好像和 set 所用的大体思想差不多（？

首先考虑没有 ? 时怎么做。设字符串中有 $x$ 个 0，有 $y$ 个 11（比如 '001110' 就有 3 个 0 和 1 个 '11'，最后的那个 '1' 不算），那么方案数就是 $\tbinom{x+y}{x}$。那么就可以用 $f_{i,j,k,0/1,0/1}$ 表示前 $i$ 个字符有 $j$ 个 0，$k$ 个 11，当前这一位是 0/1，这一段 1 的数量有偶数/奇数个。那么就有转移：

当前这一位题目给出的字符不是 1

\[f_{i,j,k,0,0}=f_{i-1,j-1,k,0,0}+f_{i-1,j-1,k,1,0}+f_{i-1,j-1,k,1,1} \]

当前这一位题目给出的字符不是 0

\[f_{i,j,k,1,0}=f_{i-1,j,k-1,1,1} \]

\[f_{i,j,k,1,1}=f_{i-1,j,k,0,0}+f_{i-1,j,k,1,0} \]

这样时间复杂度是 $\operatorname{O}(n^3)$，带 7 倍常数，不过可以加一些减枝：$j\le i,2\times k+j\le i$，最后剪完好像是 $\frac{1}{2}$ 倍常数的。

code:

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 505, kMaxS = 1e3 + 5, kM = 1e9 + 7;

LL f[2][kMaxN][kMaxN][2][2], p[kMaxS], inv[kMaxS], n, ans, op = 1;
// f[i][j][k][0/1][0/1]:前i位有j个0，k对连续的1，当前选0/1，前面有连续偶/奇个1
string s;

LL P(LL x, LL y) {
  LL ans = 1;
  for (LL i = 1; i <= y; i <<= 1, x = x * x % kM) {
    (y & i) && (ans = ans * x % kM);
  }
  return ans;
}

void DpS(int i) {  // 当前选0
  for (int j = 1; j <= i; j++) {
    for (int k = 0; k * 2 + j <= i; k++) {
      f[op][j][k][0][0] += f[op ^ 1][j - 1][k][0][0];
      f[op][j][k][0][0] += f[op ^ 1][j - 1][k][1][0];
      f[op][j][k][0][0] += f[op ^ 1][j - 1][k][1][1];
      f[op][j][k][0][0] %= kM;
    }
  }
}

void DpT(int i) {  // 当前选1
  for (int j = 0; j <= i; j++) {
    for (int k = 0; k * 2 + j <= i; k++) {
      k && (f[op][j][k][1][0] = f[op ^ 1][j][k - 1][1][1]);
      f[op][j][k][1][1] = (f[op ^ 1][j][k][0][0] + f[op ^ 1][j][k][1][0]) % kM;
    }
  }
}

int main() {
  freopen("checkers.in", "r", stdin);
  freopen("checkers.out", "w", stdout);
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> s;
  s = ' ' + s;
  f[0][0][0][0][0] = 1;
  for (int i = 1; i <= n; i++) {
    if (s[i] == '0') {
      DpS(i);
    } else if (s[i] == '1') {
      DpT(i);
    } else {
      DpS(i), DpT(i);
    }
    op ^= 1;
    for (int j = 0; j <= i; j++) {
      for (int k = 0; k * 2 + j <= i; k++) {
        f[op][j][k][0][0] = f[op][j][k][1][0] = f[op][j][k][1][1] = 0;
      }
    }
  }
  p[0] = inv[0] = 1;
  for (int i = 1; i <= n * 2; i++) {
    p[i] = p[i - 1] * i % kM;
    inv[i] = P(p[i], kM - 2);
  }
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      for (int k = 0; k < 2; k++) {
        for (int l = 0; l < 2; l++) {
          ans = (ans + f[n & 1][i][j][k][l] * p[i + j] % kM * inv[i] % kM * inv[j] % kM) % kM;
        }
      }
    }
  }
  cout << ans;
  return 0;
}

2024-09-24

开题顺序：BCAD

时间分配：A 1h，B 1.5h，C 1h，D 0.5h

难度评估：蓝/1700，蓝/2100，紫/2600，蓝/2200

yiyi

非常抽象的博弈论。

首先把 $b=c=0$ 的情况判掉，这时一定是 Second。

那么不难发现，剩下的情况下 $a$ 都只会和先后手顺序有关。考虑到一个人操作序列一定会类似于 $1,1,2,1,2,1,2,1,2,1,\cdots\cdots$ 或 $2,2,1,2,1,2,1,2,\cdots\cdots$，所以直接求出最多操作多少轮，然后按照轮数奇偶性判段即可。

code:

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

LL t, a, b, c;

int main() {
  freopen("yiyi.in", "r", stdin);
  freopen("yiyi.out", "w", stdout);
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  for (cin >> t; t; t--) {
    cin >> a >> b >> c;
    if (!b && !c) {
      cout << "Second\n";
    } else {
      a %= 2;
      bool op = ((1 + (b > c + 1)) % 2 ? c * 2 + 1 : b * 2 - 2) % 2;
      bool _op = ((1 + (c > b + 1)) % 2 ? b * 2 + 1 : c * 2 - 2) % 2;
      if ((b && (op + a) % 2) || (c && (a + _op) % 2)) {
        cout << "First\n";
      } else {
        cout << "Second\n";
      }
    }
  }
  return 0;
}

wuyi

算是比较简单的期望（？，不过赛时因为过于感性的化简式子浪费了一车时间。

枚举第一个 $i>a_i$ 的位置。令 $a_i=j,k=n-i+1$，那么前 $i$ 个数的填数方案如下：

\[\sum_{j=1}^{i-1}(k+1)^{i-j-1}\times k^{j} \]

其中 $k^{j}$ 是因为 $1$ 到 $j$ 都只能填 $k$ 个（对于一个位置 $l$，其能填 $l$ 到 $n$，而其中有 $i-l+1$ 个数已经被用了），$(k+1)^{i-j-1}$类似。

然后大力化简：

\[\sum_{j=1}^{i-1}(k+1)^{i-j-1}\times k^{j}=\frac{k}{k+1} \times (k+1)^{n-k} \sum_{j=0}^{n-k-1}(\frac{k}{k+1})^j \]

用等比数列求和公式化简：

\[=k\times [(k+1)^n-k^{n-k}] \]

然后再乘上后面那些位置的填法，每个位置贡献如下：

\[(n-k+1)\times k!\times [(k+1)^{n-k}-k^{n-k}] \]

然后加上 $\operatorname{val}(p)=n+1$ 时的情况（即所有 $a_i=i$），于是有最终的期望式子：

\[ans=\frac{\sum_{k=1}^{n}(n-k+1)\times k!\times [(k+1)^{n-k}-k^{n-k}]+n+1}{n!} \]

code:

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1e6 + 5, kM = 998244353;

LL p[kMaxN], f[kMaxN], n, ans;

LL P(LL x, LL y) {
  LL ans = 1;
  for (LL i = 1; i <= y; i <<= 1, x = x * x % kM) {
    (y & i) && (ans = ans * x % kM);
  }
  return ans;
}

int main() {
  freopen("wuyi.in", "r", stdin);
  freopen("wuyi.out", "w", stdout);
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  p[0] = 1;
  for (int i = 1; i <= n; i++) {
    p[i] = p[i - 1] * i % kM;
  }
  for (int i = 1; i <= n; i++) {
    ans = (ans + (n - i + 1) * p[i] % kM * (P(i + 1, n - i) - P(i, n - i) + kM) % kM) % kM;
  }
  cout << (ans + n + 1) % kM * P(p[n], kM - 2) % kM;
  return 0;
}

yijiu

赛时因为斐波那契数列预处理项数少了挂了 20pts /fn。

结论：对一个数进行唯一分解的方法从大到小找到最大的那小于当前数并减去所得到的方案一定是不相邻的。

非常经典的结论，在百度随便搜一下应该都有证明。

那么令 $f_i$ 为第 $i$ 项的斐波那契数列，$s_i=s_{i-1} \oplus s_{i-2} \oplus f_{i-2} \oplus f_{i}$，当 $f_{i-2}$ 为偶数的时候还要异或上 $f_{i-1}$。

然后对与一个区间 $[l,r]$ 求答案。令 $L$ 为最小满足 $l\le f_{L}$ 的数， $R$ 为最大的 $f_{R}\le r$ 的数，那么 $[l,r]$ 的答案就是 $[l,f_{L}-1]$ 的答案异或上 $[f_{R}+1,r]$ 的答案再异或上 $s_R \oplus s_L \oplus f_l$（至于为什么是这个式子可以把 $s$ 展开进行证明）。

然后考虑边界条件，此时没有合法的 $L,R$，所以找到最大的 $x$ 使得 $f_{x}<l$，然后递归求 $[l-f_{x},r-f_{x}]$ 的答案，如果 $(r-l+1)$ 是奇数那么还要额外异或上 $f_{x}$。由于在第 87 个斐波那契数就大于 $10^{18}$，所以时间复杂度大概是 $\operatorname{O}(n\log n)$ 的。

code:

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 105;
const LL kInf = 1e18;

LL f[kMaxN], s[kMaxN], cnt = 87, l, r, t;

LL Solve(LL l, LL r) {
  if (l > r) {
    return 0;
  }
  int pl = lower_bound(f + 1, f + cnt + 1, l) - f;
  int pr = upper_bound(f + 1, f + cnt + 1, r) - f - 1;
  if (pl > pr) {
    LL v = (r - l + 1) % 2 * f[pr];
    return Solve(l - f[pr], r - f[pr]) ^ v;
  } else {
    return Solve(l, f[pl] - 1) ^ Solve(f[pr] + 1, r) ^ s[pr] ^ s[pl] ^ f[pl];
  }
}

int main() {
  freopen("yijiu.in", "r", stdin);
  freopen("yijiu.out", "w", stdout);
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  f[1] = 1, f[2] = 2;
  s[1] = 1, s[2] = 3;
  for (int i = 3; i <= cnt; i++) {
    f[i] = f[i - 1] + f[i - 2];
    s[i] = s[i - 1] ^ s[i - 2] ^ f[i - 2] ^ f[i];
    (f[i - 2] % 2 == 0) && (s[i] ^= f[i - 1]);
  }
  for (cin >> t; t; t--) {
    cin >> l >> r;
    cout << Solve(l, r) << "\n";
  }
  return 0;
}

pear

赛时看出来了可能是个同余最短路板子，但考虑到复杂度最坏可能会被卡到 $\operatorname{O}(nm\log m)$，于是没有写。然而正解复杂度是基于随机生成方式的！！！！期望是 $\operatorname{O}(m\log \sqrt{m})$ 的。强烈谴责！！！！

直接求出 $a$ 中的最小值，然后以最小值为模数做同余最短路，然后直接就做完了。

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1e7 + 5;

struct T {
  LL id, x;

  bool operator<(const T &a) const {
    return x > a.x;
  }
};

LL a[kMaxN], dis[kMaxN * 3], v, n, m, seed;
bool vis[kMaxN * 3];
priority_queue<T> q;

void Dijkstra() {
  memset(dis, 0x3f, sizeof(dis));
  for (q.push({0, dis[0] = 0}); q.size();) {
    int x = q.top().id;
    q.pop();
    if (!vis[x]) {
      vis[x] = 1;
      for (int i = 1; i <= n; i++) {
        int nxt = (x + a[i]) % v;
        if (dis[nxt] > dis[x] + a[i]) {
          q.push({nxt, dis[nxt] = dis[x] + a[i]});
        }
      }
    }
  }
}

int main() {
  freopen("pear.in", "r", stdin);
  freopen("pear.out", "w", stdout);
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  v = 2e9;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    v = min(v, a[i]);
  }
  Dijkstra();
  LL ans = 0;
  for (int i = 0; i < v; i++) {
    ans = max(ans, dis[i] - v);
  }
  cout << ans;
  return 0;
}