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换一下就好了,这有点像归并。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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不多,然后就可以矩乘。

构造转移矩阵:忘了(!!!)

¥$%&#=!@#^——Dvc()

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

文章目录
  1. 1. [HEOI2015]兔子与樱花
  2. 2. Luogu P4755 Beautiful Pair
  3. 3. Luogu P4852 yyf hates choukapai
  4. 4. NOIAC32 Sort
  5. 5. 平面最近点对问题
  6. 6. [BJWC2011]最小三角形
  7. 7. [COCI2015]Norma
  8. 8. [ZJOI2016]旅行者
  9. 9. CF875D High Cry
  10. 10. 【UNR #2】积劳成疾
  11. 11. [HNOI2011]卡农
  12. 12. CF1187E Tree Painting
  13. 13. [APIO2014]连珠线
  14. 14. [SHOI2014]概率充电器
  15. 15. [HNOI2015]亚瑟王
  16. 16. CF1174E Ehab and the Expected GCD Problem
  17. 17. CF213E Two Permutations
  • 以上是我有干劲且四肢健全的时候做的题目,下面是颓废时的划水清单。
    1. 1. [Ynoi2011]D1T2
    2. 2. [清华集训2017 小Y和地铁]
    3. 3. [CQOI2018]解锁屏幕
    4. 4. CF449D Jzzhu and Numbers
    5. 5. [SDOI2009]学校食堂
    6. 6. [HNOI2010]公交线路
  • ,
    载入天数...载入时分秒... 字数统计:75.7k