THUPC2021 杂耍

# A

留坑。

# B

区间加，求位置 $i$ 上的数 $\geq\lceil\frac{x}{2}\rceil$ 的最早时刻。

主席树标记永久化 + 二分自然可以搞定，$O(m \log^2 n)$。

但是有更优的做法，将时间轴作为第二维，序列位置作为第一维，离线处理，则区间加变为时间轴上两个单点加，使用树状数组维护并在树状数组上二分即可，时间复杂度为 $O(m \log n)$。

# C

考虑如果我们可以在一次闹鬼事件中，对于 $x$ 所有的质因子 $p$ 中存在一个 $\geq X$ 即被触发怎么做。自然将监控器下放到每个质因子上，也就是在每个质因子上开一个小根堆维护监控器的权值 $y$，发生闹鬼事件的时候直接在每个质因子上统计即可。

接下来需要一定的人类智慧，我们知道若一次闹鬼事件 $(x,y)$ 触发了监控器 $(x_i,y_i)$，可以得出存在某个 $x_i$ 的质因子 $p$，在这个质因子上累计触发了 $\geq\lfloor\frac{y_i}{|\omega{fac}(x_i)|}$ 次。虽然这并不是充要条件，但它启发我们可以每次只修改这样的质因子 $p$ 处的监控器 $(x_i,y_i)$ 的贡献，即改变 $y_i$ 并刷新每个质因子处的 $\geq\lfloor\frac{y_i}{|\omega(x_i)|}$，我们认为它是一个下放到质因子上的监控器的阈值。由于 $\omega(x_i)$ 是 $O(\frac{\ln n}{\ln\ln n})$ 级别的，所以这样的更新不会进行很多次。

时间复杂度大概是 $O(6n\log_{\frac{6}{5}}n \log_2 n)$。

# D

以下称一种划分 ${[1,l],[l+1,r],[r+1,n]}$ 为划分 $(l,r)$，且 $u=a[1\dots l],v=a[l+1\dots r],w=a[r+1\dots n]$。

以下先给出不形式化的合法判定。

划分 $(l,r)$ 合法仅当 $u$ 仅失配左括号，$v$ 仅失配右括号，$w$ 仅失配左 $/$ 右括号。

如何形式化这个判定呢？

首先需要明确什么是合法括号序列的形式化判定。记

$$
S(i)=\sum_{i=1}^i 1-2\times[a[i]=')']
$$

则括号序列 $a$ 是合法的当且仅当 $\forall i\leq |a|,S(i)\geq 0$ 且 $S(|a|)=0$。我们称 $\forall i\leq |a|,S(i)\geq 0$ 的括号序列 $a$ 为合法的括号前缀，则合法的括号后缀是类似的，为 $\forall i\geq |a|,S(|a|)-S(i)\leq 0$。

可以想到若划分 $(l,r)$ 是合法的，必须满足以下三个条件：

- $u$ 是合法的括号前缀，即 $\forall i\leq l,S(i)\geq 0$
  
- $v$ 是合法的括号后缀，即 $\forall l<i\leq r,S(r)-S(i)\leq 0$

- $uw$ 是合法的括号前缀，即 $\forall i>r,S(l)+S(i)-S(r)\geq 0$

计数的话，对于条件 $1$ 很好处理，条件 $2$ 也无非就是对于一个 $r$ 找到最右端的 $L$ 令 $S(r)>S(L)$，则有效的 $l\in [L+1,R-1]$，于是转化成了一个二维数点问题。

$O(n\log n)$ 真的能过 $n=10^7$ 么？进行适当的基于题目性质的优化即可。例如处理条件 $1$ 与条件 $2$ 的交，在处理时其范围是远小于仅处理条件 $2$ 的；例如每个 $i$ 只会在二维数点上加入一次，因此修改操作不需要像传统的那种排序做法一样扔进去。细节还是有点多的。

# E

一眼 $DP$。

设 $g(l,r,0/1)$ 为消除 $[l,r]$ 后剩下的最少球数 $/$ 消除 $[l,r]$ 所需的最小栈空间。

可以发现消除的过程中我们需要寻找两个区间来辅助进行消除，或者直接把球扔进杯子里不进行消除。由于第二问的存在，我们希望这两个辅助区间在消除的过程中耗的栈空间尽可能小，于是继续 $DP$。设 $f(l_1,r_1,l_2,r_2)$ 为消除 $[l_1,r_1]$ 与 $[l_2,r_2]$ 所需的最小栈空间，转移类似于 $g(l,r)$，也是枚举辅助区间进行转移。

# F

比较简单。唯一的难度在于构造六个向量。

根据向量的合成，我一开始想到构造 $(-1,1),(-2,0),(-1,-1),(1,-1),(2,0),(1,1)$。设 $f(x,y,L_0,G_0)$ 为能否达到 $(x,y)$ 位置，且模意义下 $L=L_0,G=G_0$。时间复杂度为 $O(4n^2p^3)$。$\mathrm{bitset}$ 优化之后是 $O(\frac{4n^2p^3}{\omega})\approx 10^9$，仍然很离谱。

又是熟悉的人类智慧。注意到如果在 $x-y$ 平面上进行 $\pm 1$ 的游走，则 $x,y$ 坐标期望情况下均 $\leq \sqrt{n}$。

于是我们重新构造向量 $(0,1),(-1,0),(-1,-1),(0,-1),(1,0),(1,1)$，时间复杂度将为 $O(\frac{np^3}{\omega})$。

需要些许卡常和优化才能够通过本题。

# G

题意：求满足 $\forall s\in [1,m],\sum_{i=1}^n a_i=s$ 且 $\gcd(a_1,a_2,\dots a_n) \mid ks$ 的可重集合 ${a_i}$ 个数。

可以想到枚举 $s$，然后暴力做背包，时间复杂度为 $O(nm^3)$。

可以加一个简单的优化，枚举 $s$ 的时候我们只处理那些整除 $ks$ 但并不整除 $k$ 的，然后先做整除 $k$ 的背包。似乎不需要卡常也能过，时间复杂度我不太会算，大概是 $\sum_{i\leq m} \sqrt {i}$ 什么之类的。

# H

题意：一个 $n$ 个点的环要求连续的 $k+1$ 个点颜色不能相同，求最小染色数。

一眼题，显然有 $k+1+\lceil\frac{n\bmod ({k+1})}{\lfloor\frac{n}{k+1}\rfloor}\rceil$。

# I

答案为满足限制且 $\mathrm{xor}$ 不为 $0$ 的方案数，可以被写成满足限制的总方案数 - 满足限制且 $\mathrm{xor}$ 为 $0$ 的方案数。

满足限制的总方案数用容斥求出，为

$$
\sum_{S} (-1)^{|S|}\binom{n-\sum_{i\in S}(a_i+1)+m-1}{m-1}
$$

$\mathrm{xor}$ 为 $0$ 的方案数怎么求呢？注意到 $\mathrm{xor}$ 为 $0$ 等价于每一个二进制位上仅有偶数个 $1$。那么我们可以做类似数位 $DP$ 的东西了，即计数 $0\leq x_i\leq a_i$ 的 $(x_1,x_2,\dots,x_m)$ 的 $m$ 元组个数。设 $f[i,S]$ 为当前考虑到第 $i$ 位，已达到上界的 $a_i$ 的集合为 $S$。枚举子集以及未达到上界的 $a_i$ 这一位上填 $1$ 的个数，组合数统计贡献即可。

是不是漏了什么东西？还有 $\sum a_i = n$ 的限制。那就再加一维，设 $f[i,S,j]$ 为当前考虑到第 $i$ 位，已达到上界的 $a_i$ 的集合为 $S$，还需要 $j\times 2^i$。同之前的方式枚举，注意从高位转移下来的 $j$ 需要减去当前的进位然后再 $\times 2$ 转移到低位。

时间复杂度为 $O(3^mm^2\log n)$，$\text{200ms}$ 内可以跑过。

# J

oop 练习题，跳了。

# K

随便算一算你就发现随机枚举一个 $n$ 正确的概率特别大，建议使用 $\text{python}$。

# L

计算几何神仙题，不懂。

有个物理系神仙切了这题并且跑的飞快，我大受震撼。

# M

$\texttt{Interest}$ 和 $\texttt{Justice}$ 我当然选 $\texttt{Justice}$。