补图(bzoj1098)
题解:
在原图中相连的两个点在补图中必然不相连 在补图中相连的点在原图中必然不会相连 所以我们考虑对于每个点做BFS 去查询其补图中联通块的大小 具体来说就是对于每个点去扩展其原图中没有连边的点并且这个点也没有被选入到补图 那么这个点与当前这个点必然在一个联通块里面 然后就能维护出补图联通块的
...
P4770(SAM+主席树+倍增)
题意:给定一个母串,$q$次查询每个串的本质不同子串在原串对应的$[l,r]$子串中不出现的个数
题解:感觉非常坑人的是
并没有从题目中看出 需要满足查询串的本质不同的情况
那么对于不用考虑查询串的本质不同的话 那么就直接 对于每个询问串在原串的sam上跑一遍 通过倍增统计答案即可
现在需要求本质不
...
动态DP
前言动态DP????
难道是传说中会动的DP??? 但是据我们所知DP状态都定了 还能改变吗???
动态DP:就是DP上进行一些单点修改操作
参考博客
需要相应较强的数据结构的前置知识点和普通的DP能力(因为你发现整个过程都是再用一些数据结构在维护)
例题SP1716 GSS3 - Can you
...
圆方树入门
前言刚仙人掌入门….
对于一类点双问题 我们可以采用圆方树解决
大致做法就是点双缩环 变成树形结构 从而解决树形问题
例题P4630 APIO2018 铁人两项题意:统计有多少个三元组$(s,c,f)$ 满足从$s->c$和$c->f$的路径不相交
题解:首先我们可以确定的是 在同一个点
...
静态仙人掌
前言圆方树是一种数据结构 用来解决静态仙人掌问题
这个东西原始的出处应该是paper《Maintaining bridge-connected and biconnected components on-line》
仙人掌的正经定义是: 无向图中每条边至多在一个简单环上
而圆方树是通过点双性质,将
...
仙人掌图的判定
Posted on
| In
图论
无向图上仙人掌图的判定例题洛谷P4129
通过$tarjan$ 求出所有的点双分量
根据仙人掌图的性质 我们对于包含非树边的点双分量 判断是否是简单环即可(通过判环的点数是否等于边数)
注意仙人掌图的前提 图是联通的
然后注意这题 统计答案会很大 所以需要写高精度(黄大佬的高精板子真的快啊)
复杂度
...
cf504E(树链剖分+SA)
题意给你一颗$n$个节点的树 每个节点上都有一个字符$c$ q次查询两条路径形成的字符串的最长公共前缀
题解比较直观的做法是
树链剖分 每个点对对应$logn$个区间 然后二分答案 用$hash$取$check$
复杂度$O(qlog^2n)$ 不能通过
我们考虑对两段路径的$logn$个区间 类似
...
cf1037H
题意给定一个串$S$ $q$次查询在S[l,r]中字典序比询问串大的字典序最小的那个
题解这题有两个版本的写法
SAM考虑对原串建SAM 用线段树合并维护每个节点上$Right$集合
对于每次查询
从前往后对于每个位置找到恰好比当前前缀字典序大的 并满足区间范围的位置
然后输出即可
复杂度$O(26
...
cf547E(SAM+dfs序+主席树)
题意给定$n$个串 $q$次查询
每次查询$(l,r,k)$ 表示下标为$k$的串在下标为$[l,r]$的串中出现的次数的和
题解我们考虑建广义的SAM
这样所有串的情况都可以在一颗后缀树上表示
对于每个串我们找到他的最佳匹配位置
问题转化为 对于查询 我们在他最佳匹配位置的子树中统计节点的权值
...
cf961F(hash+线段树+二分)
题意给定一个字符串$T$
求前$\lceil \frac{|T|}{2} \rceil$ 个位置与其关于对称轴对应位置形成的串 在满足以下条件下的最长前缀
前缀的长度小于串长
前缀长度为奇数
在是前缀的同时也是串的后缀
题解在考虑没有长度是奇数限制的情况下 直接对每个串做二分 $hash$来$c
...