2024.9 模拟赛日志

• NOD2301（20240904）
• NOD2304（20240905）
• 2024年广州市赛第一试（20240907）
• 2024年广州市赛第二试（20240908）
• 金华一中24联训day15（20240910）
• SS240911（20240911）

NOD2301（20240904）

• [A 日记和最短路] 字符串字典序题，\(a<b\iff c+a<c+b\)，在 Trie 上维护倍增的哈希值。
• [B 日记和欧拉函数] \(\varphi(\varphi(n))\leq n/2\) 的数论题
• [C 日记和二叉搜索树] bitset 优化背包题
• *[D 日记和编辑器] 暴力平衡树（没必要改）

\(97+100+40=237\)。这场时间被折半了，然后 T1 是完全假的算法（写成往后加了，往后加是假的）。T3 的 bitset 优化背包如下：

template <int siz> int solve(int m, const vector<int>& vec) {
  if (siz <= m) return solve<min(siz * 2, 1000000)>(m, vec);
  bitset<siz> f;
  f[0] = 1;
  for (size_t i = 0, r = 0; i < vec.size(); i = r) {
    ++r;
    while (r < vec.size() && vec[r] == vec[r - 1]) ++r;
    for (size_t c = 1; i < r; i += c, c = min(c << 1, r - i)) {
      f |= f << (c * vec[i]);
    }
  }
  while (m && !f[m]) --m;
  return m;
}

solve<1>(m, vec) 返回 vec 的一个最大的“和不超过 \(m\)”的子集的和。使用倍增确定 bitset 大小，多重背包二进制拆分优化，复杂度据说是 \(O(n\sqrt n/w)\)（\(n=\sum a_i\)）

NOD2304（20240905）

• [A 魔力屏障] 智慧的区间 dp
• [B 诡秘之主] 区间的所有子区间的答案和。观察到性质之后，\(\leq 20\) 的二分找右端点，\(>20\) 的使用历史版本和线段树。
• *[C 博弈 / P4654] 博弈，树形 dp
• *[D 地雷] 很牛的区间 dp

\(0+25+0+0=25\)。时间折半场，只写了 T2 无数据结构的暴力。

2024年广州市赛第一试（20240907）

• [A Bbox] 矩阵快速幂
• [B 弃牌术] 多重背包
• [C 抛硬币] 三维偏序
• [D 游戏匹配] 安排顺序以限制背包值域（QOJ8049 [ECFinal23] Equal Sums 加强版）

\(100+0(100)+80(100)+40=220(340)\)。T2 写错一个细节爆零；T3 被卡常，不想改（也拿不到场上代码）。

2024年广州市赛第二试（20240908）

• [A 哈希] 数论，单位根反演
• B 乒乓球比赛 整除分块
• [C 萤火] 线段树合并维护树上直径
• [D 移动] 平衡树或分块维护分段一次函数复合（P10284 [USACO24OPEN] Splitting Haybales P 的同样技巧）

\(100+60+100+100=360\)。T2 属于是不够时间做。

金华一中24联训day15（20240910）

• [A Mansion] 回滚莫队
• [B Permutation] 简单的构造题
• [C Gird Game] 0/1 矩阵题，观察到性质以后哈希判断

\(100+100+70(100)=270(300)\)。T3 写了另外的场上觉得是对的做法，获得 WA 和 TLE。

SS240911（20240911）

• [A 天才俱乐部] 数论
• [B 实战教学] 二分以后转换为给 \(n\) 个区间，有交的两个区间可以匹配，问能否完美匹配（直接贪心不需要反悔）
• [C 穿越银匙之门] 无根树定根后刻画限制
• *[D 绳网委托 / gym103860I] 凸性，闵可夫斯基和或数据结构维护贪心

\(100+100+40+30=270\)。T4 好像是被卡常的，不是很懂。T3 没有想出来为什么答案会为 \(n\)，主要是被 T2 卡了没有写暴力。