CSP2019前的做题记录

做一个高产的人（不存在的）

说不定哪天就咕了

[HEOI2015]兔子与樱花

传送门

贪心，从下往上，每个点尽可能删去多的儿子。

考虑这个做法的正确性，考虑不动，感觉挺对的。

Luogu P4755 Beautiful Pair

传送门

分治，把当前区间最大的点拿出来，统计经过它的区间的个数。对于它左右两个区间，扫一遍小的，在另一边用主席树找符合条件的区间数。然后继续分治。

考虑这个做法的复杂度，最坏情况就是最大点在区间中间，这样一直下去有log层，所以复杂度大概是两个log的。具体证明我也不会，感觉挺对的。

Luogu P4852 yyf hates choukapai

传送门

单调队列优化dp，发现每次连抽其实就是舍弃了n-1张连续卡的欧气，让舍弃的尽量小即可。

于是可以dp，$f_{i,j}$表示前i张连抽j次，并且第i张是第j次连抽的开始时的最小值。

那么$f_{i,j}=(min_{k=i-c-d}^{i-c}f_{k,j-1})+\sum_{k=i+1}^{i+k-1}a_k$ 这个东西可以单调队列优化一下，复杂度就对了。

不过还有很对细节，比如你要判断一个状态合不合法，这用到了一些跟鸽巢原理有关的技巧，我不会就是了。

NOIAC32 Sort

传送门

分治套分治，先离散化成一个排列，然后尝试着模拟快排的做法，对于区间$[l,r]$，取出它们的中点mid，使$[l,mid]$的数都不大于mid，$[mid+1,r]$的数都大于mid。然后继续递归给左右两边区间排序，这是第一层分治。

使$[l,mid]$的数都不大于mid，$[mid+1,r]$的数都大于mid，这相当于给一个只有0和1的序列排序。可以分治，考虑先把$[l,mid]$和$[mid+1,r]$各自排好序，那这个序列的样子一定是这样：0 0 0 1 1 1 0 0 0 1 1 1 只要把中间的一堆0和一堆1换一下就好了，这有点像归并。

这个做法的复杂度我也不会证，感觉挺对的，附上分治代码。

void merge(int l,int r){
    if (l==r) return;
    int mid=(l+r)>>1;
    merge(l,mid),merge(mid+1,r);
    int lp=mid+1,rp=mid;
    while (lp>l&&b[lp-1]) lp--;
    while (rp<r&&!b[rp+1]) rp++;
    if (lp>=rp) return;
    printf("%d %d\n",lp,rp);
    for (int i=lp,j=rp; i<=j; i++,j--)
        swap(b[i],b[j]),swap(c[i],c[j]);
}
void solve(int l,int r){
    if (l==r) return;
    int mid=(l+r)>>1;
    for (int i=l; i<=r; i++) b[i]=(c[i]>mid);
    merge(l,r);
    solve(l,mid); solve(mid+1,r);
}

平面最近点对问题

传送门

平面分治思想的板子，按横坐标排序，分治时按中位数mid分到左边和右边，先递归下去得到两个子问题的答案，然后考虑现在这个问题。

假设现在答案是dis，我们现在要找的是跨过$x=mid$这条直线且距离小于dis的点对，那么有可能用到的点的横坐标会在$[mid-dis,mid+dis]$。对于横坐标符合条件的一个点$a(x,y)$，能和a一起更新答案的点的纵坐标范围是$[y-dis,y+dis]$，按纵坐标排序暴力枚举点对即可。

尝试证明这玩意的复杂度，失败了。

[BJWC2011]最小三角形

传送门

平面分治思想的应用，接着分治，把左右做完之后考虑拿一个矩形把最优三角形框进去，发现当当前最优三角形周长为dis时，最坏情况下就是那个三角形是条线，那么框它的最优矩形就是一个边长为$dis/2$的正方形，在这个正方形里暴力枚举好了。

复杂度？这辈子都不可能证的。

[COCI2015]Norma

传送门

上午看这题的时候降智了。

直接分治，考虑跨越区间中点的答案，由中间向左枚举左端点p，这样得到$[p,mid]$的最小值mi和最大值ma，之后维护向右最小值为mi和最大值为ma的最长长度mn和mx。

假设$mn<mx$，那么右边被分成三段。

第一段$[mid+1,mn]$，答案是$mi\times ma\sum_{i=mid+1}^{mn}(i-p+1)$，维护自然数前缀和就好了。

第二段$[mn+1,mx]$，答案是$ma\sum_{i=mn+1}^{mx}(i-p+1)\times minn[i]$，$minn[i]$表示$[mid+1,i]$的最小值，把$i-p+1$拆成$i-(p-1)$，维护$i\times minn[i]$和$minn[i]$的前缀和就好了。

第三段$[mx+1,r]$，答案是我懒得写的式子，维护$minn[i]\times maxn[i]$和$i\times minn[i]\times maxn[i]$的前缀和就好了。

[ZJOI2016]旅行者

传送门

我的题解

CF875D High Cry

传送门

早上交的晚上都没测完，就当我A了，祝CF早日康复（雾）。

考虑区间或和一定不小于最大值，可以减去区间或和等于最大值的区间个数，这个可以分治做，对每个点求出向左右第一个在二进制下不是它子集的位置，这个东西可以维护一下二进制下每一位当前最靠左或右的1的位置，之后枚举当前数的每一位，木桶原理一下（就是那个经常被用来批判你偏科的那个东西），然后求出最大值分治即可。

（好像有一个小技巧的样子）

10.11 update CF好了，但是垃圾洛谷把我代码弄没了，不可能重写的，就怪洛谷垃圾好了。

【UNR #2】积劳成疾

传送门

伟大的wz恒带我做的，这是他的题解。

考虑分治，对区间$[l,r]$枚举其最大值和最大值的位置mid，之后分裂成$[l,mid-1]$和$[mid+1,r]$，这样复杂度是$O(n^4)$。

这时候伟大的wz恒跳出来了，在对我实行例行嘲讽后伟大的wz恒说l和r没有什么用，只要记一下区间长度就好了，我聆听了伟大的wz恒的教诲，这样一个分治就变成记搜了。于是我就抄了伟大的wz恒的题解，而且完全看不懂正常的dp做法了。

[HNOI2011]卡农

传送门

题意其实是说，从$2^n-1$个数中无序选m个不同的数，使其异或和为0。

设$f_i$表示有序的i个各不相同且非0的数，其异或和为0的方案数，那么答案就是$\frac{f_m}{m!}$。

利用容斥转移，先考虑可以随便选，那么就是$f_i=A_{2^n-1}^{i-1}$，意思是前$i-1$个数随便选，第i个数自然就被确定了。

考虑第i个数是0的情况，这样前$i-1$个数异或和自然是0，就是$f_{i-1}$。

考虑有重复的情况，第i个数和前面$i-1$个数中任意一个相同，这样会有$i-2$个数异或和是0，还要枚举这个相同的值，所以是$(i-1)\times f_{i-2}\times (2^n-1-(i-2))$。

所以转移方程是：
$$
f_i=A_{2^n-1}^{i-1}-f_{i-1}-(i-1)\times f_{i-2}\times (2^n-1-(i-2))
$$

CF1187E Tree Painting

传送门

复习(重学)一下换根dp。

第一次dp：$f_i=size_i+\sum_{j\in son_x}f_j$

第二次换根：$f_j=f_i-size_j\times 2+n$

[APIO2014]连珠线

传送门

真正的换根dp，上面那个太水了。

考虑枚举根，那么所有的蓝边都是父-子-孙，对于每个根来说最优方法唯一。

那么还是先dp一个根的答案，$f[i][0/1]$表示i是/不是两条蓝边中点时，i子树中的最大得分。

那么$f_{i,0}=\sum_{j\in son_i}max(f_{j,0},f_{j,1}+w(i,j))$

$f[i][1]$特殊一些，就是在$f[i][0]$的基础上，从儿子中选一个价值大的连上去。

即$f_{i,1}=f_{i,0}+\max_{j\in son_i}(f_{j,0}+w(i,j)-max(f_{j,0},f_{j,1}+w(i,j)))$

现在考虑换根，从一个父亲转移到儿子的时候要去掉这个儿子对父亲的影响，之后用父亲去更新儿子。

不过这题的影响不是很好去，所以开一个vector记一下每个点没有哪个儿子时的答案，然后先用祖父更新没有这个儿子时的父亲，再用父亲更新儿子。

感觉我实现得非常丑陋，多记了很多没用的东西，改天改一下吧（一定会咕）

[SHOI2014]概率充电器

传送门

由换根过度到期望，感觉期望好神仙啊。

一个点可以被自己、儿子和爸爸点亮，这难以dp，不过如果确定一个根，那么根只会被儿子点亮，那就知道了根被点亮的的概率，枚举根就可以了。

上面是一个$O(n^2)$做法，显然可以换根dp来优化它，不过要先考虑怎么求一个点只被自己和子树点亮的概率。

思考一下发现不如求它不被点亮的概率，$f_i$表示i不被点亮的概率，有$f_i=(1-q_i)\times \Pi_{j\in son_i}(f_j\times p(i,j)+(1-p(i,j)))$。

之后是一个简单的换根：设j是i的儿子，$g_j$表示j为根时不被点亮的概率$g_j=(1-q_j)\times(\frac{f_i\times p(i,j)}{p(i,j)\times f_j+(1-p(i,j))}+(1-p(i,j)))$

就是把上面那个式子带进去。。。

[HNOI2015]亚瑟王

传送门

永远魔高一丈的概率题（是开题顺序的问题吗？）

期望的线性性：算出每张牌被打出的概率乘伤害=总伤害的期望

然后考虑算每张牌被打出的概率，不会算

可以先求出在r轮中前i张牌用了j张的概率$f_{i,j}$，这样第i张牌最后被打出的概率就是$\sum_{j=0}^rf_{i-1,j}\times(1-(1-p_i)^{r-j})$，意思就是这张牌有j次因为前面的牌被发动而被跳过，这样它不被打出的概率就是$p_i^{r-j}$。

那么考虑dp求$f_{i,j}$，这像极了组合数的求法。

如果第i张牌不被打出，那么$f_{i,j}=f_{i-1,j}\times (1-p_i)^{r-j}$，否则$f_{i,j}=f_{i-1,j-1}\times (1-(1-p_i)^{r-j+1})$，就是第i张牌被打出了。

CF1174E Ehab and the Expected GCD Problem

传送门

今天解锁了陪阿潮玩耍的正确方式(#_#)/~，更完这题题解我就去。

最近开始搞模拟赛了，到晚上就会很无聊，查鳖的水表看到了国庆去ZR讲的一道题（鳖竟然没用当时讲的做法，怕不是掉线了）

发现如果想让gcd变化尽量多，第一个数一定是$2^x3^y$的形式，任何大于3的质数都可以被2的多次幂取代，同时3的平方可以被2的立方取代，所以$y\in {0,1}$。

于是可以dp，$f[i][j][k]$表示前i个数，gcd为$2^j3^k$的方案数，转移只有三种可能：

gcd不变：有$2^j3^k$的倍数个数可以选，其中前面已经选了$i-1$个

$j-1$：有$2^{j-1}3^k$的倍数个数可以选，但不能选$2^j3^k$的倍数

$k-1$：同$j-1$的情况

滚动第一维转移就好了。

CF213E Two Permutations

传送门

感谢zhouer给的一道线段树维护hash！

这似乎是线段树维护hash的套路，就是用来维护子序列的hash，将离散化的子序列插入一棵整个序列的线段树里，通过维护子树大小和相对排名维护整个子序列的hash。

之后这题的做法就是枚举x，将$a_i+x$后的值插入线段树里得到hash值，再加一个每一位都乘x的hash值就好了。

以上是我有干劲且四肢健全的时候做的题目，下面是颓废时的划水清单。

[Ynoi2011]D1T2

传送门

线段树维护hash，离散化一下，维护每个权值的下标，对于A串的每个可能被匹配的区间，求出其hash值，开个map存进去。之后离线处理B串的修改查桶就是了，不知道哪里写挂了只有31，小数据拍不出错来于是就弃了（不愧是我）。

[清华集训2017 小Y和地铁]

传送门

没错我就是这么颓。

发现每对相同的地铁站只有4种方式，之后竟然有两对方式他们对后面影响是一样的，于是就只有2种本质不同的方式了，就是向上走或向下走，可以$2^{\frac{n}{2}}$爆搜，对于等价的两种方式，想办法判断一下他们哪个更优好了。

懒得画图也懒得说怎么判断，反正状压一下再乱搞一下好了（可见我多么颓废）。

[CQOI2018]解锁屏幕

传送门

大水题，状压dp，$f[i][j]$表示集合为i最后一个为j的方案数，预处理一下两点间的点集就可以dp了。

复杂度啊虽然看起来不大对但跟我有什么关系呢？

颓啊颓啊颓啊颓啊~~

2019/11/4：打算重新更了，可是多出来了好多题，怎么办啊。。。

CF449D Jzzhu and Numbers

传送门

高维前缀和，学的不是那么明白，以后会填坑的。

$f_s$表示子集含s的方案数，这是个前缀和的形式，需要做一个高维前缀和来得到。

高维前缀和的做法就是把每一维单独加进去，很仙就是了，有了f就可以容斥做完了。

果然学不进去新东西

[SDOI2009]学校食堂

传送门

太仙了不大会的样子。。。

状压每个人后面8个人的状态，记一下上一个做菜的人，顺序dp，枚举当前给谁做菜，在合法的前提下转移，$f_{i,j,k}$表示到第i人，状态为j，上一个是第$i+k$个人的最小时间，i能转移到i+1的条件是$i\in j$。

滥竽充数的题解。

[HNOI2010]公交线路

传送门

状压+矩乘

$f_{i,j}$表示最慢的车到了i，i前面p个位置的覆盖状况是j的方案数（如果j中一个位置是1表示这里是某辆车的最后的停靠站），对j的要求是其中必须有k个1且第一位必须是1，这样的j不多，然后就可以矩乘。

构造转移矩阵：忘了（！！！）

￥$%&#=！＠＃＾——Ｄｖｃ（）

这个更博的人心态炸了，今天就到这里了。