[长期更新]准备写掉的题

[BZOJ4869]
奇数取phi变成偶数,偶数取phi至少除以2,因此一个数取log次phi就会变成1,配合扩展欧拉定理:,修改时暴力修改,用线段树维护一个区间的和,以及是否变成固定值.

[BZOJ1492]
显然有DP方程

设式子中的分数为yj,rj*yj=xj,得到方程

,化成y关于x的一次函数得

相当于求斜率固定为且过某一点的直线的最大截距,显然决策点在凸包上,用CDQ分治或平衡树维护.

[BZOJ2653]
二分答案,设当前答案为mid,将区间内所有>=mid的数标为1,< mid的数标为-1,则只要找出一个区间和严格大于0的符合条件的区间即说明答案>=mid,其实就是找最大连续子段和.这需要对每个值mid都建立一棵线段树,用可持久化线段树搞一下.
套路:不光可以对区间维护可持久化权值线段树,还可以对权值维护可持久化区间线段树.

[BZOJ3489]A simple rmq problem
先求出pre[i]和nxt[i],那么一个询问就可以看作求三维空间中一个长方体内的最值.
于是立刻有两种做法:
一是裸上kdt,加入所有点后每个询问暴力查询,复杂度.
二是主席树套主席树,具体做法是对pre排序,对每个pre种一棵维护原来区间的可持久化线段树,树上每个节点再种一棵维护nxt的线段树,按照pre顺序插入时就像普通主席树那样插入就行了,复杂度两个log.

[BZOJ4872]
方法和网上不太一样,但差不多...
首先容易发现最大编号的灯肯定要按,然后策略就唯一了,设dp[i]表示从需要i次按动的状态期望按几下灭掉全部的灯,那么有dp[i]=i,当i<=k;dp[i]=i/n*dp[i-1]+(n-i)/n*dp[i+1]+1,当k<i<=n;特别的,dp[i]=dp[i-1]+1,当i=n.如果k不等于0就可以推了,否则可以设dp[1]=x,推出dp[n-1]和dp[n]的表达式,然后把x解出来再代回去即可.

[BZOJ3594]
容易发现每次拔高的区间肯定以n为右端点,然后就能二维树状数组优化DP了.

[BZOJ3624]
求的就是权值恰好为k的生成树,那么先求最小生成树,标记上哪些1边是必选的,然后把这些边扔进去,剩下的优先加1边直到权值为k.

[BZOJ4826]
考虑枚举合法序列中间的那个最大值,先预处理出每个位置左边和右边第一个比他大的是谁,记作pre[i]和nxt[i].
计算第一种贡献,显然只有区间[pre[i],nxt[i]]是合法的;
第二种贡献,则是区间[pre[i],x]和[y,nxt[i]],其中x∈[i+1,nxt[i]-1],y∈[pre[i]+1,i-1].
依然将每个点对看作二维平面上的点,则每个询问就是矩形求和,1类点对是单点加,2类点对是线段加.
用主席树标记永久化即可在线实现,离线的话可以用树状数组区间修改的技巧.

[BZOJ2141]
只有交换的两个数中间的逆序对会产生变化,用树状数组套权值线段树实现支持修改和二维数点就可以维护答案.

[BZOJ4923]
针对不同范围的不同性质大力分类讨论,也许是一个不错的套路.
[1,k]的数,无需修改;
[k+1,2k]的数至少会变小一半,所以暴力修改;
[2k+1,∞]的数,总排名不会有变化,因此在平衡树上打标记维护.

[BZOJ4520]
首先将无序第k大转化成有序第2k大会好做一些.
建出kdt,然后维护一个大根堆,保持堆内元素不超过2k个,然后在kdt上跑Astar.

[BZOJ2006]
发现k没有那么大,因此可以从最大的一直找到第k大的.维护一个大根堆记录以每个位置i为右端点的合法区间和的最大值,每次弹出最大值并且将这个元素的右端点的次大值扔进去,如此往复.
具体做法可以将区间和看成前缀相减,那么就变成了区间k大值问题.用主席树实现.

[BZOJ2001]
看样子是个挺厉害的CDQ分治
每层分治的时候,把当前节点内的待修改边权值设为-INF跑MST,树上的非-INF边是必须选的,直接合并两个端点;再把待修改边权值设为INF跑MST,不在树上的非INF边是无论如何不能选的,直接删掉.
然后复杂度就是两个log的了,然而并不会证明.也不想写

[BZOJ1124]
最多:多种情况,自环要死,一个环剩下一个人,基环树剩下叶子结点个数.
最少:叶子肯定还是不会死的,所以他们要打的人肯定活不了,于是让他们先开枪,看被打死的人指向的人是不是能活下来了.这类似于拓扑排序的过程,最后会剩下一个环,环的最大存活人数显然是n/2.

[BZOJ4765]
对dfs序和点编号分别分块,可以做到.

[BZOJ3679]
搜索一下发现1e9以内质因子只有2,3,5,7的数只有5194个,那么就能进行数位DP了.设dp[i][j][k]表示i位数最高位为j,各位数字之积为第k个可行状态的方案数即可.

[BZOJ2732]
设抛物线为,则每一条线段等价于两个二元不等式,二分答案后用半平面交求这些不等式是否有交(flag:学半平面交)

[BZOJ2555]
查询出现次数就是扔进SAM里跑一遍,看最后到达的节点endpos集合大小嘛.但是本题要求在线支持插入操作,那么就照常插入,只需要用lct维护parent树即可.

[BZOJ3926]
叶子结点只有20个,因此可以枚举叶子结点,进而将任一条路径变成深度递增的.(人生经验)
所以问题变成了给你20棵树,求树上深度递增的路径构成的串集合的大小,构建广义后缀自动机解决.构建方法和树上主席树很像的.

[BZOJ2780]
多文本串匹配,要用到广义后缀自动机,将后缀自动机建好以后要把所有的文本串再扔进去跑一遍,队每个状态求出sum[st]表示有多少文本串包含了st这个状态,还要用vis数组记录该状态是否已被更新过了(用时间戳),最后将匹配串扔进去即可.据说复杂度是对的?

[BZOJ2806]
显然是答案是可二分的,枚举答案为L以后就是一个DP,用广义后缀自动机求出当前match[i]表示当前串以第i个字符结尾的最大匹配长度,那么显然有方程
dp[i]=max{dp[i-1],max{dp[j]+i-j,j∈[i-match[i],i-L]}}
注意到区间两个端点都是单调的,用单调队列优化DP即可.

[BZOJ4199]
注意到答案肯定是单调不降的,因此只需要先只统计lcp恰好为r的,最后再来一波后缀最大值.
那么lcp恰好为r的怎么求泥?反串建后缀自动机,pre树就是正串的后缀树(这个性质很常用的样子),然后维护子树最大值和次大值就可以了.
其实还得维护最小和次小,因为有负数...

[BZOJ4566]
一个串建立后缀自动机,另一个进去跑,最后len*|endpos(st)|之和就是答案,注意出现次数向父亲传递.

[BZOJ3033]
我们将2^k-1以内所有数都看成点,将一个数左移或右移一位再随便补上一个0或1(如10110->01100)看作一条边,然后我们发现每个点恰好入度等于出度.这意味着此图是一张欧拉图,进而意味着存在欧拉回路,进而意味着M=2^k.
至于字典序最小什么的,dfs就好了.

[BZOJ2217]
由于一加入或删除一个数对区间和的影响只能是1或2,我们如果找到一个和为x或x+1的区间就可以很方便地构造答案了.显然,如果答案存在,则必然有一个前缀的和为x或x+1.如果是x就直接做完了,如果是x+1就不断往右平移,直到找到一个1为止.

[BZOJ2329/2209]
考虑一段括号序列答案是啥,显然是先把()这种能配对的全干掉,最后会剩一坨))))((这种东西,答案就是区间长度除以二加上两边比较少的那个,这个显然是满足区间加法的,拿splay维护一下就好了.
顺便还要解决反转操作,所以还得维护一个把左括号和右括号互换的信息.

[BZOJ2164]
就是在子树里跑个背包,再在链上维护50个最大值,然后合并一下.第一个用线段树维护dfs序加背包合并,第二个用链剖.复杂度贼吓人...

[BZOJ4025]
就差没直接把"线段树对时间分治"写到题面上了.
把边挂到线段树对应的节点上,最后DFS整棵树用带权并查集判断是否出现奇环即可.并查集需要一个逆序撤销操作,要用到按秩合并.

[BZOJ1453]
看成图,就是个动态图判断连通性问题,由于可以离线,只需要维护删除时间最大生成树即可.

[BZOJ3095]
数学题,把柿子展开一下合并同类项,发现是个二元函数求最小值,那么先让k固定就是个关于b的二次函数,把极值点带进去又变成了关于k的二次函数,然后直接求就可以啦.

[CF875F]
建图,在公主喜欢的两个王子之间连边,边权是公主的嫁妆,那么要求的东西其实就是给每条边定向,然后抛弃一些边,使得每个王子的入度至多为1,这显然是个最大基环树,用并查集维护一下即可.

[BZOJ5085]
后面那个暴力我反倒没有想出来...
显然是二分答案,然后就判断是否存在子矩形四个角都是1,根据花式枚举的套路这等价于判断是否存在一条线段出现两次,由于线段只有m^2条所以暴力即可.

[BZOJ2402]
二分答案为ans,然后化一下发现要最大化两个形如的柿子,变形一下就变成凸包形式了,用树剖加线段树维护凸包再在凸包上二分.复杂度四个log...

[BZOJ4173]
数论套路大合集,感觉自己已经把欧拉函数那一套理论忘得差不多了...
一看前面的是搞笑用的不管他
然后那个集合推两下会变成这个东西

但是怎么可能比1还大呢,所以就是等于1的.
换句话说现在要求所有k的phi的和,然后k要满足让一个非0即1的等式等于1,那我直接把等式乘进去不就得了.然后就拆成了三个长得一样的柿子,都是这种形式:

经典套路了,这个相当于把累加到所有k的倍数上求和,我们转而枚举每个数被累加了几次


所以求前面那两个搞笑用的phi就是剩下的全部任务了...

[BZOJ4241]
这题之前拿分块做过,有点卡常.今天yy了一下所谓的回滚莫队算法.
其实还是莫队,只不过每次先移动右端点,左端点不再左右摆动,而是每次都从所在块的右端点挪过去,最后再把影响还原即可.
多说两句,强制在线莫队也能做了,块大小设成,预处理任意两块之间的答案,然后询问的时候从两个端点所在块的端点往旁边走就可以了.
那加了修改岂不是一个道理,块大小还是,该怎么查询怎么查询,修改就暴力改变过这个位置的区间的答案(只有个).
这样强制在线带修改莫队就能实现了,不过不能把回滚功能也加上.
好像又能水过很多题(逃

[nowcoder79F]
今天打的一场比赛里的题,比赛时实在写不动.
给你一颗边权树,每个节点有颜色,问任意x色点和y色点的距离和是多少.
这种东西很容易想到根号分治加暴力.设两种颜色出现更多的一种出现了size次,那么:
1.size大于等于根号,这样的颜色最多根号种,暴力树形DP求出它们跟所有颜色的答案;
2.size小于等于根号,两个不超过根号的东西加起来还是根号级别的,暴力建虚树跑dp即可.注意建虚树的log在于排序,我们一开始就把每种颜色排好,用的时候归并一下就是线性了.

[BZOJ3813]
先维护一下区间乘积,然后看看哪些质数出现过即可.
由于只有60个质数,干脆对每个质数开一棵线段树.

[BZOJ3585]
以前以为这种区间数出现几次的问题难以用主席树解决,后来发现主席树就是专门拿来解决这个的.
答案显然是0~n之间的,因此在序列左边接一个0~n的序列,然后对每个数的nxt建一棵维护区间最小值的主席树,查询就相当于查询自己在区间左边,nxt在区间右边的数的最小值.用主席树维护即可.

发表评论

电子邮件地址不会被公开。 必填项已用*标注