【泛做】简单题选做·第3季

终于!终于不是UVA了!

主要整理一下之前做过的有意思的题目,也算是巩固基础了吧。

争取一句话题解…这一弹大概有 $30$ 道题左右吧。

[Luogu4318]完全平方数

小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。

这天是小 X 的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一个小 X 讨厌的数。他列出了所有小 X 不讨厌的数,然后选取了第 K 个数送给了小 X。小 X 很开心地收下了。

然而现在小 W 却记不起送给小 X 的是哪个数了。你能帮他一下吗?

$K\leq 10^9$

考察 $\mu$ 的容斥意义的神题 orz

Sol 1

发现 $\mu$ 函数的性质,$\mu (x) = (-1)^k$,当且仅当 $x$ 不含平方因子,且 $x$ 的不同素因子个数为 $k$。

所以就考虑先二分,二分完了求一下 $1\sim x$ 中不是完全平方数倍数的数的数量是否 >mid。考虑这个东西怎么求。发现根据容斥,可以知道应该是「有 $0$ 个不同质因子的平方的倍数数量」-「有 $1$ 个不同质因子的平方的倍数数量」+「有 $2$ 个不同质因子的平方的倍数数量」。

另一方面,考虑对着每个不含平方因子的数 $x$ 计数,计包含 $x^2$ 的数的个数。根据容斥可以得到答案应该是:

原理是,根据 $\mu$ 的性质,具有平方因子的数不会被统计,同时容器系数恰好就是 $\mu$。

这东西可以直接 $\sqrt n$ 求。复杂度 $T \cdot \sqrt n \log n$

顺便记录一个很绝的 idea:

Sol 2

根据 $\mu$ 的性质,发现似乎只有 $\mu(x) = 0$ 时,$x$ 才会被讨厌。所以其实二分求的就是

然后这东西可以直接杜教筛。于是复杂度就变成了 $T\cdot n^{\frac{2}{3}} \log n$。然而实际记忆化了会更快。

总结

其实这个东西一定程度上证明了

这其实是可以反演出来的。考虑对左边进行变形,令 $\zeta(x)$ 表示 $x$ 最大的平方因子。那么有

其中第三个等号是借助了 $\mu$ 的性质:因为 $\zeta(i)$ 根据定义本身是一个完全平方数,所以如果 $d|\zeta(i)$ 但是 $d$ 不包含平方因子,说明 $d^2|\zeta(i)$ ;包含平方因子会被 $\mu(d)=0$ 直接干掉。最后一个等号是因为可以知道 $d>\lfloor\sqrt n\rfloor$ 时最后一个因式恒为 $0$ 。

这似乎是某次听课听来的内容…但是当时并没有整理这个。想来已经是远古时期的回忆了。

[UVA1614]Hell on the Markets

给出一个数列 $\{a_n\}$,保证 $\forall i, 1\leq a_i\leq i$。求是否可以分成相等的两半,并给出方案。

$n\leq 10^5$。

考虑一个引理。如果 $\forall i, 1\leq a_i\leq i$ 的话,那么 $\forall v\in[1,\sum_{j=1}^ia_j]\cap \mathbb{Z_+}$ 都可以被凑出来。 证明的话考虑数学归纳。即现在只需要证明 $[s_{i-1}+1,s_{i-1}+a_i]$ 可以被凑出来即可。发现对于一个 $s_{i-1}+k$ 而言,因为根据归纳 $[1,s_{i-1}]$ 都可以被 $a_1\sim a_{i-1}$凑出来且有 $s_i+k-a_i\leq s_{i-1}$ ,所以证毕。

那么综上,在判断 $v=\frac{\sum_{i=1}^na_i}{2}$ 是否可以被凑出来时,根据上面的贪心特性,要从后向前推,每次选择一个当前小于 $v$ 的最大值减掉即可。

[HNOI2011]数学作业

给定正整数 $n,m$,要求计算 $\text{Concatenate}(n) \bmod m$ 的值,其中 $\text{Concatenate}(n)$ 是将 $1 \sim n$ 所有正整数 顺序连接起来得到的数。

$1\le n \le 10^{18}$,$1\le m \le 10^9$。

…考虑递推,那自然是 $f_{i}=(f_{i-1}\cdot T+i)\bmod m$ 。其中 T 是根据不同的数字位数而变的这么一个计数器。于是就是分段矩乘即可。

[Luogu5110]块速递推

求这个数列第 $n$ 项模 $10^9+7$ 的值,一共有 $T$ 组询问。

$1\leq T\leq 5\times 10^7,1\leq n\leq 10^{18}$ 。

朴素的矩乘是 $8\cdot \log n$ 的样子。这样算出来复杂度是 $O(8\cdot T\cdot \log n)$ ,好像很慢的样子。

于是考虑预处理一点东西。比较常见的方法当然就是分块来做,预处理 $a^{1},a^{2},a^{3}\cdots a^{\sqrt n},a^{2\cdot \sqrt n},a^{3\cdot \sqrt n}\cdots$ 这些。那么复杂度度转化成了 $O(\sqrt n\log\sqrt n+8\cdot T)$。

注意到可以借助扩展欧拉定理 $a^b\equiv a^{b\bmod \varphi(m)+\varphi(m)}\pmod{m}$ 使得复杂度变成 $O(\sqrt{Mod}\log\sqrt{Mod}+8\cdot T)$ 。信仰一波就过了。

[USACO13JAN]Seating G

有一排 $n$ 个座位,$m$ 次操作。

A操作:将 $a$ 名客人安置到最左的连续 $a$ 个空位中,没有则不操作。

L操作:$[a,b]$ 的客人离开。

求A操作的失败次数。

$n,m,10^5$ 。

这…大概就是维护区间最长连续和然后再直接线段树上二分吧…发现自从领悟了线段树上二分之后,好多奇怪的线段树题也就都这么回事了…

[UVA1620] Lazy Susan

现在有一个大转盘,上面有 $n$ 个珠子,分别写有 $1\sim n$ 之间的正整数。

给出这些珠子的排列方式,现在你可以每次翻转连续的四个珠子。问你至少要进行几次操作,才能将这个转盘上的珠子变成 $1,2,…,n-1,n$ 的排列方式。

$4\leq n\leq 10^6$ 。

感觉还是比较有意思的题目?虽然是个结论题 233

首先考虑考虑序列中某段长度为 $x$ ,内部含有 $y$ 个逆序对的子段 $[l,r]$ 的性质:

(1) 该子段无论怎么重排,对 $[1,l-1]$ 的贡献不变,对 $[r+1,n]$ 的贡献不变。

(2) 该子段内部,顺序与逆序两种排布的逆序对数量之和为 $\frac{x^2+x}{2}$。

(3) 根据 $(1)$ 和 $(2)$ 可以得知,每次操作后,逆序对数量的变化量一定是 $(\frac{x^2+x}{2}-y)-y$ 。

回归到本题,可以知道每次逆序对的变化量肯定是 $6-2\cdot y$ 的形式。注意到序列翻转时,其他的指标都没有变,只有逆序对变了,所以可以用逆序对数量来衡量可达性。注意到每次增多/减少的数量都会是偶数,所以如果这个环不存在一个断裂使得逆序对数量为偶数,那么就不可以被变换成 $1,2,3,4\cdots n$ 。

这题原本的数据范围是 $10^3$ ,当然可以暴力枚举每个断裂。注意到,如果 $n$ 是奇数,且存在某个断裂的逆序对数也是奇数,那么这个环的所有断裂逆序对数都会是奇数。证明可以考虑,每次断裂的变化相当于把开头的元素移到结尾。那么假设当前开头元素是第 $k$ 大,那么可以知道这个元素会贡献 $n-k$ 个逆序对,移动到尾部后则会贡献 $k-1$ 个逆序对,$\Delta = k - 1 - n + k=2\cdot k - n - 1$ ,可知 $\Delta$ 本身一定是偶数。于是证毕,不可能出现偶数个逆序对的情况。

[APIO2012]派遣

在这个帮派里,有一名忍者被称之为 Master。除了Master以外,每名忍者都有且仅有一个上级。为保密,同时增强忍者们的领导力,所有与他们工作相关的指令总是由上级发送给他的直接下属,而不允许通过其他的方式发送。

现在你要招募一批忍者,并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水,同时使得支付的薪水总额不超过你的预算。另外,为了发送指令,你需要选择一名忍者作为管理者,要求这个管理者可以向所有被派遣的忍者发送指令,在发送指令时,任何忍者(不管是否被派遣)都可以作为消息的传递人。管理者自己可以被派遣,也可以不被派遣。当然,如果管理者没有被排遣,你就不需要支付管理者的薪水。

你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平,其中每个忍者的领导力水平也是一定的。

写一个程序,给定每一个忍者 $i$ 的上级 $B_i$ ,薪水 $C_i$,领导力 $L_i$,以及支付给忍者们的薪水总预算 $M$ ,输出在预算内满足上述要求时顾客满意度的最大值。

简化版题面:给定一棵树,求

其中设 $s$ 是以 $u$ 为根的子树中的某个点集,$\mathrm{card}$ 表示集合的元素个数, 则

$1\leq n\leq 10^6$ 。

读题读半天系列x

…发现是暴力,暴力选每个点当根,然后拿一个支持快速合并的数据结构对子树内的点进行合并,选出重量最小的那几个即可。注意到暴力合并的话似乎是要二分…这样一般而言复杂度就变成两个 $\log$ 了。但是如果每次插入完之后,统计答案时选择不断删掉当前 $c_i$ 最大的元素,这样就可以在保证正确性的同时降低询问的复杂度。发现可以直接拿左偏树来维护。复杂度 $O(n\log n)$ 。

[Luogu1858]多人背包

01背包的前 $k$ 优解。

$k\le 50,m\le 5000,n\le 200$ .

考虑暴力做并不简单,一个直观的想法就是再记一维 $k$ ,即 $f_{i,v,k}$ 表示考虑了前 $i$ 个物品,总体积为 $v$ 的 $k$ 优解是多少。考虑转移。通过观察单调性,可以发现当 $p>q$ 时, $i-1,v$ 时的 $p$ 优解是不会对 $i,v+w_i$ 时的 $q$ 优解产生贡献的,也就是说对于一个状态 $f_{i,v,k}$ ,都是从某个 $f_{i-1,v,j}$ 或者 $f_{i-1,v-w_i,j}+v_i$ 转移过来的。于是考虑直接把这两个状态集归并排序一下即可。复杂度 $O(n\cdot m\cdot k)$ 。

[SCOI2016]萌萌哒

一个长度为 $n$ 的大数,用 $s_1s_2s_3 \cdots s_n$表示,其中 $s_i$ 表示数的第 $i$ 位, $s_1$ 是数的最高位。告诉你一些限制条件,每个条件表示为四个数,$l_1,r_1,l_2,r_2$,即两个长度相同的区间,表示子串$s_{l_1}s_{l_1+1}s_{l_1+2} \cdots s_{r_1}$与$s_{l_2}s_{l_2+1}s_{l_2+2} \cdots s_{r_2}$完全相同。

求本质不同的大数个数。

$1\le n\le 10^5$,$1\le m\le 10^5$ 。

(以下默认并查集的复杂度是 $O(\log n)$ ,实际上这是一个很松的上界)

考虑暴力做当然是对每个位置开一个并查集,然后对于每个修改暴力 for 过去,这样最后答案就是 $9\cdot 10^{cnt-1}$ ,其中 $cnt$ 是不同的集合数量。这样做是 $O(nm\log n)$ 修改、$O(n\log n)$ 查询的。发现这样做的复杂度十分不平衡。考虑将复杂度向查询倾斜,即优化修改操作的复杂度。

考虑二进制拆分。对每个位置 $i$ 维护 $i\sim i+2^k-1$ 的连通状态,这样每次修改就是 $\log ^2n$ 的了。之后考虑对于一个长为 $2^k$ 的区间,可以push_down成两个长为 $2^{k-1}$ 的子区间再分别连边。于是查询的时候就可以直接查询了。

总复杂度 $O(m\log ^2n+n\log ^2 n)$ 。

[SCOI2010]生成字符串

lxhgww 最近接到了一个生成字符串的任务,任务需要他把 $n$ 个 $1$ 和 $m$ 个 $0$ 组成字符串,但是任务还要求在组成的字符串中,在任意的前 $k$ 个字符中,$1$ 的个数不能少于 $0$ 的个数。现在 lxhgww 想要知道满足要求的字符串共有多少个,聪明的程序员们,你们能帮助他吗?

$1\leq m,n\leq 10^6$ 。

这…理论上如果没有个数限制的话就是卡特兰数了吧。

考虑一个转化,从 $(0,0)$ 开始出发,设当前点为 $(x,y)$ 每次如果遇到 $1$ 就走到 $(x+1,y-1)$ ,每次遇到 $0$ 就走到 $(x+1,y+1)$,那么最终就是走到 $(n+m,m-n)$ 的、不跨过直线 $x=0$ 方案数。这…似乎是一个十分经典的组合问题了。大概就是考虑把走到 $y=1$ 这条直线以下的那些路径全都翻转到 $y=1$ 以下(做镜像对称),那么就可以看做是从 $(0,2)$ 走到 $(n+m,m-n)$ 的方案数。所以答案就是两者相减。

考虑怎么算这两部分。发现本质上从 $(0,0)$ 走到 $(n+m,m-n)$ 、每次向右下或者右上走的方案数。一种比较简单的理解就是从 $n+m$ 步里面选出 $n$ 步向右下走的方案数,所以答案是 $\binom{n+m}{m}-\binom{n+m}{m-1}$ ,因为从 $(0,2)$ 开始走相当于把其中向上走的某一步魔改成了成了向下走的,所以 $m$ 要减一。

[SP19148]Kill them All

$n$ 只怪兽,每一次可让 Digo 杀或 Sharry 杀。求在每杀掉一只怪物后,Digo 的击杀数都比 Sharry 的击杀数多的方案数。

$1\leq n\leq 10^6$ 。

回顾历史的时候顺便发现了这道题…

大概就是上个题把 $\geq $ 换成了 $>$ 。考虑首先让 $1$ 号怪兽必须被 Digo 干掉,那么就变成了从 $(1,0)$ 出发,走 $n-1$ 步,途中不能碰到 $y=0$ 的方案数。考虑最后走到的地方只会是 $(n,\lceil\frac{n}{2}\rceil),(n,\lceil\frac{n}{2}\rceil+1)\cdots (n,n)$,那么不妨对这些东西分别计数,那么答案就是

其中第一个 $1$ 是全部被 Digo 干掉的方案数。那么可以知道…这个式子里面前面的都被消掉了,最后只剩一个 $1+\binom{n-1}{\lceil\frac{n}{2}\rceil-1}-\binom{n-1}{0}=\binom{n-1}{\lceil\frac{n}{2}\rceil-1}$ 。 然后就没有然后了。

[UVA11149]Power of Matrix

给定整数 $k$ 和一个 $n$ 阶矩阵 $A$ ,求

$n\leq 100,k\leq 10^6$ 。

这题其实有两种做法。一种做法是 $O(n^3\log k)$ 的,另一种也是 $O(n^3\log k)$ 的,只不过会多一个 $8$ 的常数。

Sol 1

考虑对着这个找规律(雾),大概是考虑分块做,发现原来的式子可以写成:

那么就可以预处理再做了。这样复杂度是 $O(n^3\sqrt k)$ 的,好像大概是 $10^9$ 的复杂度…过不去。

不过既然分块可以,那倍增应该也可以。具体的,可以这么化:

那么这样就可以先预处理出 $n^3\log k$ 个 $A,A^2,A^4\cdots$ ,然后就可以再用 $n^3\log k$ 的时间预处理出 $s_1,s_2,s_4\cdots$ 其中 $s_i=\sum{A^i}$ 。之后就可以直接二进制拆分了。总复杂度 $n^3\log k$ 。

Sol 2

考虑直接对所有矩阵的和进行递推。计 $A^u$ 为当前矩阵的 $u$ 次幂,那么不妨构造一个复合矩阵

其中

发现它可以这么转移:

其中 $I_n$ 表示 $n$ 阶单位矩阵。然后就没有然后了。注意到这样做矩阵其实是升阶了,所以会带一个常数。

[SDOI2011]打地鼠

打地鼠是这样的一个游戏:地面上有一些地鼠洞,地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时,用锤子砸其头部,砸到的地鼠越多分数也就越高。

游戏中的锤子每次只能打一只地鼠,如果多只地鼠同时探出头,玩家只能通过多次挥舞锤子的方式打掉所有的地鼠。你认为这锤子太没用了,所以你改装了锤子,增加了锤子与地面的接触面积,使其每次可以击打一片区域。如果我们把地面看做 $m\times n$ 的方阵,其每个元素都代表一个地鼠洞,那么锤子可以覆盖 $r\times c$ 区域内的所有地鼠洞。但是改装后的锤子有一个缺点:每次挥舞锤子时,对于这的区域中的所有地洞,锤子会打掉恰好一只地鼠。也就是说锤子覆盖的区域中,每个地洞必须至少有 $1$ 只地鼠,且如果某个地洞中地鼠的个数大于 $1$,那么这个地洞只会有 $1$ 只地鼠被打掉,因此每次挥舞锤子时,恰好有$r\times c$ 只地鼠被打掉。由于锤子的内部结构过于精密,因此在游戏过程中你不能旋转锤子(即不能互换 $r$ 和 $c$)。

你可以任意更改锤子的规格(即你可以任意规定 $r$ 和 $c$ 的大小),但是改装锤子的工作只能在打地鼠前进行(即你不可以打掉一部分地鼠后,再改变锤子的规格)。你的任务是求出要想打掉所有的地鼠,至少需要挥舞锤子的次数。

Hint:由于你可以把锤子的大小设置为 $1\times 1$,因此本题总是有解的。

$1\leq m,n\leq 100$。

以下是翻车现场,这题根本没有「行列无关」的性质:

一道十分经典的行列无关技巧普及题目。但这题行列无?关比较的深刻。

考虑如果暴力枚举的话,复杂度大概是枚举 $r\times c$ 之后再一个一个打,这样复杂度是 $O(n^6)$,实现的好一点就可以 $O(n^4\log^2 n)$ 。但是,如果这题满足行列无关的话,就可以 $r$ 和 $c$ 分别枚举。准确来说,对于另一维设为 $1$,那么可以只去找这一维的最大值。考虑这么做判断的复杂度就是 $O(n^3)$,枚举的复杂度是 $O(n)$ 。那么最后总复杂度就是 $O(n^4)$ 。

那么唯一的问题在于如何证明行列无关在这题里面是对的。考虑对于所枚举的锤子大小所覆盖的某个区域,其中有两个点 $(a,b)$ 和 $(c,d)$ ,不同行也不同列,但是可以知道 $(a,b)$ 和 $(c,b)$ 的确定关系,$(c,d)$ 和 $(c,b)$ 的确定关系。即我断言,如果 $(a,b)$ 和 $(c,b)$ 满足同时合法,$(c,d)$ 和 $(c,b)$ 也同时合法,那么这三个点就可以同时合法,反之则不可以。

考虑这个断言为什么合理。发现每次如果以 $(c,b)$ 为量度去砸,那么 $(c,d)$ 和 $(a,b)$ 被砸的次数都只会与 $(c,b)$ 的地鼠数量有关,因为 $(c,b)$ 必须被精确砸完……

编不下去了,就当记结论了

然后就是一个二维差分,然后就没了。

[Luogu1357]花园

小 L 有一座环形花园,沿花园的顺时针方向,他把各个花圃编号为 $1 \sim n$。花园 $1$ 和 $n$ 是相邻的。

他的环形花园每天都会换一个新花样,但他的花园都不外乎一个规则:任意相邻 $m$ 个花圃中都只有不超过 $k$ 个 C 形的花圃,其余花圃均为 P 形的花圃。

请帮小 L 求出符合规则的花园种数对 $10^9+7$ 取模的结果。

$1\leq n\leq 10^{15},2\leq m\leq 5$。

发现一共只有两种方格,并且转移只跟 $m$ 有关,于是考虑状压。考虑 $g(s, t)$ 表示从状态 $s$ 转移到 $t$ 的方案数。其中转移指的是向右扩展一格。

那么显然这东西可以 dfs 预处理出来。然后发现这东西类似于 floyd 的转移矩阵,就可以快速幂了。考虑由于花圃是个环,那么合法的方案就是 $1…m$ 和 $n+1….n+m$ 要相同。所以就直接把开头结尾相同的累加一波即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(int x, int u, int s){
if (x == m + 1){
ok[s] = 1 ;
ans.ma[s >> 1][s] = 1 ;
if (u == k && ~s & 1) return ;
ans.ma[(s >> 1)|st[m]][s] = 1 ; return ;
}
dfs(x + 1, u, s) ;
if (u >= k) return ;
dfs(x + 1, u + 1, s | st[x]) ;
}

int main(){
cin >> n >> m >> k ;
for (int i = 1 ; i <= m ; ++ i)
st[i] = (1 << i) >> 1 ;
dfs(1, 0, 0) ; ans = expow(ans, n) ;
for (int i = 0 ; i <= 1 << m ; ++ i)
if (ok[i]) add(res, 1ll * ans.ma[i][i], P) ;
cout << res << '\n' ; return 0 ;
}

[UVA11134]Fabled Rooks

在一个 $n\times n$($1\leq n\leq 5000$)的棋盘上放置 $n$ 个车,每个车都只能在给定的一个矩形( $x_{l_i},x_{r_i},y_{l_i},y_{r_i}$) 里放置,使其 $n$ 个车两两不在同一行和同一列,判断并给出解决方案。

一道(真正)考察了行列无关知识的题目。

考虑放每个车时行与列显然是无关的,所以就可以分开做。那就是给定一堆区间,每个区间内选一个点使之不被放在同一个位置。贪一波就完了。

[NOI2005]瑰丽华尔兹

舞厅是一个 $N$ 行 $M$ 列的矩阵,矩阵中的某些方格上堆放了一些家具,其他的则是空地。钢琴可以在空地上滑动,但不能撞上家具或滑出舞厅,否则会损坏钢琴和家具,引来难缠的船长。每个时刻,钢琴都会随着船体倾斜的方向向相邻的方格滑动一格,相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法:如果不施魔法,则钢琴会滑动;如果施魔法,则钢琴会原地不动。

艾米丽是个天使,她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行的路程尽量长,这样 1900 会非常高兴,同时也有利于治疗托尼的晕船。但艾米丽还太小,不会算,所以希望你能帮助她。

$1\leq N$, $M \leq 200$,$K \leq 200$,$T\leq 40000$。K是时间段的数量,T 是总时间。

考虑最朴素的 $dp$ 就是 $f_{t,i,j}$ 表示时刻 $t$ 时在位置 $(i,j)$ 结尾的最长路径。转移时 $O(1)$ 的。但由于状态数太高导致不得不放弃。发现本质上每段时间内,转移的方向唯一。所以可以按段来 $dp$ ,$f_{k,i,j}$ 表示经过了 $k$ 段之后,结尾于位置 $(i,j)$ 的最长路径。这样状态数就是 $O(nmk)$ 的、转移是 $O(\max\{n,m\})$ 的了。发现由于每一段决策区间单调,且决策点彼此之间存在单调性,于是可以拿单调队列优化到均摊 $O(1)$ 转移。

[BalticOI2008]Elect

$n$ 个政党要组成一个联合内阁,每个党都有自己的席位数。

现在希望你找出一种方案,你选中的党的席位数要大于总数的一半,并且联合内阁的席位数越多越好。

对于一个联合内阁,如果某个政党退出后,其它党的席位仍大于总数的一半,则这个政党被称为是多余的,这是不允许的。

求最大席位并构造一组解。

$1\leq n\leq 300,1\leq m\leq 10^5$ 。

大概是长个经验?

发现倒着贪心并不是对的…虽然观察数据范围发现 $O(nm)$ 可过,但是一般情况下很难想到要去背包,因为有一个「多余」的限制…

但是发现如果从大到小排完序之后再背包,当前加进去的东西一定是最小的。此时如果出现把这个东西拿出来,剩下的都一定比这个大。所以不难理解这么更新的正确性。

考虑如何记录方案。可以对于每种权值都开一个 bitset,对于每种权值,第一次更新的时候顺便更新 bitset(根据单调性这样一定是最合法的那个)。那么最后的复杂度就是 $O(nm+\frac{nm}{w})$。注意到这么写的意义在于,通过聚和分析可以得知,对于每个权值 $m$ 至多会与其他的价值 $or$ 一次,所以本质上是 $O(\frac{nm}{w})$ 而不是 $O(\frac{n^2m}{w})$(虽然也能过就是了)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int f[MAXM] ;
int half, sum ;
int i, v, ans, n ;
bitset <MAXN> b[MAXM] ;
pair<int,int> base[MAXN] ;

inline bool cmp(pair<int,int> a, pair<int,int> b){ return a.fr > b.fr ;}
int main(){
cin >> n ; f[0] = 1 ;
for(i = 1; i <= n ; i ++){
scanf("%d", &base[i].fr) ;
sum += base[i].fr, base[i].sc = i ;
}
sort(base + 1, base + n + 1, cmp) ; half = sum >> 1 ;
for(i = 1; i <= n ; i ++){
for (v = sum ; v >= base[i].fr ; v --){
if (!f[v] && f[v - base[i].fr])
b[v] = b[v - base[i].fr], b[v].set(base[i].sc), f[v] = 1 ;
if (v > half && f[v] && v - base[i].fr <= half) ans = max(ans, v) ;

}
}
cout << b[ans].count() << '\n' ;
for (int i = 1 ; i <= n ; ++ i)
if (b[ans][i]) cout << i << ' ' ;
}

[LuoguP1531]鬼子进村

县城里有 $n$ 个用地道相连的房子,第 $i$ 个只与第 $i-1$ 和第 $i+1$ 个相连。这时有 $m$ 个消息依次传来:

  1. 若消息为 D x:鬼子将 $x$ 号房子摧毁了,地道被堵上。

  2. 若消息为 R :村民们将鬼子上一个摧毁的房子修复了。

  3. 若消息为 Q x:有一名士兵被围堵在 $x$ 号房子中。

李云龙收到信息很紧张,他想知道每一个被围堵的士兵能够到达的房子有几个。

$1\leq n,m\leq 5\times 10^4$。

降智题,说实话我第一眼觉得那必然是 LCT;又觉得可达性不好统计,然后就懵了 1min

其实是有两种方法的:

Sol 1

考虑暴力线段树维护,修复和拆毁都是单点修改。查询的话自然是查询一个点左边第一个 $0$ 的位置、右边第一个 $0$ 的位置。首先这显然是可以外层二分,内层区间查询来做到 $\log ^2$ 的(其实也可以不线段树维护,用分块技巧,$O(1)$ 查询区间和、 $O(\sqrt n)$ 单点加的分块,也可以通过本题,同时虽然插入删除都是 $O(\sqrt n)$ 的,但是询问变成了 $\log$ 的);或者直接在线段树上二分,做到一个 $\log$ 。

Sol 2

发下有一个性质并没有很好利用起来(虽然本身就是一个很没用的性质)。每次删除的点一定是之前插入的点。所以考虑对于所有炸毁的点维护一棵平衡树,以 $pos$ 作为键值,那么每次查询本质上就是询问前驱和后继。

……还有要注意可能本身就被炸了,判一下就好了。这种方法也是 $1$ 个 $\log$ 的。

[AT3741] String Problem

给出两个字符串S和T. 通过执行以下操作,判断是否可以将字符串S转换为字符串T.

  • 操作 A:删除S中任意位置的字母 A .
  • 操作 B:在S的任意位置插入一个字母 B .

S 和 T 的字符都为大写字母,并且 S 和 T 的长度 $\le 1000$ 。

……其实是水题,不过发生了一些奇妙的事情,然后就打算整理一下我的做法?感觉其他人的做法都一毛一样…

大概就是首先根据样例解释的提示,可以想出一个「先加 B 再删 A」的思路,然后发现前半部分就是一个魔改的 LCS,后半部分就只需要记录一下最少要用多少个 B,看看 s 比 t 多的那些字符是否全是 A 就好了。

[Contest Hunter5105] Cookies

圣诞老人共有 $m$ 个饼干,准备全部分给 $n$ 个孩子。每个孩子有一个贪婪度,第 $i$ 个孩子的贪婪度为 $g_i$。如果有 $a_i$ 个孩子拿到的饼干数比第 $i$ 个孩子多,那么第 $i$ 个孩子会产生 $g_i\times a_i$ 的怨气。给定 $n$、$m$ 和序列 $g$,圣诞老人请你帮他安排一种分配方式,使得每个孩子至少分到一块饼干,并且所有孩子的怨气总和最小。

$1≤n≤30, n≤m≤5000, 1\leq g_i\leq 10^7$。

首先不难想到要按照 $g_i$ 从大到小排个序,因为肯定要让 $g_i$ 大的人分到更多的饼干。之后设 $f_{i,j}$ 为前 $i$ 个人分了 $j$ 块饼干的最小怨气总和。发现并不好转移。因为要考虑有多少个人和 $i$ 获得的饼干数量相同。此时当然可以考虑多记一维,但是发现其实我们不关心饼干的具体数量,只关心彼此之间的相对关系。

考虑对于一个状态 $f_{i,j}$ ,如果让第 $i$ 个人只拿到 $1$ 个饼干,则考虑枚举前面有多少人同样拿了 $1$ 个饼干,此时有

注意到次数由于钦定了后 $k$ 个人都拿 $1$ 个饼干,所以前后就无关了,需要重新计算这 $k$ 个人的贡献。

如果让第 $i$ 个人拿到 $>1$ 块饼干,那么考虑由于不关心具体数量,所以这种情况等价于让所有人都少拿一块饼干,即 $f_{i,j}=f_{i,j-i}$ 。于是最后就对这两种情况取一个 $\min$ 即可。

[UVA1621] Jumping Around

一条 $[0,n]$ 数轴,一开始在 $0$ 处。每次可以选择向左/右以步长为 $1/2/3$ 跳到对应位置,分别只能最多跳 $a,b,c$ 次,保证 $a+b+c=n,a>3,b>3,c>3$ 。求构造一种跳的方案,使得跳到 $1\sim n$ 每个位置恰好 $1$ 次。

$1\leq n\leq 10^6$ 。

比较有趣的构造题吧…也是化归子问题的构造技巧。

考虑如果 $c=0$,如果此时 $a>1$ ,那么可以先不断向右以步长为 $1$ 走,直到 $a=1$,然后考虑以步长为 $2$ 向右跳,跳到不能继续跳的时候考虑向左或者向右用一个 $a$,之后再以步长为 $2$ 向左跳回来。可以知道这样一定是合法的。

如果 $c>0$ ,那么考虑化归到上一种情况。自然是想到,用完全部的 $c$ 跳到某个位置 $p$ 后,$1\sim p$ 都被覆盖了。这个地方有点神:

(1)如果 $3|c$,大概是考虑先用 $c/3$ 次跳到 $c$ ,然后向右用一个 $a$ ,再向左跳到 $1$ ,再向右用一个 $a$,再向右跳到 $c+2$ 。之后就变成了第一个问题。注意到由于 $a>3$,所以这种方法总是可行的。

(2)如果 $3|(c+1)$ ,考虑向右用一个 $a$ 转化到 $(1)$ 的情况。发现 $(1)$ 最多需要用到 $3$ 个 $1$ 且 $a>3$ ,这样做总是可行的。

(3)如果 $3|(c+2)$,考虑先向右一个 $c$ ,再向左一个 $b$,再向右一个 $a$。那么现在的 $c$ 的数量可以被 $3$ 整除。但是考虑由于(1)中的等价位置 $1$ 已经在第一次被跳了,所以最后一步要用 $b$ 。可以知道这样最多用 $2$ 个 $b$ ,也是合法的。

[Luogu3795]钟式映射

设集合 $N=M=\left\{x|x\in N_+,x\leq k,k\in N_+\right\}$ 。设 $f$ 为 $N$ 到 $M$ 的映射。求满足 $f[f(x)]=x$ 的不同的映射 $f$ 的个数。

$k\leq 10^{8}$ 。

说实话…我遇到这种题就会战术后仰然后不会…类似于什么置换啊、复合映射啊,我就蒙圈的很。

考虑新加入一个元素。对于一个 $x$,要么 $f(x)=x$,要么就会有一个 $y$ 和 $x$ 配对。所以有

然后就递推即可。

感觉这个式子本质上和错排可能会有点类似。考虑一个 $n-$完全错位排列 的方案数。假设 $n$ 号元素排到了 $k$ 号位置上,$k$ 号元素恰好也排在了 $n$ 号位置上,那么就是 $(n-1)\cdot g_{n-2}$ ;否则 $k$ 号元素随便错排,那么就是 $(n-1)\cdot g_{n-1}$。那么就是

感觉递推思想方面是有类似的吧…自己还是…太不聪明了啊

别找那些理由,就是泥萌的不努力!

[UVA1451]Average

给定一个长度为 $n$ 的 $01$ 串,选一个长度至少为 $L$ 的连续子串,使得子串中数字的平均值最大。如果有多解,子串长度应尽量小;如果仍有多解,起点编号尽量小。序列中的字符编号为 $1$ ~ $n$,因此 $[1,n]$ 就是完整的字符串。

$1\le n\le 100000,1\le L\le 1000$。

又到了复习斜率优化的时间了,斜率优化,常读常新。

考虑前缀和一下就转化成了对每个 $i$ 找到一个 $j<i$ 使得 $\frac{s_i-s_j}{i-j}$ 最大。发现这就是在求最大的斜率。考虑本质上 $x$ 坐标和 $y$ 坐标都是不降的,所以为了斜率单增,要维护一个下凸壳。于是拿一个单调栈维护斜率就好了。复杂度线性。

[HNOI2008]玩具装箱

P 教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。

P 教授有编号为 $1 \cdots n$ 的 $n$ 件玩具,第 $i$ 件玩具经过压缩后的一维长度为 $C_i$。

为了方便整理,P教授要求:

  • 在一个一维容器中的玩具编号是连续的。

  • 同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物。形式地说,如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中,那么容器的长度将为 $x=j-i+\sum\limits_{k=i}^{j}C_k$。

制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为 $x$,其制作费用为 $(x-L)^2$。其中 $L$ 是一个常量。P 教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过 $L$。但他希望所有容器的总费用最小。

对于全部的测试点,$1 \leq n \leq 5 \times 10^4$,$1 \leq L \leq 10^7$,$1 \leq C_i \leq 10^7$

大概是斜率优化板板题?考虑方程:

然后考虑拆一下,并且令 $p(i)=s(i)+i,q(i)=s(i)+i+L$ ,那么:

那么证明斜率优化可行的基本讨论就是找一个 $j$ 和一个 $k$ 来比大小:

若 $j>k$ 且 $j$ 比 $k$ 优,那么有

设 $X_i=q(i),Y_i=f_{i-1}-q(i)^2$,那么有

也就说当这个式子满足的时候,存在 $j>k$ 且 $j$ 比 $k$ 优。

所以对此可以直接采用斜率优化。注意到 $X$ 单增的同时,斜率本身不降;同时据此可以知道应该维护一个上凸壳,所以可以直接取到队首进行转移的元素。复杂度线性。

[HAOI2008]硬币购物

共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$。

某人去商店买东西,去了 $n$ 次,对于每次购买,他带了 $d_i$ 枚 $i$ 种硬币,想购买 $s$ 的价值的东西。请问每次有多少种付款方法。

$1 \leq c_i, d_i, s \leq 10^5$,$1 \leq n \leq 1000$。

比较常规的容斥题目。考虑由于硬币个数的限制,大概是要做一个多重背包计数,这样复杂度是 $O(4\cdot n\cdot s)$,大概是 $4e8$ 的级别,如果常数小的话没准信仰一波也是可以过的。

考虑更加正经一点的做法。发现虽然硬币个数很多,但是种类很少,同时发现不限制使用次数的方案数是很好计算的,于是考虑容斥。$f_v$ 表示不考虑硬币个数,用四种面值凑出 $v$ 的方案数。那么考虑如何统计不合法的方案数。考虑对于一种硬币 $(c_i,d_i)$,看上去,所有他的不合法方案应该是

但是发现背包模型在计算方案时,状态本身具有简并性。 也就是对于任何一个状态 $f_{i,k}$ 都是被更小的 $f_{i,k-t\cdot c_i}$ 给拼插起来的。所以方案数应该为

于是容斥一下即可。复杂度 $O(4\cdot s+16\cdot n)$ 。

[CF933A]A Twisty Movement

给定一个序列 A,你可以翻转其中的一个区间内的数,求翻转后的序列的最长不下降子序列的长度。($|A|\le 2000,1\le a_i \le 2$ )

$1\leq n\leq 10^3$。

自己想了一个暴力做法。大概是对于每个位置 $s$ ,可以比较方便地维护出 $s$ 之前以 $0/1$ 结尾的最长上升子序列,同时也可以维护出 $s$ 之后以 $0/1$ 开头结尾的最长上升子序列,这一部分不是那么直观,但是考虑对于一个位置 $p$ ,一定是有某个位置 $q>p$ 使得 $p+1\sim q$ 之间只选 $0$,$q+1\sim n$ 之间只选 $1$ 。这个东西倒着预处理似乎可以 $poly(\log)$ 或者线性,但是由于数据范围所以可以直接暴力。然后每次枚举两个端点暴力即可。中间可能要进行一下玄学的 dp。

……但其实是可以直接暴力 $dp$ 的。考虑最后选取的一定是一个形如 $1…2….1…2…$ 的子序列,于是就可以设状态 $f_{i,0/1/2/3/4}$ 表示分成了 $0/1/2/3/4$ 后的、形如这样的子序列。转移的话就是相邻状态转移即可。复杂度线性。

当然这题也存在一个闲的胃疼的高级做法,就是线段树上分别维护 $1 \rightarrow 1,1 \rightarrow 2,2 \rightarrow 1,2 \rightarrow 2$ 的最长上升子序列,然后暴力枚举每个区间,复杂度 $O(n^2\log n)$ 。

emmm 启发了一个 Idea 但是自己不会做,惨惨。

[LuoguP6435] 「EZEC-1」数列

给你一个正整数 $n$,有数列 $\{a_n\}:1,2,3,…,n$。

分别求相邻两项中左边一项的 $a$ 倍与右边一项的 $b$ 倍的和再加上 $c$,得到一个有 $n-1$ 项的新数列:

$1\times a+2\times b+c,2\times a+3\times b +c,…,(n-1)\times a+n\times b+c$。

对这个新数列重复上述操作得到若干数列,最后的数列只有一项,求最后这个项对 $p$ 取模的值。

$1\le n\le 10^{18}$,$1\le p \le 10^{14}$,$1 \le a,b\le 10^9$,$0\le c \le 10^9$ 。

…比较有意思的题目?本质上数学题。

考虑直接递推。设 $f_k$ 表示经历完 $k$ 次操作之后的第一项。那么考虑最开始 $a_2-a_1$ 的值是 $1$ ,之后每次会变成原来的 $(a+b)$ 倍,那么也就是有:

那么也就是

考虑高中数学技巧

那么可以通过差分得到

发现前面很好算,后面是一个等比数列的形式。由于不保证 $p$ 是素数,所以不能直接求逆元。于是考虑分治乘法。具体的,对于一个 $\sum_{i=1}^n(a+b)^i$ 可以这么算:

然后就可以分治做下去了。复杂度 $\rm poly(\log )$ 。

[UVA1611] Crane

输入 $n$ 个数,要求把它变成升序排列,每次操作都可以交换一个长度为偶数的区间的左右两半。要求操作数 $\leq 2n$ 。

$n\leq 10^6$ 。

大概是一道降智题…

考虑一个逐步缩小问题规模的思想。元素从小到大考虑,每次把当前未考虑的数列中最小元素 $x$ 移动到他该在的位置 $x$。考虑 $pos_x-x$ 与$\frac{n-x+1}{2}$ 的大小关系,如果 $2\cdot(pos_x-x)+1\leq n-x+1 $,那么就可以直接对区间 $[x,2\cdot pos_x-x]$ 进行操作,否则要先对 $[x,pos_x]$ 进行操作使其不会越界,因为此时 $pos_x-x$ 的长度会缩短为原来的 $\frac{1}{2}$,而由于最长时 $pos_x-x=n-x$ ,所以可知这样一定不会越界。

[LuoguP5007] DDOSvoid 的疑惑

给定一棵以 1 为根的有根树,定义树的一个毒瘤集为一个集合,并且集合中任意两个元素之间不存在祖先与后代关系。

定义一个毒瘤集的毒瘤指数为集合内所有元素的价值之和

要求给定树的所有毒瘤集的毒瘤指数之和,答案对 $10^8+7$ 取模。

但这个问题太难了,所以我们考虑化简。

因为点的编号跟它毒瘤指数密切相关,所以我们将会再给出一个整数 T,T = 1 表示 i 号点的毒瘤指数为 i,T = 0,表示所有点的毒瘤指数都是 1。

$1\leq n\leq 10^6$ 。

懵了半天还是不会做……

不难发现这个可以以子树为状态来转移。然后考虑如何将孩子的贡献转移到根,发现需要处理的本质上是合并两棵树的所有毒瘤集。假设两棵树的毒瘤集权值和分别为 $F_1,F_2$,那么发现合并得到的 $F$ 应该至少为 $F_1+F_2$,并且还需要考虑两棵树对彼此的贡献。即将一棵树中的所有元素都分批合并进另一棵树的集合里产生的贡献。

那么不难知道要记录一下各自树中毒瘤集的个数。于是考虑从下向上 $dp$。设 $g_u$ 表示以 $u$ 为根的子树中毒瘤集的个数,$f_u$ 表示权值和。那么每次考虑将一棵新的子树 $v$ 并进来,所以有转移:

复杂度 $O(n)$ 。