未归类问题

/kk

Posted by ShanLunjiaJian's Blog on February 9, 2023

标题五个字/cf


spoj CARD - Cardsharper

来自fajne zadania。

考虑每个元素会如何移动。在$a$上沿着一个环走,在$b$上同样沿着一个环走。

我们想起来一个经典问题,好像来自atc,说的是如果你能够转整个序列,或者转前三个元素,就可以排序。显然还有很多类似的东西。猜测我们总是可以生成绝大多数的排列。

事实证明确实是这样,在几乎所有情况下我们可以生成所有排列。但是我没有证明,并打算咕咕。

据说大力随机然后schreier-sims就好啦!


cf1578l

这个题是牛逼老哥给我看的啊。

跑个mst先。二分答案先。

时间倒流。然后在kru重构树上往上走即可。

于是也不需要二分答案了。


agc061a

先打表。观察小的感觉偶数的形式很好,这里给出16~30的偶数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
16
2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 
18
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17 
20
2 1(4 3)5 6 7 8 9 10 11 12 13 14 15 16 18 17 20 19 
22
2 1 3 4(6 5)7 8 9 10 11 12 13 14 15 16 18 17 19 20 22 21  
24
2 1(4 3)(6 5)(8 7)9 10 11 12 13 14 15 16 18 17 20 19 22 21 24 23 
26
2 1 3 4 5 6 7 8(10 9)11 12 13 14 15 16 18 17 19 20 21 22 23 24 26 25 
28
2 1(4 3)5 6 7 8(10 9)(12 11)13 14 15 16 18 17 20 19 21 22 23 24 26 25 28 27 
30
2 1 3 4(6 5)7 8(10 9)11 12(14 13)15 16 18 17 19 20 22 21 23 24 26 25 27 28 30 29 

可以注意到只可能是每对$2i-1,2i$交换,这是因为$\mathrm{shuffle}(1,n)=\mathrm{shuffle}(1,n-2),\mathrm{shuffle}(2,n-1),\mathrm{shuffle}(2,n-1),\mathrm{shuffle}(3,n)$,中间抵消了,然后归纳即可。括号标记的是除$n=16$之外,左半边非两头的交换了的位置。

$\mathrm{shuffle}(1,n-2),\mathrm{shuffle}(3,n)$,实际上就是把自己和自己平移一位之后每两个内部是否交换的状态$\operatorname{xor}$一下。于是我们看看$x\leftarrow x\operatorname{xor}(x\operatorname{shift}1)$是什么,把$\operatorname{xor}$看成加法膜$2$我们知道它是$F\leftarrow (1+z)F$,于是当我们想要一个位置的时候,提取出来是一个二项式系数膜$2$,可以用lucas定理算出它那里换没换。如果$n$是偶数那么做完了,如果$n$是奇数那么递归一层即可。


cf717a

求$\sum\limits_{i=l}^r\binom{f_i}{k}$,其中$f$是fib数。

看起来很是不好做。考虑下降幂转普通幂,我们算$\sum\limits_{i=l}^rf_i^k$。尝试塞通项$c(a^n+b^n)$然后二项式定理,它就是$\sum\limits_{j=0}^k\binom{k}{j}\sum\limits_{i=l}^r(a^jb^{k-j})^i=\sum\limits_{j=0}^k\binom{k}{j}\frac{(a^jb^{k-j})^l-(a^jb^{k-j})^{r+1}}{1-a^jb^{k-j}}$,这里需要特判$a^jb^{k-j}=1$的情况。复杂度$O(k^2\log v)$,可以预处理一些东西然后线性求逆做到$O(k^2)$。

洛谷讨论区的题

$f$是$a,b$-fib数,也就是$f_i=af_{i-1}+bf_{i-2}$。

那么问题就是怎么求通项了。$F=azF+bz^2F+f_0+z(f_1-f_0)$,设后面是$p+zq$,那么$F=\frac{p+zq}{1-az-bz^2}$。那么我们知道上面的$a,b$这里就是$1-az-bz^2$的两个根,剩下的东西就乱算一通!


cco2020 Shopping Plans

从xxiii poi stage 1 korale过来的。

首先每种买上最小的$x_j$个。然后第$k$小的钱数$d$,尝试搜出所有方案,我们要调整当前这个颜色到任意一个方案,可以通过在最右一个右边加入一个,或者把一个连续的后缀右移一位。

那么需要保证不能有重复的方案。为了做到这一点,考虑我们依次处理每个种类,也就是可以选择这个颜色的两种操作,或者移动到下一个颜色。我们需要保证移动到下一个颜色时能操作,所以按$2$和$1$位的差从大到小排,二分出可以到哪个后缀去。复杂度$O(n\log^2 n)$。

然后这东西也适用于那个扩展的想法,并且这样我们只需要二分$k$次。复杂度$O(n\log n)$。


loj6500 雅礼集训18 D2 操作

牛逼群友给我看的。

考虑最左边那个数,它确定了最左边的区间是不是需要操作,如此往右递推就是$O(nm)$。

注意到如果我们操作了$[l,l+k)$之后其中还有$1$,必然继续操作下去,但是这个复合有点困难。

还是考虑差分吧!那么操作就是把$s_i,s_{i+k}$同时$\operatorname{xor}$上$1$。于是每个膜$k$等价类中的$1$需要两两配对,答案就是这个距离和,那么处理每个等价类中奇数位置和偶数位置的前缀和,查询的时候差分一下扫描线扫过去就好了。还需要判断是否可行,也就是两边在各等价类状态的奇偶性是否相同,hash一下即可。


loj6736 最小连通块

这个题有一个牛逼做法啊。考虑我们可以$O(c(1+\log\frac{n}{c}))$地在$n$个点的树中找到一棵大小为$c$的子树中的所有点,然后我们还知道随机一个根和一个点,得到的子树大小期望是$<\frac{n}{2}$的,所以就$O(n\log n)$了。


tjoi2017 城市

有趣题。首先我们必然断直径上的一条边,然后我们会连两边的直径中点,那么问题是怎么求两边的直径中点,随便取一个直径端点为根做一边的,考虑直径中点总是在到任何一个点距离最大的点上,那么dp求出直径长度,长链剖分,从重儿子到父亲直径端点会沿长链向上shift若干步,总移动量是线性。


cf1776G

虽然反对出这种题,但是还是很厉害!


An Optimal Algorithm for Calculating the Profit in the Coins in a Row Game

pa2010 Termites/hnoi2010 取石头游戏

题意是若干个序列,每个序列可能有一端是锚定的或者没有。两个人每次选一个序列,取走一端,如果是锚定的则只能最后取走,都希望自己获得的总和尽可能大。求最终A获得的减去B获得的。

或者说锚定一端的是栈,没有的是deque。

显然每个人选的个数是确定的。

翻译一下论文。

定义一个策略是状态到选择的映射。定义$\operatorname{val}(a,b)$是A采用策略$a$,B采用策略$b$得到的结果。

如果A固定使用策略$a$,那么结果就是$\min\limits_b\operatorname{val}(a,b)$。为了证明$a_1$不比$a_2$优,我们可以对于每个$b_2$,找到一个$b_1$使得结果不会更大。这里$a_2,b_1$都是我们自己选择的。也就是说我们把证明一个策略不优转化成了一个博弈问题。阅读定理1获得更好的体验。

设最大值是$m$。

定理1 如果某个$m$可以选,那么必然选它。

证明 使用上面那个方法,我们同时进行两个博弈,不妨称为$M_A$和$M_B$。在$M_B$中我们操纵B,而A先手选择了某个序列的某端$t$上的数$x_t$。在$M_A$中我们操纵A,我们让A先手选择一个$m$。根据上面的结论,我们就是要找到一个策略,使得$M_A$的结果总是不比$M_B$小。

首先操纵B在$M_B$中选择$m$。这也是为什么命名为$M$。

接下来进行若干轮,保持$M_B$比$M_A$多进行一步。每轮让对手在两个游戏中各走一步,然后我们反过来走,也就是说如果对手操纵B在$M_A$中选一个数,我们就操纵B在$M_B$中选同一个这样的。

对手选择了$t$的时候我们没法模仿了,因为两个博弈在$t$这里是不同的。不过可以修补一下 :

  • 如果对手在$M_B$中操纵A选择$t$。我们也在$M_A$中操纵A选择$t$,尽管这两个元素不同。这样两个博弈在$t$上总是只差一个元素。

  • 如果对手在$M_A$中操纵B选择$t$(只考虑$t$上这个元素被选,而不一定是在$t$这一端选,也就是这个元素的另一端空了而选到它也算)。此时两个游戏的状态就相同了。那么算一算发现两个游戏的差距在于$M_A$中你选了$m$丢了$t$上最后一个元素。那么由于$m$最大,$M_A$是不劣的。

第二个case总会出现,否则$t$所在的序列永远不会选完。这就结束了。

引理2 如果$m$不能选,它的两边分别是$x,y$,那么如果一个人,不妨设为A,选了$x$,根据定理1,B必然选$m$,引理2断言接下来A必然选$y$。

证明 如法炮制。现在博弈$M_B$中A选择了$x$,我们操纵B选择了$m$。

和上面一样进行若干轮模仿。还是考虑何时不能模仿了。

  • 如果对手在$M_A$中操纵B选择$x$。那么我们操纵A选择$m$。由于$m$是最大的,$M_A$不劣。

  • 如果对手在$M_A$中操纵B选择$m$。这说明之前某个时刻有人在$M_A$中选择了$y$。那么我们考虑有人在$M_A$中选择$y$的时候应该怎么办。

    • 如果对手在$M_B$中操纵A选择了$y$(如果一直模仿,我们会模仿他在$M_A$中选择$y$)。如果$x$还没有被选,我们在$M_A$中操纵A选择$x$,那么对手必然跟着选$m$。不管$x$有没有被选,此时我们选择$y$。此时两个游戏完全一样了。

    • 如果对手在$M_A$中操纵B选择了$y$(此时$x$没被选,否则是case 1)。我们在$M_A$中选择$m$。归纳,那么对手必然在$M_A$中选择$x$。于是我们在$M_B$中选择$x$。此时两个游戏又完全一样了。

于是我们知道如果最大值是$m$且不能选,可以把它和两边的$x,y$合并成$x+y-m$。

那么现在我们已经可以解决没有锚定的情况了,也就是每次找到最大值做这样的。

引理3 如果$m$两侧是$x,y$,且$x,y$中某一个锚定,可以把它们合并成锚定的$x+y-m$。

证明 在引理2的证明中去掉case 2。

引理4 如果$m$是锚定的,它和$x$相邻,并且目前还剩$n$个数,可以把它们合并成锚定的$(-1)^n(x-m)$。

证明留作练习。

那么现在我们已经完全会做啦!开个堆就是$O(n\log n)$了。

考虑一些更强力的结论。

定理2 现在$m$不一定是$\max$。如果$m$没有锚定,左右是$x,y$,且$m>x,y$,那么可以把$x,m,y$合并成$x+y-m$,它锚定当且仅当$x,y$中有一个锚定。如果$m$锚定了,一侧是$x$,且$m>x$,那么可以把$x,m$合并成锚定的$(-1)^n(x-m)$。

证明 没太看懂。懒了。

所以我们只需要开个栈,每次拿出前三个看看能不能这么合并,然后就会把每个栈变成单调的,每个deque变成双调的。然后排序即可。


cf1461f

空跌给的。

感觉让人比较智障。

只有一种符号显然。$+,-$全填$+$。$\times,-$填$\times$直到第一个$0$,在这里填一个$-$,后面的全填$\times$。

$\times,+$。$0$两侧必然是$+$。考虑如果一些数的乘积$>nv$,这里$v$是$9$,那么我们必然是乘起来,不过如果两边有$1$我们会改成$+$。否则容易想到一个dp,求出前缀积然后李超树优化,但是这里斜率居然只有$\log(nv)$种,所以直接每个斜率维护最大的截距即可。复杂度$O(n\log(nv))$。


thupc2021 鬼街

据说很经典!

感觉比较厉害啊。根据第一篇题解,考虑如果是有一个$>y$就触发,那就直接每个素数开个堆维护$y$最小的监控器。但是是和$>y$才触发,我们每个素数开个堆维护$\lceil\frac{y}{\omega(x)}\rceil$最小的监控器,那么一个监控器每弹一次,二分一下求出它是不是真的触发了,如果没触发,$y$必然已经减小到原来的$\frac{\omega(x)-1}{\omega(x)}$以下了,此时我们直接remake一下它。复杂度$n\omega(n)\log_{\frac{\omega(n)}{\omega(n)-1}}n\log n$。这里$\omega(n)=6$。

icpc19~20 hong kong I. Incoming Asteroids

一样的trick捏。


xxii open cup gp of Yuquan G. Dynamic Reachability

时间分治。然后发现bitset的时候好像会影响很多点啊。

时间分块。每$K$个分一块,但是一个问题是怎么做到$qK$啊。发现我们好像不是很容易做到。考虑$\frac{qK^2}{w}$是简单的,我们只需要找到所有端点然后把它们之间的连通块拿出来跑一个bitset优化的bfs就好了。复杂度$O(\frac{n^\frac{4}{3}m}{w})$,这里认为$m,q$同阶。算量2e9,不多不少。


ccpc2021 Weihai L. shake hands

考虑这个图有啥性质。发现如果$i,j$有边,$(i,j)$中每个点到$i,j$之一都有边。并且如果其中$k$到$i$有边,$l$到$j$有边,$i<j,k>l$,那么$k,l$必然有边。之类的东西。

这个东西好像没见过。考虑它的补有啥性质。如果原图中$i<j<k$,$i,j$没有边,$j,k$没有边,那么$i,k$也没有边。也就是说这个补是一个可比图。

可比图的最大独立集也就是最长反链。考虑经典的网络流建图,每个点拆成入点和出点跑最大匹配,那么这里只有$O(m)$条边不存在。这就没法用经典网络流算法了。不过有牛逼做法,考虑如果这个图很满我们就必然有完美匹配了,看看它需要有多满,hall定理,如果有$n$个点,我们选了一个大小为$k$的集合,那么每个点要删至少$n-k+1$条邻边,那取$k=n$就爆炸啦。注意到此时对面必然有一个度数非常大的点。考虑我们把删的度数$>K$的点都特殊处理,现在所有点删的度数$\leq K$,那么我们选大小$>K$的集合,邻接的必然是另一部所有点。此时每个点还是至少要删$n-K+1$条邻边,也就是说$K<n-K+1$就赢啦。

那么我们就把两边一起按删的度数从大到小排序,设为$d$,找到第一个$i$满足$d_i<n-i-d_i+1$。显然当$n$足够大,比如$n>\Theta(\sqrt{m})$,这样的点在$O(\frac{m}{n})$处就出现了;否则我们爆力dinic就是$O(n^\frac{5}{2})$。取根号分治的阈值为$\Theta(m^\frac{4}{7})$,对$i$和前面的这些点进行爆力匈牙利,每个点是$O(m)$的,复杂度$O(m^\frac{10}{7})$。现在左右都剩下至少$n-i$个点,而每个点删的度数都满足$d<n-i-d+1$,于是必然存在完美匹配。

如果要构造方案,好像我们还不会快速找到这个完美匹配。

引理1 如果每个点的度数$\geq\frac{n}{2}$,且现在不是完美匹配,则必然存在一条长$\leq 3$的增广路。

证明 考虑现在左部点$u$和右部点$v$还没匹配。如果有边$u\leftrightarrow v$,那就赢了。

如果到处都没有这么一条边。那么$u$的所有邻接点都匹配了,$v$的所有邻接点都匹配了。由于每个点的度数足够大,必然存在一个$u$的邻接点$x$和一个$v$的邻接点$y$匹配。这就找到了长$3$的增广路。

上面那个条件$d<n-d+1$就等价于每个点删剩下的度数$\geq\frac{n}{2}$。考虑如何利用这东西。先处理所有长$1$的增广路,让每条边的至少一个端点在匹配中。然后枚举长$3$增广路的中间那条边,在两侧各找一个未匹配点。关键的观察是这样产生的新的匹配边不会再出现在长$3$的增广路中,因为在第一步中,它的端点的邻接点都已经是匹配点了。复杂度线性。


loj3657 集训队胡策2021 挑战分解质因数

考虑$pq$怎么做。也就是我们知道$pq$和$(p-1)(q-1)=pq-p-q+1$。那么我们就知道$p+q$。那么就可以用韦达定理构造一下了。

考虑无平方因数怎么做。感觉不好做啊。

感觉比较厉害。考虑一个类似于mr的想法,我们知道如果$a\perp n$,那么$a^{\varphi(n)}\bmod{n}=1$。设$\varphi(n)=2^km$,那么把$1$移过来并平方差,我们又有了$(a^m-1)\prod\limits_{i=0}^{k-1}(a^{2^im}+1)=0$。如果这些项中有一个$0$,那就不好,否则由于它们都不是$0$而乘积是$0$,我们都和$n$取一下gcd就找到了$n$的一个因数。

看一眼二次探测定理的证明,发现它确实说明成功的概率是$\frac{3}{4}$。


usaco23feb Pt A. Hungry Cow

看起来是单侧递归线段树例题。以前是管它叫类楼房重建的,从今天开始我要改叫单侧递归了。

看起来我们需要考虑一个点左边留下的非$0$的情况。考虑左儿子区间中有多少个$0$,如果左边来的比这些要多,那么左儿子就被填满了,只需要递归右儿子。否则左儿子留下的是固定的,每个点维护此时右儿子的情况即可。


icpc2020 Shenyang L. Forged in the Barrens

dag定长最短路。很遗憾这东西显然并不四边形不等式。

考虑极差有啥性质。想起最大化极差的一个经典做法是改成任意两个数的差,然后就可以费用流了,这里需要拆点保证包含每个点的区间只有一个。那么我们知道答案是凸的。然后可以写个dp,分治闵和,或者直接模拟费用流。这里只可能在有东西的一段或空的一段中间选或者在相邻的 有东西的一段和空的一段 之间选,线段树支持查询区间左边选一个贡献负,右边选一个贡献正,或者反过来的最大值,然后开个堆模拟即可。


cco2018 Boring Lectures

时间分治。插入一个数,找到附近的$\max$并尝试更新答案即可。一开始先用单调队列扫个答案出来,复杂度$O(n+q\log^2 n)$。

多头给了一个牛逼做法。考虑按$k$大小分块,那么我们断言答案中两个数在其所在块中必然是最大或次大。对于同一块的情况显然正确,对于不同块的情况,如果我们选择了$x,y$,两块的最大值分别是$a,b$,那么选择$a,x$或$b,y$必然不劣,否则我们知道$a<y,b<x,x<a,y<b$,这就成环啦。


slyzoj485 未知来源题

简化之后是,仙人掌,每条边都在至少一个简单环上,求所有点对间最小割的和。

那我们必然割环,割环的话必然割最小的那条边,所以把它先割掉,把它的边权加到同一环的所有边上,然后按树做。树是经典的。


区间平面最近点对

大家都会平面最近点对。考虑按$d$大小把平面分成若干$d\times d$的矩形,那么如果一个矩形中有两个点,就给出一个$\leq \sqrt{2}d$的方案。取$d$为各$\lfloor\sqrt{2}2^k\rfloor$,从大到小枚举一个$d$看是否存在一个矩形中有两个点,那么对每个矩形排序之后,只有每两个序列上位置相邻的点需要贡献,BiT数数就好啦。现在每个矩形中有最多一个点,可以看到的是每个矩形最多和周围$5\times 5$并挖掉四角的矩形产生贡献,并且由于每个矩形中有最多一个点,我们现在处理矩形$A$中的$a$和矩形$B$,只有$B$中出现位置离$a$最近的两个点有用,更远的如果和$a$贡献,就说明$B$中不止一个点。复杂度$O(n\log^2 n)$,但是常数太大,多叉树或者根号平衡会变快。


区间一维最近点对,随机数据

我并不会降低这玩意的复杂度。


usaco23 feb Pt C. Watching Cowflix

https://codeforces.com/blog/entry/113088?#comment-1008590

厉害的。

考虑从小到大枚举$k$,那么一个非常有道理的感觉是选的连通块之间只会合并。把选的连通块缩成一个点,这还是一棵树,树上任意两个选的点的距离$\geq k$,否则直接合并更优,所以考虑以每个选的点为中心画半径$\frac{k}{2}$的邻域,那么任意两个邻域不能有交,而如果直径长度$\geq \frac{k}{2}$,每个邻域覆盖至少$\frac{k}{2}$个点,否则只能有一个邻域,也就是说选的点只有不超过$\frac{2n}{k}$个。建立虚树然后dp即可。

但是因为我们在缩点,所以还有一些小问题,缩起来的点的dfn取其中随便一个点的即可,求lca的时候,就是求出lca再找到对应的连通块。看起来还是比较正常的!

然后这个东西其实是线性的。注意到当$k$减少了$1$,每个连通块的代价都减少$1$,所以如果连通块个数是$t$,$k$减少$1$之后答案至少减少$t$。而答案一共减少不超过$2n$,所以连通块总数不超过$2n$。


1st ucup Slovenia F. Differences

考虑我们容易算一个串和其它串共有多少个位置不同。

考虑我们给每个串一个随机权值,然后带权算这个东西,容易算出结果应该是多少。


pa2022 Palindrom

先把两边换到两种字符出现次数相同,然后把左边和倒过来的右边求个逆序对即可。


洛谷8456 swtr-8 地地铁铁

感觉比较带劲啊。考虑如果有个环,环上同时有D和d,那么环上任意两个点都行了啊,除了$O(1)$对点可能不太行。所以考虑一些连通性操作,因为是点简单路径,缩个v-dcc先,然后如果树上两个点之间有两个方点满足v-dcc中分别有D和d,那肯定就能满足要求了。全D或全d显然不行,问题是一个v-dcc中同时有D和d的情况。

看看v-dcc有啥性质。我们找到共端点的一个D和一个d,设$u,v,w$中$u,v$之间是D,$v,w$之间是d,那么猜测从任何一个点$s$进到v-dcc中,走过$u,v,w$然后从任何一个点$t$出去是几乎必然有方案的。因为这是v-dcc,$u$到$w$还有另一条路径,这就给出一个包含$u\leftrightarrow v,v\leftrightarrow w$的环。从$s,t$分别走到这个环上,如果本来在环上那就不走。如果$s,t$在同一个点上,那么因为这是v-dcc,必然还有另一条路径到这个环上。如果使用了这另一条路径,或者因为本来就在环上而没有另一条路径,此时$s,t$中还是有至少一个在$v$上,那就不是很有救啦。如果$s,t$都不在$v$上,那就赢啦。

然后还是这个环上至少有两个$v$。有问题当且仅当$s$就是其中一个而$t$就是其中另一个,此时可以爆力dfs求解,更简单的方法是如果dcc中有至少三个$v$则有解否则无解。注意到如果还是不行,我们总是可以选择d还是D,也就是说对外面的影响相当于是如果经过这个dcc和别的至少一个dcc就必然有解。那么减去这个情况和路径上方点全部是同一个颜色的情况即可,后者可以直接在圆方树上dfs得到。


cf1511G

也就是每次求一个值域区间减去区间左端点的xor和。不妨考虑减去任何一个$k$。枚举一个$t$,$t-1$位有值当且仅当$(i-k)\bmod{2^t}$的$t-1$位有值,也就是$(i-k)\bmod{2^t}\in[2^{t-1},2^t)$,或者$i\bmod{2^t}\in[(2^{t-1}+k)\bmod{2^t},k\bmod{2^t})$,这里的区间是用 从左端点每次$+1$直到右端点,经过的所有点 来定义的。

注意到这是值域区间,相当于我们在序列上每$2^t$个求后$2^{t-1}$个的和,然后加起来,这样的。差分,求出每个$t$,每个点开始的这样的答案,边界处可能会多加一段,特殊处理一下即可。复杂度$O(n\log n)$。


thupc2022 rsraogps

range subrange range and or gcd prod sum。

这些东西都一共只有$n\log n$段,所以直接枚举左端点,直线乘矩形求和就是$O(n\log^2 n)$。

砍砍你的。考虑如果只有and/or,我们可以对每一位分开,然后就可以前缀和啦。如果只有gcd,好像不太会了。

感觉比较厉害。从右往左扫$l$,注意到当一个$[l,r]$的权值改变的时候影响的前缀很多,但是影响的后缀有均摊(具体为啥可以往后看),所以我们把$[l,r]\times [l,r]$差分为$[l,n]\times [l,n]-[l,r]\times [r+1,n]+[r+1,n]\times [r+1,n]$,没有$[r+1,n]\times [l,r]$是因为它是$0$。$[l,n]\times [l,n]$这样的东西是好求的。从右往左扫$l$,对每个位置$r$维护$[l,r]\times [r+1,n]$,那么$l$移动一步,我们需要加入$l\times [r+1,n]$的权值和。如果$[l,r+1]$的权值和改变了,这样的事情只会发生$O(n\log n)$次,否则$l\times [r+1,n]$的权值都没改变,因此变化量和上一轮相同,也就是支持修改$b$,$a\leftarrow a+b$这样的,记录上一次推标记的时刻就$O(1)$啦。复杂度$O(n\log v+q)$。

去补了 洛谷8283 MCOI-08 Dantalion 的类似做法,可以看看我关于sdptt22 r1的文章。


未知来源题

有长$n$的序列$a$和$m$个初始为$0$的计数器,每次随机一个$a_i$和一个计数器,给它加上$a_i$,求所有计数器都达到$k$的期望时间,膜$998244353$。$n,m,k\leq 100$。

min-max容斥。我都忘了min-max容斥了!对于每个$j$计算子集$T$内走了$j$步还未结束的概率,求和然后乘上$\frac{m}{\vert T\vert}$(因为min-max容斥需要考虑子集外的影响),概率可以用方案数来算。为啥是和呢?考虑一个$t$步结束的方案,它会在$j=0,…,t-1$各贡献一次,一共$t$次。

\[\sum_{i=0}^m\binom{m}{i}(-1)^{i-1}\sum_{j=0}^{mk}\frac{j!m}{i^{j+1}}[t^j]{\left(e^{t\sum\limits_l z^{a_l}}\bmod{z^k}\right)_{z=1}}^i\]

这个exp,直接展开,发现每次卷上一个$\sum\limits_l z^{a_l}$即可,复杂度$O(n^3)$。外面直接做就是$O(n^4)$,法法可以做到$O(n^3\log n)$。


unr6 D1 C. 稳健型选手 $q=1$

正的序列,你每次取走一个数,然后第一个数会消失,最大化你取走的总和。

结论是,一个方案是我们选的数的集合,那么它合法当且仅当前$2k$个选了不超过$k$个。证明考虑如果选了超过$k$个显然不行,否则,选择第一个还没选的就可以维持这个性质。

进一步的,我们必然选一半,如果$n$是奇数那么最后一个数必然是我们选走,所以可以把它删掉变成$n$是偶数的情况。倒着考虑,就是后$2k$个选了至少$k$个,并且一共选了$k$个,那么我们从后往前每次加入两个数,然后选择还没选的数中的一个。用堆维护即可。

完整题解请见 一些比赛的题解。

也许是唐队长题

正的序列,你每次取走一个数,如果序列长度是奇数,并且你取的数在正中间,你的得分加上它,最大化得分。

结论是,一个方案是我们取的时候在正中间的数的集合,那么它合法当且仅当距离两边$\leq d$的数选了不超过$d$个。证明考虑如果取了超过$d$个显然是不行的,否则,这个等价于从大到小考虑到两边的距离(的$\min$),每次加入距离$=i$的数(必然是一个或两个),然后选择不超过一个还没有选择的数。那么如果选了一个这一轮加入的数,我们就把它和另一个加入的数配对,也就是这俩在相邻两轮选走。否则,把选的那个数和这俩中一个配对,原来和它配对的数和这俩中另一个配对,两个新配对交叉的方案必然保持中位数不变。如果$n$是奇数,先删掉中间那个数。对于最大化的问题,用堆维护即可。


k倍动态减法游戏

icpc 2008 asia beijing B. A simple stone game

取石子,第一次不能取完,接下来每一次不能超过上次的$k$倍,不能取就输了。

如果$k=1$,那么所有$2^i$先手必败。如果不是$2^i$,先手可以每次拿lowbit。

如果$k=2$,那么所有斐波那契数先手必败。拿zeckendorf表示的lowbit,因为zeckendorf表示中没有相邻的1,而相距2的fib数,后一个至少是前一个的两倍。

那么对于$k$任意的情况,我们构造一个数制,满足如果两个1可能相邻,那么后一个的位权至少是前一个的$k$倍。也就是说如果各位权是$a$,当然从小到大处理,我们找到目前最小的不能表示的数,那么它就作为下一位的位权,而最小的不能表示的数也就是最大的能表示的数$+1$,我们先选最后一个$a$,然后每次往前找到第一个不比上一个的$\frac{1}{k}$大的$a$即可。


loj6728 u群把妹王

集合划分容斥。来自djq的命名。

只介绍怎么做到$O(n^2)$。首先两维分别钦点一个集合划分,那么如果两维各有$i,j$个行,列的等价类,一共就有$ij$个格子的等价类,非常好对吧!然后乘个容斥系数以在钦点和恰好之间转化,就可以dp出这个钦点的方案数了。关键是容斥系数应该如何算,这里是集合所以设$F$是合法大小的egf,$G$是容斥系数的egf,那么$\exp G=1+F$对吧。

要做到$O(an\log n)$,使用拉格朗日反演直接推那个dp的结果。


vuq的矩阵乘法题

给$n$个长$m$的序列,每次问两个有没有交,$nm$和$q$同阶。

我好像会除$w$。


cf1626 F. A Random Code Problem

大家都会$O(2^knk^2)$。但是$n$好大啊!

考虑一个数贡献的变化只跟膜$\operatorname{lcm}(1,…,17)$的值有关。但是这也有1e7捏。

注意到是求和,所以直接拆贡献即可。这样就可以$O(2^kn)$了。

对一个数可以dp,设$dp(i,j)$表示前$i$轮,现在一共减了$j$的方案数和总贡献,它是一个一次多项式。转移考虑这一轮选不选,如果选要乘$1+(a-j)z$,否则要乘$n-1$表示选了一个别的的方案数。复杂度$O(nk^3)$。

能不能再给力一点啊?考虑膜$17$的余数没有用,所以$\operatorname{lcm}$可以除一个$17$。

考虑对所有数同时dp,设$dp(i,j)$表示现在膜$\operatorname{lcm}$是$i$,进行到$j$轮,的贡献,它是一个一次函数。复杂度$O(n+\operatorname{lcm}(1,…,k-1)k)$。


cf1827 C. Palindrome Partition

问题是证明选最短的是对的!

如果一个串有border,那么一定有长度不超过一半的border。转而考虑周期,如果有不超过一半的周期,让它不停翻倍就必然能得到超过一半的周期。

manacher之后单调栈即可。


hnoi2003 历史年份

最后一个数最小就是直接设$dp(i)$表示前缀$i$最后一个数最小是多少对吧。转移枚举这一段,那么$dp(j)$要比$j+1,…,i$小,这里$dp(j)$只需要记长度,可以用sa判断做到$O(n^2)$。

那么可以注意到$j+1,…,i$总是随$i$增加而单增的,也就是说每个位置一旦可以转移就一直可以转移了。那么对每个$j$向后二分出第一个可以转移到它的$i$即可。

然后问题是怎么让第一个尽可能大,再dp,固定住最小的最后一个数,设$dp(i)$表示后缀$i$,第一个数最大是多少,看起来和前面一样做。

注意到比较大小的时候,两个数去掉前导$0$之后如果长度不同那就直接比出来了,所以我们其实不需要二分,只需要往后找到第一个非$0$的数,然后检查两种情况。可以直接用二分hash来比较,复杂度$O(n\log n)$。


cf1458 F. Range Diameter Sum

看起来是根号题啊。但是啥都没什么想法/cf

注意到直径可以合并,考虑对序列嗯分治,但是直接考虑直径比较麻烦,我们考虑外接邻域,两边分别是$\mathrm{N}(c_1,r_1),\mathrm{N}(c_2,r_2)$,$d=\mathrm{dis}(c_1,c_2)$,那么如果$d+r_2<r_1$或$d+r_1<r_2$则并的外接邻域是$\mathrm{N}(c_1,r_1),\mathrm{N}(c_2,r_2)$,否则直径必然是$r_1+r_2+d$,证明只需要考虑外接邻域的定义是,一个点集的外接邻域是$\mathrm{N}(c,r)$当且仅当有两个来自$c$不同子树的点到$c$的距离是$r$,且没有点超过$r$。更进一步的结论是,并的外接邻域中心是$c_1$到$c_2$路径上距离$c_1$为$\frac{1}{2}(d+r_2-r_1)$的点。

然后问题是有若干个邻域,静态查一个邻域包含的所有邻域的权值和这样的,点分治双指针即可。总复杂度$O(n\log^2 n)$。

但是有更简单的做法,注意到前缀邻域显然是每一个都包含上一个,那么固定左边的邻域,贡献就分成左边包含右边,互不包含,右边包含左边三段,都是单调的可以双指针。问题是要求一个点到一个点集的距离和,支持修改点集,点分即可。但是复杂度还是$O(n\log^2 n)$。