由于篇幅问题,题解太长的可能会只放个链接。

2020

联合省选

冰火战士

最优温度一定是某个战士的温度,所以可以先离散化。

显然总能量是能量较小一方的两倍,于是我们只需要二分两方的差值接近 $0$ 的位置即可。可以直接在树状数组上二分解决。

还要考虑温度最大的限制。假设 $0$ 左右的两个位置是 $p$ 和 $p+1$,那么如果 $ans_p>ans_{p+1}$ 则最优温度为 $p$,否则还需要二分出最大的答案为 $ans_{p+1}$ 的温度,同样可以在树状数组上二分解决。

时间复杂度 $\mathcal{O}(Q\log n)$,不懂开到 $2\times 10^6$ 的意义何在。

代码

组合数问题

$$ \begin{aligned} &\sum_{k=0}^nf(k)x^k{n\choose k}\\ =&\sum_{k=0}^n\sum_{i=0}^ma_ik^ix^k{n\choose k}\\ =&\sum_{i=0}^ma_i\sum_{k=0}^nx^k{n\choose k}\sum_{j=0}^k{k\choose j}\begin{Bmatrix}i\\j\end{Bmatrix}j!\\ =&\sum_{i=0}^ma_i\sum_{j=0}^i{n\choose j}\begin{Bmatrix}i\\j\end{Bmatrix}j!\sum_{k=0}^{n-j}x^{j+k}{n-k\choose j}\\ =&\sum_{i=0}^ma_i\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}n^{\underline{j}}x^j(x+1)^{n-j} \end{aligned} $$

代码

魔法商店

link

信号传递

link

考虑每个节点用一个数据结构维护子树中所有点的信息。

则我们需要支持插入、合并、全局加 $1$、求全局异或和四个操作。

可以用 01-Trie 来维护。前面两个操作是基本操作。

考虑全局加 $1$。如果是一个偶数,它的最低位会变为 $1$;否则它的最低位会变成 $0$,然后给次低位加上 $1$,仍然可以根据次低位讨论。放到 Trie 树上就是从低到高枚举每一位,交换当前节点的左右儿子,然后往 $0$ 对应的儿子递归下去。

全局异或和在上面三个操作的同时维护一下即可。

代码

作业题

首先莫比乌斯反演一下,那么我们就是要求所有边权是 $d$ 的倍数的边构成的子图的所有生成树边权和的和。

令每条边的边权为 $wx+1$,那么矩阵树定理求出的多项式的一次项系数即为答案。

因为只要求一次项系数,所以可以对 $x^2$ 取模,只需要手推一下求逆即可。

直接跑也不一定跑得过去,可以加一个剪枝:如果满足条件的边数 $<n-1$ 就不算。

复杂度据说是 $\mathcal{O}(n^2\sum \mathbf{d}(w_i))$。

代码

卡牌游戏

显然每次都会选最左边的两张,直接模拟即可。

代码

消息传递

点分治模板。把询问挂到点上,对每个分治重心统计经过它的路径即可。注意把同一棵子树中两条路径的情况减掉。

代码

幸运数字

暴力就是把所有可能的数拿出来,然后每个奖励相当于区间异或,可以差分维护。

问题是可能的数实在是太多了,事实上我们只需要把端点周围的若干个数拿出来即可。注意要把 $-\infty$、$+\infty$ 和 $0$ 也拿出来。

代码

丁香之路

走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数,这个条件长得很像欧拉回路。

我们首先把 $m$ 条关键边连上,然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点,显然相邻的两个间连一条边是最优的。这样子满足了度数限制。

但是我们还需要让图连通。我们把所有连通块缩成一个点,然后求最小生成树,那么可以花费最小生成树上边权和的两倍的代价让图连通起来。

时间复杂度 $\mathcal{O}(n^2\log n)$。

代码

BJOI

封印

首先求出 $L_i$ 表示最小的满足 $s_{j..i}$ 是 $t$ 的子串的 $j$,并设 $len_i=i-L_i+1$。这可以通过对 $t$ 建 SAM,然后按照求 LCS 的方法把 $s$ 丢上去匹配来求出。

答案即为 $\max_{i=l}^r\left\{\min\left\{len_i,i-l+1\right\}\right\}$。

注意到一定存在一个分界点 $p$ 满足 $\forall i\in[l,p),i-l+1<len_i$、$\forall i\in[p,r],len_i\leq i-l+1$。这个分界点可以直接二分求出,$[p,r]$ 中 $len$ 的最大值可以用 ST 表求出。

代码

2019

十二省联考

异或粽子

类似 NOI2010 超级钢琴

首先求一遍异或前缀和,设为 $s_i$。

考虑固定右端点,求出与 $s_r$ 异或和最大的 $s_{l-1}$,把这些值全部存到一个堆里。于是只要每次取出堆顶,然后把右端点固定、异或和的排名小 $1$ 的异或值存到堆里,重复 $k$ 次即可。

我们需要支持求某个前缀中和某个值异或后第 $k$ 大的值,可以用可持久化 Trie 实现。

代码

字符串问题

link

骗分过样例

1_998244353 就是求 $19^x$ 对 $998244353$ 取模后的结果。根据欧拉定理,读入时对 $\varphi(998244353)$ 取模即可。

1? 是模数未知,可以暴力枚举模数,得到模数是 $1145141$。

1?+ 是也是模数未知,且模数很大。对数据进行分析可以找到这样两行:

264708066 1996649514996338529
264708068 1589589654696467295

从而模数一定是 $719200885258981741674$ 的因数,且大于最大值 $5211500658258874318$,同样可以枚举。最后得到模数为 $5211600617818708273$。

1wa_998244353 根据提示可以猜出是暴力乘的时候把 19ll* 写成了 19* 导致爆了 int。可以发现结果存在从 $19^{55245}$ 开始的、长度为 $45699$ 的循环节,于是把循环节找出来直接算即可。

2p 是判质数,直接 Miller-Rabin 即可。

2u 是求莫比乌斯函数。先筛出 $10^6$ 内的质数,然后枚举每个质数 $p$ 在 $[l,r]$ 内的倍数并把它们除掉 $p$。这样子 $[l,r]$ 内的数会剩下至多 $2$ 个质因子,先用 Miller-Rabin 判断它是否为质数,再判断它是否为完全平方数,即可得知它的质因子情况,从而推出 $\mu$ 值。这个点很卡常,需要仔细优化。

2g 是判原根。一个做法是对 $\varphi(p)$ 质因数分解,然后如果每个 $p_i$ 都满足 $a^{\frac{\varphi(p)}{p_i}}\neq 1$ 则 $a$ 是原根,复杂度 $\mathcal{O}((r-l+1)\mathrm{d}(p)\log p)$。另一个做法是先找到最小原根 $g$,那么如果 $a=g^x$ 满足 $\gcd(x,\varphi(p))\neq 1$,则 $a$ 不是原根;于是可以枚举 $\varphi(p)$ 的质因子,然后筛掉它的倍数判断每个数是否合法,复杂度 $\mathcal{O}(p\log p)$。

2g? 同样是判原根,只是有一个模数未知。暴力枚举,可以求出模数为 $1515343657$。事实上可以和出题人斗智斗勇从中间开始枚举质数来很快地找到模数。

代码

皮配

link

春节十二响

先考虑一条链的情况:

  • 如果 $1$ 是端点,那么显然只能每个程序单独成一段,答案即为 $\sum M_i$;
  • 如果 $1$ 不是端点,那么两条子链中的最大值分成一段、次大值分成一段、…… 是最优的,可以用两个堆维护。

考虑扩展到树上。对每个节点开一个堆维护其划分成的若干段的最大值,每次与子节点启发式合并即可。

代码

希望

link

BJOI

奥术神杖

这是一个分数规划问题,考虑二分答案,问题变为求 $\sum v_i-mid\times cnt$ 的最大值。直接在 AC 自动机上 DP 即可。

代码

勘破神机

link

送别

link

排兵布阵

对每座城堡分开考虑,相当于一个分组背包问题,直接 DP 即可。

代码

光线

首先要大概想清楚光线在其中透射、反射的过程。

设 $f_i$ 为前 $i$ 块玻璃、从第 $1$ 块玻璃射入的透射率,$g_i$ 为前 $i$ 块玻璃、从第 $i$ 块玻璃射入的反射率。

不难列出递推式

$$ \begin{aligned} f_i&=f_{i-1}a_i\sum_{j\geq 0}(b_ig_{i-1})^j=\frac{f_{i-1}a_i}{1-b_ig_{i-1}}\\ g_i&=b+i+g_{i-1}a_i\!^2\sum_{j\geq 0}(b_ig_{i-1})^j=b_i+\frac{g_{i-1}a_i\!^2}{1-b_ig_{i-1}} \end{aligned} $$

边界是 $f_1=a_1,g_1=b_1$。

代码

删数

可以发现一个事情:我们把每个值的出现次数看成这个值对应的一根“柱子”的高度,然后把所有柱子向左推倒,那么最少需要修改的数的个数即为 $[1,n]$ 中未被柱子覆盖的数的个数。

于是可以直接用线段树维护,区间平移维护平移标记即可。在平移时两侧的柱子可能会进来、出去,需要及时加入和去除掉。

代码

GXOI / GZOI

与或和

拆位,那么只需要计算全 $1$、全 $0$ 子矩阵的个数,悬线法即可。

代码

宝牌一大堆

首先可以发现打杠子是不优的,因为 ${4\choose 4}\times 2^4<{4\choose 3}\times 2^3$。

七对子和国士无双是很好计算的,我们只考虑计算 $3\times 4+2$ 的最大分数。

设 $f_{i,j,k,x,y,z}$ 表示前 $i$ 张牌、凑了 $j$ 个顺子和刻子、$k$ 个雀头、$i-2$ 用了 $x$ 张、$i-1$ 用了 $y$ 张、$i$ 用了 $z$ 张的最大得分,转移讨论一下即可。为了方便可以在 $i$ 处计算 $i-2$ 的贡献、在 $34$ 处计算 $32,33,34$ 的贡献。

代码

特技飞行

显然强行二合一。

首先用 std::set 找出所有交点,然后将坐标系旋转 $45^\circ$ 后扫描线即可求出 $C$ 的贡献。

接下来考虑两种极端情况,即对向交换最多和最少。首先全部对向交换一定是可以的;否则考虑全部擦身而过得到的置换,一次对向交换相当于交换两个数,所以我们至少需要 $n-$环数 次对向交换。

代码

逼死强迫症

OEIS;矩阵快速幂即可。

代码

旅行者

link

旧词

先考虑 $k=1$ 的情况:对于所有 $i\leq x$,把 $1\to i$ 路径上的点权加 $1$,然后 $1\to y$ 路径上的点权和即为答案。

扩展到 $k\neq 1$ 也很简单:把加 $1$ 变成加 $dep_u\!^k-(dep_u-1)^k$ 即可。正确性显然。

只需要把询问离线按 $x$ 排序后扫描,用树剖+线段树维护即可。

代码

SDOI

快速查询

记两个标记 $addv$ 和 $mulv$,表示全局乘和全局加,并维护 $sumv$ 表示所有元素的和。

全局加和全局乘很好处理;全局赋值也很好处理,只需要令 $mulv\gets 1$、$addv\gets w$ 即可。

考虑单点赋值。我们直接开一个 unordered_map 存下所有被单点赋值过的点,每次只需要将 $\frac{w-addv}{mulv}$ 插入其中即可。我们只要在全局赋值时清空这个 unordered_map 即可。

单点查询时,只需要查询 unordered_map 中有无 $p$ 来得到对应值,再乘上 $mulv$ 并加上 $addv$ 即可得到真实值。

同时不难在修改操作中维护 $sumv$(对于单点赋值可以把原来的减掉再加上新的值),这样子也支持了全局求和。

线性预处理逆元,即可做到 $\mathcal{O}(qt)$。

代码

热闹的聚会与尴尬的聚会

题目中的条件相当于 $(p+1)(q+1)\geq n$。

第一问可以每次选一个度数最小的点删去,然后更新答案。用堆维护可以做到 $\mathcal{O}(n\log n)$。

第二问是求独立集,也可以每次选一个度数最小的点,然后把它和与它相连的点都删去。

可以证明这样子一定是满足条件的。设第 $i$ 次删掉的点的度数为 $d_i$,那么有 $\sum_{i=1}^q(d_i+1)\geq n$,而 $p=\max\{d_i\}$,故 $(p+1)(q+1)\geq n$ 必成立。

代码

移动金币

一次移动后会让左边的空位减少若干,右边的空位增加若干,从而可以转化为一个阶梯博弈。

不妨把左右反过来,那么就是要算有多少种方案满足编号为偶数的空位的异或和不为 $0$。

再转化问题,相当于求 $n-m$ 个物品放进 $m+1$ 个盒子中,使得编号为偶数的盒子中的物品数的异或和不为 $0$ 的方案数。

这个不为 $0$ 不好处理,可以容斥一下,变成算为 $0$ 的。那么就是每一位上为 $1$ 的数都要是偶数个。

考虑 DP。设 $dp_{i,j}$ 表示最高的 $i$ 位、还剩 $j$ 个物品没放的方案数,转移枚举放入的盒子数 $k$:

$$ {(m+1)/2\choose k}dp_{i,j}\to dp_{i-1,j-k\times 2^{i-1}} $$

最后枚举没放的物品数,用把这些物品放到奇数盒子中去即可算出答案。

代码

连续子序列

考虑 T.M. 序列的另一种生成方式:从 $0$ 开始,每次将 $0$ 替换为 $01$、$1$ 替换为 $10$。

这样子就可以考虑 DP。设 $f_{s,k}$ 表示以 $s$ 为前缀的长度为 $|s|+k$ 的连续子序列数,转移枚举 $s$ 的两种划分方式即可。注意特判边界情况。

复杂度不太会证(

代码

SNOI

字符串

直接排序,问题在于比较两个串的大小,即求出两个串的 LCP 然后比较后面一位。可以发现这道题中只会用到相邻两个后缀的 LCP,直接 $\mathcal{O}(n)$ 求出即可。

代码

数论

link

通信

link

纸牌

考虑一个 DP。设 $dp_{i,j,k}$ 表示前 $i$ 种牌、$(i-1,i,i+1)$ 选了 $j$ 个、$(i,i+1,i+2)$ 选了 $k$ 个的方案数,这里 $j,k\in\{0,1,2\}$。

转移分类讨论一下(设 $s=j+k+l$)

$$ dp_{i+1,k,l}\gets\begin{cases}dp_{i,j,k}\times\left(\lfloor\frac{C-s}{3}\rfloor+1\right),& a_{i+1}\leq s \\ dp_{i,j,k}\times\left(\Big\lfloor\frac{C-s-3\lceil\frac{a_{i+1}-s}{3}\rceil}{3}\Big\rfloor\right),& a_{i+1}>s\end{cases} $$

$a_i\neq 0$ 的纸牌只有 $1000$ 种,在这些位置之间矩阵快速幂转移、这些位置上暴力转移即可。

代码

TJOI

甲苯先生的字符串

矩阵快速幂即可。

代码

甲苯先生的滚榜

平衡树板子题。

代码

唱、跳、rap 和篮球

link

大中锋的游乐场

分层图最短路。

代码

甲苯先生和大中锋的字符串

建 SAM,差分统计即可。

代码

2018

九省联考

一双木棋

min-max 搜索即可。可以状压每一行的右边界来作为状态。

代码

IIIDX

先考虑一个贪心。我们把 $d_i$ 从大到小排序,那么每个子树都对应一段区间,我们把儿子按照编号排序,然后把区间依次划分下去即可。

这样子只能通过所有 $d_i$ 互不相同的点,原因是在 $d_i$ 相同时可以通过一些交换使得编号小的点的 $d_i$ 变大。

考虑修正这个贪心。我们维护 $c_i$ 表示 $\leq d_i$ 的可用的难度的个数,那么节点 $u$ 只能选择 $c_i\geq sz_u$ 的 $d_i$,而 $c_i$ 是不降的,所以一定会选最大的那个。

我们按照 BFS 序枚举所有点。假设 $u$ 已经选好了难度,那么其子树中的难度值就只能 $\geq d_i$ 了,又因为我们不知道子树会选择哪些,所以把 $c_{i..n}$ 都减去 $sz_i$,相当于为子树预留位置。在第一次进入某一棵子树时,我们需要把它父亲预留的位置给加回去。

以上操作可以通过线段树实现,找位置可以在线段树上二分。需要注意的是找到的难度可能不是相同的中最靠右的,我们要强制选择最靠右的位置。

代码

秘密袭击

link

劈配

我们对匈牙利算法进行一些修改,使得它能够让导师匹配多个学员,即可解决第一问。具体的,按排名顺序枚举左部点,然后找到最高的能够匹配的志愿。在匹配时,如果某个导师队伍没有满员就加入,否则看一下这个导师队伍里有没有人能换成同志愿的导师即可。

第二问可以二分每个人最后的排名解决。具体的,记录每个前缀的匹配情况,只需要在 $mid-1$ 的情况下看能否匹配即可。

代码

林克卡特树

问题相当于选出恰好 $k+1$ 条点不相交的路径使得权值和最大,这里 $1$ 个点也算一条路径。

先考虑一个朴素 DP。设 $dp_{i,j,0/1/2}$ 表示以 $i$ 为根的子树、选了 $j$ 条路径、$i$ 的度数为 $0/1/2$ 的最大权值和,转移讨论各种情况把子树合并进来即可。

设 $f(k)$ 为选恰好 $k$ 条点不交路径时的最大权值和,通过打表或者感性理解可以知道 $f(k)$ 是凸的,于是可以考虑 WQS 二分。

具体的,二分斜率 $m$,则我们需要求 $b=f(x)-mx$ 的最大值。

这个东西相当于每条链有 $-m$ 的额外价值,仍然可以 DP。设 $dp_{i,0/1/2}$ 表示以 $i$ 为根的子树、$i$ 的度数为 $0/1/2$ 的最大权值和以及此时最小选的链数,转移同样讨论各种情况把子树合并进来即可。

代码

制胡窜

link

BJOI

求和

注意到 $k$ 很小,对每个 $k\in[1,50]$ 求出树上前缀和即可。

代码

二进制

link

染色

这里只给出结论,具体证明可以参照这篇

首先拓扑排序把所有度数 $\leq 1$ 的点删掉。

首先判掉有奇环的情况,显然答案为 NO。下面只考虑图中仅有偶环的情况。

依次考虑每个连通块,设 $V$ 为点数,$E$ 为边数,那么

  • 如果 $E\leq V$,显然答案为 YES
  • 如果 $E\geq V+2$,答案为 NO
  • 如果 $E=V+1$,找到图中仅有的两个度数为 $3$ 的点,它们之间会有三条路径,答案为 YES 当且仅当三条路径的边数分别为 $2$、$2$、偶数。

直接判断即可。

代码

双人猜数游戏

link

链上二次求和

设 $s_i$ 为 $\sum_{j=1}^i a_j$,$s2_i$ 为 $\sum_{j=1}^i s_j$。答案为

$$ \sum_{i=l}^r\sum_{j=i}^n s_j-s_{j-i}=(r-l+1)s2_n-\sum_{i=l-1}^{r-1}s2_i-\sum_{i=n-r}^{n-l}s2_i $$

于是我们只需要支持对区间加、区间查询二阶前缀和的区间和即可。不难发现这个贡献是一个二次函数的形式,只需要维护一个二次函数式的标记即可。

因为是一条链所以会有 $l>r$ 的情况,需要注意。

代码

治疗之雨

link

2017

BJOI

机动训练

显然拆成两条路径相同的方案数计算。

枚举两条路径的方向,然后再枚举两个起点,计算方案数。这里会算重,需要容斥,容斥系数为 $(-1)^c$($c$ 为平行与坐标轴的方向数)。

计算方案数时枚举下一步的方向、记搜即可。

代码

树的难题

显然考虑点分治,下面考虑如何对一个分治中心计算答案。

首先把所有出边按颜色排序,使得相同颜色的紧挨在一起,方便下面的处理过程。

对于某棵子树,我们先找出其中所有路径,并记录长度和权值。

因为路径合并和长度、顶端颜色都有关,所以我们开两棵以长度为下标的线段树,分别维护顶端颜色与当前出边颜色不同 / 相同的路径。我们只需要将当前子树中的每条路径在两棵线段树上查一下对应长度范围内的最大值,然后全部插入到第二棵线段树中,并在出边颜色改变时合并两棵线段树即可。

代码

魔法咒语

显然强行二合一。

首先对禁止词汇建 AC 自动机,那么第一问就是一个简单的 DP。

第二问的话,只会从 $f_{i-1}$ 和 $f_i$ 转移到 $f_{i+1}$,因此可以考虑矩阵快速幂。转移大概是个这样的东西

$$ \begin{bmatrix}F_{i-1} & F_i\end{bmatrix}\times\begin{bmatrix}0 & T_2 \\ I & T_1\end{bmatrix}=\begin{bmatrix}F_i & F_{i+1}\end{bmatrix} $$

这里的 $F_i$ 表示 $\begin{bmatrix}f_{i,0} & \cdots & f_{i,tot}\end{bmatrix}$,$I$ 是单位矩阵,$T_i$ 是长度为 $i$ 的词的转移矩阵。

代码

喷式水战改

显然每段取同样的状态是最优的。

设 $f_{i,j}$ 表示前 $i$ 段、末尾是第 $j$ 种状态的最大能量,转移显然。

修改考虑动态 DP 的套路:不难把转移写成矩阵的形式,用平衡树维护即可。实现时有一些细节。

代码

最后修改:2021 年 01 月 26 日 08 : 46 AM