退役前的做题记录2.0
最近在刷省选题......大致上是按照省份刷的。
不过上面的题目顺序是按照写题的顺序排列的，所以可能会有点乱哈。
[BZOJ2823][AHOI2012]信号塔
最小圆覆盖，随机增量法，期望复杂度(O(n))。
[Luogu4899][IOI2018] werewolf 狼人
(mbox{Kruskal})重构树+二维数点。
[Luogu4900]食堂
求(sum_{i=1}^nsum_{j=1}^ifrac ij-sum_{i=1}^nsum_{j=1}^ilfloorfrac ij
floor)。
前半部分随便弄弄就好了。
后半部分，(sum_{j=1}^ilfloorfrac ij
floor)实质上等于(sum_{j=1}^id(j))。
所以前缀和一下就好了。
[Luogu4902]乘积
求(frac{prod_{i=1}^ni^{sum_{j=1}^ilfloorfrac ij
floor}}{prod_{i=1}^nprod_{j=1}^ij^{lfloorfrac ij
floor}})。
上半部分就是(sum_{i=1}^ni^{sum_{j=1}^id(j)})。
下半部分，(prod_{j=1}^ij^{lfloorfrac ij
floor})实质上是(i)的各约数的乘积，也就是(i^{frac{d(i)}2})。
所以前缀积一下就好了。
[BZOJ2178]圆的面积并
辛普森积分，虽然是假的。
[BZOJ4913][SDOI2017]遗忘的集合
多项式求(ln+mbox{MTT})。谁说莫比乌斯反演的来着？
[BZOJ4911][SDOI2017]切树游戏
[LuoguT46780]ZJL的妹子序列
很显然是要求(prod_{i=1}^nfrac{1-x^i}{1-x})的(x^m)次项系数。
一种做法是求(ln)之后大力开式子，然后可以(O(nln n))调和级数求得一多项式然后再(exp)回去。
还有一种做法是拆成前后两部分，((frac1{1-x})^n=(sum_{i=0}^{infty}x^i)^n)，相当于(n)个盒子每个盒子可以无限放球的生成函数，所以(x^m)次项系数是(inom{n+m-1}{m})。(prod_{i=1}^n(1-x^i))可以看做一个带符号的(01)背包计数，其中第(i)个物品的重量恰好为(i)。考虑到至多选(O(sqrt m))个物品，所以可以做(O(nsqrt m))的(dp)。
[Luogu4921]情侣？给我烧了！
设(f_{i,j})表示前(i)对情侣已经入座，有(j)对情侣是挨着的的方案数。考虑插入第(i+1)对情侣。
(f_{i,j})可以转移到(f_{i+1,j-2},f_{i+1,j-1},f_{i+1,j},f_{i+1,j+1})，分别表示第(i+1)对情侣分别拆散了两对情侣、只拆散了一对情侣、没有拆散情侣以及他俩坐在一起。注意两人分开座时可能会导致某对情侣复合，转移的时候要额外算一下贡献。
[BZOJ3307]雨天的尾巴
线段树合并模板题。树上差分的时候，对(lca)与(fa_{lca})打标记而不是做线段树单点插入，即可把空间减小到一半。
[BZOJ1227][SDOI2009]虔诚的墓主人
坐标离散，横坐标从左往右扫，维护每个纵坐标已存在的点数，组合数算一下，再用树状数组区间求和即可。
[BZOJ4870][SHOI2017]组合数问题
矩阵快速幂模板题。
[BZOJ3434][WC2014]时空穿梭
枚举(n)维中每一维坐标的极差(Delta x_i)，有
枚举(gcd(Delta x_1,Delta x_2...Delta x_n))，有
反个演
换个写法
令(T=dt)，改变枚举顺序
令(F(T)=prod_{i=1}^nsum_{Delta x_i=1}^{m_i/T}(m_i-Delta x_iT))，(G(T)=sum_{d|T}inom{d-1}{c-2}mu(frac Td))。
首先(G(T))在给定(c)的前提下可以(O(nln n))预处理出来。
观察(F(T))，将其划开
如果(lfloorfrac{m_i}T
floor)确定的话，那么(F(T))就是一个关于(T)的(n+1)次多项式。所以可以预处理(G(T)T^i)的前缀和，然后对于每个(lfloorfrac{m_i}T
floor)相同的连续段暴力求(F(T))。
总体复杂度(O(nln nc+nmc+Tn^3sqrt m))有点爆炸啊。
[BZOJ3629][JLOI2014]聪明的燕姿
直接爆搜质因子，特判最后一个大于根号的质因子即可。
[BZOJ5157][TJOI2014]上升子序列
对于前面的相同元素，直接强制从最后一个这种元素转移即可。
[BZOJ3628][JLOI2014]天天酷跑
先枚举跳跃高度和连跳次数，然后直接记搜转移即可。
[BZOJ3505][CQOI2014]数三角形
正难则反，求三点共线的方案数。枚举相隔较远的两点的横纵坐标之差，然后第三个点就有(gcd-1)种选法。注意特殊处理横纵坐标差为(0)。
[BZOJ4001][TJOI2015]概率论
设(f_n)表示(n)点二叉树的数量，(g_n)表示(f_n)棵二叉树的总叶子节点个数。
最近做初赛题发现(f_n)就是卡特兰数。
(g_n)是啥？考虑(f_n)中的一棵(n)点二叉树，设其有(m)个叶子，那么删掉这(m)个叶子后就能得到(m)棵不同的(n-1)点二叉树；而每棵(n-1)点二叉树有(n)个位置可以挂叶子，也就是说在上述过程中被计算了(n)次。所以(g_n=nf_{n-1})。
(ans=frac{g_n}{f_n}=frac{nf_{n-1}}{f_n}=frac{n(n+1)}{4n-2})。
[BZOJ3999][TJOI2015]旅游
树剖+线段树两只(log)，用(mbox{LCT})写可以做到一个(log)。
每个点维护区间最大值，最小值，后面最大值减前面最小值的最大值，前面最大值减后面最小值的最大值。
[BZOJ4000][TJOI2015]棋盘
其实棋子是放在中间那一行的。
所以直接按行(dp)就行了。处理一下相邻两行的两个状态是否可以转移，因为转移都是一样的所以可以矩乘优化，复杂度(O(2^{3m}log n))
[BZOJ5156][TJOI2014]拼图
据说这玩意儿叫精确覆盖？直接状压完事了。
[BZOJ5158][TJOI2014]Alice and Bob
因为保证(a)可以由一个排列得到，所以(x)就一定会是排列，否则不更优。贪心，尽量把数值大的放在前面，把数值小的放在后面。对于(a_i)值相差为(1)的点对建立拓扑关系，然后依次填数，最后统计一遍答案就行了。
[BZOJ5155][TJOI2014]电源插排
正解是动态开点线段树，但是感觉比较难写，就换了一种写法。
开个(mbox{std::set})维护未放置的区间，平衡树维护已放置的位置集合，支持插入删除，找前驱后继，统计区间点数即可。（如果迭代器支持相减的话就可以直接开两个(mbox{std::set})做了）
[BZOJ3173][TJOI2013]最长上升子序列
其实只要能够得到最终生成的序列就很好办了。考虑从大到小确定每个数在最终序列里的位置，相当于查找当前的第(k)大元素。(BIT)可做。
[BZOJ3174][TJOI2013]拯救小矮人
对于所有要出去的小矮人，一定是按照(a+b)权值从小到大出去最优。
排序，然后设(f_i)表示出去了(i)个小矮人时人梯的最高高度。如果(f_j+b_ige h)就可以用(f_j-a_i)更新(f_{j+1})。
[BZOJ3175][TJOI2013]攻击装置
黑白染色然后跑最小割。
[BZOJ3167][HEOI2013]Sao
一条链是考过的原题。
如果是树的话同样可以设(f_{u,i})表示(u)点子树内，(u)点排在第(i)个的方案数，每次转移就是合并两个序列，枚举(f_{u,i})以及在(u)的前面放(j)个元素，根据大小限制决定是从(f_{v,1...j})转移过来还是从(f_{v,j+1...sz_v})转移过来，同样可以用前缀和优化转移，同时要乘上前后隔板插入的方案数(inom{i+j-1}{j} imesinom{sz_u-i+sz_v-j}{sz_v-j})，复杂度(O(n^2))。
[BZOJ4824][CQOI2017]老C的键盘
上一题弱化版。双倍经验。
[BZOJ5019][SNOI2017]遗失的答案
[BZOJ3163][HEOI2013]Eden的新背包问题
预处理多重背包的前后缀(dp)，每组询问(O(m))回答。
[BZOJ3164][HEOI2013]Eden的博弈问题
(f_u)表示(u)点子树内最少要选多少个叶子才能必胜，如果(u)点是自己控制的那么(f_u=min{f_v})，否则(f_u=sum f_v)。找出所有可能是最优转移点的叶子即可。
[BZOJ2742][HEOI2012]Akai的数学作业
找到最高和最低的非零系数(a_m,a_n)，因为答案是有理数所以一定是(frac pq)的形式，更具体的(p)一定是(a_m)的约数(q)一定是(a_n)的约数。所以暴力枚举一下然后(mbox{check})。(mbox{check})的话，(x)是浮点数不好做，可以选几个大质数做模意义下的运算判断结果是不是(0)即可。
[BZOJ3610][HEOI2014]林中路径
维护三个矩阵(A,B,C)分别表示走不超过(x)步任意两点之间的路径条数、路径长度和、路径长度平方和，还要维护一下走恰好(x)步两点间的路径条数。倍增转移大力讨论一波即可。
[UOJ405][IOI2018]组合动作
先问两次确定首位，剩下三种字符，假设为(012)，设当前已知串为(S)，那么询问(S0S10S11S12)即可一次得知下一位是什么。末位还需要问两次，共计(n+2)次。
[BZOJ3516]国王奇遇记加强版
再加强版以后再写吧。
首先把(m=1)的情况特判掉。
(O(n^2))递推即可。
[BZOJ4567][SCOI2016]背单词
题意理解题。相当于是给你一棵树要你给节点标号，要求儿子标号不得大于父亲，同时要最小化(每个点标号-其父亲标号)。直接按照子树大小访问儿子即可。
[BZOJ1024][SCOI2009]生日快乐
直接搜索就过了。
[BZOJ1071][SCOI2007]组队
先枚举(minh)再枚举(minv)，第二层的枚举显然是单调的，但是因为每个人都有(minh)和(minv)的限制，所以考虑用两种不同的顺序加入和删除，保证在删除一个位置的时候它已经被加入过了。
[BZOJ1077][SCOI2008]天平
(Floyed)求出任意两数之差的取值范围，然后(O(n^2))枚举点对算就行了。
[BZOJ1078][SCOI2008]斜堆
最后插入的点一定是斜堆左侧链中没有右儿子的最浅点，如果这个最浅点只有一个叶子左儿子的话就还可能是这个叶子左儿子。(O(n^2))模拟即可。
[BZOJ1295][SCOI2009]最长距离
枚举起点，求出到达每个点最少需要经过的障碍数量，取不超过(T)的即可。
[BZOJ1293][SCOI2009]生日礼物
相当于(K)个单调队列，每次弹出(K)个中的最小值，答案就是每个队首放在一起的极差。
[BZOJ1296][SCOI2009]粉刷匠
对每块单独考虑。因为每个位置只能涂一次颜色，所以可以设(f_{i,j})表示前(i)个位置涂了(j)次的最大收益，从(f_{k,j-1})转移过来。然后再对所有块放在一起做个背包就好了。
[BZOJ1297][SCOI2009]迷路
每个点新建(8)个入点用来表示不同的距离，然后直接矩乘。
[BZOJ1294][SCOI2009]围豆豆Bean
一条路径围住了一粒豆豆当且仅当从这颗豆豆出发向外引一条射线，与路径相交奇数次。枚举起点，设(f_{x,y,s})表示目前在((x,y))这个点，已经围住了(s)集合的豆豆的最小路径长度，即(s)这个集合内的豆豆引出的射线与路径相交了奇数次。可以假设每条射线都是向右上以一个极小的斜率发射出的，这样就可以方便地处理出每走一步(s)的变化。更新一圈回到原点后计算答案即可。
[BZOJ1855][SCOI2010]股票交易
设(f_{i,j})表示第(i)天手持(j)股的最大收益，(g_{i,j})表示对(i)作前缀和。显然(f_{i})从(g_{max(0,i-w-1)})转移过来，转移的过程分买入和卖出两种讨论，显然可以用单调队列优化。
[BZOJ1857][SCOI2010]传送带
三分套三分。(mbox{yyb})说卡精但是我一遍过了呀？
[BZOJ1853][SCOI2010]幸运数字
搜出所有合法数字，去掉是别的数的倍数的数字（因为容斥的时候直接抵消了），然后大力容斥。还可以降序排这些数使(lcm)尽快增长到很大从而剪枝。（这什么鬼题）
[BZOJ1856][SCOI2010]字符串
(inom{n+m}{m}-inom{n+m}{m-1})
[BZOJ1858][SCOI2010]序列操作
线段树。附核心代码
struct node{
int len,s0,s1,l0,r0,l1,r1,v0,v1,t0,t1,tt;
void init(){len=s0=s1=l0=r0=l1=r1=v0=v1=t0=t1=tt=0;}
void set0(){s0=l0=r0=v0=len;t0=1;s1=l1=r1=v1=t1=tt=0;}
void set1(){s1=l1=r1=v1=len;t1=1;s0=l0=r0=v0=t0=tt=0;}
void rev(){swap(s0,s1);swap(l0,l1);swap(r0,r1);swap(v0,v1);swap(t0,t1);tt^=1;}
}t[400005];
node operator + (node a,node b){
node c;c.t0=c.t1=c.tt=0;
c.len=a.len+b.len;c.s0=a.s0+b.s0;c.s1=a.s1+b.s1;
c.l0=a.s0==a.len?a.len+b.l0:a.l0;c.r0=b.s0==b.len?b.len+a.r0:b.r0;
c.l1=a.s1==a.len?a.len+b.l1:a.l1;c.r1=b.s1==b.len?b.len+a.r1:b.r1;
c.v0=max(max(a.v0,b.v0),a.r0+b.l0);c.v1=max(max(a.v1,b.v1),a.r1+b.l1);
return c;
}
[BZOJ1854][SCOI2010]游戏
每个点匹配一条边，如果是一棵树的话就是标号最大的那个点没有匹配。
[BZOJ2330][SCOI2011]糖果
(mbox{spfa})的做法是假的。考虑先把所有带等号的关系连上边((ge,le,=))，然后(mbox{Tarjan})缩点求出需要相等的点集，再连上(>,<)的边跑拓扑(dp)即可。
[BZOJ2331][SCOI2011]地板
插头(dp)。用(0/1/2)状态表示没有插头/有一个未拐弯的插头/有一个已拐弯的插头。转移看上去要分(3 imes3=9)种情况，但实际上(12,21,22)都是不合法的，所以就只剩六种了。
[BZOJ2757][SCOI2012]Blinker的仰慕者
数位(dp)。把(K eq0)与(K=0)的分开做，(K eq0)那(K)一定只含(2,3,5,7)这四种因子，在(10^{18})内只有几万个，所以先预处理一下(f_{i,j},g_{i,j})表示(i)位数各位数字乘积是(j)的方案数以及这些数之和，每组询问的复杂度大概就是(O(18 imes9))的。(K=0)反过来求乘积不为(0)的随便搞搞就好了。
[BZOJ2753][SCOI2012]滑雪与时间胶囊
第一问(bfs)。第二问最小树形图。不过这是一个分层图（按高度分层），所以直接把边按照较低点高度为第一关键字，边权为第二关键字排序然后(mbox{Kruskal})即可。
[BZOJ2754][SCOI2012]喵星球上的点名
貌似有很多种奇奇怪怪的复杂度正确或是不正确的做法。
这里写的是(mbox{SA+BIT})，就是拿所有串放在一起求一个(SA)，然后每个询问串就是后缀数组上的一个区间，相当于是求区间内有多少种颜色以及每种颜色被多少个区间覆盖。都可以用树状数组维护，前一个是经典问题，后一个就对每个位置考虑有多少个区间覆盖了自己而没有覆盖自己的前驱即可。
[BZOJ4974][Lydsy1708月赛]字符串大师
先手写一遍(mbox{kmp})，然后只要把(mbox{kmp})倒着做一遍就好了。
[BZOJ3325][SCOI2013]密码
先手写一遍(mbox{manacher})，然后只要把(mbox{manacher})倒着做一遍就好了。
[BZOJ3326][SCOI2013]数数
一个(n)位数的第(i)位的贡献是(i imessum_{j=i}^nB^{j-i})，于是就可以把贡献拆开分别计算。大力讨论，写起来很复杂。
[BZOJ3322][SCOI2013]摩托车交易
建最大生成树，题目中给的那(q)个点就预先用(inf)边连起来。然后求出树上路径最小值后模拟最大流直接贪心即可。注意中途运算过程可能会爆(mbox{int})。
[BZOJ3323][SCOI2013]多项式的运算
平衡树随便搞搞。
[BZOJ4448][SCOI2015]情报传递
离线，每次询问相当于是求路径上加入时间在(T-c-1)及以前的点的个数。链剖+(BIT)。
[BZOJ4446][SCOI2015]小凸玩密室
设(f_{i,j})表示从(i)点出发，遍历完(i)的子树后走到(i)深度为(j)的祖先的最小代价。
(g_{i,j})表示从(i)点出发，遍历完(i)的子树后走到(i)深度为(j)的祖先的兄弟的最小代价。
转移比较简单，判一下(i)没有儿子或是只有左儿子，否则就是先走左儿子和先走右儿子取(min)。
之后枚举起点，暴力向上跳计算答案，复杂度(O(nlog n))。
[BZOJ3009][SDOI2012]集合
据说数据很水......写了一个(O(qsqrt mlog n))的做法，就是把所有边重定向后保证每个点度数不超过(O(sqrt m))，然后修改直接暴枚出边，对每个点维护(3)个(mbox{multiset})，即三种颜色的点指向当前点的所有边，再在全局维护(9)个(mbox{multiset})，讨论一下即可。
以下是正解。考虑一棵树的做法，直接套用上面那个方法可以做到(O(qlog n))，因为每个点都只有一条出边。而原题的性质实质上是说原图可以被划分成为不超过三个森林，所以把上述算法做三次就行了。
[51nod1355]斐波那契的最小公倍数
首先斐波那契数列有一个性质(gcd(f_n,f_m)=f_{gcd(n,m)})，证明这里就不证了。
考虑最值反演(max_s=sum_{tsubseteq s,t
eqvarnothing}(-1)^{|t|+1}min_t)，把它放到每个质因子的指数上去，于是答案就是(prod_{tsubseteq s,t
eqvarnothing}f_{gcd_t}^{(-1)^{|t|+1}})。
枚举(gcd)，式子变为(prod_{d=1}^nf_d^{sum_{tsubseteq s,t
eqvarnothing}(-1)^{|t|+1}[gcd_t=d]})。
(prod_{d=1}^nf_d^{sum_{d|i}mu(frac id)sum_{tsubseteq s,t
eqvarnothing}(-1)^{|t|+1}[i|gcd_t]})
(prod_{i=1}^n(prod_{d|i}f_d^{mu(frac id)})^{sum_{tsubseteq s,t
eqvarnothing}(-1)^{|t|+1}[i|gcd_t]})
(sum_{tsubseteq s,t
eqvarnothing}(-1)^{|t|+1}[i|gcd_t])当且仅当存在一个数是(i)的倍数时为(1)，否则为(0)。
而(prod_{d|i}f_d^{mu(frac id)})，如果你令(f_d=prod_{i|d}g_i)，那么(g_d=prod_{i|d}f_i^{mu(frac di)})。
所以求出(g_d)之后就直接做吧。
[BZOJ4833][Lydsy1704月赛]最小公倍佩尔数
和上一题一样的，递推式(f_i=2f_{i-1}+f_{i-2})，同样满足斐波那契数列的性质。
[BZOJ5286][HNOI2018]转盘
考场上写了(40pts)单调队列，答案是(min_{i=1}^n{max_{j=i}^{i+n-1}{T_j-j}+i+n-1})。
首先内层的(j)可以直接循环到(2n)，所以内层实际上是一个后缀最大值，而每个后缀最大值贡献答案的位置一定是在下标最小的那个位置。线段树维护单调栈即可。
[BZOJ4591][SHOI2015]超能粒子炮·改
设(f_{n,m}=sum_{i=0}^minom ni)，根据(mbox{Lucas})定理有
(sum_{i=0}^minom ni=sum_{i=0}^{p-1}inom{n/p}{0} imesinom{n\%p}{i}+sum_{i=0}^{p-1}inom{n/p}{1} imesinom{n\%p}{i}+...+sum_{i=0}^{m\%p}inom{n/p}{m/p} imesinom{n\%p}{i}\=f_{n/p,m/p-1} imes f_{n\%p,p-1}+f_{n\%p,m\%p} imesinom{n/p}{m/p})
预处理一下然后搞搞。
[BZOJ4590][SHOI2015]自动刷题机
二分即可。
[BZOJ4593][SHOI2015]聚变反应炉
设(f_i)表示(i)点子树全部激活，(i)点先于父亲被激活的最小代价，(g_i)表示(i)点晚于父亲被激活的最小代价。比较显然的一点是(0le f_i-g_i le c_i)。
若(c_ile1)则至多两种情况，若(f_i=g_i)则选(f_i)，否则选(g_i)，可以证明不存在更优。复杂度(O(n))。
若(c_i>1)则可以背包做一下，复杂度(O(n^2c))。
[BZOJ4597][SHOI2016]随机序列
考虑一个含加减号的序列，将加减全部取反，运算结果除开头的一段连乘外全部抵消。
所以答案就是(sum_{i=1}^{n-1}(prod_{j=1}^ia_j) imes2 imes3^{n-i-2}+prod_{i=1}^na_i)。
线段树随便维护一下即可。
[BZOJ4416][SHOI2013]阶乘字符串
建个序列自动机预处理(g_{i,j})表示从(i)位置开始第一个(j)字符的出现位置。
(f_s)表示(s)这个集合内的(|s|!)种排列的最晚出现位置，xjb转移一下，复杂度(O(n2^n))。
据说(n>21)一定不合法。。。然后就做完了吧。
[BZOJ4418][SHOI2013]扇形面积并
扫描线，每次查询当前已有半径的(mbox{kth})，可以用树状数组反正我写的线段树。
[BZOJ4419][SHOI2013]发微博
记(f_i)表示(i)这个人目前发了多少条微博，(g_i)表示(i)这个人的答案。连接一条边时(g_u-=f_v,g_v-=f_u)，断开时(g_u+=f_v,g_v+=f_u)，最后再把所有没断开的边断开即可。
[BZOJ4417][SHOI2013]超级跳马
一开始还以为有什么组合意义上的高论......直接(O((2n)^3log m))矩乘即可。
[BZOJ4415][SHOI2013]发牌
维护(mbox{kth})，还是树状数组可做（怎么(mbox{SHOI2013})考两道一样的题啊）
[BZOJ4420][SHOI2013]二重镇
就是个傻逼状压(dp)，先搜出所有稳定状态，然后枚举每个状态转移，(f_{i,j,k})表示前(i)个物品，仓库里是(j)，地面上状态是(k)的最优解，复杂度大概是(O(m imes6^8))的。
[BZOJ3564][SHOI2014]信号增幅仪
转一下坐标轴，再把横坐标除以(p)，就变成了最小圆覆盖的板子。期望复杂度(O(n))。
[BZOJ3562][SHOI2014]神奇化合物
是不是几年前没有线段树分治这种科技啊......为什么要加这么多奇怪的限制条件啊......