SCZ 模拟赛总结

因为能做的题不多，所以用一篇简单的对常中模拟赛中能做懂的题进行一些总结。

D1T1 count

题目描述

有一张 $n$ 个点 $m$ 条边的无向图。

记 $C_1$ 为这个图导出子图为 $K_4$ 的数量, $C_2$ 为补图导出子图为 $K_4$ 的数量（ $K_4$ 是 $4$ 个点的完全图）。

请你求出 $C_1 - C_2$ 的值。

思路

一个容斥。

考虑对 $C_1$ 进行容斥。设 $Fi$ 表示对于 $4$ 个点，只对 $i$ 条边进行限制的导出子图方案数。可以发现：

$C_1 = \sum_i^6 (-1)^{i + 1} Fi = - F0 + F1 - F2 + F3 - F4 + F5 - F6$

然后可以发下 $C_2$ 正好和 $F6$ 有关系，可以消掉，接下来就好办了。

分别求出 $F0\sim F5$ 即可。

对于 $F0$ ，随便选 $4$ 个点，再除以他们的排列数。

n * (n - 1) * (n - 2) * (n - 3) / 24

对于 $F1$ ，其中两个点限制一条边，另外两个点随便选。

m * (n - 2) * (n - 3) / 2

对于 $F2$ ，分两类考虑，分别是两条边有交点和两条边无交点。

对于有交点，枚举每一个点，分别从它的度数中选取两个作为边，这两条边无序，所以需要 $/2$ ，剩下一个点随便选。

(n - 3) * d[i] * (d[i] - 1) / 2

对于无交点，两条边正好 $4$ 个端点。

只要枚举每条边，分别扣掉和它相邻的边即可。同样，边无序，需要 $/2$ 。

(m - (d[e[i].u] + d[e[i].v] - 1)) / 2

对于 $F3$ ，一共有三类情况：

这 $3$ 条边构成了三元环，这边是一个经典的 $m\sqrt m$ 的三元环计数问题。最后再 $\times (n - 6)$ 代表环外的那个点。
这 $3$ 条边构成了一个菊花。

类似于 $F2$ 的有交点，分别枚举每个点的 $3$ 条边，最后 $/6$ 。

d[i] * (d[i] - 1) * (d[i] - 2) / 6
这 $3$ 条边构成了一条链。

直接枚举每条边，对它的两个端点分别再连一条边。

(d[e[i].u] - 1) * (d[e[i].v] - 1)

对于 $F4$ ，有两类情况，分别是四元环和三元环链一个点。

对于 $F5$ ，只有一种情况，两个三元环有一个公共点。

代码

// Code By CloudySky
#include <bits/stdc++.h>
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;

int n, m, cnt[Maxn << 1], d[Maxn], id[Maxn], rk[Maxn];
struct edge {int u, v;} e[Maxn << 1];
vector <int> G[Maxn], g[Maxn];
bool cmp(int x, int y) {return d[x] == d[y] ? x > y : d[x] < d[y];}

// 不对任何边进行限制的方案数
long long f0() {return 1ll * n * (n - 1) * (n - 2) * (n - 3) / 24;}
// 仅对一条边进行限制的方案数
long long f1() {return 1ll * m * (n - 2) * (n - 3) / 2;}
// 对于 2 条边进行限制的方案数
long long f2() {
  long long res = 0;
  // 两条边无交点
  for (int i = 1; i <= m; ++i) res += 1ll * m - (d[e[i].u] + d[e[i].v] - 1);
  res /= 2;
  // 两条边有交点
  for (int i = 1; i <= n; ++i) res += 1ll * (n - 3) * d[i] * (d[i] - 1) / 2;
  return res;
}
// 对于 3 条边进行限制的方案数
long long f3() {
  static int vis[Maxn], c[Maxn];
  long long res = 0;
  // 3 条边构成 3 圆环
  memset(vis, 0, sizeof(vis)), memset(c, 0, sizeof(c));
  for (int i = 1, x, y; i <= n; ++i) {
    for (int x : G[i]) if (rk[i] > rk[x]) vis[x] = 1;
    for (unsigned j = 0; j < G[i].size(); ++j)
      if (rk[i] > rk[x = G[i][j]])
        for (unsigned k = 0; k < G[x].size(); ++k)
          if (rk[x] > rk[y = G[x][k]] && vis[y])
            ++res, ++cnt[g[x][k]], ++cnt[g[i][j]], ++c[y];
    for (unsigned j = 0; j < G[i].size(); ++j)
      if (rk[i] > rk[x = G[i][j]])
        cnt[g[i][j]] += c[x], vis[x] = c[x] = 0;
  }
  res = res * (n - 6);
  // 3 条边构成菊花
  for (int i = 1; i <= n; ++i) res += 1ll * d[i] * (d[i] - 1) * (d[i] - 2) / 6;
  // 3 条边构成链
  for (int i = 1; i <= m; ++i) res += 1ll * (d[e[i].u] - 1) * (d[e[i].v] - 1);
  return res;
}

// 对于 4 条边进行限制的方案数
long long f4() {
  static int vis[Maxn], c[Maxn];
  long long res = 0;
  // 4 条边构成 4 元环
  memset(vis, 0, sizeof(vis)), memset(c, 0, sizeof(c));
  for (int i = 1; i <= n; ++i) {
    for (int x : G[i]) if(rk[i] > rk[x]) vis[x] = 1;
    for (int x : G[i])
      if (rk[i] > rk[x])
        for (int y : G[x])
          if (rk[x] > rk[y] && vis[y]) res += 1ll * d[i] + d[x] + d[y] - 6;
    for (int x : G[i]) vis[x] = 0;
  }
  // 4条边构成一个 3 元环带一个点
  for (int i = 1; i <= n; ++i) {
    for (int x : G[i])
      if (rk[i] > rk[x])
        for (int y : G[x]) if (rk[i] > rk[y]) res += 1ll * c[y], ++c[y];
    for (int x : G[i])
      if (rk[i] > rk[x])
        for (int y : G[x]) c[y] = 0;
  }
  return res;
}

// 对于 5 条边进行限制的方案数
long long f5() {
  // 只有一种情况，两个三元环有一个公共边
  long long res = 0;
  for (int i = 1; i <= m; ++i)
    res += 1ll * cnt[i] * (cnt[i] - 1) / 2;
  return res;
}

long long Abs(long long x) {return x > 0 ? x : -x;}

signed main() {
  n = read(), m = read();
  for (int i = 1, u, v; i <= m; ++i)
    u = read(), v = read(), ++d[u], ++d[v],
    G[u].push_back(v), G[v].push_back(u),
    g[u].push_back(i), g[v].push_back(i),
    e[i] = {u, v};
  for (int i = 1; i <= n; ++i) id[i] = i;
  sort(id + 1, id + n + 1, cmp);
  for (int i = 1; i <= n; ++i) rk[id[i]] = i;
  print(-f0() + f1() - f2() + f3() - f4() + f5());
  return 0;
}

总结

这道题算是对图计数的一个较为综合的考察吧。感觉学到了很多。

D1T2 geometry

题目描述

给定一个凸多边形，你需要构造 $6$ 个与之相切且全等的多边形，且它们互不相交。

思路

考虑将 $6$ 条斜率分别为 $0, 0, \sqrt3, \sqrt{-3}, \sqrt{-3}, \sqrt3$ 的直线切在多边形的上，下，左上，左下，右上，右下。然后关于他们对称即可。找切点的时候需要比截距，对称的话直接用点关于直线对称坐标公式：

$\begin{cases} x = x_0 - 2A\dfrac{Ax_0 + By_0 + C}{A^2 + B^2} \\ y = y_0 - 2B\dfrac{Ax_0 + By_0 + C}{A^2 + B^2} \end{cases}$

由于题目的特殊输出格式，需要判断是顺时针还是逆时针，随便找两条相邻的边叉积一下即可。

代码

// 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;
const double k = -sqrt(3);
using namespace std;

double x[Maxn], y[Maxn];
pair <double, double> up, dn, ul, dl, ur, dr;
pair <double, double> t1, t2;

pair <double, double> rev(double x1, double y1, double x2, double y2, double op) {
  pair <double, double> res;
  res = {x2 + op * k * (op * -k * x2 - y2 + op * k * x1 + y1) / 2, y2 + (op * -k * x2 - y2 + op * k * x1 + y1) / 2};
  return res;
}

signed main() {
  int n = read(), op = 0;
  x[1] = read(), y[1] = read();
  up = dn = ul = dl = dr = ur = make_pair(x[1], y[1]);
  for (int i = 2; i <= n; ++i) {
    x[i] = read(), y[i] = read();
    if (y[i] > up.second) up = make_pair(x[i], y[i]);
    if (y[i] < dn.second) dn = make_pair(x[i], y[i]);
    if (1.0 * x[i] * k + y[i] > 1.0 * ul.first * k + ul.second) 
      ul = make_pair(x[i], y[i]);
    if (1.0 * x[i] * -k + y[i] < 1.0 * dl.first * -k + dl.second)
      dl = make_pair(x[i], y[i]);
    if (1.0 * x[i] * k + y[i] < 1.0 * dr.first * k + dr.second) 
      dr = make_pair(x[i], y[i]);
    if (1.0 * x[i] * -k + y[i] > 1.0 * ur.first * -k + ur.second)
      ur = make_pair(x[i], y[i]);
  }
  print(6);
  op = ((x[2] - x[1]) * (y[3] - y[1]) - (x[3] - x[1]) * (y[2] - y[1]) < 0);
  // 对上边界翻转
  printf("%.10lf %.10lf %.10lf %.10lf %d\n", 1.0 * x[1], 2.0 * up.second - 1.0 * y[1], 1.0 * x[2], 2.0 * up.second - 1.0 * y[2], op);
  // 对下边界翻转
  printf("%.10lf %.10lf %.10lf %.10lf %d\n", 1.0 * x[1], 2.0 * dn.second - 1.0 * y[1], 1.0 * x[2], 2.0 * dn.second - 1.0 * y[2], op);
  // 对左上边界进行翻转
  t1 = rev(ul.first, ul.second, x[1], y[1], 1.0),
  t2 = rev(ul.first, ul.second, x[2], y[2], 1.0);
  printf("%.10lf %.10lf %.10lf %.10lf %d\n", t1.first, t1.second, t2.first, t2.second, op);
  // 对左下边界进行翻转
  t1 = rev(dl.first, dl.second, x[1], y[1], -1.0),
  t2 = rev(dl.first, dl.second, x[2], y[2], -1.0);
  printf("%.10lf %.10lf %.10lf %.10lf %d\n", t1.first, t1.second, t2.first, t2.second, op);
  // 对右下边界进行翻转
  t1 = rev(dr.first, dr.second, x[1], y[1], 1.0),
  t2 = rev(dr.first, dr.second, x[2], y[2], 1.0);
  printf("%.10lf %.10lf %.10lf %.10lf %d\n", t1.first, t1.second, t2.first, t2.second, op);
  // 对右上边界进行翻转
  t1 = rev(ur.first, ur.second, x[1], y[1], -1.0),
  t2 = rev(ur.first, ur.second, x[2], y[2], -1.0);
  printf("%.10lf %.10lf %.10lf %.10lf %d\n", t1.first, t1.second, t2.first, t2.second, op);
  return 0;
}

总结

一道模拟计算几何，构造题不要看样例输出，多猜深究。

代码自己调出来了，感觉还不错。

D2T1 排列

题目描述

对于一个 $1, 2, \cdots, n$ 的排列 $A$ ，我们会为它定义一个贡献：

$\sum_{i = 2}^{n - 1} ([a_{i - 1} > a_i][a_i < a_{i + 1}])^k$

现在我们会随机生成一个排列，我们希望知道排列的贡献的期望是多少。

$n$ 的排列：将 $1, 2, \cdots, n$ 以任意顺序填入新的序列，每个数出现且仅出现一次。

思路

一个计数 DP

答案的 $K$ 次方可以转换成在 $1$ 个排列中选 $K$ 个谷（可重复选择）的方案数。

设 $f_{i, k, j}$ 表示选了 $i$ 段，指定了 $k$ 个位置，共有 $j$ 个谷的方案数。打表出转移贡献值。

代码

// 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 = 1e7 + 10;
using namespace std;
const int g[] = {0, 2, 16, 272, 7936, 353792};
int f[20][20][20], P, ch[30], inv[30], fac[Maxn];

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

int C(int n, int m) {
  int ans = 1;
  for (int i = n - m + 1; i <= n; ++i)
    ans = ans * i % P;
  for (int i = 1; i <= m; ++i)
    ans = ans * inv[i] % P;
  return ans;
}

signed main() {
  int n = read(), m = read(); P = read();
  inv[1] = 1;
  for (int i = 2; i <= 3 * m; ++i)
    inv[i] = (P - P / i) * inv[P % i] % P;
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) 
    fac[i] = fac[i - 1] * i % P;
  f[0][0][0] = 1;
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= m; ++j)
      for (int k = 2 * j + 1; k <= 3 * m; ++k)
        for (int v = j; v <= m; ++v)
          f[i][k][v] = (f[i][k][v] + f[i - 1][k - 2 * j - 1][v - j] * C(k, 2 * j + 1) % P * g[j] % P) % P;
  }
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j <= i; ++j) {
      if (j & 1)
        ch[i] = (ch[i] + P - C(i, j) * Pow(i - j, m) % P) % P;
      else
        ch[i] = (ch[i] + C(i, j) * Pow(i - j, m) % P) % P;
    }
  }
  int ans = 0;
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= min(n, 3 * m); ++j)
      for (int k = 1; k <= m; ++k)
        ans = (ans + f[i][j][k] * C(n, j) % P * C(n - j + i, i) % P * ch[k] % P * fac[n - j] % P) % P;
  }
  print(ans * Pow(fac[n], P - 2) % P);
  return 0;
}

D3T1 拆分

题目描述

现有一整数 $n$ ，求满足以下条件的整数序列个数：

$a_1 + a_2 + \cdots + a_m = n$
$0 < a_1 ≤ a_2 ≤ \cdots ≤ a_m$
$∀i \ne j, |ai − aj| ≥ k$
$h_{m \bmod p} = 1$

思路

不考虑 $k$ 的限制的话 $n^2$ 整数拆分即可。

$f_{i, j}$ 表示划分了 $i$ 段，总和为 $j$ 的方案数。

转移的话因为单调不降，所以有两种方法，把前面所有数都加 1 和另开一段 1。

$f_{i, j} = f_{i, j - i}, f_{i - 1, j - 1}$

对于 $k$ 的限制，直接垫高补齐就行了（如果要拆分成 $i$ 个数，那么只需要和为 $n - \frac{i \times (i - 1)}{2} \times k$ ）。反而可以消掉一些复杂度，使它满足 $O(n\sqrt n)$ 。

对于剩下的 $10\%$ $k = 0$ ，这样做的复杂度显然是过不去的。但可以发现这部分数据同时满足 $p = 1$ 。

就可以进行 $n\sqrt n$ 的整数划分，把组成 $n$ 的数拆成两部分。分别是 $\le \sqrt n$ 的数和 $> \sqrt n$ 的数，对于前一部分跑完全背包，对于后一部分跑类似 $O(n^2)$ 的做法，只不过另开的话需要开 $\lceil \sqrt n\rceil$ 而不是 $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 = 1e6 + 10, P = 998244353;
using namespace std;
int h[Maxn], f[2][Maxn];

namespace Subtask0k {
int sum[Maxn], g[2][Maxn];

int main(int n) {
  int s = ceil(sqrt(n)), u = 0, ans = 0;
  f[0][0] = 1;
  for (int i = 1; i < s; ++i) {
    for (int j = i; j <= n; ++j) {
      f[0][j] = (f[0][j] + f[0][j - i]) % P; 
    }
  }
  sum[0] = 1, g[0][0] = 1, u = 0;
  for (int i = 1; i * i <= n; ++i) {
    u ^= 1, memset(g[u], 0, sizeof(g[u]));
    for (int j = i * s; j <= n; ++j) {
      g[u][j] = (g[u][j - i] + g[u ^ 1][j - s]) % P;
      (sum[j] += g[u][j]) %= P;
    }
  }
  for (int i = 0; i <= n; ++i) {
    (ans += 1ll * sum[i] * f[0][n - i] % P) %= P;
  }
  return ans;
}

} // namespace Subtask0k

signed main() {
  int n = read(), k = read(), p = read(), u = 0, ans = 0;
  for (int i = 0; i < p; ++i) h[i] = read();
  if (k == 0) return print(h[0] == 0 ? 0 : Subtask0k::main(n)), 0;
  f[0][0] = 1;
  for (int i = 1, t = 0; i <= n - t; ++i, t = i * (i - 1) / 2 * k) {
    u ^= 1, memset(f[u], 0, sizeof(f[u]));
    for (int j = i; j <= n - t; ++j) {
      f[u][j] = (f[u ^ 1][j - 1] + f[u][j - i]) % P;
    }
    if (h[i % p]) ans = (ans + f[u][n - t]) % P;
  }
  print(ans);
  return 0;
}

总结

警钟，掌握程度。

D3T2 集合

题目描述

现有 $N$ 个集合 $S_i$ ，每个集合可以表示成两个闭区间的并。

$Q$ 次询问，每次询问 $l, r$ ，求最小的 $x$ 满足 $∀l ≤ i ≤ r, x ∈ S_i$ 。

思路

一道非常妙的数据结构。

首先可以把询问离线下来，按照右端点排序，依次扫描，每到一个询问，就把 $r_{i - 1} \sim r_i$ 中所有集合拿出来更新。

对于每个集合 $S_i$ ，我们不考虑它的作用区间，而考虑剩下的 $1\sim3$ 个区间。对于这些区间里的数，给它标记上 $i + 1$ 。表示这些位置从 $i + 1$ 开始到现在没有被覆盖过。考虑每个位置，它的数字一定是到目前为止最后没有被包含的时刻。

所以对于每组询问 $i$ ，只需要找到第一个标号 $\le l_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;
const int Maxn = 1e6 + 10, inf = 1e9;
using namespace std;

pair <int, int> a[Maxn], b[Maxn];
int t[Maxn << 2], tot, ans[Maxn];
struct query{
  int r, l, id; 
  bool operator < (const query y) const {return r == y.r ? l < y.l : r < y.r;}
} q[Maxn];

struct Stree {
  int l, r, val, tag;
  #define l(x) St[x].l
  #define r(x) St[x].r
  #define v(x) St[x].val
  #define t(x) St[x].tag
} St[Maxn << 4];

#define ls p << 1
#define rs p << 1 | 1

void build(int p, int l, int r) {
  l(p) = l, r(p) = r;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(ls, l, mid), build(rs, mid + 1, r);
}

void spread(int p) {
  if (t(p)) v(ls) = v(rs) = t(ls) = t(rs) = t(p), t(p) = 0;
}

void change(int p, int l, int r, int k) {
  if (l(p) >= l && r(p) <= r) {
    v(p) = t(p) = k; return;
  }
  spread(p);
  int mid = (l(p) + r(p)) >> 1;
  if (l <= mid) change(ls, l, r, k);
  if (r > mid) change(rs, l, r, k);
  v(p) = min(v(ls), v(rs));
}

int ask(int p, int l, int r) {
  if (l(p) >= l && r(p) <= r) return v(p);
  spread(p);
  int mid = (l(p) + r(p)) >> 1, ans = inf;
  if (l <= mid) ans = min(ans, ask(ls, l, r));
  if (r > mid) ans = min(ans, ask(rs, l, r));
  return ans;
}

int Find(int p, int k) {
  if (l(p) == r(p)) return l(p);
  spread(p);
  if (v(ls) <= k) return Find(ls, k);
  else return Find(rs, k);
}

void test_print(int p) {
  if (l(p) == r(p)) return print(v(p), ' ');
  spread(p);
  test_print(ls), test_print(rs);
}

signed main() {
  int n = read(), m = read();
  for (int i = 1, l1, r1, l2, r2; i <= n; ++i) {
    l1 = read(), r1 = read(), l2 = read(), r2 = read();
    a[i] = make_pair(l1, r1), b[i] = make_pair(l2, r2);
    if (a[i] > b[i]) swap(a[i], b[i]);
    t[++tot] = l1, t[++tot] = r1, t[++tot] = l2, t[++tot] = r2;
  }
  sort(t + 1, t + tot + 1);
  tot = unique(t + 1, t + tot + 1) - t - 1;
  build (1, 1, tot);
  for (int i = 1, l, r; i <= m; ++i)
    l = read(), r = read(), q[i] = {r, l, i};
  sort(q + 1, q + m + 1);
  for (int i = 1, lst = 1; i <= m; ++i) {
    for (; lst <= q[i].r; ++lst) {
      int l1 = lower_bound(t + 1, t + tot + 1, a[lst].first) - t,
          r1 = lower_bound(t + 1, t + tot + 1, a[lst].second) - t,
          l2 = lower_bound(t + 1, t + tot + 1, b[lst].first) - t,
          r2 = lower_bound(t + 1, t + tot + 1, b[lst].second) - t;
      if (r1 > r2) r2 = l2 = r1;
      else if (r1 > l2) l2 = r1 = r2;
      if (1 < l1) change(1, 1, l1 - 1, lst + 1);
      if (r2 < tot) change(1, r2 + 1, tot, lst + 1);
      if (r1 + 1 <= l2 - 1) change(1, r1 + 1, l2 - 1, lst + 1);
    }
    if (v(1) > q[i].l) {ans[q[i].id] = -1; continue;}
    ans[q[i].id] = t[Find(1, q[i].l)];
  }
  for (int i = 1; i <= m; ++i) {
    if (ans[i] == -1) printf("NO\n");
    else print(ans[i]);
  }
  return 0;
}

总结

思维 + 数据结构

想的越多，码的越少。

D4T1 藏弓待用

题目描述

对于一个长度为 $n$ 的序列 $a_1 \sim a_n$ ，支持动态修改点权。每次选取一段区间 $[l, r]$ ，求其中不连续选取的最大价值。

思路

动态 DP 板子题。

设 $f_{i, 0/1/2}$ 表示当前位置为 $i$ ，距离左边，右边选择的数为 $0/1/2$ 的最大价值。

矩阵初始化合法为 $0$ , 不合法为 $-\inf$ ，可以选的设成 $a[i]$ 。

将矩乘中积的和改成和的最值套个线段树即可。

另外对于这道题的卡空间，设定一个块长 $s$ ，长度 $\le s$ 的区间暴力即可。

代码

// 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 = 1.2e6 + 10;
const long long inf = 1e18;
using namespace std;

const int sz = 3;

struct mat {
  long long a[sz][sz];
  mat () {
    for (int i = 0; i < sz; ++i) 
      for (int j = 0; j < sz; ++j) a[i][j] = -inf;
    for (int i = 0; i < sz; ++i) a[i][i] = 0;
  }
  mat(int v) {
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) a[i][j] = -inf;        
    a[0][0] = a[1][0] = a[2][0] = 0ll, a[0][1] = a[1][2] = 1ll * v;
  }
  mat operator * (const mat &T) const {
    mat res;
    for (int i = 0; i < sz; ++i) {
      for (int j = 0; j < sz; ++j)
        for (int k = 0; k < sz; ++k)
          res.a[i][j] = max(res.a[i][j], a[i][k] + T.a[k][j]);
    }
    return res;
  }
};

int a[Maxn], s = 34;

struct Stree {
  int l, r; mat v;
  #define l(x) St[x].l
  #define r(x) St[x].r
  #define v(x) St[x].v
} St[150010];

#define ls p << 1
#define rs p << 1 | 1

mat bf(int l, int r, mat res = mat()) {
  for (int i = l; i <= r; ++i) res = res * mat(a[i]);
  return res;
}

void build(int p, int l, int r) {
  l(p) = l, r(p) = r;
  if (r - l + 1 <= s) return v(p) = bf(l, r), void();
  int mid = (l + r) >> 1;
  build(ls, l, mid), build(rs, mid + 1, r);
  v(p) = v(ls) * v(rs);
}

void change(int p, int v, int k) {
  if (r(p) - l(p) + 1 <= s) 
    return a[v] = k, v(p) = bf(l(p), r(p)), void();
  int mid = (l(p) + r(p)) >> 1;
  if (v <= mid) change(ls, v, k);
  else change(rs, v, k);
  v(p) = v(ls) * v(rs);
}

mat ask(int p, int l, int r) {
  if (l(p) >= l && r(p) <= r) return v(p);
  if (r(p) - l(p) + 1 <= s) return bf(max(l, l(p)), min(r, r(p)));
  int mid = (l(p) + r(p)) >> 1; 
  mat ans;
  if (l <= mid) ans = ans * ask(ls, l, r);
  if (r > mid) ans = ans * ask(rs, l, r);
  return ans;
}

long long as(int l, int r, long long res = 0) {
  mat ans = ask(1, l, r);
  for (int i = 0; i < sz; ++i) res = max(res, ans.a[0][i]);
  return res;
}

signed main() {
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  int n = read(), m = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  build(1, 1, n);
  for (int i = 1; i <= m; ++i) {
    int op = read(), l, r, x, y;
    if (op == 1) l = read(), r = read(), print(as(l, r));
    if (op == 2) x = read(), y = read(), change(1, x, y);
  }
  return 0;
}

总结

初探了动态 DP。

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

CloudySky || AFO

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

SCZ 模拟赛总结

D1T1 count

D1T2 geometry

D2T1 排列

D3T1 拆分

D3T2 集合

D4T1 藏弓待用