SLOJ2623 Three
D3T3 ThreeDesciption:给定一颗 $n$ 个节点的无根树,在树上选三个互不相同的节点,使得三个节点两两之间距离相等,输出方案数。
Solution:首先,我不是很会 $dp$
其次,我完全不会长链剖分优化 $dp$
最后,我
其实 $dp$ 部分还是听懂了。
设 $f_{i,j}$ 表示以 $i$ 为根的子树中距离 $i$ 为 $j$ 的点数,$g_{i,j}$ 表示 $i$ 的子树中有多少两个点的 $lca$ 到 $i$ 的距离为 $d-j$ ,两个点到他们 $lca$ 的距离是 $d$ 。
很容易发现这两个状态可以互补(?
因此对于一对父子 $(p,v)$ 有如下转移式:
ans+=g_{v,i+1}*f_{p,i}+g_{p,i}*f_{v,i-1}
g_{p,i}+=g_{v,i-1}+f_{v,i-1}*f_{p,i}
f_{p,i}+=f_{v,i-1}但是代码就完全就看不懂了,什么指针转移力(哭
Code:1234567891011121314151617181920212223242526272829303132333435363738 ...
西川实验随笔
0. 写在前面懒癌晚期患者,本来说毕业暑假找个时间写写,结果拖到现在
在外面漂泊了大半年,仍然还是很想xcsy
怎么说呢,已经算是一种精神寄托了属于是
1.大事祭1.1 初一之前1.1.1 2019.6以前的事最早关于xcsy还是在2018.9的样子。听说ljz被挖到xczx去了,后面才知道是xcsy,1w的奖学金,还有晚自习练魔方的权利,爽死了。心想我也身为一个cuber会不会也有这种待遇。后面才发现ljz是我永远无法企及的高度。
2019.1以及2019.6 ljz拿世界冠军、去上节目确实让xcsy好好吹了一把,感觉还能再宣传5年。
好了该是我自己的事了。
好怀念我们当时还没有全摇号的日子。
大概2019.1(记不太清了 tyc首先拿到了xcsy的offer,好像是小考进的,xhx整个六年级下大概都在外面补课,那个机构也有进xcsy的手段。我大概是2019.5小面试的时候拿到了减分的政策,7月的大面试不失常就肯定能进了。
当时还是很开心的立马停掉了奥数课然后2019.6还去打了桂林赛,属于保送了。
记得小考还拿到了tfqz的offer,区上摇号还有qzcz。因为那年xcsy风头太盛 ...
Luogu1712 [NOI2016]区间
D2T1 [NOI2016]区间Desciption:有 $n$ 个闭区间 $[l_i,r_i]$ ,从中选出 $m$ 个区间,使得存在 $x$ ,使得每个被选择的区间都有 $l_i \leq x \leq r_i$。
选择一个合法的方案,它的花费为最长的区间长度减去最短区间长度,定义区间长度为 $r_i-l_i$。
求最小的花费,如果没有合法方案则输出 $-1$ 。
Solution:考虑先将区间按照花费从小到大排序,然后用尺取法加线段树维护即可。
Code:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#include<bits/stdc++.h>using namespace std;const int maxn=5e5+10;#define in ...
dfs序
感觉这个也算是个知识点但是到处都没有教程捏
这里有一篇写的很好的关于dfs序的教程。
dfs序就是把树上问题转化为序列问题,从而通过树状数组或线段树进行维护。
dfs序本身不难理解,难的是与树状数组以及线段树结合,再加上巨大的码量。一下的四个例题码量平均100+。
多码预警
下面用一些例题讲解。
1.单点修改,子树查询在dfs序中,$x$ 的子树在两次 $x$ 出现的中间,且是连续的。
所以问题就转化为序列上单点修改,区间查询。树状数组维护即可。
code:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include<bits/stdc++.h>using namespace std;#define in read()#define ll long longinline ll read(){ ll x=0,f=1;c ...
Luogu2048 超级钢琴
传送门
Description:有一个长度为 $n$ 的序列,从中选出 $k$ 个长度为 $l \leq k \leq r$ 的不同的区间,使得区间和最大。
Solution:前缀和+堆+RMQ
首先前缀和优化区间和。
以区间最大值为关键字建立大根堆 ,枚举左端点,查找 $[l,r]$ 区间加入堆中。然后循环 $k$ 次,每次取出堆顶,累加贡献,间 $[l,pos-1]$ 和 $[pos+1,r]$ 加入堆, $pos$ 代表 $[l,r]$ 区间中最大值的位置。
Code:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn=5e5+10;int n,k,l,r,logn[maxn],f[maxn][24];ll a[maxn];vo ...
Luogu2680 [NOIP2015提高组]运输计划
题目传送门](https://www.luogu.com.cn/problem/P2680) )
一道感觉不算很难的紫题
翻译一下
给定一棵有边权的树,和 $m$ 组点对,需要选择并清零一条边,使得 $m$ 条边之间的最长路最短。
solution最小化最大值,一眼二分。
然后考虑 $check$ 函数怎么写。很容易想到一个很暴力的解法:暴力枚举清零每一条边。一算时间复杂度肯定接受不了。
考虑优化。观察到枚举过程可以进行优化。先预处理出每条路径的长度, $check$ 时统计大于 $mid$ 的边有 $k$ 条,找出被经过 $k$ 次的边且边权最大的一条,判断最长路径 $maxlen$ 减去最长边 $maxd$ 是否小于 $mid$.
综上所述,先用树上差分+$LCA$ 预处理出每条路径的长度,二分答案,树上差分进行 $check$。
code细节都批注在代码里了。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960 ...
Luogu2839 middle
description传送门
丽洁还是很吊的
这道题我还尚未完全摸透做法,所以仅作为一道好题放在这里
代码难度不大,但是思维含量极高
但我是绝对不会说我的 $queryrmax$ 和 $querylaxm$ 函数因为是复制粘贴的所以 debug 了一个小时(逃
说不定几万年后我 AKIOI 之后再回来看就明白了呢
solution首先对于每一个询问可以进行二分答案。
然后考虑求中位数。一个小套路:==将所有大于等于 $mid$ 的设为 1,小于的设为 -1,当区间和为 0 的时候就 $mid$ 就是中位数==。为了选择更大的中位数,所以要尽可能多选择 1。(why?)那么就要维护一个最长子序列。
对于每一个询问都要开一个线段树,那么肯定选择主席树啦(why?)。每个节点维护一个区间和,区间最大前缀和区间最大后缀。
code:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707 ...
Luogu2894 Hotel
D1T4 HotelDescription:对于一个01序列,维护两个值:
1 x 找出长度为 $x$ 的区间变为 1,并输出最左的一个左端点。
2 l r 将 $[l,r]$ 变成 0。
Solution:对于操作 1,用线段树维护最长子段和,在 query 函数里的查询操作改为
1234567int query(int l,int r,int p,int length){ pushdown(p); int mid=t[p].l+t[p].r>>1; if(t[p<<1].sum>=length) return query(l,r,p<<1,length); if(t[p<<1].rmax+t[p<<1|1].lmax>=length) return mid-t[p<<1].rmax+1; return query(l,r,p<<1|1,length);}
对于操作 2,区间赋值操作即可
Code:123456789101112131415161718192021222 ...
Luogu3225 [HNOI2012]矿场搭建
题目
是一道练习 $tarjan$ 的好题。
首先读题,很容易想到是要先跑一遍 $tarjan$ 求割点。然后想想每一个连通块,分为几种情况:
如果没有割点,如果其中一个点断开,那么就会分成两个连通块,所以需要增加两个出口,在其中随便选两种就好, 共$C_n^2$种选择。
如果有一个割点,无论是否断在割点都需要一个出口,在非割点的地方随机选择即可。
如果有两个及以上割点,无论断在哪里,图都是联通的,所以不需要建立出口。
这道题有一些小坑,比如某些数据记得清零。记录最大值的变量没清零: $100pts->90pts$ (悲
然后是代码
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include<bits/stdc++.h>using namespace std;con ...
Luogu3313 [SDOI2014]旅行
D4T1 [SDOI2014]旅行传送门
Desciption:给定一颗 $n$ 个节点的树,每个节点都有一个权值和一种颜色。
有 $q$ 个询问:
CC x c 将节点 $x$ 的颜色改为 $c$
CW x w 将节点 $x$ 的权值改为 $w$
QS x y 询问 $$ 路径上与 $x,y$ 颜色相同的点的权值和
QM x y 询问 $$ 路径上与 $x,y$ 颜色相同的点的最大权值
Solution:首先明确肯定用树剖来维护询问和修改。
对于每一个宗教我们都要开一颗线段树来维护,所以考虑用主席树。
主席树+树剖,其他的与线段树+树剖一样。
Hint:
查询最大最小值得时候记得加上if(qr<l||ql>r) return 0;,不然不晓得飞到哪里去。
主席树的空间玄学问题。本题的 $maxn$ 为 $1e^5$ ,理论上要开到 $maxn<<7$ 的范围才保险,但是 SLOJ上 $maxn<<6$ 才能过。
Code:123456789101112131415161718192021222324252627282930313233343536 ...
Luogu3569 Cards
D2T3 CardsDescription:每个卡片有 $a_i$ 和 $b_i$ 两个数。交换 $c_i$ 和 $d_i$ 两个位置上的卡片,判断能否将任意卡片翻转,保证卡片正面的数单调不减。
Solution:考虑线段树维护区间能否单调不减。合并时判断即可。但是常数巨大还在 $T$ 着呢。
对于合并的pushup
1234567891011121314void pushup(int p){ int mid=t[p].l+t[p].r>>1; //t[p].f[0][0]=t[p].f[1][0]=t[p].f[0][1]=t[p].f[1][1]=0; for(int i=0;i<=1;i++){ for(int j=0;j<=1;j++){ t[p].f[i][j]=0; for(int k=0;k<=1;k++){ for(int l=0;l<=1;l++){ t[p].f[i][j]|=t[p<<1].f[i][k]&t[p<<1|1] ...
Luogu3852 Kinoman
D1T3 KinomanDesciption共有 $m$ 部电影,第 $i$ 部电影的好看值为 $w_i$。
在 $n$ 天之中,每天会放映一部电影,第 $i$ 天放映的是第 $f_i$ 部。
你可以选择 $l,r(1<=l<=r<=n)$,并观看第 $l,l+1,\dots,r$ 天内所有的电影。如果同一部电影你观看多于一次,你会感到无聊,于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
Solution:第 $i$ 部电影对 $[pre_i+1,i]$ 区间有贡献。用线段树维护区间最大值。每次枚举右端点,每次操作时,将 $[pre_i+1,i]$ 加上 $w_i$ ,但是前面的贡献要减去,所以$[pre_{pre_i},pre_i]$ 减去 $w_i$ 。
Code:123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707 ...


![Luogu1712 [NOI2016]区间](/img/posts/pCt6E9S.jpg)


![Luogu2680 [NOIP2015提高组]运输计划](/img/posts/pCtX7kV.jpg)


![Luogu3225 [HNOI2012]矿场搭建](/img/posts/pCtXIwq.jpg)
![Luogu3313 [SDOI2014]旅行](/img/posts/pCtXhOs.jpg)

