省选知识点做题记录

标签：知识点 记录 省选 题解 sum 区间 可以 线段 dp

luogu

[IOI2014]Wall 砖墙

题解

可以转化为区间取 \(min\) 和区间取 \(max\) .

规定一下下传标记的顺序推一下式子就行了.

[NOIP2013 提高组] 华容道

题解

先想到了朴素的 \(O(q(nm) ^ 2)\) 的算法.

接着发现只需要记录可移动棋子周围的空格情况.

但空格从这个棋子的一侧一道另一侧需要保证不经过这个棋子.

发现这个可以 \(O((nm) ^ 2)\) 预处理.

询问的时候就按照那个方法跑最短路就行了.

最短路的状态数为 \(O(nm)\).

[NOIP2017 提高组] 宝藏

思考

类比最小斯坦纳树的状态设计.

记 \(dp _ {i, S}\) 表示以 \(i\) 为根, 集合为 \(S\) 的最小代价.

\(dp _{i, S} = \min \{ dp _ {j, T} + w _ {i, j} + \text{T中的边权和}\}\).

\(T\) 中的边权和不太好算, 于是令 \(f _ {i, S}\) 表示当前以 \(i\) 为根, 集合为 \(S\) 的边权和.

但这样是错误的.

因为 \(dp _ {i, S}\) 可能由一个不那么优的 \(dp _ {j, T}\) 加上很优的 \(f _ {j, T}\) 转移过来.

题解

转变思路, 不从根的位置开始接, 从叶子开始接. (根 \(\rightarrow\) 叶)

设 \(dp _ {S, d}\) 表示集合为 \(S\) 最多经过的节点数为 \(d\) 的最小代价.

\(dp _ {S, d} = \min \{ dp _ {T, d - 1} + \text {S - T 中的最小边权和} \}\).

至于正确性的证明, 由于节点是按深度一层一层的加的, 所以一定能包含最优解, 而加边的过程只可能偏大不可能偏小, 因此能得到最优解.

总结

我认为, 要得到最优解必须满足这两个条件:

1. 状态必须包含最优解.
2. 状态不能包含多余的部分或多余的部分一定劣于最优解.

[NOI2010] 超级钢琴

题解

考虑对于每个起始点 \(s\) 的一段子串如何得到最大值.

很明显用 \(st\) 表就可以做到 \(O(1)\) .

题目需要求前 \(k\) 大的和, 可以考虑在得到一个最大值后把区间拆开.

这个用堆维护就行了.

[JLOI2015]管道连接

题解

最小斯坦纳树 \(+\) "多余部分劣于最优解"定理.

对最小斯坦纳树转移式子的证明似乎也可以用这个定理 ? ? ?

总结

其实对于最优解问题, 只要转移方式合法, 且能够得到一种对最优解的划分, 那这个转移一定是正确的, 因为其它转移的情况一定更劣.

[ZJOI2007]最大半连通子图

题解

\(tarjan\) 缩点 \(+\) 记忆化搜索.

注意缩点后有重边.

[USACO07MAR]Gold Balanced Lineup G

题解

将一长串连等式拆成很多个等式, 再分离变量.

只需要维护每个前缀的信息就行了.

[POI2015]MYJ

题解

设\(dp _ {i, j, k}\)表示\([i, j]\)最小值为\(k\)的最大和.

转移

\[dp _ {i, j, k} = \max {dp _ {i, x - 1, k1} + dp _ {x + 1, j, k2} + w | k1, k2 \geq k, x \in [i, j]} \]

P6617 查找 Search

https://www.luogu.com.cn/problem/P6617

https://www.luogu.com.cn/problem/P3792

https://www.luogu.com.cn/problem/P5278

总结

感觉这三道题用到的方法比较类似.

一般线段树是维护区间可合并的值.

如果问题需要支持修改,且询问的是值的相互关系,可以使用线段树 + set (平衡树).

P4198 楼房重建

总结

这道题启示我线段树的\(push\_up\)不一定是\(O(1)\),也可能是其它复杂度,比如\(O(\log)\).

只要区间的值能够通过子区间的值合并,都可以考虑使用线段树.

当然前提是合并的复杂度不能过高.

[HEOI2013]Segment

题解

李超线段树的模板题.

由于是求最值,因此维护的值可以不严格.

有这样一个定理,相交的两条线段一定可以从交点处分成两部分,一部分一条线段严格优于另一条.

因此可以只往一个区间递归.

这也是保证更新复杂度为\(O(\log ^ {2}n)\)的原因.

[CEOI2017]Building Bridges

题解

设\(sum _ i\)表示前\(i\)个\(w\)的和.

设\(dp _ i\)表示以\(i\)结尾的最小代价.

\[\begin {aligned} & dp _ {i} = sum _ {i - 1} + h _ {i} ^ {2} + dp _ {j} - sum _ {j} + h _ {j} ^ {2} - 2h _ {i} h _ {j} \\ & A(j) = -2h _ {j} \\ & B(j) = dp _ {j} - sum _ {j} + h _ {j} ^ {2} \\ & C(i) = sum _ {i - 1} + h _ {i} ^ {2} \\ & dp _ {i} = C(i) + A(j) h _ {i} + B(j) \\ \end {aligned} \]

相当于每次加入一条线段,每次查询线段的最值.

使用李超线段树维护即可.

表面上看,如果用李超线段树维护复杂度应该是\(O(n\log ^ {2} \max w)\).

但实际上每次更新的区间都是整个值域,线段树划分的区间数为\(1\).

所以实际复杂度应该是\(O(n \log \max w)\).

P5069 [Ynoi2015] 纵使日薄西山

题解

\(a _ {x - 1} - 1\),\(a _ {x} - 1\),\(a _ {x + 1} - 1\)并不会改变它们三者之间的关系,因此只需要维护一个选择的被减的数的集合.

只要能进行区间合并的题都可以用线段树,这道题可以合并,因此可以用线段树.

设\(s _ {x, 0/1/2/3}\)表示线段树上的节点\(x\)的区间的答案.

\(s _ {x, 0}\)表示未去除端点\(l\),\(r\).

\(s _ {x, 1}\)表示去除了端点\(l\).

\(s _ {x, 2}\)表示去除了端点\(r\).

\(s _ {x, 3}\)表示去除了端点\(l\),\(r\).

再记一下状态\(vl _ {x, 0/1/2/3}\),\(vr _ {x, 0/1/2/3}\)分别表示在\(s _ {x, 0/1/2/3}\)状态下是否选择了左端点或右端点.

转移的情况有点多,就不在这里写了.

总结

我太菜了!!!

自己以前总结过的东西还是忘了.

如果能够合并就可以用线段树维护,做题的时候一定要多想想维护的区间能否合并!

这道题如果用\(\text {set}\)维护的话代码非常复杂,而用线段树维护却很好写.但是题解里基本上都是用\(\text {set}\)维护的.

很明显,\(\text {set}\)维护没有通用性,用线段树要好一点.

所以不能盲目的只看几个题解,要善于从茫茫题解中发现最好的那一个.

P1251 餐巾计划问题

https://www.luogu.com.cn/problem/P1251

设每条需求量为\(x\),新餐巾费用为\(c\),洗餐巾的费用和时间分别为\(c _ 1\),\(c _ 2\),\(t _ 1\),\(t _ 2\).

最开始的错误想法是这样的:

1. \(S\)到早上连一条流量为无穷大,费用为\(c\)的边.
2. 晚上到\(T\)连一条流量为无穷大,费用为\(0\)的边.
3. 早上到晚上连一条流量为\(x\),费用为\(0\)的边.
4. 晚上到早上连洗餐巾的边.
5. 早上到下一天早上连一条流量为无穷大,费用为\(0\)的边.

这样的问题在于同一流量花在了两个费用上,结果不是最大流,因此跑最小费用最大流是错误的.

所以,每一流量必须对应唯一确定事件.

发现每天产生的旧餐巾数是固定的,可以考虑它们的去向,它们一部分可以清洗,一部分直接丢弃,用流量限制即可.

而新餐巾可以无限制的买,流量为无穷大.

如何限制每天需要的餐巾数呢?

将每一种提供餐巾的方案用一总的流量限制即可.

P2766 最长不下降子序列问题

https://www.luogu.com.cn/problem/P2766

这道题以前水过了,今天重做,发现还是有颇多问题.

刚开始,我是只把一个点内部的边连成有限值,其余都连成\(inf\).

但这有问题,仔细分析一下会发现当\(maxlen = 1\)或\(2\)时需要特殊处理.

于是将数之间的边改成\(1\),再判断一下\(maxlen = 1\)的情况就行了.

P2770 航空路线问题

https://www.luogu.com.cn/problem/P2770

使用了一个重要的技巧.

将无向图中一条\(1\rightarrow n\rightarrow 1\)的路径转化为有向图中两条\(1\rightarrow n\)的路径.

输出方案上有颇多细节,例如在残量网络上跑\(dfs\)时一条路径的流量不一定减少\(1\),也可能减少\(2\).

[NOI2004] 郁闷的出纳员

https://www.luogu.com.cn/problem/P1486

平衡树裸题.

从中加深了对\(splay\)写法的理解.

比如\(lowerbound\)可以这样写

int find(int val) {
	int x = root, res = -1;
	int mn = inf;
	while(x) {
		push_down(x);
		if(b[x].val < val) x = rc;
		else if(b[x].val >= val) {
			if(b[x].val <= mn) mn = b[x].val, res = x;
			x = lc;
		}
	}
	return res;
}

P3356 火星探险问题

https://www.luogu.com.cn/problem/P3356

输出方案的时候要注意.

不能边跑费用流边输出,因为可能会反悔.

对残量网络建新图时要注意反向边.

[NOI2008] 志愿者招募

https://www.luogu.com.cn/problem/P3980

线性规划转费用流.

设第\(i\)类志愿者的数量为\(x _ i\).

设\(t _ {i, j}\)表示第\(i\)天是否可以有第\(j\)类志愿者工作.

题目要求

\[\begin{cases} \sum _ {i} x _ i t _ {1, i}\geq a _ 1 \\ \sum _ {i} x _ i t _ {2, i}\geq a _ 2 \\ \text {...} \\ \sum _ {i} x _ i t _ {n, i}\geq a _ n \end{cases} \]

变量为\(x _ i \geq 0\).

需转化为网络流,因此引入新变量\(y _ i \geq 0\),得

\[\begin{cases} \sum _ {i} x _ i t _ {1, i} - a _ 1 - y _ 1 = 0\\ \sum _ {i} x _ i t _ {2, i} - a _ 2 - y _ 2 = 0\\ \text {...} \\ \sum _ {i} x _ i t _ {n, i} - a _ n + y _ n = 0\\ \end{cases} \]

因为\(s _ i\)到\(t _ i\)连续,所以上减下差分后可以发现

	初始\(x _ i\)的系数	差分后\(x _ i\)的系数
\(s _ i\)	\(1\)	\(-1\)
\((s _ i, t _ i)\)	\(1\)	\(0\)
\(t _ i\)	\(1\)	\(0\)
\(t _ i + 1\)	\(0\)	\(1\)

即\(s _ i\)向\(t _ i + 1\)连一条容量为\(inf\)的边.

剩余部分

\[\begin{cases} a _ 1 + y _ 1 = 0 \\ a _ 2 + y _ 2 - a _ 1 - y _ 1 = 0 \\ a _ 3 + y _ 3 - a _ 2 - y _ 2 = 0 \\ \text{...} \\ a _ n + y _ n - a _ {n - 1} - y _ {n - 1} = 0 \\ -a _ n - y _ n = 0 \end{cases} \]

即\(i + 1\)向\(i\)连一条容量为\(inf\)边.

对于常数项,如果为正,则从\(S\)连边,如果为负,则向\(T\)连边.

要满足题目要求的不等式等价于\(S\)连出去的所有边和连进\(T\)的所有边满流,并最小化\(\sum _ {i}x _ i c _ i\)的代价.

因此可以用最小费用最大流解决.

[NOI2012] 美食节

https://www.luogu.com.cn/problem/P2050

考虑把厨师拆开,分别表示最后做某种菜,倒数第二做某种菜......

费用分别为\(k\cdot t _ {i, j}\).

若直接建图数量太大,会超时.

由于\(EK\)每次只找一条路径,因此可以考虑动态加边.

P3357 最长k可重线段集问题

https://www.luogu.com.cn/problem/P3357

与https://www.luogu.com.cn/problem/P3980类似.

从\((0, 1)\)开始将开区间标号.

则\((x _ i, y _ i)\)表示的是区间\([x _ i, y _ i - 1]\).

令\(a _ {i, j}\)表示下标\(i\)是否有区间\(j\).

同之前那道题推导即可.

但是,这种做法太过复杂,熟练之后有更好的理解方式.

这道题的一般想法是并联表示选不选区间,但区间之间有关系.

那就干脆直接串联,一个单位的流量表示一段长度能被哪些区间覆盖.

[SHOI2014]三叉神经树(动态树)

利用三叉树情况少的性质(本质上只有两种),想到了\(O(n \log ^ {2} n)\)的树链剖分.

令我震惊的是\(LCT\)的\(access\)复杂度竟然是\(O(\log n)\).

因此,把树链剖分改成\(LCT\)就可把复杂度降为\(O(n \log n)\)

总结

这道题调了一段时间的原因是\(\text{push\_up}\)的时候只上传了右子树.这样做是不对的,因为\(\text{splay}\)端点后并不是一条链.

[HNOI2012]永无乡

https://www.luogu.com.cn/problem/P3224

用时

\(1\)小时\(20\)分.

总结

我\(splay\)写得越来越熟练了!

调题的主要时间花在了并查集\(sz\)没赋初值,以及合并时将\(sz\)与平衡树混淆上.

P3950 部落冲突

https://www.luogu.com.cn/problem/P3950

一遍过了!

用时

\(25\)分钟.

[AHOI2005] 航线规划

https://www.luogu.com.cn/problem/P2542

用时

\(1\)小时\(30\)分钟.

总结

这是一道\(LCT\)维护边双连通分量的题.

由于每次只会更改连向某条实链的\(fa\)指针,因此\(access\)的时候修改就行了.

写这道题的时候不是很清楚为什么可以这道修改,导致不仔细,有很多细节错误.

[WC2006]水管局长

https://www.luogu.com.cn/problem/P4172

用时

\(1\)小时

总结

三者取最大值是要用大于等于,因为两个最大值相等的情况可能返回较小值.

[WC2006]水管局长

https://www.luogu.com.cn/problem/P4172

用时

\(40\)分钟

总结

同https://www.luogu.com.cn/problem/P4172.

都是用\(LCT\)维护最小生成树.

P2617 Dynamic Rankings

题解

题解说是"树状数组套主席树".

我认为"树状数组套动态开点权值线段树"更合适一些.

树套树可以理解为使用多棵树维护一段序列,再将这些树用一棵树来维护.

[ZJOI2013]K大数查询

题解

同"P2617 Dynamic Rankings".

只是因为有区间修改,因此只能使用线段树套动态开点权值线段树.

等等,这好像有问题,因为外层线段树需要维护区间修改,要打\(lazytag\),但这似乎打不了\(lazytag\).

因此,考虑把位置线段树套权值线段树改为权值线段树套位置线段树.

权值上只需要维护单点修改,这是可以不打\(lazytag\)的.

[POI2011]ROT-Tree Rotations

题解

对每个叶子节点开一棵权值线段树,每次合并时计算贡献.

若不交换,贡献为\(t[t[x].rc].siz * t[t[y].lc].siz\).

若交换,贡献为\(t[t[y].rc].siz * t[t[x].lc].siz\).

[湖南集训]更为厉害

题解

如果\(b\)在\(a\)的上方,那么对答案的贡献为\(min(k, depth[a] - 1) * (siz[a] - 1)\).

如果\(b\)在\(a\)的下方,有贡献的点为\(depth \in [depth[a] + 1, depth[a] + k]\),且为\(a\)的子孙节点,每个这样的点对答案的贡献为\(siz - 1\).

这是一个二维的结构,可以使用线段树套线段树,仔细想想可以发现没有修改,因此只需使用主席树.

[HEOI2016/TJOI2016]排序

题解

区间更新为排序的问题使我想到了\(CF\)的几道字母排序的题,只需要对每种值记录在某个位置是否出现就行了.

但这道题的值太多了,并不能直接这么做.

可是考虑到只有最后一次询问,所以可以离线.

二分最后的答案,把\(\geq mid\)的变为\(1\),\(< mid\)的变为\(0\),最后检验那个位置的数是不是\(1\)就行了.

[CTSC2018]混合果汁

题解

二分一个最小美味度,把这些果汁放到权值线段树上二分.

先按每美味度从大到小排序,这样每次放入的果汁是一个前缀.

因此可以建出主席树.

P6071 [MdOI R1] Treequery

题解

分三种情况讨论:

1. \([l, r]\)全在\(p\)的子树内,答案为所有点的\(LCA\)到\(p\)的距离.
2. \([l, r]\)有一部分在\(p\)的子树内,有一部分不在,答案为\(0\).
3. \([l, r]\)全不在\(p\)的子树内,答案为距离\(p\)最近的一个祖先的子树中有在\([l, r]\)的点到\(p\)的距离.但注意需要判断特殊情况.

区间\(LCA\)可以考虑求最小\(dfn\)对应的点和最大\(dfn\)对应的点的\(LCA\),这可以使用线段树维护.但因为选的点有限制,因此要用主席树.

这样做的复杂度为\(O(n \log ^ {2} n)\),但我似乎有一种\(O(n \log n)\)的算法.

考虑倍增的过程本质上是要找到一个深度最大的点,它既是\(p\)的祖先也是\([l, r]\)中某个点的祖先.根据\(dfn\)的性质,似乎可以在\(p\)的\(dfn\)左边和右边都找一个最近的\(dfn\),求它们的\(LCA\),取深度大的那一个,再特判一下特殊情况就行了.

[国家集训队] middle

题解

考虑二分中位数\(\geq mid\),使用经典套路,把\(\geq mid\)的设为\(1\),\(\leq mid\)的设为\(-1\),这个数是某段区间的中位数必须满足这段数的区间和\(\geq 0\).又由于题目要求强制在线,因此需要建\(n\)棵线段树.但又发现每次只改变一个数的值,因此可以放到主席树上.

P4891 序列

题解

相当于是要支持对\(B\)单点修改,对\(C\)区间赋值.

对于区间赋值操作,如果\(C _ \min \geq B_ \max\)直接对\(C\)赋值且不修改答案;如果\(v \leq B _ \min\)直接对\(C\)赋值且修改答案;如果不是这两种情况之一,需要暴力递归到子树内更新.

考虑分析这样做的复杂度.

设\(C _ i < B _ i\)的数量为势能.

每次单点修改最多使势能增加\(1\),而区间修改只会对\(C _ i < B _ i\)的情况暴力修改,所以总修改次数为\(O(n + q)\).

修改时需要使用快速幂,因此总复杂度为\(O(n \log ^ 2 n)\)(\(n\)与\(q\)同阶).

P6242 【模板】线段树 3

题解

对于区间取\(\min\)操作,维护区间最大值,区间严格次大值,如果\(v \geq\)最大值直接跳出;如果\(v >\)次大值调整最大值;如果\(v \leq\)次大值暴力递归.因此,这需要维护两套标记,一套是最大值的加法标记,一套是非最大值的加法标记.

题目中加了历史最大值的查询,因此还需要维护加法标记的累计,总共\(4\)套标记.

codeforces

CF1623D

题解

\[d _ i \text {第i次能清扫与第i - 1次能清扫之间走过的距离} \]

\[\begin {aligned} & ans = \sum _ {i = 1} ^ {+\infty} \frac {p} {100} (1 - \frac{p} {100}) ^ {i - 1} (\sum _ {j = 1} ^ {i} d _ j) \\ & (1 - \frac{p} {100}) ans = \sum _ {i = 1} ^ {+\infty} \frac {p} {100} (1 - \frac{p} {100}) ^ {i} (\sum _ {j = 1} ^ {i} d _ {j}) \\ & ans = \frac{p} {100} d _ {1} + \sum _ {i = 1} ^ {+\infty} \frac{p} {100} (1 - \frac{p} {100}) ^ {i} (\sum _ {j = 1} ^ {i + 1} d _ j) \\ & ans = d _ {1} + \sum _ {i = 1} ^ {+\infty} (1 - \frac{p} {100}) ^ {i} d _ {i + 1} \\ & = \sum _ {i = 1} ^ {+\infty} (1 - \frac{p} {100}) ^ {i - 1} d _ {i} \\ \end {aligned} \]

\[\text {令一个周期} D = \sum _ {i = 1} ^ {T} (1 - \frac{p} {100}) ^ {i - 1} d _ {i} \]

\[\begin {aligned} & ans = \sum _ {i = 1} ^ {+\infty} D (1 - \frac{p} {100}) ^ {T(i - 1)} \\ & = \frac{D (1 - (1 - \frac{p} {100}) ^ {+\infty})} {1 - (1 - \frac{p} {100}) ^ T} \\ & = \frac{\sum _ {i = 1} ^ {T} (1 - \frac{p} {100}) ^ {i - 1} d _ {i}} {1 - (1 - \frac{p} {100}) ^ T} \end {aligned} \]

CF1622F

题解

1. 先算几个\(n\)发现答案与\(n\)很接近.
2. 于是想办法推一下\(\prod _ {i = 1} ^ {n} i!\).
3. 发现剔除\(2\),\(\lfloor \frac {n} {2} \rfloor\),\(n\)一定合法.
4. 最后用异或\(\text {hash}\)解决.

总结

1. 构造题要学会猜结论.如,这道题不知道要去除哪些,可以假设都选,再调整.

2. 将\(1\)到\(n\)分解质因数可以\(O(n \log n)\)实现.

3. 解决组合问题时可以用异或\(\text {hash}\)确定是哪一种组合情况.

CF1620D

总结

这是一道构造题.

如果结论比较好想,可以直接用结论解决.

如果结论难想,可以适当的用暴力枚举.

比如,这道题很明显可以考虑枚举\(1\)和\(2\)的硬币的数量.

CF1627E

题解

首先可以发现每一层只需要在相邻的点之间连一条边权为\(x _ {i}\)的双向边就行了.

又因为点数是\(O(k)\),所以可以用最短路解决.

但有一个问题,图中有负权边,不能用\(dijkstra\),用\(spfa\)的话又会超时.

如果把一层看成一个整体的话是一张\(DAG\),因此可以考虑\(dp\).

CF1627F

题解

把格子的交点看成一张图.

跑一个关于点\((n / 2 + 1, n / 2 + 1)\)中心对称的最短路就行了.

CF1634D

题解

先考虑\(n = 4\)时怎么做.

发现可以用\(3\)次操作排除掉\(1\)个数.

接下来又是\(3\)个数,于是可以用同样的方法解决.

总结

构造题可以从小数据开始研究.

CF1634E

题解

有一个关键的性质:答案为YES当且仅当每种数字出现的次数都为偶数.

于是可以变成一张二分图,数组为一列点,每种数为一列点,数组向它有的数字连可重的双向边.

最后使用欧拉路径染色.

总结

新技能:

1. 欧拉路径.

这题没想到是因为没有发现"每种数字出现的次数都为偶数"这个性质.

CF1634F

题解

类比给一个区间加数时使用的差分,可扩展为给一个区间加上一个数列.

加数

\[f _ i = f _ {i - 1} \]

于是构造

\[d _ i = a _ i - a _ {i - 1} \]

同理,若

\[f _ i = f _ {i - 1} + f _ {i - 2} \]

可构造

\[d _ i = a _ i - a _ {i - 1} - a _ {i - 2} \]

于是可以解决这道题.

总结

新技能:

1. 区间加数列且数列的递推关系为线性,可使用差分解决.

CF739C

题解

本题的关键在于需要想到差分.

这样问题就转化为求一段形如\(+\cdots+-\cdots-\)的最大长度.

用线段树维护即可.

CF817F

题解

对\(l\),\(r\),\(r + 1\)离散化.

接下来,只需要维护一棵支持区间赋值和区间取反的线段树就行了.

注意,\(1\)也要加入数组中离散化,因为有可能\(l _ {\min} > 1\).

CF609F

题解

先将青蛙和蚊子的坐标离散化建出线段树.

线段树的叶子节点表示当前坐标能吃到它的青蛙的最小值.

青蛙舌头变长相当于区间取\(\min\).

对于那些吃不到的蚊子,把它们的坐标和编号放入一个\(multiset\)中,当青蛙舌头变长时取出来吃掉.

CF85D

题解

将序列\(a\)离散化建出线段树.

每个节点维护如下信息:

\(len\):当前子树的数的个数.

\(sum[0-4]\):模\(5\)余\(0 - 4\)的位置的和.

CF1070C

题解

如果本题需要支持区间查询,就变成了主席树裸题.

但本题连区间查询都不用,因此只使用权值线段树就行了.

CF1093E

题解

如果一个问题在全局能用某种树解决而区间却不能就可以考虑使用树套树.

令\(p _ i\)表示\(b _ i\)在\(a _ i\)中出现的位置.

如果没有特定区间的限制,只需要维护一个\(p _ i\)的权值线段树,每次区间查询\([l _ a, r _ a]\)中数的个数即可.

接下来思考,为什么不支持区间查询呢?

很明显,我们一棵线段树只能只能维护一段区间的信息,而我们需要有效的将查询区间进行划分,所以可以在外面套一棵位置线段树.

仔细想想还可以发现满足区间可减性,因此外面只需要套一个树状数组就行了.

总结

1. 这启示我对于支持区间查询的问题可以先考虑区间固定的情况怎么做.

CF1633E

题解

最小生成树边的选择只与边的相对大小关系有关.

将\(|w - q|\)表示成绝对值函数的形式.

从最左边开始扫描,可以发现每经过一个交点,相对大小关系发生一次改变,因此交点之间的相对大小关系不变.

所以最多有\(O(m ^ 2)\)种最小生成树.

预处理出所有的最小生成树,若记录边,查询的复杂度为\(O(qn)\).

再仔细观察绝对值函数可以发现,若把顶点加入交点中,查询复杂度可做到\(O(q\log m)\).

CF1633F

题解

新加入一个点可以想成是把这个点到根路径上的边取反.

这可以使用树链剖分维护,注意,树链剖分不要打成"强链剖分"了!

CF1632D

题解

考虑刚开始的时候有很多区间都不合法,显然每个区间只需要修改一个数就能做到合法.因此,可以贪心地加数.

设\(lst\)为上一个加数的位置,很明显以新加的一个数\(a _ i\)为结尾的区间的左端点不能达到\(lst\).

再思考一下可以发现,\(\gcd\)单减,区间长度单增,因此可以二分位置.

CF1632E1/E2

题解

很明显边一定是从\(1\)连出来的.

设新加的边的边权为\(w\),答案为\(x\).

深度为\([1,x + 1]\)的都可直接走到,因此要求的是深度为\((x + 1, n]\)的点的最大距离(不是直径).

设一个点的子树中的最大深度为\(mx _ 1\),次大深度为\(mx _ 2\),那么这个点对\([1,mx _ 2]\)的贡献就为\(mx _ 1\).

CF570D

题解

树上启发式合并维护每棵子树的字母种类.

总结

新知识点:

1. 树上启发式合并.

CF246E

题解

还是树上启发式合并.

对删除操作的理解:\(dfs\)的时候优先遍历轻儿子,删完后才遍历重儿子并加入重儿子的贡献,因此消除影响的时候可以直接清零.

CF679E

题解

记录每个点离最近的\(42\)的幂次的距离.

如果没有操作\(2\),修改的时候暴力修改是可以的,因为每个点最多修改\(\log\)次.

考虑如果加入操作\(2\)怎么做.

加入操作\(2\)后,增加了一个区间赋值操作.

区间加的时候如果有区间赋值标记,可以直接修改,否则进入子区间修改.

CF920F

题解

\(d(x)\)这个函数减少的速度很快,当减少到一定数的时候就不会减少了.

因此可以暴力修改,时间复杂度为\(O(n \log n)\).

CF1070F

题解

首先,"1 1"的情况肯定可以随便选,选了一个"1 0"就必选一个"0 1",剩下的必然是"0 0"和"0 1"或"0 0"和"1 0".

考虑选一些"0 1""1 0"这样的数对是否对"0 0"是否有影响,假设选了\(n\)个"1 1",又选了\(k\)个"1 0""0 1"对.

此时为\(\frac{n + k}{n + 2k}\),还能选\(n\)个"0 0".也就是说,选多少个"1 0"和"0 1"对后面的选择无影响,因此可以直接贪心选取.

CF1070G

题解

贪心策略如下:从集结点往两边扩展,能走到集结点的就直接加入,否则最后才加入.

CF1637B

题解

先假设一个长度为\(n\)的字段我们分成了\(n\)段.

它能产生的\(mex\)的贡献只能是\(1\).

要想产生\(2\)的贡献,至少合并一次,但这又会使得段数减少\(1\).

因此答案为\(n\)加区间\(0\)的个数.

CF1637D

题解

很明显需要把括号拆开,拆开后可以发现只需要计算\(\sum _ {i = 1} ^ {n} x _ {i} \sum _ {i = 1} ^ {i - 1} x _ j\)就行了.

又发现\(x _ i\)的值域为很小,因此可以直接\(dp\).

CF1638D

题解

考虑倒着做.如果有合法的方案,那么最后一步一定是选择一个四块相同的位置.选择一块位置之后,把这些位置的颜色染成\(0\),表示可以任意选颜色,这是一个\(BFS\)的过程.

CF1638E

题解

好题,应该是一道势能分析的线段树题.

因为加是全局的,所以可以维护一个全局加的标记\(tag _ x\),表示第\(x\)种颜色加了多少.

考虑区间改颜色的操作,先考虑这段区间的颜色都相等,维护一个\(sum _ x\),若颜色从\(c _ 1\)改成了\(c _ 2\),那么\(sum _ x = sum _ x + tag _ {c _ 1} - tag _ {c _ 2}\),查询答案的时候返回\(sum _ x + tag _ {col _ x}\)即可.

于是在线段树上暴力更新即可,可以通过对相同颜色的连续段势能分析证明这样做的复杂度为\(O(q \log n)\).

CF1290E

题解

根据笛卡尔树的性质,一个节点\(i\)包含的是一个极大的区间\([l, r]\),满足这个区间内的数的\(val\)都\(< val _ i\).

因此动态加数,维护每个数左边第一个比它大的位置\(l _ i\),右边第一个比它大的位置\(r _ i\).

先考虑维护\(r _ i\),\(l _ i\)同理.

发现需要支持区间取\(\min\),区间加,单点改.

使用线段树维护即可.

CF1194G

题解

这道题需要使用数位\(dp\).相当于是求满足\(Cx = Cy(Cx, Cy \leq n)\)的数满足一定限制的个数.

限制那一维可以状压,并不是这道题的关键.

本题的问题在于如何设计状态使之满足\(Cx = Cy(Cx, Cy \leq n)\)这个等式.

问题可以转化为在\(x, y\)固定的情况下有多少个\(C\)满足\(Cx \leq n 且 Cy \leq n\).

考虑从低位到高位做,每次枚举\(C\)在这一位填什么数,这会使得它进位,处理一下进位情况即可.

总结

数位\(dp\)不但可以从高位到低位枚举,也可以从低位到高位枚举.

只需记录状态\(exist\)表示从当前位开始到高位是否需要一位不填满即可.

这道题没有想出来的原因就在于只会从高位到低位的数位\(dp\),但这道题如果从高位开始做并不好做,因为进位是从低位转移到高位.

新技能:

1. 从低位开始枚举的数位\(dp\).

CF1644F

首先,如果只有\(G\)操作,只需要求\(\sum _ {i = 0} ^ {\min(n, k)} \begin{Bmatrix} n \\ i\end{Bmatrix}\)即可.

如果有\(F\)操作,只需要枚举复制的次数\(k\),容斥一下就行了,容斥系数为\(\mu\).

atcoder

ARC 134C

题解

可以先将编号为\(2 - n\)的球一次放入\(k\)个盒子中(可空),使用插板法就是\(\prod _ {i = 2} ^ {n} \binom{a _ i + k - 1}{k - 1}\).

再将编号为\(1\)的球放入\(k\)个盒子中(非空),使用插板法是\(\binom{a _ 1 - 1}{k - 1}\).

ARC 134D

题解

设第一关键字为\(a _ i\),第二关键字为\(b _ i\).

刚开始一定选\(a _ i\)最小的数.

若\(a _ i\)最小的数中存在\(a _ j \geq b _ j\),那么答案就是\(a _ j\ b _ j\).

否则,所有的\(a _ i\)最小的数都满足\(a _ i < b _ i\),按顺序输出即可.

再对\(a _ i > mina\),\(a _ i < b _ {ans _ 1}\)的数按第一关键字排序,按顺序输出即可.

但是,还要注意一下\(a _ i = b _ {ans _ 1}\)的情况(就是因为这种情况没过),需要\(b _ i < b _ {ans _ t}\)才可输出.

其中,\(b _ {ans _ t}\)是第一个不等于\(b _ {ans _ 1}\)的数.

ARC 134E

题解

分类讨论题.

先手必败:数字均为\(0\)或\(1\).

先手必胜:

1. 最大的数为0.
2. 至少有一个奇数.
3. 没有奇数且存在除以\(4\)的余数为\(2\).

接下来讨论所有数字均为\(4\)的倍数的情况:

1. 若存在数字不被\(3\)整除,除了\(\{4, 8\}\),先手必胜.因为如果余数相同,选择\(3\)取余就可转化为先手必败的局面;如果余数不同,选择\(12\)就可转化为\(\{4, 8\}\).
2. 若数字均为\(12\)的倍数,可以\(2 ^ {\lfloor\frac{200}{12}\rfloor}\)枚举每种数字是否存在,暴力检验即可.

最后设\(dp _ {i, S}\)表示前\(i\)个数中,\(12\)的选择情况为\(S\)的方案数.

\[dp _ {i, S} \longrightarrow dp _ {i + 1, T} \]

即考虑每个位置选择哪个\(12\)的倍数.

ARC 133B

题解

可以每个\(a\)向它能匹配的\(b\)连边,问题就转化为求最多的边使之不相交.

这是一个二维偏序问题,可以使用树状数组维护.

ARC 133C

题解

需要发现性质才能解决这道题.

若有解,则必须满足\(\sum _ {i = 1} ^ {n} A _ i \equiv \sum _ {i = 1} ^ {m} B _ i mod\ K\).

先考虑所有格子都选\(K - 1\),那么可以算出一个使每行,每列满足要求的需要减少的最小值.

最后减去行要减去的和与列要减去的和的最小值.

ARC 133D

题解

前缀异或和满足如下性质:

\[sum _ {4i} = 4i \]

\[sum _ {4i + 1} = 1 \]

\[sum _ {4i + 2} = 4i + 3 \]

\[sum _ {4i + 3} = 0 \]

这样原问题可转化为在\(i \leq L,j \leq R\)中选择两个\(sum\),使\(sum _ i \bigoplus sum _ j = V\),记这个答案为\(solve(L, R)\).

最后的答案可以用\(solve(R, R) + solve(L - 1, L - 1) - 2 \times solve(L - 1, R)\)容斥计算.

考虑如何求\(solve(L, R)\).

分类讨论即可,重点在于如何求\(4i + 3\)和\(4i\)组合起来的贡献.

发现二进制下最后两位异或起来要么是\(1\)要么是\(3\),而高位需满足异或起来和\(V\)相等,因此可以数位\(dp\).

总结

新技能:

1. 前缀异或和的性质.

ARC 070B

考虑什么样的数可以成为可有可无的数.

一个数\(a[i]\)是可有可无的数必须满足对任意的包含\(a[i]\)的选法,和要么小于\(k\),要么大于等于\(k+a[i]\).

即当存在一种选法的和\(\geq k\)且\(< k + a[i]\)时\(a[i]\)就不是可有可无的数.

也就是说,我们可以仿照倍增的方式从大到小枚举数,使它们尽量凑成小于\(k+a[i]\)的数.

对每个\(a[i]\)都这样判断就行了.

ARC 098D

考虑把减数换成加数.

令\(c[i] = \max(0, a[i] - b[i])\),想当于进入一个点至少需要\(c[i]\)元,可以获得\(b[i]\)元.

可以按\(c[i]\)从大到小建出一棵重构树.

一个点的子树表示这个点只走比它小的点能走到的所有点.

等价于,如果能走到这个点,就能走到它子树内的所有点.

于是,令\(f[i]\)表示走到\(i\)的最小初始钱数,对它进行\(dp\)即可.

ARC 097C

设状态\(dp _ {i, j}\)表示放前\(i\)个白球,前\(j\)个黑球的最小代价.

\[dp _ {i, j} = \min \{ dp _ {i - 1, j} + costw _ {i - 1, j}, dp _ {i, j - 1} + costb _ {i, j - 1} \} \]

其中,\(costw _ {i, j}\)表示已经放了\(i\)个白球,\(j\)个黑球,再放一个白球在这\(i + j\)个球的末尾的最小代价,\(costb\)同理.

考虑\(cost\)怎么转移,以\(costw\)为例.

\[costw _ {i, j} = cost _ {i, j - 1} + posb _ {j} > posw _ {i + 1} \]

其中,\(posw _ i,posb _ i\)分别表示第\(i\)个白球/黑球的位置.

这使我对动态规划的无后效性有了新的理解,动态规划必须从子问题转移过来.而什么是子问题呢?必须与后面的元素没有任何关系.例如这道题当我们考虑\(dp _ {i, j}\)时,需要把后面的所有元素"删掉",即假设只有前\(i\)个白球和前\(j\)个黑球,考虑\(costw _ {i, j}\)时同理.这能帮助我们更好的理解动态规划的转移本质.

ARC 095D

一道构造题.

先考虑已知\(p _ i\)时怎么做.

把\(p\)从小到大排序,从小到大枚举权值\(i\),每个\(i\)都向它左边的点的编号的最大值连边.

然后就发现树的形态是一个毛毛虫.

于是把树的直径求出来,查看非直径上的点的度数是不是都为\(1\),如果存在大于\(1\)的,则判定无解.

考虑如何构造.

每个直径上的点的权值一定比它连向的非直径上的点的权值小,编号一定比它们大.

假设前面染了\(s\)个,当前点有\(d\)个它连向的非直径上的点,则它的权值按权值依次增大,编号依次减小的顺序赋值.

ARC138D

构造一个长度为\(2^n\)的数列,包含数字\(0\)到\(2^n-1\),使得相邻两个数字的异或和为\(k\).

找到所有\(popcount\)等于\(k\)的数字构成的集合\(b\),假设当前数字为\(a\),那么下一个数字就为\(a\oplus b_i\),其中\(a\oplus b_i\)没有在之前出现过.

考虑为什么这样做是对的,相邻两个数字的和一定是\(a\oplus b_i\oplus a=b_i\),\(b_i\)的\(popcount\)等于\(k\),所以一定是对的.

UVA

UVA11542 Square

https://www.luogu.com.cn/problem/UVA11542

题解

把异或转化为加和乘,用高斯消元解决.

总结

在一个只有\(0\)和\(1\)的系统中,即模\(2\)意义下,有

\[a \bigoplus b \Longleftrightarrow a + b \]

\[a \bigwedge b \Longleftrightarrow a \times b \]

\[a \bigvee b \Longleftrightarrow a \times b + a + b \]

标签：知识点,记录,省选,题解,sum,区间,可以,线段,dp
From： https://www.cnblogs.com/yanchengzhi/p/17002010.html