2021高一有基础省选模拟赛

或许最大的敌人是自己吧。

3.4 / 模拟赛 1

T1 「2017 山东二轮集训 Day1」第二题

题目描述

有 $n$ 个整数 $H_i$ 代表按顺序排列着 $n$ 栋高 $H_i$ 的楼。你每次可以带 $k$ 块砖，可以向左，向右，向上走（注意不能下）。你甚至可以悬空。但你到过的地方必须有砖头。求最小的搭建次数。

思路

贪心策略一定是按片搭，先考虑搭高的，然后把多余的向左右匀。

对应成代码就是递归建笛卡尔树的过程。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();}
  return x * f;
}
void print_n(long long x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(long long x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 1e5 + 10;
using namespace std;
typedef long long ll;

int stc[Maxn], top, fa[Maxn], siz[Maxn];
vector <int> g[Maxn];

long long a[Maxn], s[Maxn], ans, k;

void solve(int x) {
  siz[x] = 1;
  for (int y : g[x]) solve(y), siz[x] += siz[y], s[x] += s[y];
  s[x] += 1ll * siz[x] * (a[x] - a[fa[x]]);
  if (s[x] > 0) {
    ll val = (s[x] - 1) / k + 1; ans += val, s[x] -= val * k;
  }
}

signed main() {
  int n = read(); k = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 1; i <= n; ++i) {
    while (top && a[stc[top]] > a[i]) stc[top + 1] = 0, top--;
    fa[i] = stc[top], fa[stc[top + 1]] = i;
    stc[++top] = i;
  }
  int rt = 0;
  for (int i = 1; i <= n; ++i) {
    if (fa[i]) g[fa[i]].push_back(i);
    else rt = i;
  }
  solve(rt), print(ans);
  return 0;
}

T2 「2017 山东二轮集训 Day1」第一题

题目描述

给定一个长度为 $n$ 的序列 $a_i$ 。多组询问，求 $l \sim r$ 中异或不降子段的个数。

思路

首先发现一个性质。如果懒惰值下降，一定是某一位作为最高位时由 $1$ 变成 $0$ 。

可以用 $f[0/1][i][j]$ 表示前缀 $i$ 中，第 $j$ 位作为最高位，由 $0/1$ 变成 $1/0$ 的次数。

这样就可以二分找到从每个点出发，保持异或不降最远能到达的位置。

如果某一位本身就是 $1$ ，则整个 $[l, r]$ 中，不能存在这一位作为最高位 $0 \to 1$ ，反之亦然。

然后需要用一个支持访问历史版本，区间加，区间求和的数据结构来维护。可以选择用标记永久化的可持久化线段树。

代码

// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 1e5 + 10;
using namespace std;

int rt[Maxn], tot;

struct Stree {
  int ls, rs, val, tag;
  #define ls(x) St[x].ls
  #define rs(x) St[x].rs
  #define v(x) St[x].val
  #define t(x) St[x].tag
} St[Maxn << 6];

int ask(int r1, int r2, int l, int r, int ql, int qr) {
  int _tag = (t(r2) - t(r1)) * (min(r, qr) - max(l, ql) + 1);
  if (l >= ql && r <= qr) return v(r2) - v(r1) + _tag;
  int mid = (l + r) >> 1, ans = 0;
  if (ql <= mid) ans += ask(ls(r1), ls(r2), l, mid, ql, qr);
  if (qr > mid) ans += ask(rs(r1), rs(r2), mid + 1, r, ql, qr);
  return ans + _tag;
}

int add(int p, int l, int r, int al, int ar) {
  int np = ++tot;
  St[np] = St[p];
  if (l >= al && r <= ar) return t(np)++, np;
  v(np) += min(r, ar) - max(l, al) + 1;
  int mid = (l + r) >> 1;
  if (al <= mid) ls(np) = add(ls(p), l, mid, al, ar);
  if (ar > mid) rs(np) = add(rs(p), mid + 1, r, al, ar);
  return np; 
}

int nxt[Maxn], a[Maxn], s[Maxn], f[2][Maxn][33];

inline int bit(int x, int y) {return (x >> y) & 1;}

bool check(int l, int r) {
  for (int j = 0; j < 33; ++j) {
    if (bit(s[l - 1], j) == 0 && f[1][r][j] - f[1][l - 1][j] > 0) return 0;
    if (bit(s[l - 1], j) == 1 && f[0][r][j] - f[0][l - 1][j] > 0) return 0;
  }
  return 1;
}

signed main() {
  int n = read();
  for (int i = 1; i <= n; ++i) 
    a[i] = read(), s[i] = s[i - 1] ^ a[i];
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 33; ++j)
      f[0][i][j] = f[0][i - 1][j], f[1][i][j] = f[1][i - 1][j];
    int x = 0;
    for (int j = 0; a[i] >> j; ++j)
      if ((a[i] >> j) & 1) x = j + 1;
    f[bit(s[i - 1], x - 1)][i][x - 1]++;
  }
  for (int i = 1; i <= n; ++i) {
    int l = i, r = n;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(i, mid)) l = mid;
      else r = mid - 1;
    }
    nxt[i] = l;
  }
  for (int i = 1; i <= n; ++i)
    rt[i] = add(rt[i - 1], 1, n, i, nxt[i]);
  int m = read();
  for (int i = 1, lst = 0; i <= m; ++i) {
    int l = (read() + lst) % n + 1, r = (read() + lst) % n + 1;
    if (l > r) swap(l, r);
    printf("%lld\n", lst = ask(rt[l - 1], rt[r], 1, n, l, r));
  }
  return 0;
}

3.5 / 模拟赛 2

T1 【长沙2020年1月集训day10】黎曼几何

题目描述

玩一种类似汉诺塔的游戏，只不过围成了一圈，你只能顺时针走。分别求将 $n$ 个盘子移动到 $2$ 柱和 $3$ 柱的最小步数，多组询问。

如：两个盘子移到 $2$ 柱： $1$ 盘移两步到 $3$ 柱， $2$ 盘移一步到 $2$ 柱， $1$ 盘移两步 $2 \to 3 \to 1$ 。最终答案为 $5$ 。

思路

一道找规律题。

考虑如果想要移到 $2$ 柱，一定是先把 $n - 1$ 移两步，把第 $n$ 个移一步，然后再把 $n - 1$ 移两步。

而如果要移到 $3$ 柱，则需要先把 $n - 1$ 移两步，把第 $n$ 移一步，再把 $n - 1$ 移一步，再把第 $n$ 移一步。再把 $n - 1$ 移两步。

因为只要是移两步或者移一步，从哪个柱开始是不重要的。所以可以分别设将 $n$ 个盘子移 $1$ 步和移 $2$ 步的最小步数为 $a_n, b_n$ 。

转移式就是 $a_n = 2 \times b_{n - 1} + 1,\ b_n = 2 \times b_{n - 1} + a_{n - 1} + 2$

发现这个东西可以套矩阵快速幂。但是复杂度过不去，俩字 $\Large{\text{分块}}$ 。专业术语光速乘。

时间复杂度 $O(\sqrt n \times sz^3)$ 预处理 $O(1)$ 查询。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline long long read() {
  long long x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(long long x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(long long x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const long long P = 998244353;
const int Maxn = 1.2e6 + 10;
using namespace std;

const int sz = 3;

struct matrix {
  long long a[sz][sz];
  matrix () {memset(a, 0, sizeof(a));}
  matrix operator * (const matrix &T) const {
    matrix res; long long r;
    for (int i = 0; i < sz; ++i)
      for (int k = 0; k < sz; ++k) {
        r = a[i][k];
        for (int j = 0; j < sz; ++j)
          (res.a[i][j] += r * T.a[k][j] % P) %= P;
      }
    return res;
  }
} st, bs, ans, f[Maxn], g[Maxn];

long long ansa, ansb;

signed main() {
  int t = read(), s = 1e6;
  st.a[0][0] = 1, st.a[0][1] = 2, st.a[0][2] = 1;
  bs.a[0][1] = 1, bs.a[1][0] = 2, bs.a[1][1] = 2,
  bs.a[2][0] = 1, bs.a[2][1] = 2, bs.a[2][2] = 1;
  g[0].a[0][0] = g[0].a[1][1] = g[0].a[2][2] = 1;
  f[0].a[0][0] = f[0].a[1][1] = f[0].a[2][2] = 1;
  for (int i = 1; i <= s; ++i) g[i] = g[i - 1] * bs;
  for (int i = 1; i <= s; ++i) f[i] = f[i - 1] * g[s];
  for (int i = 1; i <= t; ++i) {
    long long n = read();
    ans = st * f[(n - 1) / s] * g[(n - 1) % s];
    ansa ^= ans.a[0][0], ansb ^= ans.a[0][1];
  }
  print(ansa, ' '), print(ansb);
  return 0;
}

T2 【长沙2020年1月集训day10】代数几何

题目描述

一个长为 $n$ 的序列。给定一个数 $k$ 要求重排序列使得 $\sum_{i = 0}^{n - 1} a_i \cdot a_{(i + k) \% n}$ 最大。

思路

观察样例描述，发现当 $k = 1$ 时一定是单谷的。

然后你发现整个序列可以根据 $\frac{n}{\gcd(n, k)}$ 分成连通块。然后猜想对于每个联通块是单谷的。

最后猜想第 $i$ 个大小为 $s$ 连通块中存在的数一定是排完序后的 $[a_{s \cdot (i - 1) - 1}, a_{s \cdot i - 1}]$ 。也就是说先把最大的几个给第一个连通块，把之后的几个给 2 块。

进行一些简单验证直接交，然后你发现你过了。。

代码

// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 5e3 + 10;
using namespace std;

int a[Maxn], t[Maxn];

bool cmp(int a, int b) {return a > b;}

int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}

int calc(int l, int r) {
  int n = r - l + 1, mid = (n + 1) / 2, ans = 0;
  for (int i = l, L = mid, R = mid + 1; i <= r; i += 2, --L, ++R) {
    t[L] = a[i];
    if(R <= n) t[R] = a[i + 1];
  }
  for (int i = 1; i < n; ++i) ans += t[i] * t[i + 1];
  return ans + t[n] * t[1];
}

signed main() {
  int n = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  sort(a + 1, a + n + 1, cmp);
  int m = read();
  for (int i = 1; i <= m; ++i) {
    int k = read(), ans = 0;
    if (k == 0) for (int i = 1; i <= n; ++i) ans += a[i] * a[i];
    else {
      int cnt = gcd(n, k), len = n / cnt;
      for (int j = 1; j <= n; j += len) ans += calc(j, j + len - 1);
    }
    print(ans);
  }
  return 0;
}

T3 【长沙2020年1月集训day10】几何考试

题目描述

给定 $n$ 个人，成绩区间为 $[l_i, r_i]$ ，求对于每个人排名的期望。

思路

只会 80’ 暴力。。。

经典的几何概型。对于每个人，以自己成绩为横轴，别人成绩为纵轴，做出矩形。 $y = x$ 上面那部分就是会让排名 $+1$ 的部分。也就是说对于每个人，求

$ans_i = 1 + \sum_{j \ne i}\frac{\text{y = x 上的矩形面积}}{\text{矩形总面积}}$

只需要 $n^2$ 枚举大力分讨切割后形状求面积就行。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 1e5 + 10;
using namespace std;

pair <int, int> a[Maxn];

double sq(int l, int r, int dn, int up) {return 1.0 * (r - l) * (up - dn);}

double calc(int l, int r, int dn, int up) {
  if (l > up) return sq(l, r, dn, up);
  if (r < dn) return 0.0;
  if (l >= dn) {
    if (r >= up) return sq(l, r, dn, up) - 1.0 * (up - l) * (up - l) / 2;
    if (r < up) return 1.0 * ((l - dn) + (r - dn)) * (r - l) / 2;
  }
  if (l < dn) {
    if (r >= up) return 1.0 * ((r - up) + (r - dn)) * (up - dn) / 2;
    if (r < up) return 1.0 * (r - dn) * (r - dn) / 2;
  }
}

signed main() {
  int n = read();
  for (int i = 1; i <= n; ++i) a[i] = {read(), read()};
  for (int i = 1; i <= n; ++i) {
    double ans = 1;
    for (int j = 1; j <= n; ++j) {
      if (i == j) continue;
      ans += 1.0 - calc(a[i].first, a[i].second, a[j].first, a[j].second) / sq(a[i].first, a[i].second, a[j].first, a[j].second);
    }
    printf("%.8lf\n", ans);
  }
  return 0;
}

3.7 / 模拟赛 3

骗分大赛嗯哼？

T1 我永远喜欢月

题目描述

给出两个 $n\times m$ 的 $01$ 矩阵 $A,B$ 。一次操作可以指定 $A$ 中一个为 $0$ 的位置，将它变为 $1$ ，同时将该行该列其它元素变为 $0$ 。求是否可能通过这些操作将 $A$ 变成 $B$ 。

思路

大结论题。

先判完全相等。

你发现如果 $B$ 矩阵中某行某列有超过 $1$ 个 $1$ ，那么这行/列锁了。同时 $1$ 所对的列/行锁了。

如果锁定点与 $A$ 不同，那么判定失败。（考场上判错了）

把锁定行/列从图里扣掉，如果剩下的位置 $A$ 没有 $0$ 或者 $B$ 没有 $1$ 判定失败，否则成功。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();}
  return x * f;
}
inline int read_n() {
  int x = 0; char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  if (c >= '0' && c <= '9') x = (c ^ 48);
  return x;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 1e3 + 10;
using namespace std;

int a[Maxn][Maxn], b[Maxn][Maxn], line[Maxn], col[Maxn];
int _a[Maxn][Maxn], _b[Maxn][Maxn], cl, cc;
bool visl[Maxn], visc[Maxn];

bool work() {
  memset(visl, 0, sizeof(visl));
  memset(visc, 0, sizeof(visc));
  memset(line, 0, sizeof(line));
  memset(col, 0, sizeof(col));
  cl = cc = 0;
  int n = read(), m = read();
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      a[i][j] = read_n();
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      b[i][j] = read_n();
      if (b[i][j]) line[i]++, col[j]++;
    }
  int flag = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j)
      if (a[i][j] != b[i][j]) flag = 0;
  }
  if (flag) return true;
  for (int i = 1; i <= n; ++i) {
    if (line[i] > 1) {
      visl[i] = 1;
      for (int j = 1; j <= m; ++j) {
        if (b[i][j]) visc[j] = 1;
      }
    }
  }
  for (int j = 1; j <= m; ++j) {
    if (col[j] > 1) {
      visc[j] = 1;
      for (int i = 1; i <= n; ++i) {
        if (b[i][j]) visl[i] = 1;
      }
    }
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      if (visl[i] && visc[j] && a[i][j] != b[i][j]) return false;
  for (int i = 1; i <= n; ++i) {
    if (visl[i]) continue;
    ++cl, cc = 0;
    for (int j = 1; j <= m; ++j)
      if (!visc[j]) _a[cl][++cc] = a[i][j],
        _b[cl][cc] = b[i][j];
  }
  flag = 1;
  for (int i = 1; i <= cl; ++i)
    for (int j = 1; j <= cc; ++j) flag &= _a[i][j];
  if (flag) return false;
  flag = 0;
  for (int i = 1; i <= cl; ++i)
    for (int j = 1; j <= cc; ++j) flag |= _b[i][j];
  if (!flag) return false;
  return true;
}

signed main() {
  int t = read();
  while (t--) printf("%s\n", work() ? "Yes" : "No");
  return 0;
}

T2 找朋友

题目描述

$N$ 个鱼缸排成一列，按照 $1,2,\cdots,N$ 的顺序编号。第 $i$ 个鱼缸里水的高度为 $H_i$ ，保证 $H_i<W$ 。

现在放入 $M$ 条鱼，第 $i$ 条鱼被放入第 $P_i$ 个鱼缸，同时它最多能跳 $J_i$ 单位。鱼 $i$ 能从鱼缸 $a$ 跳到鱼缸 $b$ 当且仅当 $|a−b|\le 1$ 且 $J_i>W−H_a$ 。

现在每条鱼开始寻找朋友，他们从一开始所在的鱼缸开始跳，直到跳到某个鱼缸然后停下。等所有鱼都停下了，处在同一鱼缸的鱼就会相互认识。求最后相互认识的鱼的对数的最大值。

思路

直到看懂 $std$ 才读懂题。。

求出每个鱼能到的左端点和右端点。

将序列离散化跑区间 $DP$ 。为了防止重复计算，只有左右端点均被包含的鱼才能被统计。

枚举断点表示将这个区间的鱼集中到这个点。

$f_{l, r} = \max_{k = l}^r\{f_{i, k - 1} + f_{k + 1, r} + \binom{sum}{2}\}$

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 1e4 + 10;
using namespace std;

int h[Maxn], L[210], R[210], x[420], tot;
int vis[420], f[420][420];

signed main() {
  openfile();
  int n = read(), m = read(), w = read();
  for (int i = 1; i <= n; ++i) h[i] = w - read();
  for (int i = 1; i <= m; ++i) {
    int st = read(), t = read(), l = st, r = st;
    for (; l > 1 && t > h[l]; --l);
    for (; r < n && t > h[r]; ++r);
    L[i] = l, R[i] = r, x[++tot] = l, x[++tot] = r;
  }
  sort(x + 1, x + tot + 1), 
  n = unique(x + 1, x + tot + 1) - x - 1;
  for (int i = 1; i <= m; ++i) 
    L[i] = lower_bound(x + 1, x + n + 1, L[i]) - x,
    R[i] = lower_bound(x + 1, x + n + 1, R[i]) - x;  
  for (int len = 1; len <= n; ++len) {
    for (int l = 1, r = len; r <= n; ++l, ++r) {
      for (int i = 1; i <= m; ++i) 
        if (L[i] >= l && R[i] <= r) vis[L[i]]++, vis[R[i] + 1]--;
      for (int i = l; i <= r; ++i) vis[i] += vis[i - 1];
      for (int k = l; k <= r; ++k)
        f[l][r] = max(f[l][r], f[l][k - 1] + f[k + 1][r] + vis[k] * (vis[k] - 1) / 2);
      for (int i = l; i <= r + 1; ++i) vis[i] = 0;
    }
  }
  print(f[1][n]);
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

T3 欧洲皇室女士的名字

暴力赶上 $SAM$ 。。

题目描述

给定 $n$ 个模式串 $S_i$ 和 $k$ 个文本串 $T_i$ 。求以 $T_i$ 为后缀的 $S_j$ 的个数。

（但原题是反的）

思路

将所有的模式串和文本串都插到 $AC$ 自动机里。把模式串的末尾标记为 $1$ ，然后 $fail$ 树上一遍树形 $DP$ 。统计文本串末尾 $siz$ 即可。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 2e6 + 10;
using namespace std;

int ac[Maxn][26], siz[Maxn], fail[Maxn], tot;
int que[Maxn];

void insert(char* s, int _id) {
  int n = strlen(s), p = 0;
  for (int i = n - 1; i >= 0; --i) {
    if (!ac[p][s[i] - 'A']) ac[p][s[i] - 'A'] = ++tot;
    p = ac[p][s[i] - 'A'];
  } que[_id] = p;
}

void build() {
  queue <int> q;
  for (int i = 0; i < 26; ++i) if (ac[0][i]) q.push(ac[0][i]);
  while (!q.empty()) {
    int p = q.front(); q.pop();
    for (int i = 0; i < 26; ++i) {
      int np = ac[fail[p]][i];
      if (ac[p][i]) fail[ac[p][i]] = np, q.push(ac[p][i]);
      else ac[p][i] = np;
    }
  }
}
struct edge {int v, nxt;} e[Maxn];
int hd[Maxn], cnt;
void add(int u, int v) {e[++cnt] = {v, hd[u]}, hd[u] = cnt;}
void dfs(int x) {
  for (int i = hd[x]; i; i = e[i].nxt) dfs(e[i].v), siz[x] += siz[e[i].v];
}

signed main() {
  openfile();
  int n = read(), m = read();
  static char s[Maxn];
  for (int i = 1, id; i <= n; ++i)
    scanf("%s", s), id = read(), ac[id][s[0] - 'A'] = ++tot, siz[tot]++;
  for (int i = 1; i <= m; ++i)
    scanf("%s", s), insert(s, i);
  build();
  for (int i = 1; i <= tot; ++i) add(fail[i], i);
  dfs(0);
  for (int i = 1; i <= m; ++i)
    print(siz[que[i]]);
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

3.9 / 模拟赛 4

T1 完全平方数

题目描述

求周长一定的矩形有多少种面积为完全平方数。

思路

对周长分解质因数，然后求出每个质因数能表示为多少对互质的完全平方数的和然后求和。

代码

// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
using namespace std;

int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}

void work() {
  int n = read(), ans = 0, k;
  if (n & 1) return print(0); n /= 2;
  vector <int> inv;
  for (int i = 1; i * i < n; ++i) 
    if (n % i == 0) inv.push_back(i), inv.push_back(n / i);
  k = sqrt(n); if (k * k == n) inv.push_back(k);
  for (int p : inv) {
    for (int i = 1; i * i <= p / 2; ++i) {
      k = sqrt(p - i * i);
      if (k * k == p - i * i && gcd(i, k) == 1) ans++;
    }
  }
  print(ans);
}

signed main() {
  openfile();
  int t= read();
  while (t--) work();
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

T2 素数

题目大意

小 $B$ 有 $n$ 张不同的卡片，每张卡片上有一个正整数 $a_i(1\le a_i \le 106)$ 。接下来小 $B$ 进行 $m$ 轮操作。每轮操作中，他可以任选 $2$ 张卡片，但要求卡片上的数之和是素数，并将这 $2$ 张卡片标记。问 $m$ 轮之后小 $B$ 最多标记多少张卡片？

思路

第一眼二分图跑网络流，第二眼没说不能重复选，傻了。

其实多看几眼就能发现贪心策略。

只要按照计划选择，最后再和存在度数的点个数取个 $\max$ 就行。

我们发现，偶数质数只有 $2$ 一个，而 $2$ 只能由 $1 + 1$ 拼出，所以先考虑其他质数。将 $a_i$ 按照奇偶性分成两组，把和为质数的两个数连边，最后一定是一个二分图。先跑一遍最大匹配，然后比一下有没有到达极限。如果没有的话就将 $1$ 之间连边加入残量网络，再跑最大流。考场上想的是把 $1$ 之间的边权连成 $1$ 剩下连成 $0$ 跑费用流然而写出来 $T$ 了。。然后因为没想出来和存在度数的点个数取 $max$ 就没交。。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 3e3 + 10, inf = 0x3f3f3f3f;
using namespace std;

int p[2000010], d[2000010];

void prime(int n, int cnt = 0) {
  for (int i = 2; i <= n; ++i) {
    if (!d[i]) d[i] = i, p[++cnt] = i;
    for (int j = 1; j <= cnt; ++j) {
      if (p[j] * i > n || p[j] > d[i])
        break;
      d[p[j] * i] = p[j];
    }
  }
}

struct edge {int v, nxt, t;} e[Maxn * Maxn * 2];
int hd[Maxn], hhd[Maxn], cnt = 1;
void add(int u, int v, int t) {e[++cnt] = {v, hd[u], t}, hd[u] = cnt;}

int s, t, ans, dep[Maxn];

int dfs(int x, int flow) {
  if (!flow || x == t) return flow;
  int res = flow;
  for (int &i = hhd[x]; i && res; i = e[i].nxt) {
    int y = e[i].v;
    if (!e[i].t || dep[y] != dep[x] + 1) continue;
    int k = dfs(y, min(e[i].t, res));
    e[i].t -= k, e[i ^ 1].t += k, res -= k;
  }
  return flow - res;
}

bool bfs() {
  memset(dep, 0, sizeof(dep));
  queue <int> q;
  q.push(s), dep[s] = 1;
  while (!q.empty()) {
    int x = q.front(); q.pop();
    for (int i = hd[x]; i; i = e[i].nxt) {
      int y = e[i].v;
      if (e[i].t && !dep[y]) 
        dep[y] = dep[x] + 1, q.push(y);
    }
  }
  return dep[t];
}

void dinic() {while(bfs()) memcpy(hhd, hd, sizeof(hhd)), ans += dfs(s, inf);}

int a[Maxn], deg[Maxn];
vector <int> l, r;

void work(int n) {
  l.clear(), r.clear(), s = n + 1, t = n + 2;
  int m = read(), tot = 0, mn = 0, ans1, c1, S = n + 3;
  for (int i = 1; i <= n; ++i) {
    a[i] = read(), tot += (a[i] == 1);
    if (a[i] & 1) l.push_back(i);
    else r.push_back(i);
  }
  cnt = 1, ans = 0;
  memset(hd, 0, sizeof(hd)), memset(deg, 0, sizeof(deg));
  add(s, S, m), add(S, s, 0);
  for (int u : l) add(S, u, 1), add(u, S, 0);
  for (int v : r) add(v, t, 1), add(t, v, 0);
  for (int u : l) for (int v : r) 
    if (d[a[u] + a[v]] == a[u] + a[v] && a[u] != 1)
      add(u, v, 1), add(v, u, 0);
  dinic(), ans1 = ans;
  for (int u : l) for (int v : r)
    if (d[a[u] + a[v]] == a[u] + a[v] && a[u] == 1)
      add(u, v, 1), add(v, u, 0);
  dinic(), c1 = ans - ans1;
  if (m + ans + (tot - c1) / 2 > 2 * m)
    return print(2 * m);
  for (int u = 1; u <= n; ++u) 
    for (int v = u + 1; v <= n; ++v)
      if (d[a[u] + a[v]] == a[u] + a[v]) 
        deg[u]++, deg[v]++;
  for (int i = 1; i <= n; ++i) if (deg[i] > 0) mn++;
  print(min(mn, m + ans + (tot - c1) / 2));
}

signed main() {
  openfile(), prime(2e6);
  int n;
  while (scanf("%d", &n) != EOF) work(n);
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

T3 广播

题目描述

给定一个 $n$ 个节点的树，每个节点有一个值 $a_i$ 表示从 $i$ 号节点所能传播的最远距离，求从 $1$ 号点到每个点的最小次数。

思路

点分树优化建图 + 双端队列广搜。

由于这个东西直接 $BFS$ 是 $O(n^2)$ 的，过不去。所以考虑进行一些优化。

建出来点分树，然后按层构建一坨虚点。虚点之间连边权为 $0$ 的边。虚点向子树中相同层的点连边权为 $0$ 的边，子树向 $a_x - dep_x$ 层虚点连边权为 $1$ 的边，代表用一步才能跑过去。

这样建出来总点数为 $nlogn$ 。需要线性广搜才能跑出来。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 5e6 + 10;
using namespace std;

struct edge {int v, nxt;} e[Maxn << 1];
int hd[Maxn], cnt;
void add(int u, int v) {e[++cnt] = {v, hd[u]}, hd[u] = cnt;}
vector <pair <int, int> > g[Maxn];
vector <int> id;

int rt, siz[Maxn], mx[Maxn], vis[Maxn], dep[Maxn];
int a[Maxn], c[Maxn], tot;

int dfs(int x, int f, int mx = 0) {
  id.push_back(x);
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v;
    if (y == f || vis[y]) continue;
    dep[y] = dep[x] + 1;
    mx = max(dfs(y, x) + 1, mx);
  }
  return mx;
}

void calc(int x) {
  id.clear(), dep[x] = 0;
  int mx = dfs(x, 0);
  for (int i = 0; i <= mx; ++i) {
    c[i] = ++tot;
    if (i) g[c[i]].push_back({c[i - 1], 0});
  }
  for (int y : id) {
    g[c[dep[y]]].push_back({y, 0});
    int res = a[y] - dep[y];
    if (res < 0) continue;
    g[y].push_back({c[min(mx, res)], 1});
  }
}

void getrt(int x, int f, int s) {
  siz[x] = 1, mx[x] = 0;
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v;
    if (y == f || vis[y]) continue;
    getrt(y, x, s), siz[x] += siz[y];
    mx[x] = max(mx[x], siz[y]);
  }
  mx[x] = max(mx[x], s - siz[x]);
  if (!rt || mx[x] < mx[rt]) rt = x;
}

void solve(int x) {
  vis[x] = 1, calc(x);
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v, s = siz[y];
    if (vis[y]) continue;
    rt = 0, getrt(y, x, s), getrt(y = rt, x, s);
    solve(y);
  }
}

int dis[Maxn];

void bfs(int s) {
  memset(dis, 0x3f, sizeof(dis));
  deque <int> q;
  q.push_back(s), dis[s] = 0;
  while (!q.empty()) {
    int x = q.front(); q.pop_front();
    for (auto tmp : g[x]) {
      int y = tmp.first, t = tmp.second;
      if (dis[y] > dis[x] + t) {
        dis[y] = dis[x] + t;
        if (!t) q.push_front(y);
        else q.push_back(y);
      }
    }
  }
}

signed main() {
  openfile();
  int n = read(); tot = n;
  for (int i = 1; i <= n; ++i) a[i] = min(n, read());
  for (int i = 1, u, v; i < n; ++i)
    u = read(), v = read(), add(u, v), add(v, u);
  rt = 0, getrt(1, 0, n), getrt(rt, 0, n);
  solve(rt), bfs(1);
  for (int i = 2; i <= n; ++i) print(dis[i], ' ');
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

3.11 / 模拟赛 5

T1 如何优雅的送分

题目描述

$\sum_i^n 2^{F(i)} , F(i) = |\{p \in P | p \mid n\}|$

思路

~~这竖线也太多了吧，我自动忽略两个~~

由于我当成质因数和来做了，所以对于正解的思考几乎没有。正解莫比乌斯反演两步拆式子。

首先可以积累一个性质

$2^{F(i)} = \sum_{d\mid n} \mu^2(d)$

这个可以理解成在所有的质因数中选择了一些质因数组合，因为有平方因子的数 $\mu$ 为 $0$ 。然后这个式子可以根据 $\mu^2(n) = \sum_{d\mid n}\mu(d)$ 进一步化简成

$\sum_{i = 1}^n\sum_{d\mid i}\sum_{k^2\mid d} \mu(k) = \sum_{k = 1}^n\mu(k) \sum_{k^2 \mid d} \lfloor \frac{n}{d}\rfloor = \sum_{k = 1}^n\mu(k)\sum_{i = 1}^{\lfloor \frac{n}{k^2}\rfloor} \lfloor\frac{n}{k^2i}\rfloor$

后面那一坨东西可以整数分块，总的复杂度 $O(\sqrt{n}logn)$

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline long long read() {
  long long x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 1e6 + 10, P = 1e9 + 7;
using namespace std;

int mu[Maxn], p[Maxn], vis[Maxn], cnt;

void prime(long long n) {
  mu[1] = 1;int up = sqrt(n);
  for (int i = 2; 1ll * i * i <= n; ++i) {
    if (!vis[i]) vis[i] = i, p[++cnt] = i, mu[i] = -1;
    for (int j = 1; j <= cnt; ++j) {
      if (p[j] > vis[i] || p[j] * i > up) break;
      vis[p[j] * i] = i;
      if (i % p[j]) mu[i * p[j]] = -mu[i];
    }
  }
}

long long s(long long n) {
  long long res = 0;
  for (long long l = 1, r = 0; l <= n; l = r + 1) {
    r = n / (n / l);
    res = (res + (n / l) * (r - l + 1) % P) % P;
  }
  return res;
}

signed main() {
  // openfile();
  long long n = read(), ans = 0;
  prime(n);
  for (long long i = 1; i * i <= n; ++i)
    ans = (ans + (mu[i] * s(n / (i * i)) % P) + P) % P;
  print(ans);
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

T2 阴阳

题目描述

动态求黑白树上距离点 $x$ 最近的黑点，支持访问历史版本。

思路

正解来了。

建出点分树。维护 3 种可持久化数组。 $1$ 数组维护某个点到根路径上距离最近的黑点， $2$ 数组维护某个 $1$ 数组版本对应的哪个点。 $3$ 数组维护全局黑白点状态。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 2e5 + 10, inf = 1e9;
using namespace std;

struct edge {int v, nxt;} e[Maxn << 1];
int hd[Maxn], cnt;
void add(int u, int v) {e[++cnt] = {v, hd[u]}, hd[u] = cnt;}

int rt, siz[Maxn], mx[Maxn], vis[Maxn];
vector <pair <int, int> > F[Maxn];

void getrt(int x, int f, int S) {
  siz[x] = 1, mx[x] = 0;
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v;
    if (y == f || vis[y]) continue;
    getrt(y, x, S), siz[x] += siz[y];
    mx[x] = max(mx[x], siz[y]);
  }
  mx[x] = max(mx[x], S - siz[x]);
  if (!rt || mx[x] < mx[rt]) rt = x;
}

void dfs(int x, int f, int r, int dep) {
  F[x].push_back({r, dep});
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v;
    if (y == f || vis[y]) continue;
    dfs(y, x, r, dep + 1);
  }
}

void build(int x) {
  vis[x] = 1, dfs(x, 0, x, 0);
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v, S = siz[y];
    if (vis[y]) continue;
    rt = 0, getrt(y, 0, S),
    getrt(y = rt, 0, S), build(y);
  }
}

struct Stree {
  int mn, ls, rs;
  #define mn(x) St[x].mn
  #define ls(x) St[x].ls
  #define rs(x) St[x].rs
} St[Maxn << 7];

int tot;

int add(int p, int l, int r, int v, int k) {
  int np = ++tot; St[np] = St[p];
  if (l == r) return mn(np) = k, np;
  int mid = (l + r) >> 1;
  if (v <= mid) ls(np) = add(ls(p), l, mid, v, k);
  else rs(np) = add(rs(p), mid + 1, r, v, k);
  return mn(np) = min(mn(ls(np)), mn(rs(np))), np;
}

int ask(int p, int l, int r, int k) {
  if (l == r) return mn(p);
  int mid = (l + r) >> 1;
  if (k <= mid) return ask(ls(p), l, mid, k);
  else return ask(rs(p), mid + 1, r, k);
}

int tot2, T1[Maxn << 4], T2[Maxn], T3[Maxn];

void change(int pre, int nw, int x, int n) {
  int t = ask(T3[pre], 1, n, x);
  T2[nw] = T2[pre], T3[nw] = add(T3[pre], 1, n, x, t == inf ? 0 : inf);
  for (int i = F[x].size() - 1; i >= 0; --i) {
    int f = F[x][i].first, dis = F[x][i].second;
    int pr = ask(T2[pre], 1, n, f);
    if (pr == inf) pr = 0;
    T1[++tot2] = add(T1[pr], 1, n, x, t == inf ? dis : inf);
    T2[nw] = add(T2[nw], 1, n, f, tot2);
  }
}

int query(int nw, int x, int n) {
  int ans = inf;
  for (int i = F[x].size() - 1; i >= 0; --i) {
    int f = F[x][i].first, dis = F[x][i].second;
    int pr = ask(T2[nw], 1, n, f), res = 0;
    if (pr == inf) res = inf;
    else res = mn(T1[pr]);
    ans = min(ans, dis + res);
  }
  return ans;
}

signed main() {
  openfile();
  int Type = read(), n = read();
  for (int i = 1, u, v; i < n; ++i)
    u = read(), v = read(), add(u, v), add(v, u);
  mn(0) = inf;
  getrt(1, 0, n), getrt(rt, 0, n), build(rt);
  int m = read(), t = 0, c = 0;
  for (int i = 1, lst = 0; i <= m; ++i) {
    int op = read(), x = read() ^ (lst * Type);
    if (op == 1) change(c, ++t, x, n), c = t;
    if (op == 2) print(lst = query(c, x, n)),
      lst = lst == inf ? 0 : lst;
    if (op == 3) c = x;
  }
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

T3 你猜是不是找规律

~~找个*规律~~

题目描述

优秀的出题人的题面从来都是一句话：求有多少长为 $n$ 的排列交换任意两个数字不超过 $k$ 次即能使之有序。

思路

虽然有序有争议吧，不过看样例还是能看出来的。

首先考虑 $k$ 次变有序不太好做，转成对一个有序序列做 $k$ 次能变成什么序列，但是你要保证 $k$ 次没有反复操作。

考场上突然灵光乍现想到了可以 $dp$ 。然后又瞎写了个转移方程，看了看没准有戏，模了组数据发现应该是对的。

设 $f_{i, j}$ 表示当前枚举到 $i$ 号点，交换了 $j$ 次。那么转移是不是就是：

$f_{i, j} = f_{i - 1, j - 1} \times (i - 1) + f_{i - 1, j}$

意思就是如果当前位置要交换就从前面 $i - 1$ 个位置随便挑一个来换。由于你前面的 $j - 1$ 次操作只是在前 $i - 1$ 个数里进行的，所以把第 $i$ 个数换进去一定不会造成反复。满足条件。

然后这个复杂度是过不去的，但是你发现这个转移可以用斯特林数来优化。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 6e3 + 10, P = 1e9 + 7;
using namespace std;

int add(int x, int y) {return x + y < P ? x + y : x + y - P;}

int Pow(int x, int y, int ans = 1) {
  for (; y; y >>= 1, x = 1ll * x * x % P) if (y & 1) ans = 1ll * ans * x % P;
  return ans;
}

int jc_inv[Maxn], fjc[Maxn], s[Maxn][Maxn];

signed main() {
  // openfile();
  int n = read(), k = read(), ans = 1;
  s[0][0] = 1;
  for (int i = 2; i <= (k << 1); ++i) {
    for (int j = 1; j <= k; ++j) 
      s[i][j] = add(1ll * (i - 1) * s[i - 1][j] % P, 1ll * (i - 1) * s[i - 2][j - 1] % P);
  }
  fjc[1] = n;
  for (int i = 2; i <= (k << 1); ++i)
    fjc[i] = 1ll * fjc[i - 1] * (n - i + 1) % P;
  jc_inv[0] = 1;
  for (int i = 1; i <= (k << 1); ++i)
    jc_inv[i] = 1ll * jc_inv[i - 1] * Pow(i, P - 2) % P;
  for (int i = 1; i <= k; ++i)
    for (int j = 1; j <= k; ++j)
      ans = add(ans, 1ll * fjc[i + j] * jc_inv[i + j] % P * s[i + j][j] % P);
  print(ans);
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

3.14 / 模拟赛 6

T1 工作

题目描述

有 $n$ 个工人，第 $i$ 个工人的初始效率值为 $a_i$ 。

有 $m$ 个工作，第 $i$ 个工作需要恰好 $k_i$ 个工人来完成。

你可以分配工人去完成工作，一个工人可以参加多个工作，但不能重复参加一个工作。当一个工人参加一个工作时，你会获得等同于这个工人当前效率值的收益，然后这个工人效率值减 $1$ 。

你想知道你完成所有任务所能获得的最大收益。

思路

想一想应该就知道，每个任务应该找到的是前 $k_i$ 的工人。

现在的问题就是动态排序，区间减，区间求和。

既然要动态排序，那基本上就寄了。所以，时间不够，分讨来凑。考虑第 $k$ 个和第 $k + 1$ 个的大小关系：

第 $k$ 个大于第 $k + 1$ 个。直接减就行了。
第 $k$ 个等于第 $k + 1$ 个，不好办了，假设 $\forall x \in [l, r], a_x = a_k$ 。那么你要减 $[l, k]$ 是不是就能变成减 $[r - k + l, r]$ 。这样就不用重新排序了。然后就完事了。

维护相等可以用差分和 $set$ 。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(long long x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(long long x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 2e6 + 10, inf = 0x3f3f3f3f;
using namespace std;

long long v1[Maxn], v2[Maxn];

void add(int x, long long v) {
  for (int i = x; i < Maxn; i += (i & -i)) v1[i] += v, v2[i] += x * v;
}

long long ask(int x, long long res = 0) {
  for (int i = x; i; i -= (i & -i)) res += (x + 1) * v1[i] - v2[i];
  return res;
}

long long a[Maxn];
set <int> seg;

void ins(int x) {add(x, 1), ++a[x]; if (a[x] == 1) seg.insert(x);}

void del(int x) {add(x, -1), --a[x]; if (a[x] == 0) seg.erase(x);}

signed main() {
  openfile();
  int n = read(); long long ans = 0;
  for (int i = 1; i <= n; ++i) a[i] = read();
  sort(a + 1, a + n + 1);
  a[0] = -inf;
  for (int i = n; i; --i) {
    a[i] -= a[i - 1];
    if (a[i]) seg.insert(i);
    add(i, i == 1 ? a[i] + a[0] : a[i]);
  }
  seg.insert(n + 1);
  int m = read();
  for (int i = 1; i <= m; ++i) {
    int k = read();
    ans += ask(n) - ask(n - k + 1 - 1);
    if (a[n - k + 1]) del(n - k + 1);
    else {
      auto pos = seg.lower_bound(n - k + 1);
      int r = *pos, l = *(--pos), t = k - (n - r + 1);
      del(l), ins(l + t), del(r);
    }
  }
  print(ans);
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

3.16 / 模拟赛 7

T1 跳蚤王国的宰相

题目描述

给定一棵树。你可以对断掉任何一条边，并连接一条边，使它仍是树。求对于每个点最少的操作次数使它变成重心。

思路

奇奇怪怪的结论题增加了。

对于所有答案，只会有 $0, x, x + 1$ 三种。

原因就是你把重心的儿子按照从大到小排序，开始割。最终一定会在总大小到一半附近得到满足。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 2e6 + 10;
using namespace std;

struct edge {int v, nxt;} e[Maxn << 1];
int hd[Maxn], cnt;
void add(int u, int v) {e[++cnt] = {v, hd[u]}, hd[u] = cnt;}

int rt, siz[Maxn], mx[Maxn];

void getrt(int x, int f, int S) {
  siz[x] = 1, mx[x] = 0;
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v;
    if (y == f) continue;
    getrt(y, x, S), siz[x] += siz[y];
    mx[x] = max(mx[x], siz[y]);
  }
  mx[x] = max(mx[x], S - siz[x]);
  if (!rt || mx[x] <= mx[rt]) rt = x;
}

int col[Maxn], pos[Maxn], pre[Maxn];

void dfs(int x, int f, int _col) {
  col[x] = _col;
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v;
    if (y == f) continue;
    dfs(y, x, _col);
  }
}

struct son { int siz, id;
  bool operator < (const son y) {return siz == y.siz ? id < y.id : siz > y.siz;}
};

vector <son> a;

signed main() {
  // openfile();
  int n = read();
  for (int i = 1, u, v; i < n; ++i)
    u = read(), v = read(), add(u, v), add(v, u);
  getrt(1, 0, n), getrt(rt, 0, n);
  col[rt] = -1;
  for (int i = hd[rt]; i; i = e[i].nxt) {
    int y = e[i].v;
    a.push_back({siz[y], y}), dfs(y, rt, y);
  }
  sort(a.begin(), a.end());
  int t = 0;
  for (int i = 0; i < a.size(); ++i) {
    pos[a[i].id] = i, pre[i] = pre[i - 1] + a[i].siz;
    t += pre[i] < n / 2;
  }
  for (int i = 1; i <= n; ++i) {
    if (col[i] == -1) {print(0); continue;}
    if (pos[col[i]] <= t) {
      if (pre[t] - a[pos[col[i]]].siz + siz[i] >= n / 2) print(t);
      else print(t + 1);
    } else {
      if (pre[t - 1] + siz[i] >= n / 2) print(t);
      else print(t + 1);
    }
  }
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

T2 事情的相似度

题目描述

给定一个字符串，多次询问，求起始位置在 $[l_i, r_i]$ 中的后缀的最长公共前缀。

思路

离线， $SAM$ 上跑 $LCT$ 。当存在不好处理的去区间时，就要考虑把询问离线，把区间右端点变成版本，左端点来处理询问。

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 2e5 + 10;
using namespace std;

namespace BIT {
  int v[Maxn];
  void add(int x, int val) {for (; x; x -= (x & -x)) v[x] = max(v[x], val);}
  int ask(int x, int ans = 0) 
    {for (; x < Maxn; x += (x & -x)) ans = max(ans, v[x]); return ans;}
}

int sam[Maxn][2], fail[Maxn], len[Maxn], lst, tot, id[Maxn];

void insert(char c, int _id) {
  int p = lst, np = ++tot, ch = c - '0';
  id[_id] = lst = np, len[np] = len[p] + 1;
  for (; p && !sam[p][ch]; p = fail[p]) sam[p][ch] = np;
  if (p == 0) return fail[np] = 1, void();
  int q = sam[p][ch];
  if (len[q] == len[p] + 1) return fail[np] = q, void();
  int nq = ++tot;
  fail[nq] = fail[q], fail[q] = fail[np] = nq;
  memcpy(sam[nq], sam[q], sizeof(sam[nq]));
  len[nq] = len[p] + 1;
  for (; p && sam[p][ch] == q; p = fail[p]) sam[p][ch] = nq;
}

void SAM(int n) {
  len[0] = 0, tot = lst = 1;
  static char s[Maxn];
  scanf("%s", s + 1);
  for (int i = 1; i <= n; ++i) insert(s[i], i);
}

struct node {
  int ch[2], val;
  #define ls(x) Sp[x].ch[0]
  #define rs(x) Sp[x].ch[1]
  #define v(x) Sp[x].val
  #define ch(x, y) Sp[x].ch[y]
} Sp[Maxn];

bool isroot(int x) {return ls(fail[x]) != x && rs(fail[x]) != x;}
void change(int x) {v(ls(x)) = v(rs(x)) = v(x);}
void spread(int x) {if (!isroot(x)) spread(fail[x]); change(x);}

void rotate(int x) {
  int y = fail[x], z = fail[y], c = rs(y) == x, w = ch(x, !c);
  if (!isroot(y)) ch(z, rs(z) == y) = x;
  ch(x, !c) = y, ch(y, c) = w;
  if (w) fail[w] = y;
  fail[y] = x, fail[x] = z;
}

void splay(int x) {
  spread(x);
  while (!isroot(x)) {
    int y = fail[x], z = fail[y];
    if (!isroot(y)) rotate((rs(y) == x) ^ (rs(z) == y) ? x : y);
    rotate(x);
  }
}

void access(int x, int k, int y = 0) {
  for (; x; x = fail[y = x]) splay(x), BIT::add(v(x), len[x]), rs(x) = y;
  v(y) = k;
}

int ans[Maxn];
vector <pair<int, int> > q[Maxn];

signed main() {
  openfile();
  int n = read(), m = read();
  SAM(n);
  for (int i = 1, l, r; i <= m; ++i)
    l = read(), r = read(), q[r].push_back({l, i});
  for (int i = 1; i <= n; ++i) {
    access(id[i], i);
    for (auto x : q[i]) ans[x.second] = BIT::ask(x.first);
  }
  for (int i = 1; i <= m; ++i) print(ans[i]);
  return 0;
}

void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

T3 蛐蛐国的修墙方案

题目描述

给定一个排列 $p_i$ 。求构造一种括号序列 $a_i$ ，使得当 $a_i = '('$ 时， $i \to p_i$ 连边，最终每个点的度数均为 2。

思路

可以先贪心的把互相指的匹配上。剩下的再爆搜。时间复杂度 $O(2^{\frac{n}{4}})$

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 110;
using namespace std;

vector <int> s[Maxn];
int tot, a[Maxn], n, vis[Maxn], ans[Maxn];

void link(int x) {
  s[++tot].clear();
  for (int i = x; !vis[i]; i = a[i])
    s[tot].push_back(i), vis[i] = 1;
  if (s[tot].size() == 2) ans[s[tot][0]] = 1, ans[s[tot][1]] = -1, --tot;
}

void dfs(int x) {
  if (x == tot + 1) {
    for (int i = 1, del = 0; i <= n; ++i) {
      del += ans[i];
      if (del < 0) return;
    }
    for (int i = 1; i <= n; ++i) putchar(ans[i] == 1 ? '(' : ')');
    exit(0);
  }
  for (unsigned i = 0; i < s[x].size(); i += 2) 
    ans[s[x][i]] = 1, ans[s[x][i + 1]] = -1;
  dfs(x + 1);
  for (unsigned i = 0; i < s[x].size(); i += 2)
    ans[s[x][i]] = -1, ans[s[x][i + 1]] = 1;
  dfs(x + 1);
}

signed main() {
  n = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 1; i <= n; ++i) if (!vis[i]) link(i);
  dfs(1);
  return 0;
}

本文作者：CloudySky
写作时间： 2022-03-19
最后更新时间： 2022-03-25
遵循协议： BY-NC-SA

CloudySky || AFO

永远相信美好的事情即将发生。

2021高一有基础省选模拟赛

3.4 / 模拟赛 1

T1 「2017 山东二轮集训 Day1」第二题

T2 「2017 山东二轮集训 Day1」第一题

3.5 / 模拟赛 2

T1 【长沙2020年1月集训day10】黎曼几何

T2 【长沙2020年1月集训day10】代数几何

T3 【长沙2020年1月集训day10】几何考试

3.7 / 模拟赛 3

T1 我永远喜欢月

T2 找朋友

T3 欧洲皇室女士的名字

3.9 / 模拟赛 4

T1 完全平方数

T2 素数

T3 广播

3.11 / 模拟赛 5

T1 如何优雅的送分

T2 阴阳

T3 你猜是不是找规律

3.14 / 模拟赛 6

T1 工作

3.16 / 模拟赛 7

T1 跳蚤王国的宰相

T2 事情的相似度

T3 蛐蛐国的修墙方案