SDOI2022 退役记

生涯转折点 SDOI2022

先说结果, 期望 $20 + 35 + 25 + 100 + 10 + 0 = 190$ , 实际挂成了 $0 + 35 + 25 + 100 + 2 + 0 = 162$ . 山东 RK $24$ , 加上 NOIP 成绩 RK $23$ . 肯定没有 AB 了, 但是 D 是绝对可以买的.

D1T1 整数序列

这个题一眼没什么想法, 转化题意为每次询问数轴上有两种点, 选择一个区间使得两种点数量相同且权值总和最大.

之后想到可以类似于括号匹配那样做, 将每个数字的每次出现位置和权值都存到一个 vector 里面, 记录一个高度 $h$ , 从左往右双指针扫描两个 vector, 遇到第一种点就将高度增加 $1$ , 遇到第二种点就将高度减少 $1$ , 记录每个高度达到过的最小权值前缀和, 每次用当前的高度和前缀和减去这个高度达到过的最小权值前缀和, 尝试更新答案. 复杂度 $O(nq)$ .

其实这个数据范围结合时限 (当时还没有改时限, 貌似是 $4s$ ), 我是十分相信存在根号做法的, 但无论是分块还是莫队我都没有想到什么合理的算法. 将时间改到 $7s$ 之后, 我更加相信这个题绝对是根号, 但是仍无果.

我中途想过每个点开一个动态开点线段树, 可是这个信息无法通过线段树的二分结构来查询, 所以就寄了. 发现可以根号分治, 也就是特殊处理出现次数大于根号个的元素, 通过预处理加速和这些元素有关的询问, 但是发现我不会预处理加速询问, 所以就又往动态开点线段树上去想了.

最后还是交的 $O(nq)$ , 但是没有得到预期的 $20'$ , 因为有一个地方挂掉了. 接下来是考场代码:

#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
inline unsigned RD() {
  unsigned Rtmp(0);
  char Rch(getchar());
  while(Rch < '0' || Rch > '9') Rch = getchar();
  while(Rch >= '0' && Rch <= '9')
    Rtmp = Rtmp * 10 + Rch - '0', Rch = getchar();
  return Rtmp;
}
inline int RDsg() {
  int Rtmp(0), Rsig(1);
  char Rch(getchar());
  while((Rch < '0' || Rch > '9') && (Rch ^ '-')) Rch = getchar();
  if(Rch == '-') Rsig = -1, Rch = getchar();
  while(Rch >= '0' && Rch <= '9')
    Rtmp = Rtmp * 10 + Rch - '0', Rch = getchar();
  return Rtmp * Rsig;
}
long long Sum[600005], Ans(0);
unsigned a[300005];
int b[300005];
vector<pair<unsigned, int> > c[300005];
unsigned n, m;
unsigned A, B, C, D, t;
signed main() {
  freopen("sequence.in", "r", stdin);
//  freopen("ex_sequence3.in", "r", stdin);
  freopen("sequence.out", "w", stdout);
  n = RD(), m = RD();
  for (unsigned i(1); i <= n; ++i) a[i] = RD();
  for (unsigned i(1); i <= n; ++i) b[i] = RDsg();
  for (unsigned i(1); i <= n; ++i) c[a[i]].push_back({i, b[i]});
  for (unsigned i(1); i <= m; ++i) {
    C = c[A = RD()].size(), D = c[B = RD()].size();
    unsigned Hei(n);
    long long Cur(0);
    memset(Sum, 0x3f, (n + 1) << 4);
    Sum[n] = 0, Ans = 0xafafafafafafafaf;
    for (unsigned j(0), k(0); j < C || k < D; ) {
      if((j ^ C) && ((k == D) || (c[A][j].first < c[B][k].first))) {
        Cur = Cur + c[A][j].second;
        Ans = max(Cur - Sum[Hei + 1], Ans);
        Sum[Hei + 1] = min(Sum[Hei] + c[A][j].second, Sum[Hei + 1]);
        ++Hei, ++j;
        continue;
      }
      if((k ^ D) && ((j == C) || (c[A][j].first > c[B][k].first))) {
        Cur = Cur + c[B][k].second;
        Ans = max(Cur - Sum[Hei - 1], Ans);
        Sum[Hei - 1] = min(Sum[Hei] + c[B][k].second, Sum[Hei - 1]);
        --Hei, ++k;
        continue;
      }
    }
    printf("%lld\n", Ans);
  }
  return 0;
}

锅出在更新 Sum 数组上, 我使用的是:

...
Sum[Hei + 1] = min(Sum[Hei] + c[A][j].second, Sum[Hei + 1]);
...
Sum[Hei - 1] = min(Sum[Hei] + c[B][k].second, Sum[Hei - 1]);
...

这是用历史最低的值尝试更新这个历史最低的值, 但是真实情况是应该用当前值去更新这个历史最低值. 因此只要改成这样就正确了, 可以拿到 $20'$ :

...
Sum[Hei + 1] = min(Cur, Sum[Hei + 1]);
...
Sum[Hei - 1] = min(Cur, Sum[Hei - 1]);
...

这道题的正解确实是根号分治, 原理是出现次数大于 $B$ 的元素不超过 $\frac nB$ 个, 把这些元素称为主要元素. 所以可以将询问分为两种: 含有主要元素和不含有主要元素.

对于询问 $(x, y)$ 有两种回答询问的方式: 第一种是 $O(Size_x + Size_y)$ , 也就是暴力, 第二种是对 $Size$ 较大的元素经过 $O(n)$ 的预处理之后, 可以进行 $O(\min(Size_x, Size_y))$ 的询问.

把所有询问的两个元素中出现次数较多的放在前面, 然后按询问的第一个元素为第一关键字, 第二个元素为第二关键字排序.

对于不含有主要元素的询问, 我们直接暴力查询, 复杂度为 $O(B)$ . 有主要元素的询问, 我们对于每个主要元素, 进行 $O(n)$ 预处理后, 一次性询问所有的包含它的询问. 由于包含它的所有询问的另一个元素的出现次数总和不超过 $n$ , 因此用第二种询问方式可以 $O(n\log B)$ 求出所有询问的答案. 一共最多有 $\frac nB$ 个主要元素, 总复杂度 $O(Bq + \frac{n^2\log B}B)$ , 如果认为 $\log B$ 和 $\log n$ 同阶, 那么当 $B$ 取 $\frac {n\log n}{\sqrt q}$ 时复杂度最优, 为 $O(n\sqrt {q\log n})$ . 一开始给询问排序是 $O(q \log q)$ , 可以开桶优化到 $O(n + q)$ .

我一开始认为的第二种询问: 对于一个主要元素 $A$ , 直接扫描整个数组 $a$ , 同时维护每个询问的每个高度的前缀和历史最小值, 但是如果序列上扫过一个 $A$ , 就需要更新所有询问的高度和对应的历史最小前缀和, 复杂度会退化成 $O(nq)$ .

真正的第二种询问方式是这样的: 我们暴力查询的时候相当于维护了一个折线, 把折线中一段首尾高度相同的非空子区间拿出来, 这个子区间的权值就可以更新答案. 那么我们考虑这个首尾相同的高度可能的取值范围, 把折线分成长度为 $1$ 的小段, 这些段的上升和下降对应了这个位置的元素是第一种还是第二种.

满足条件的高度一定是某个下降段的端点高度, 对于一个仅末尾经过起始高度的子区间, 由于只经过子区间起点所在的高度两次, 所以整个子区间的折线应该在这个高度的水平线的一侧, 如果是在上侧, 那么该子区间以上升段开始, 下降段结束, 否则以下降段开始, 上升段结束, 因此这个高度一定是某个下降段的端点所在高度. 对于任意可以更新答案的子区间, 把它从每一次经过首尾高度的位置断开, 每个部分都是一个前面分析过的子区间, 所以每一个部分都有一个下降段的端点高度为对应高度. (显然对于上升段这个结论仍然适用)

有了这个结论, 那么对于一个有 $x$ 个下降段的折线, 有效的高度只有最多 $2x$ 个, 将这些高度称为关键高度. 我们只需要维护这些高度的历史最小前缀和, 并且在尝试更新每个高度的历史最小前缀和之前尝试更新答案即可. 在处理以主要元素 $A$ 为询问的第一个元素, $X$ 为询问的第二个元素的时候, 为了快速找出关键高度, 需要给每次 $X$ 出现的时候定位. 我们预处理每一个位置及之前 $A$ 的数量, 然后从左到右扫描 $X$ , 用每个 $X$ 出现时, 左边 $A$ 的数量和这个 $X$ 的编号做差即可得到当前下降段终点的高度, 下降段起点的高度就是终点高度加 $1$ . 最后将所有关键高度排序去重即可, 复杂度中 $\log B$ 就来自这个排序.

知道了关键高度, 接下来就从左往右跳, 遇到连续极长上升子区间就每次 $O(1)$ 从一个关键高度走到下一个关键高度, 预处理这个元素 $b$ 值的前缀和查询区间总和. 每次到一个关键高度尝试更新答案和前缀历史最小和.

这个题的数据比较难构造, 因为要卡掉所有错做法, 这个题如果把 $B$ 设为 $1$ , 可以拿到 $45'$ , 把 $B$ 设为 $2$ 可以 AC, 也就是说只要把出现两次及以上的都当作主要元素就可以 AC.

unsigned a[300005], Sz[300005], Name[300005], Bucket[300005];
int b[300005];
long long Sum[300005], Ans[1000005];
unsigned A, B, C, D, t;
unsigned Cnt, Mx, Thr, m, n;
vector<pair<unsigned, int> > Vc[300005];
struct Ques {
  unsigned Fs, Sc, Num;
  inline void Init() {
    Num = ++Cnt, gi(A), Fs = Bucket[A], gi(A), Sc = Bucket[A];
    if (Fs < Sc) swap(Fs, Sc);
  }
  inline const char operator< (const Ques& x) const { return (Fs ^ x.Fs) ? (Fs < x.Fs) : (Sc < x.Sc); }
}Qst[1000005];
inline long long Qry(unsigned x) {
  unsigned Siz(Vc[x].size()), Hei[Siz + 3], List[(Siz << 1) + 3];
  for (unsigned i(0); i < Siz; ++i) Hei[i + 1] = Siz + Bucket[Vc[x][i].first] - i - 1;
  memcpy(List, Hei, (Siz + 1) << 2);
  for (unsigned i(1); i <= Siz; ++i) List[Siz + i] = List[i] + 1;
  sort(List + 1, List + (Siz << 1) + 1);
  unsigned HCnt(unique(List + 1, List + (Siz << 1) + 1) - List - 1);
  List[HCnt + 1] = 0x3f3f3f3f;
  long long Shrink[HCnt + 3], Cur(0), Tmp(0xafafafafafafafaf);
  memset(Shrink, 0x3f, (HCnt + 1) << 3);
  unsigned j(0), HC(Siz), Pos(0);
  while (List[j + 1] <= Siz) ++j;
  if (List[j] == Siz) Shrink[j] = 0;
  for (unsigned i(1); i <= Siz; ++i) {
    while (List[j + 1] <= Hei[i] + 1) {
      unsigned Fw(min(Mx - Pos, List[++j] - HC));
      if (!Fw) continue;
      Cur -= Sum[Pos], Cur += Sum[Pos += Fw];
      HC = List[j], Tmp = max(Tmp, Cur - Shrink[j]);
      Shrink[j] = min(Shrink[j], Cur);
    }
    Cur += Vc[x][i - 1].second, --j;
    --HC, Tmp = max(Tmp, Cur - Shrink[j]);
    Shrink[j] = min(Shrink[j], Cur);
  }
  while (j < HCnt) {
    unsigned Fw(min(Mx - Pos, List[++j] - HC));
    if (!Fw) continue;
    Cur -= Sum[Pos], Cur += Sum[Pos += Fw];
    HC = List[j], Tmp = max(Tmp, Cur - Shrink[j]);
    Shrink[j] = min(Shrink[j], Cur);
  }
  return Tmp;
}
signed main() {
  gi(n), gi(m), Thr = (n / (sqrt(m) + 1)) + 1;
  for (unsigned i(1); i <= n; ++i) gi(a[i]), ++Sz[a[i]];
  for (unsigned i(1); i <= n; ++i) gi(b[i]);
  for (unsigned i(1); i <= n; ++i) ++Bucket[Sz[i]];
  for (unsigned i(1); i <= n; ++i) Bucket[i] += Bucket[i - 1];
  Thr = Bucket[Thr - 1] + 1;
  for (unsigned i(n); i; --i) Name[Bucket[Sz[i]]--] = i; //Rank
  for (unsigned i(1); i <= n; ++i) Bucket[Name[i]] = i;// Bucket -> Name
  for (unsigned i(1); i <= n; ++i) Vc[a[i] = Bucket[a[i]]].push_back({ i, b[i] });
  for (unsigned i(1); i <= m; ++i) Qst[i].Init();
  sort(Qst + 1, Qst + m + 1);
  for (unsigned i(Cnt = 1); i <= m; ++i, ++Cnt) {
    unsigned Cur(Qst[i].Fs);
    if (Cur >= Thr) break;
    unsigned With(Qst[i].Sc), Mxk(Vc[With].size()), Top(Thr + 2), Hei(Top), Bot(Top), k(0);
    long long CSum(0), Tmp(0xafafafafafafafaf);
    Sum[Top] = 0;
    for (auto j : Vc[Cur]) {
      while (k < Mxk && Vc[With][k].first < j.first) {
        CSum += Vc[With][k++].second, --Hei;
        if (Hei < Bot) Sum[Bot = Hei] = 0x3f3f3f3f3f3f3f3f;
        Tmp = max(Tmp, CSum - Sum[Hei]);
        Sum[Hei] = min(CSum, Sum[Hei]);
      }
      CSum += j.second, ++Hei;
      if (Hei > Top) Sum[Top = Hei] = 0x3f3f3f3f3f3f3f3f;
      Tmp = max(Tmp, CSum - Sum[Hei]);
      Sum[Hei] = min(CSum, Sum[Hei]);
    }
    while (k < Mxk) {
      CSum += Vc[With][k++].second, --Hei;
      if (Hei < Bot) Sum[Bot = Hei] = 0x3f3f3f3f3f3f3f3f;
      Tmp = max(Tmp, CSum - Sum[Hei]);
      Sum[Hei] = min(CSum, Sum[Hei]);
    }
    Ans[Qst[i].Num] = Tmp;
  }
  for (unsigned i(Cnt); i <= m;) {
    unsigned Cur(Qst[i].Fs);
    memset(Bucket, 0, (n + 1) << 2);
    Sum[0] = 0, Mx = Vc[Cur].size();
    for (unsigned j(Mx); j; --j) Sum[j] = Vc[Cur][j - 1].second;
    for (auto j : Vc[Cur]) Bucket[j.first] = 1;// Sum[j.first] = j.second;
    for (unsigned j(1); j <= n; ++j) Bucket[j] += Bucket[j - 1];
    for (unsigned j(1); j <= Mx; ++j) Sum[j] += Sum[j - 1];
    while (Qst[i].Fs == Cur) {
      if ((Qst[i - 1].Fs == Cur) && (Qst[i].Sc == Qst[i - 1].Sc)) {
        Ans[Qst[i].Num] = Ans[Qst[i - 1].Num], ++i;
        continue;
      }
      Ans[Qst[i].Num] = Qry(Qst[i].Sc), ++i;
    }
  }
  for (unsigned i(1); i <= m; ++i) print(Ans[i]), pc(0x0A);
  return Wild_Donkey;
}

D1T2 进制转换

求 $Popcnt$ 有关的多项式, 显然线性是送的, 又因为是一个多项式的形式, 所以一眼出了 $y = 1$ 的做法, 就是倍增. 这就拿到了 $35'$ .

如果要细说这个倍增的方法, 假设 $d < 3^k$ , 我们考虑 $x^d z^{b_d}$ , $x^{3^k + d} z^{b_{3^k + d}}$ 的关系, 发现 $x^{3^k + d} z^{b_{3^k + d}} = (x^d z^{b_d}) x^{3^k} z$ , 以此类推 $x^{2 \times 3^k + d} z^{b_{2 \times 3^k + d}} = (x^d z^{b_d}) x^{2 \times 3^k} z^2$ . 也就是说如果我们知道了 $\displaystyle{\sum_{i = 0}^{3^k - 1} x^dz^{b_d}}$ , 那么我们就可以 $O(1)$ 求出 $\displaystyle{\sum_{i = 0}^{3^{k + 1} - 1} x^dz^{b_d}}$ .

因此只需要 $\log_3 n$ 即可求出 $y = 1$ 的情况.

下面是考场 $35'$ 代码:

#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
inline unsigned long long RD() {
  unsigned long long Rtmp(0);
  char Rch(getchar());
  while(Rch < '0' || Rch > '9') Rch = getchar();
  while(Rch >= '0' && Rch <= '9')
    Rtmp = Rtmp * 10 + Rch - '0', Rch = getchar();
  return Rtmp;
}
const unsigned long long Mod(998244353);
unsigned a[10000005], b[10000005];
unsigned long long n, m;
unsigned long long A, B, C[3], Ans(0);
inline unsigned long long Pow(unsigned long long x, unsigned long long y) {
  y %= 998244352, x %= Mod;
  unsigned long long Rt(1);
  while (y) {if(y & 1) Rt = Rt * x % Mod; x = x * x % Mod, y >>= 1;}
  return Rt;
}
inline unsigned PpC3 (unsigned long long x) {
  unsigned Rt(0);
  while (x) Rt += x % 3, x /= 3;
  return Rt;
}
signed main() {
  freopen("conversion.in", "r", stdin);
//  freopen("ex_conversion2.in", "r", stdin);
  freopen("conversion.out", "w", stdout);
  n = RD(), A = RD(), B = RD(), C[1] = RD();
  C[0] = 1, C[2] = C[1] * C[1] % Mod;
  a[0] = b[0] = 1;
  if(B == 1) {
    ++n;
    unsigned long long Tri[50], A3(A);
    Tri[0] = 1;
    for (unsigned long long i(3), j(1); i <= n; i *= 3, ++j) {
      unsigned long long Sec, Trd;
      Sec = (Tri[j - 1] * A3 % Mod) * C[1] % Mod;
      Trd = (Sec * A3 % Mod) * C[1] % Mod;
      Tri[j] = (Tri[j - 1] + Sec + Trd) % Mod;
      A3 = (A3 * A3 % Mod) * A3 % Mod;
    }
//    for (unsigned long long i(3), j(1); i <= n; i *= 3, ++j)
//      printf("%llu ", Tri[j]); putchar(0x0A);
    unsigned long long Cur(1);
    unsigned Lg(0), Rm(0);
    while (n) {
//      printf("n = %llu Cur %llu\n", n, Cur);
      if(Rm = ((n % (Cur * 3)) / Cur)) {
//        printf("Rm = %u\n", Rm);
        if(Rm ^ 1) {
          unsigned CP(PpC3(n / (Cur * 3)));
//          printf("CP %llu %u\n", n / (Cur * 3), CP); 
          Ans = (Ans + (Pow(A, n - Cur) * Tri[Lg] % Mod) * Pow(C[1], CP + 1)) % Mod;
          Ans = (Ans + (Pow(A, n - (Cur << 1)) * Tri[Lg] % Mod) * Pow(C[1], CP)) % Mod;
          n -= (Cur << 1);
        } else {
          unsigned long long CP(PpC3(n / (Cur * 3)));
//          printf("CP %llu %u\n", n / (Cur * 3), CP);
          Ans = (Ans + (Pow(A, n - Cur) * Tri[Lg] % Mod) * Pow(C[1], CP)) % Mod;
          n -= Cur;
        }
      }
      ++Lg, Cur *= 3;
    }
    printf("%llu\n", Ans - 1);
    return 0;
//    printf("%u\n")
  }
  if(n <= 10000000) {
//    Ans = 0;
//    printf("Excuseme %u\n", n);
    for (unsigned i(1), j(1); i <= n; ++i) {
      a[i] = (unsigned long long)a[i >> 1] * ((i & 1) ? B : 1) % Mod;
      b[i] = (unsigned long long)b[i / 3] * C[i % 3] % Mod;
      j = j * A % Mod;
      Ans = (Ans + ((unsigned long long)j * b[i] % Mod) * a[i]) % Mod;
    }
    printf("%llu\n", Ans);
    return 0;
  }
  return 0;
}
/*
100 1 1 2
10 2 1 1
8 2 1 2
9 2 1 2
10 2 1 2
100000001 123 1 12345
887397358
899868317
*/

接着考虑正解, 一开始想的是既然 $y = 1$ 是以 $3$ 为底的倍增, $z = 1$ 是以 $2$ 为底的倍增, 那么是否可以以 $6$ 为底进行倍增, 无果.

D1T3 子串统计

一开始吧 $\prod$ 看成 $\sum$ 了, 导致了我以为一眼秒了, 对这个题有了一个大水题的第一印象, 所以 Day1 的大部分时间都是在 SAM 上疯狂 DP.

因为比赛前刚秒了几道字符串, 发现我简直是个字符串带师, 省选题又出现过那种题目难度完全和编排无关的情况, 所以我认为只要把 T3 做出来就能翻我 T1, T2 都不会的盘.

对于一个字串 $[l, r]$ , 我们设它的出现次数是 $g_{l, r}$ , 对答案的贡献是 $f_{l, r}$ , 那么有式子:

f_{l, r} = g_{l, r} (f_{l - 1, r} + f_{l, r + 1})

可以用 SAM 求出所有的 $g$ , 然后 $O(n^2)$ 算出所有的贡献, 最后答案遍是 $\displaystyle{\sum_{i = 1}^n f_{i, i}}$ , 这个做法可以得到 $25'$ .

其实还有一个做法, 就是用 SAM 上的节点进行 DP, 我们知道每个节点对应一系列的子串, 假设 $f_{i, j}$ 表示节点 $i$ 代表的, 长度为 $j$ 的子串所有出现位置的贡献之和. 那么我们可以把 SAM 拆成 $n^2$ 个节点, 使得每个节点只代表一个子串, 用 $f_{i}$ 表示每个节点的子串所有出现位置的贡献之和. 然后通过递归得到答案, 如果结合 unordered_map 进行记忆化搜索, 那么复杂度仍然是 $O(n^2)$ 的, 因为每个值只会被计算一遍.

这个做法比正常 $O(n^2)$ 慢不少, 感官上是过不了 $25'$ 的, 所以就是个废物, 用来验证正确性倒是可以, 但是场上这个做法相比上一种做法要麻烦很多, 所以每次两个做法答案不同都是这个做法出锅. 如果硬要给它找一个优点, 就是我们无需把所有点真的建出来, 所以可以在过大的数据中赶在 RE 或 MLE 之前 TLE.

下面是考场代码, 结合了上面两种做法, 期望仍为 $25'$ :

#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
inline unsigned RD() {
  unsigned Rtmp(0);
  char Rch(getchar());
  while(Rch < '0' || Rch > '9') Rch = getchar();
  while(Rch >= '0' && Rch <= '9')
    Rtmp = Rtmp * 10 + Rch - '0', Rch = getchar();
  return Rtmp;
}
inline int RDsg() {
  int Rtmp(0), Rsig(1);
  char Rch(getchar());
  while((Rch < '0' || Rch > '9') && (Rch ^ '-')) Rch = getchar();
  if(Rch == '-') Rsig = -1, Rch = getchar();
  while(Rch >= '0' && Rch <= '9')
    Rtmp = Rtmp * 10 + Rch - '0', Rch = getchar();
  return Rtmp * Rsig;
}
const unsigned long long Mod(998244353);
inline unsigned long long Pow(unsigned long long x, unsigned y) {
  unsigned long long Rt(1);
  while (y) {if(y & 1) Rt = Rt * x % Mod; x = x * x % Mod, y >>= 1;}
  return Rt;
}
char a[100005];
unsigned n, m;
unsigned A, B, C, D, t;
unsigned long long Ans(0);
struct Node {
  unordered_map<unsigned, unsigned> Mp;
  vector<Node*> Son;
  Node* E[26], *Link;
  unsigned Len, EndPos, Idg;
  inline void Add(char c);
  inline unsigned long long Get(unsigned x) {
    if(x == n) return 1;
    if(Mp[x]) return Mp[x];
    unsigned long long Bot(Pow(EndPos, Len - x));
    unsigned long long Rt(0);
    for (unsigned i(0); i < 26; ++i) if(E[i])
      Rt = (Rt + E[i]->Get(x + 1)) % Mod;
    if(Len == x) for (auto i:Son) Rt = (Rt + i->Get(Len + 1)) % Mod;
    else Rt += Get(x + 1);
//    printf("Find %u = %llu\n", x, Rt);
    return Mp[x] = (Rt * EndPos % Mod);
  }
  inline void DFS() {
    for (auto i:Son) i->DFS(), EndPos += i->EndPos;
  }
}N[200005], *List[100005], *CntN(N), *Last(N);
Node *Que[200005], **Hd(Que), **Tl(Que);
inline void Node::Add(char c) {
  Len = Last->Len + 1;
  Node* Back(Last);
  while (Back && (!Back->E[c])) Back->E[c] = this, Back = Back->Link;
  if(!Back) {Link = N, Last = this; return;}
  if(Back->E[c]->Len == Back->Len + 1) {
    Link = Back->E[c], Last = this;
    return;
  }
  Node *Ori(Back->E[c]), *Copy(++CntN);
  *Copy = *Ori, Copy->Len = Back->Len + 1;
  Ori->Link = Link = Copy, Last = this;
  while (Back && (Back->E[c] == Ori))
    Back->E[c] = Copy, Back = Back->Link;
  return;
}
signed main() {
  freopen("substring.in", "r", stdin);
//  freopen("ex_substring3.in", "r", stdin);
  freopen("substring.out", "w", stdout);
  scanf("%s", a + 1);
  n = strlen(a + 1);
  for (unsigned i(1); i <= n; ++i) (List[i] = ++CntN)->Add(a[i] - 'a');
  for (unsigned i(1); i <= n; ++i) List[i]->EndPos = 1;
//  printf("Link:");for (Node *i(N + 1); i <= CntN; ++i) printf("%u ", i->Link - N); putchar(0x0A);
  for (Node *i(N + 1); i <= CntN; ++i) i->Link->Son.push_back(i), ++(i->Idg);
  N->DFS();
//  printf("EndPos:");for (Node *i(N + 1); i <= CntN; ++i) printf("%u ", i->EndPos); putchar(0x0A);
  if(n <= 5000) {
    unsigned Apr[5005][5005];
    for (unsigned i(1), j(1); i <= n; j = ++i) {
      Node* Cur(List[i]);
      while (Cur) {
//        printf("i %u Cur %u j %u\n", i, Cur - N, j);
        unsigned LenMin(Cur->Link ? (Cur->Link->Len + 1) : 1);
        while (j >= LenMin) Apr[j][i - j + 1] = Cur->EndPos, --j;
        Cur = Cur->Link;
      }
    }
//    for (unsigned i(n); i; --i) {
//      for (unsigned j(n - i + 1); j; --j) printf("%3u", Apr[i][j]); putchar(0x0A);
//    }
    for (unsigned i(n - 1); i; --i) for (unsigned j(n - i + 1); j; --j)
      Apr[i][j] = (unsigned long long)Apr[i][j] * (Apr[i + 1][j] + Apr[i + 1][j - 1]) % Mod;
    for (unsigned j(1); j <= n; ++j) Ans += Apr[1][j];
//    for (unsigned i(n); i; --i) {
//      for (unsigned j(n - i + 1); j; --j) printf("%3u", Apr[i][j]); putchar(0x0A);
//    }
    printf("%llu\n", Ans % Mod);
    return 0;
  }
  Ans = 0;
  for (Node *i(N); i <= CntN; ++i)
      for (char j(0); j < 26; ++j) if(i->E[j]) ++(i->E[j]->Idg);
    *(++Tl) = N;
    while (Hd < Tl) {
      Node* Cur(*(++Hd));
      for (auto i:Cur->Son) if(!(--(i->Idg))) *(++Tl) = i;
      for (char i(0); i < 26; ++i) if(Cur->E[i])
        if(!(--(Cur->E[i]->Idg))) *(++Tl) = Cur->E[i];
    }
    /*for (unsigned i(1), j(1); i <= n; j = ++i) {
      Node* Cur(List[i]);
      while (Cur) {
  //    printf("i %u Cur %u j %u\n", i, Cur - N, j);
        unsigned LenMin(Cur->Link ? (Cur->Link->Len + 1) : 1);
        while (j >= LenMin) printf("%llu ", Cur->Get(j--));
        Cur = Cur->Link;
      }
      putchar(0x0A);
    }*/
//    for (unsigned i(1); i <= n; ++i) printf("%llu ", List[i]->Val); putchar(0x0A);
    for (char j(0); j < 26; ++j) if(N->E[j]) Ans += N->E[j]->Get(1);
    printf("%llu\n", Ans % Mod), Ans = 0;  
  return 0;
}

当时有好多人切了 T1, 而我发现这道题非常的简单, 我甚至在两三天之前做了一道根号分治 (三元环计数模板), 但是我中途往动态开点线段树那里想了, 所以越想越觉得不可做.

接下来我表示如果下午但凡有个字符串或者数数, 我都能翻, 因为我是字符串大师 + 计数天才. 这个说法是相对的, 因为我对各种自动机的理解比较透彻, 并且在计数方面没有下很大功夫, 但是可以比本校的人在这方面强一些.

D2T1 小 N 的独立集

好歹是 A 了一道题, 这是继 CSP2021 T2, NOIP2021 T2 之后, 我场上 AC 的又一道数数题. (貌似这个题被认为是 SDOI2022 最简单的一道题)

出场后问了别人才发现, 其实很多人不知道树形背包的复杂度其实是 $O(nV)$ 的. 所以好多人都不敢去写这个正解.

我和别人有一点不同, 就是我做题的时候大部分时间答案都是错误的, 当我可以保证正确性的时候, 我就已经把这道题做到 $100'$ 了, 而很多 AC 本题的选手则是一开始保证正确性, 不断优化得到了正解.

#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
inline unsigned RD() {
  unsigned Rtmp(0);
  char Rch(getchar());
  while(Rch < '0' || Rch > '9') Rch = getchar();
  while(Rch >= '0' && Rch <= '9')
    Rtmp = Rtmp * 10 + Rch - '0', Rch = getchar();
  return Rtmp;
}
inline int RDsg() {
  int Rtmp(0), Rsig(1);
  char Rch(getchar());
  while((Rch < '0' || Rch > '9') && (Rch ^ '-')) Rch = getchar();
  if(Rch == '-') Rsig = -1, Rch = getchar();
  while(Rch >= '0' && Rch <= '9')
    Rtmp = Rtmp * 10 + Rch - '0', Rch = getchar();
  return Rtmp * Rsig;
}
const unsigned long long Mod(1000000007);
unsigned n, m;
unsigned A, B, C, D, t;
struct Node {
  vector<Node*> E;
  unsigned f[5005][6], Size;
  inline void DFS(Node* Fa) {
    Size = m;
    if((E.size() == 1) && Fa) {
      for (unsigned i(1); i <= m; ++i) f[0][i] = 1;
      return;
    }
    for (auto i:E) if(i != Fa) i->DFS(this), Size += i->Size;
    unsigned Tmp[Size + 5][6], NoRoot[Size + 5], TNoR[Size + 5], Bot(0);
    unsigned MeL((Size + 5) << 2), MeB(MeL * 6), Cur(m);
    memset(NoRoot, 0, MeL);
    while (E[Bot] == Fa) ++Bot;
    memcpy(f, E[Bot]->f, MeB), Cur += E[Bot]->Size;
    for (int I(E.size() - 1); I > Bot; --I) if(E[I] != Fa) {
      Node* i(E[I]);
      memcpy(Tmp, f, MeB), memset(f, 0, MeB);
      memcpy(TNoR, NoRoot, MeL), memset(NoRoot, 0, MeL);
      unsigned *TTo, Mx, SMx;
      for (unsigned My(Cur); ~My; --My)
        for (unsigned Son(i->Size); ~Son; --Son) {
          for (unsigned k(m); ~k; --k)
            NoRoot[My + Son + k] = (NoRoot[My + Son + k] + (unsigned long long)TNoR[My] * i->f[Son][k]) % Mod;
          for (unsigned j(0); j <= m; ++j) for (unsigned k(0); k <= m; ++k) {
            if(j + k >= m) TTo = NoRoot + My + Son + j + k;
            else TTo = f[My + Son] + j + k;
            *TTo = (*TTo + (unsigned long long)Tmp[My][j] * i->f[Son][k]) % Mod;
          }
        }
      Cur += i->Size;
    }
    memcpy(Tmp, f, MeB);
    memset(f, 0, MeB);
    for (unsigned i(Size); ~i; --i) {
      f[i][0] = NoRoot[i] * (unsigned long long)m % Mod;
      for (unsigned j(0); j <= m; ++j) {
        f[i + j][0] = (f[i + j][0] + (unsigned long long)j * Tmp[i][j]) % Mod;
        for (unsigned k(j + 1); k <= m; ++k)
          f[i + j][k - j] = (f[i + j][k - j] + Tmp[i][j]) % Mod;
      }
    }
    char Flg(0);
    unsigned Ori(Size);
//    printf("Ori = %u\n", Size);
    while (!Flg) {
      for (unsigned i(0); i <= m; ++i) if(f[Size][i]) {Flg = 1; break;}
      if(!Flg) {
//        for (unsigned i(0); i <= m; ++i) printf("%u ", f[Size][i]); putchar(0x0A);
        --Size;
      }
    }
    Size += 5;
  }
}N[1005];
signed main() {
  freopen("nset.in", "r", stdin);
//  freopen("ex_nset2.in", "r", stdin);
  freopen("nset.out", "w", stdout);
  n = RD(), m = RD();
  for (unsigned i(1); i < n; ++i) {
    A = RD(), B = RD();
    N[A].E.push_back(N + B);
    N[B].E.push_back(N + A);
  }
  N[1].DFS(NULL);
  for (unsigned i(1); i <= n * m; ++i) {
    unsigned long long Ans(0);
    for (unsigned j(min(m, i)); ~j; --j) Ans += (i - j > N[1].Size) ? 0 : N[1].f[i - j][j];
    printf("%llu\n", Ans % Mod);
  }
  return 0;
}

这道题的心路历程是一开始没有保证状态为最大独立集, 而是把它当成一个求最大独立集的问题. 因为早就知道一般图最大独立集是个 NP Hard, 但是做题过程中发现树的最大独立集貌似可以求, 于是就想到了一个类似求最大独立集的 DP, $f_{i, j, 0/1}$ 表示一个点 $i$ 的子树中, $i$ 选/不选的最大独立集为 $j$ 的方案数, 手玩发现显然是错误的, 因为它不能转移, 转移则无法保证 $j$ 确实是某个方案的最大独立集 (当时是这样认为的, 其实事后发现并没有这么简单, 反正显然是错误的就是了).

接下来我又开始往别的方向去思考, 就是设 $f_{i, j, k}$ 表示 $i$ 选 $k$ 的情况下 ( $k = 0$ 则不选), $i$ 的子树的最大独立集为 $j$ 的情况, 这显然更加扯淡, 不一会手玩失败的我就放弃了想法.

其实场上我并没有搞懂为什么我最终的方程是正确的, 但是后来暴力哥的做法却给我指明了一条路: $f_{i, j, k}$ 表示 $i$ 的子树内, 最大独立集为 $j$ , $i$ 强制不选的最大独立集为 $k$ . 这样保存了两个值, 而我前面的做法只保留了一个有效的值, 第三维的值显然是对转移没有任何作用的. 这两个值就包括了 $i$ 的子树的权值分配方案在任何状态中的两种选择最大独立集的方案, 因为 $i$ 的父亲也就无非两种情况, 选或者不选, 如果它的父亲被某个方案中的最大独立集包含, 那么 $i$ 就强制不选, 否则 $i$ 没有限制, 可以直接按 $i$ 子树内的最大独立集来选.

而我当时考虑的也和这个过程差不多, 但是我没有想维护两个最大独立集, 我同样也是分析了这两种情况, $i$ 受限制和不受限制, 首先因为 $i$ 不受限制的合法的独立集完全包含了 $i$ 受限制的合法的独立集, 所以 $i$ 不受限的最大独立集一定不小于 $i$ 受限的最大独立集. 又因为 $i$ 受限的最大独立集和 $i$ 不受限的最大独立集的差值如果大于 $5$ , 那么我们完全可以从 $i$ 不受限的最大独立集中删除 $i$ , 得到一个合法的, 比原有方案更优的方案, 因此两者最大独立集的差不超过点权的上限. 所以我们记录一个 $j$ 表示受限的最大独立集, 然后 $k$ 表示如果我们给 $i$ 自由, 它可以给我们带来多少好处, 也就是 $i$ 不受限会让最大独立集增加多少, 这个值不超过 $5$ .

然后就把这道题做出来了. 树上背包的复杂度是 $O(n^2)$ , 这是老祖宗给我们留下来的精神瑰宝, 好多人因为不知道这个而不敢写, 痛失 AC.

D2T2 无处存储

刮痧题. 场上大部分选手们都刮了 $20'~50'$ , 只有我只刮了 $10'$ , 可能是因为 DFS 原因, MLE 导致只拿到了 $2'$ .

这两分就是只有 $3000$ 的那个点, 考场代码是这样的, 写了 $2\times 10^6$ 的单点修改, 单点查询但是没有过:

#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
#define Lbt(x) (((~(x))+1)&(x))
using namespace std;
inline unsigned RD() {
  unsigned Rtmp(0);
  char Rch(getchar());
  while(Rch < '0' || Rch > '9') Rch = getchar();
  while(Rch >= '0' && Rch <= '9')
    Rtmp = Rtmp * 10 + Rch - '0', Rch = getchar();
  return Rtmp;
}
inline int RDsg() {
  int Rtmp(0), Rsig(1);
  char Rch(getchar());
  while((Rch < '0' || Rch > '9') && (Rch ^ '-')) Rch = getchar();
  if(Rch == '-') Rsig = -1, Rch = getchar();
  while(Rch >= '0' && Rch <= '9')
    Rtmp = Rtmp * 10 + Rch - '0', Rch = getchar();
  return Rtmp * Rsig;
}
unsigned n, m;
unsigned A, B, C, D, Tmp(0);
unsigned Ans(0);
inline unsigned CalcV(unsigned x) {return x * (A * x + B) + C;}
unsigned Pre[1000005], Heavy[1000005], Cnt(0);
inline void Ins (unsigned x, unsigned y) {while (x <= n) Pre[x] += y, x += Lbt(x);}
inline void Qry (unsigned x) {Tmp = 0; while (x) Tmp += Pre[x], x -= Lbt(x);}
char FlgZ(0);
struct Node {
  vector<unsigned> Son;
  unsigned Fa, DFSr, Dep, Top;
}N[1000005];
inline unsigned DFS(unsigned x) {
  unsigned Size(1), CS(0), TS(0);
  for (auto i:N[x].Son) {
    N[i].Dep = N[x].Dep + 1, Size += (CS = DFS(i));
    if(TS < CS) TS = CS, Heavy[x] = i;
  }
  return Size;
}
inline void DFS2(unsigned x) {
  N[x].DFSr = ++Cnt;
  if(Heavy[x]) N[Heavy[x]].Top = N[x].Top, DFS2(Heavy[x]);
  for (auto i:N[x].Son) if(i != Heavy[x])N[i].Top = i, DFS2(i);
}
signed main() {
  freopen("problemprovidercreep.in", "r", stdin);
//  freopen("12.in", "r", stdin);
  freopen("problemprovidercreep.out", "w", stdout);
  A = RD();
  if(A == 31) FlgZ = 1;
  n = RD(), m = RD(), A = RD(), B = RD(), C = RD(), Heavy[0] = RD();
  for (unsigned i(2); i <= n; ++i) N[N[i].Fa = RD()].Son.push_back(i);
  N[1].Dep = 1, DFS(1), DFS2(1);
//  for (unsigned i(1); i <= n; ++i) printf("%u ", N[i].DFSr); putchar(0x0A);
  if(FlgZ) {
    for (unsigned i(1); i <= n; ++i) Heavy[N[i].DFSr] = CalcV(Heavy[N[i - 1].DFSr]);
    for (unsigned i(n); i >= 2; --i) Heavy[i] -= Heavy[i - 1];
    for (unsigned i(1); i <= n; ++i) Ins(i, Heavy[i]);
  }
  else {
    for (unsigned i(1); i <= n; ++i) Heavy[i] = CalcV(Heavy[i - 1]);
    for (unsigned i(1); i <= n; ++i) Ins(N[i].DFSr, Heavy[i]);
  }
  if(FlgZ) {
    for (unsigned i(1); i <= m; ++i) {
      Ans &= ((1 << 20) - 1);
      A = RD(), B = (RD() ^ Ans), C = (RD() ^ Ans);
      if(A) {
        Ans = 0;
        Qry(N[B].DFSr), Ans += Tmp;
        printf("%u\n", Ans);
      } else {
        D = (RD() ^ Ans);
        while (B && C && (N[B].Top ^ N[C].Top)) {
          if(N[N[B].Top].Dep < N[N[C].Top].Dep) swap(B, C);
          Ins(N[B].DFSr + 1, -D);
          Ins(N[N[B].Top].DFSr, D);
          B = N[N[B].Top].Fa;
        }
        if(N[B].Dep < N[C].Dep) swap(B, C);
        Ins(N[B].DFSr + 1, -D);
        Ins(N[C].DFSr, D);
      }
    }
    return 0;
  }
//  for (unsigned i(1); i <= n; ++i) printf("%u ", Heavy[i]); putchar(0x0A);
  for (unsigned i(1); i <= m; ++i) {
//    printf("Done %u\n", i);
    Ans &= ((1 << 20) - 1);
    A = RD(), B = (RD() ^ Ans), C = (RD() ^ Ans);
//    printf("%u To %u\n", B, C);
    if(A) {
      Ans = 0;
      while (B && C && (N[B].Top ^ N[C].Top)) {
        if(N[N[B].Top].Dep < N[N[C].Top].Dep) swap(B, C);
        Qry(N[B].DFSr), Ans += Tmp;
        Qry(N[N[B].Top].DFSr - 1), Ans -= Tmp;
        B = N[N[B].Top].Fa;
      }
//      printf("Jumped %u %u\n", B, C);
      if(N[B].Dep < N[C].Dep) swap(B, C);
      Qry(N[B].DFSr), Ans += Tmp;
      Qry(N[C].DFSr - 1), Ans -= Tmp;
//      printf("Tmp %u\n", Tmp);
      printf("%u\n", Ans);
    } else {
      D = (RD() ^ Ans);
      if(N[B].Dep < N[C].Dep) swap(B, C);
      while (N[B].Dep > N[C].Dep) Ins(N[B].DFSr, D), B = N[B].Fa;
      while (B ^ C)
        Ins(N[B].DFSr, D), Ins(N[C].DFSr, D), B = N[B].Fa, C = N[C].Fa;
      Ins(N[C].DFSr, D);
    }
  }
  return 0;
}

D2T3 多边形

其实当时写完 T1 先来干的是 T3, 写出了一个 $O(n^3)$ 的区间 DP, Hack 掉, 改 DP, 再 Hack. 其实问题的核心就是没法很好地断环为链, 所以心想再耗也不一定有结果, 不如去刮 T2.

所以这个题就摆烂了, 交了一个狗屁不通的代码上去:

#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
inline unsigned RD() {
  unsigned Rtmp(0);
  char Rch(getchar());
  while(Rch < '0' || Rch > '9') Rch = getchar();
  while(Rch >= '0' && Rch <= '9')
    Rtmp = Rtmp * 10 + Rch - '0', Rch = getchar();
  return Rtmp;
}
inline int RDsg() {
  int Rtmp(0), Rsig(1);
  char Rch(getchar());
  while((Rch < '0' || Rch > '9') && (Rch ^ '-')) Rch = getchar();
  if(Rch == '-') Rsig = -1, Rch = getchar();
  while(Rch >= '0' && Rch <= '9')
    Rtmp = Rtmp * 10 + Rch - '0', Rch = getchar();
  return Rtmp * Rsig;
}
const unsigned long long Mod(998244353);
inline void Mn(unsigned &x) { x -= (x >= Mod) ? Mod : 0;}
unsigned f[5005][5005], a[500005];
unsigned n, m, Nom;
unsigned A, B, C, D, t;
signed main() {
  freopen("polygon.in", "r", stdin);
//  freopen("polygon1.in", "r", stdin);
  freopen("polygon.out", "w", stdout);
  n = RD(), a[m = 1] = 1;
  for (unsigned i(1); i <= n; ++i) {a[m += RD()] = 1;if(!Nom) Nom = m;} --m;
//  for (unsigned i(1); i <= m; ++i) printf("%u ", a[i]); putchar(0x0A);
  for (unsigned i(m - 2); i; --i) {
    unsigned j(i + 1);
    while (!a[j]) ++j; ++j;
    if(j > m) continue;
    do f[j - i][i] = 1; while (!a[j++]);
//    printf("Done %u\n", i);
  }
//  for (unsigned i(2); i < m; ++i) {
//    for (unsigned j(1); j + i <= m; ++j) printf("%3u", f[i][j]); putchar(0x0A);
//  }
//  printf("Done\n");
  for (unsigned i(2); i <= m - 2; ++i) {
    for (unsigned j(m - i); j; --j) {
      if(j + i < m) {
        unsigned k(j + i + 1);
        do Mn(f[k - j][j] += f[i][j]); while (!a[k++]);
      }
      if(j > 1) {
        unsigned l(j - 1);
        do Mn(f[i + j - l][l] += f[i][j]); while (!a[l--]);
      }
    }
  }
//  for (unsigned i(2); i < m; ++i) {
//    for (unsigned j(1); j + i <= m; ++j) printf("%3u", f[i][j]); putchar(0x0A);
//  }
  printf("%u\n", f[m - 1][1]);
  return 0;
}