• .Title|raw

    CodeForces 710F. String Set Queries 模拟二进制堆启发式合并的AC自动机合并


    题目大意维护一个集合支持: 1." data-mce-tabindex="0">1.1. 添加一个模式串。 2." data-mce-tabindex="0">2.2. 删除一个串。 3." data-mce-tabindex="0">3.3. 给出一个串,询问有多少个子串在集合中出现过,多次出现多次计算。 题目要求使用fflush(stdout)方法强制在线。 题解更新了AC自动机内存池回收写法的模板。 多模式串匹配算法,明显的AC自动机的题目。 但是众所周知,AC自动机不支持动态的插入操作以及删除操作(Trie树是支持动态插入的,但是AC自动

  • .Title|raw

    CodeForces - 1055F Tree and XOR 01-Trie


    题目大意有n个节点的有根树,根为1,每条边有权值,点对(u,v)的路径长度为从u到v路径上所有权值的异或值,认为点对(u,v)与(v,u)表示两个路径,总共有n2个点对路径(自己到自己也算一个),求问其中路径长度第k小的路径长为多少。 题解n的范围是很大的,不可能通过枚举计算。 两点(u,v)之间的路径长度,可以通过lca转化为: (u,lca) xor (v,lca) = (u,lca) xor (lca,root) xor(lca,root) xor (v,lca) = (u,root) xor (v,root); 所以可以将每个点到根节点的路径异或长度预处理出来,之后再进行下面的操作。

  • .Title|raw

    CodeForces - 484E Sign on Fence 二分+主席树


    Input5 1 2 2 3 3 3 2 5 3 2 5 2 1 5 5Output2 3 1题目大意给出一个序列,有m组询问。 每一组询问有三个参数l,r,w,问区间[l,r]中所有由连续w个元素组成的子序列中的最小值中的最大值是多少。 题解看到题目里面的最小值最大,肯定能意识到应该是用二分+check去验证元素的(因为其他能想到的方法基本都是暴力,复杂度太高,这题数据范围在105级别没法用的)。 然后问题就在于这个check如何去操作。 如果我们当前二分一个值mid,怎么检查区间l-r中是否所有的连续的w个元素中的最小值中的最大值是mid呢? 这个没法做到,我们只能去确定,是否存在连续w的

  • .Title|raw

    51Nod 1601 完全图的最小生成树计数 kruskal + trie异或运算贪心


    题解每条边的权值都是根据每个点的定值通过二进制异或得出的。 如果有两个点的数二进制高k位相等,那么我们如果要想要把这两个点的边加入最小生成树,那么花费的代价是与高k位无关的。 假设在第k+1位发生分歧,则这条边的最小权值即为这一位对应的二进制值。然后要做的就是继续向更低位检查。 这明显是个递归过程,而且很容易能想到这个过程是与01Trie的节点访问实际上是一样的。 于是所有的答案统计全部都在01trie上。 接下来看kruskal算法的核心:每一次将最小边权的边试图加入最小生成森林。 所以我们必然优先去找01Trie中同一个叶子节点上的点对的边。 假如一个叶节点上有k个点(k > 2),

  • .Title|raw

    luogu P4178 Tree 点分治+树状数组


    题解树上点对距离问题,非常经典的点分治问题。 点分治的基本思路: 对于当前的树(子树),求出其重心,统计过重心的合法路径数,然后以重心为分隔点,分别递归对删除该重心后的子树进行求解(继续求重心、统计,再进行递归)。 重心的概念:若一个点为树的重心,那么其作为根的时候,其子树的大小的最大值最小。 重心的性质:重心分割出的子树的大小不会超过now_n/2,可以用来证明其时间复杂度为O(logn * 统计的时间)。 此题要求距离小于等于k的路径数目,如果把每一种都算出来累加复杂度是相当高的。 可以使用树状数组,不过要注意树状数组的0号位对答案是不会造成任何影响的,所以在统计入树状数组的时候要稍微处理

icontofig | 发布于 2020-02-12 22:36:15 | 阅读量 273 | 字符串
发布于 2020-02-12 22:36:15 | 字符串

题目大意

维护一个集合支持:

1.1. 添加一个模式串。

2.2. 删除一个串。

3.3. 给出一个串,询问有多少个子串在集合中出现过,多次出现多次计算。

题目要求使用fflush(stdout)方法强制在线。

题解

更新了AC自动机内存池回收写法的模板。

多模式串匹配算法,明显的AC自动机的题目。

但是众所周知,AC自动机不支持动态的插入操作以及删除操作(Trie树是支持动态插入的,但是AC自动机里面的fail指针是不支持的,插入字符串只能重新暴力重构fail指针)。

于是考虑建立多个AC自动机,但是很遗憾的是,如果每一次添加or删除操作我们都去建立一个AC自动机,那么查询的时候时间复杂度会炸掉,但是多个AC自动机的做法又不可避免。

所以我们就要想如何优化。

首先将插入和删除分开建AC自动机组是没有任何异议的。最终答案就是在插入的AC自动机组中的答案减去在删除的AC自动机组中的答案。

根据二进制加法(二进制堆的启发式合并)的启发,我们对属于同一种操作的AC自动机进行二进制分组。

我们在动态维护该种操作的时候,将新来的模式串新建一个AC自动机,并设置其数量为1,表示该AC自动机中带有的模式串的数量。

当当前的AC自动机中的模式串数量和前一个AC自动机中模式串数量相等的时候,我们就将两个AC自动机暴力合并。

能证明这样每个字符串最多被加入AC自动机并重构fail的次数在log2n次。

每次查询的时候,只需要将某种操作的AC自动机组中的全体AC自动机全部扫一遍就行了。

注意合并的时候回收空间。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
typedef long long ll;
int st[maxn<<1];
int cnt;
struct trie_node{
    int next[26],fail,end,sum,ac[26];
}tr[maxn<<1];
struct AC_auto{
    int root;
    inline int newnode(){
        int p = st[cnt];
        for(in
继续阅读
icontofig | 发布于 2020-02-11 17:05:57 | 阅读量 313 | Trie
发布于 2020-02-11 17:05:57 | Trie

题目大意

有n个节点的有根树,根为1,每条边有权值,点对(u,v)的路径长度为从u到v路径上所有权值的异或值,认为点对(u,v)与(v,u)表示两个路径,总共有n2个点对路径(自己到自己也算一个),求问其中路径长度第k小的路径长为多少。

题解

n的范围是很大的,不可能通过枚举计算。

两点(u,v)之间的路径长度,可以通过lca转化为:

(u,lca) xor (v,lca) = (u,lca) xor (lca,root) xor(lca,root) xor (v,lca) = (u,root) xor (v,root);

所以可以将每个点到根节点的路径异或长度预处理出来,之后再进行下面的操作。

建立一个01Trie,我们可以有办法求得路径异或长度不超过某个值val的路径数目。

对于当前位bit,我们去检查小于之前已经决定的答案ans加1<<bit的值的个数。也即当前的二进制位上的数为0的个数。

如果这个个数size小于k,说明答案应该是大于等于ans + (1<<bit)的,于是就决定当前的二进制位为1,k -= size,进入当前层表示为1的子树内再向下搜寻。

否则就直接进入当前层表示为0的子树内再向下搜寻。

整个搜寻答案的过程是O(62·n)的。加二分实际上是没意义的。

最后的一个问题就是,空间明显不允许我们开这样一个完整的Trie,所以需要动态建立每一层的Trie节点,用到什么建什么,不用的不管,搜寻下一层的时候要将上一层的节点表示清空。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll k;
int id;
const int maxn = 1e6+5;
ll v[maxn];
int pre[maxn];
int tot = 0;
ll siz[maxn];
int son[maxn][2];
int a[maxn],b[maxn];
void init(){
    for(int i = 1;i <= n;++i)
        son[i][0] = son[i][1] = 0,siz[i] = 0;
    tot = 0;
}
int new_tag(int now,int ch){
    if(!son[now][ch])
        son[now]
继续阅读
icontofig | 发布于 2020-02-10 23:17:59 | 阅读量 221 | 二分 可持久化线段树 可持久化数据结构
发布于 2020-02-10 23:17:59 | 二分 可持久化线段树 可持久化数据结构

Input

5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5

Output

2
3
1

题目大意

给出一个序列,有m组询问。

每一组询问有三个参数l,r,w,问区间[l,r]中所有由连续w个元素组成的子序列中的最小值中的最大值是多少。

题解

看到题目里面的最小值最大,肯定能意识到应该是用二分+check去验证元素的(因为其他能想到的方法基本都是暴力,复杂度太高,这题数据范围在105级别没法用的)。

然后问题就在于这个check如何去操作。

如果我们当前二分一个值mid,怎么检查区间l-r中是否所有的连续的w个元素中的最小值中的最大值是mid呢?

这个没法做到,我们只能去确定,是否存在连续w的区间的数全部大于等于mid。

我们假设当前二分到的值为mid,大于等于mid的数都设为1,小于mid的数都设为0,那么问题就变成了询问区间内[l,r]上最长的连续为1的子序列长度len是否大于w的问题。

但是我们注意到一些问题,序列中的数比较大,直接二分的话常数会大些,而且也没有办法对每次二分的mid建一棵线段树去check,时间上会炸掉。

这种情况下我们可以考虑将序列中的值从大到小排序,保留其原先所在的位置下标,对排完序之后的值,我们可以直接用序列进行二分。

而在排完序的情况下,可以注意到,以当前位置的值为check的值时,其构建的线段树就是上一个位置对应的check所用的线段树上在当前位置的值在原序列中的下标对应的位置插入1。

这个修改只有一次,因此可以建立可持久化线段树进行check。

当前二分的位置为mid时,对root[mid]对应的线段树进行check,检索是否可行就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n,q;
struct height{
    int h;
    int id;
}a[maxn];
int rt[maxn];
int u,v;
const int INF = 1e9+7;
struct tree{
    int l,r;
    int lc,rc;
    int suml,sumr,sum,len;
}tr[maxn*25];
int cnt = 0;
void push_up(int now){
    tr[now].len = t
继续阅读
icontofig | 发布于 2020-02-06 20:52:24 | 阅读量 299 | 最小生成树 Trie
发布于 2020-02-06 20:52:24 | 最小生成树 Trie

题解

每条边的权值都是根据每个点的定值通过二进制异或得出的。

如果有两个点的数二进制高k位相等,那么我们如果要想要把这两个点的边加入最小生成树,那么花费的代价是与高k位无关的。

假设在第k+1位发生分歧,则这条边的最小权值即为这一位对应的二进制值。然后要做的就是继续向更低位检查。

这明显是个递归过程,而且很容易能想到这个过程是与01Trie的节点访问实际上是一样的。

于是所有的答案统计全部都在01trie上。

接下来看kruskal算法的核心:每一次将最小边权的边试图加入最小生成森林。

所以我们必然优先去找01Trie中同一个叶子节点上的点对的边。

假如一个叶节点上有k个点(k > 2),那么对应的建边方案就是kk-2种。

当从叶节点向上走的时候,假设某节点的父亲节点的两个子树上都有点存在(即两个子树都非空),那么我们肯定要用边把这两个子树连起来,连起来的时候就需要顺着trie往下找异或值最小的边的权值是多少。

细节不是很好解释,不过这种思路是二进制异或时一种常见的贪心思路,可以看代码理解一下。

这个题不需要并查集,因为当刚向上走到某个点时,如果其两个子树都非空,那么这两个子树代表的两个已经构建好的生成树必然属于两个不同的连通块。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PI;
const int maxn = 1e5+5;
const int INF = 2e9;
const ll MOD = 1e9+7;
int n, sz, fac[35], rt;
ll ans,sum;
struct tree{
    int l, r, cnt;
} tr[maxn*30];
ll quick_pow(ll x, ll y){
    ll ans = 1;
    while (y){
        if (y & 1)
            ans = ans * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return ans;
}
void insert(int &d, int dep, int v){
    if (!d)
        d = ++sz;
继续阅读
icontofig | 发布于 2020-02-03 23:19:32 | 阅读量 333 | 点分治 树状数组
发布于 2020-02-03 23:19:32 | 点分治 树状数组

题解

树上点对距离问题,非常经典的点分治问题。

点分治的基本思路:

对于当前的树(子树),求出其重心,统计过重心的合法路径数,然后以重心为分隔点,分别递归对删除该重心后的子树进行求解(继续求重心、统计,再进行递归)。

重心的概念:若一个点为树的重心,那么其作为根的时候,其子树的大小的最大值最小。

重心的性质:重心分割出的子树的大小不会超过now_n/2,可以用来证明其时间复杂度为O(logn * 统计的时间)。

此题要求距离小于等于k的路径数目,如果把每一种都算出来累加复杂度是相当高的。

可以使用树状数组,不过要注意树状数组的0号位对答案是不会造成任何影响的,所以在统计入树状数组的时候要稍微处理一下。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct edge{
    int to,next,val;
}e[maxn<<1];
int siz[maxn],mx[maxn],vis[maxn],dis[maxn];
int c[maxn*100],tmp[maxn];
int n,rt;
int h[maxn];
int lowbit(int x){
    return x & -x;
}
void update(int now,int d){
    while(now <= n * 100 - 2){
        c[now] += d;
        now += lowbit(now);
    }
    return;
}
int query(int now){
    int ret = 0;
    while(now > 0){
        ret += c[now];
        now -= lowbit(now);
    }
    return ret;
}
int cnt = 0,num = 0,sum = 0;
void add(int u,int v,int d){
    e[cnt].to = v;e[cnt].val = d;e[cnt].next = h[u];h[u] = cnt++;
    return;
}
void get_root(int now,int fa){
    siz[now] = 1;mx[n
继续阅读
icontofig | 发布于 2020-01-27 16:34:36 | 阅读量 588 | 字符串
发布于 2020-01-27 16:34:36 | 字符串
#include <bits/stdc++.h>
const int maxn = 2e5 + 5;
using namespace std;
struct Trie{
    int nex[maxn][26], fail[maxn], end[maxn];
    int root, p;
    inline int newnode() {
        for (int i = 0; i < 26; ++i) {
            nex[p][i] = -1;
        }
        end[p++] = 0;
        return p - 1;
    }
    inline void init() {
    	p = 0;
    	root = newnode();
    }
    inline void insert(char *buf) {
        int now = root;
        for (int i = 0; buf[i]; ++i) {
            if (nex[now][buf[i]-'a'] == -1) 
                nex[now][buf[i]-'a'] = newnode();
            now = nex[now][buf[i]-'a'];
        }
        end[now]++;
    } 
    inline void build() {
        queue<int> que;
        fail[root] = root;
        for (int i = 0; i < 26; ++i) {
            if (nex[root][i] == -1)
                nex[root][i] = root;
            else {
                fail[nex[root][i]] = root;
                que.push(nex[root][i]);
            }
        }
        while (!que.empty()) {
            int
继续阅读
icontofig | 发布于 2020-01-15 19:57:24 | 阅读量 884 | 思维题 树状数组
发布于 2020-01-15 19:57:24 | 思维题 树状数组

题目大意

一开始有一个初始顺序的排列[1,n],一共有m次操作,每次将数ai从序列中取出,放到最开头的位置生成一个新的排列。

求问在所有过程中每一个数最小的下标位置和最大的下标位置。

题解

最小的下标位置是非常容易求得的,这很明显,因为如果从来没有被放到开头,那么答案一定是i,否则答案就是1。

需要思考的点在于求最大的下标位置。

这个数据范围不允许进行模拟,链表也不行(链表的单个操作、查询效率极差)。

先来考虑一种特殊情况1:

假设当前所有的数字都已经被放置到第一位过了,在满足这种条件后的最大的下标位置怎么求。

明显元素之间一开始的位置在哪里已经完全互不影响了。

如果一个数再被要求放到第一位,那么这个操作之前的下标位置可能就会影响答案。

而这个下标位置是什么?我们想什么样的操作会影响这个下标位置。很明显只有在上一次此数被放到第一位的时间之后,不同的数字放置到第一位才会使得这个数字的位置向后推移。也就是说,这个下标位置,就是当前未操作时刻和上一次这个数被放到第一位以后的时刻,这之间的不同数字的个数再+1,也就是区间内不同数的个数。

树状数组可以离线询问区间内不同数的个数。由于这道题的特殊性,我们无需对询问区间进行右端点优先排序,直接操作查询即可。

然后再考虑剩下的情况2:

如果一个数之前没有被放置在第一位的经历该如何计算?

这样在它被第一次放置到第一位的命令执行以前,其最大下标位置是之前的时刻被放置在第一位的大于此数的数字的个数 + 此数最初的坐标值。问题变成了维护区间内出现的不同数字的个数,需要用另外一个树状数组进行维护,只需要再每个数字第一次被放置在第一位时维护一次,查询一次即可。

在问题的最后,这样不一定已经求得最大值,因为对于每一个数字,最后可能有影响到最大值的问题但是没有查询更新。

所以在最后我们就要:

对于在操作序列中出现过的数字,我们执行情况1的查询一次。

对于未在操作序列中出现过的数字,我们执行情况2的查询一次。

代码

#include <bits/stdc++.h>
const int maxn = 3e5+5;
using namespace std;
map<int,int>mp;
int tr[maxn],a[maxn],ans[maxn],c[maxn];
int n,m;
int lowbit(int x){
	return x & (-x);
}
void add(int x,i
继续阅读
icontofig | 发布于 2020-01-14 18:21:16 | 阅读量 727 | DP 字符串
发布于 2020-01-14 18:21:16 | DP 字符串

题目大意

给出n个模式串和一个匹配串,求问最少要修改匹配串中多少个字符才能使得匹配串中不含有任意一个模式串。

题解

多个模式串一定要用AC自动机的

所以首先把AC自动机给建出来

然后在AC自动机上跑DP,dp[i][j]表示当前匹配到长度为i,在AC自动机的Trie树上走到节点j的状态下的所需要修改的字符数量的最小值。

要注意不能走到模式串结尾的节点上。

在转移的时候,从当前状态向其子节点转移(前提是子节点非模式串结束的位置对应的节点),如果转移的节点的字符与字符串下一个字符相同,那么下一个状态的dp值继承当前状态dp值,代表不修改下一个字符的情况;否则下一个状态的dp值要在当前状态的dp值的基础上+1,表示修改下一个字符。

最后对dp[len][i]的所有值取min,即为最终答案。

(做这个题主要是为了写一遍AC自动机的板子)

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int INF = (1<<30)-1;
struct AC_auto{
    int next[4];
    bool flag;
    int fail;
}tr[maxn];
int root;
int index = 0;
int newnode(bool f){
    tr[index].flag = f;
    tr[index].fail = 0;
    for(int i = 0;i < 4;++i){
        tr[index].next[i] = 0;
    }
    return index++;
}
int n;
char ss[maxn];
int change(char c){
    switch(c){
        case 'A' : return 0;break;
        case 'T' : return 1;break;
        case 'G' : return 2;break;
        default : return 3;break;
    }
    return 0;
}
void build(char *s){
    int now = root;
    int len = strlen(s);
  
继续阅读
icontofig | 发布于 2019-12-22 13:56:06 | 阅读量 305 | 思维题
发布于 2019-12-22 13:56:06 | 思维题

题目大意

给一个不完整的棋盘,每一列的方格数单调非升,问最多可以用多少个不重叠的1x2或者2x1的矩形覆盖棋盘(可以不完全覆盖)

题解

说实话思路比较巧妙

这种问题可以看成二分图匹配,相邻格子染色不同,假设分别染成黑白两种颜色,那么很明显想要用一个矩形覆盖,就必须要有一个黑格和一个白格匹配(两者相邻)。最大匹配数就是最终的答案。

但是这个数据范围过大,不能用匈牙利或者网络流解决。

注意到棋盘每一列的方格数是单调非升的,于是很明显只要先进行染色处理,然后从黑白格子中选出数量最少的那一种,其个数就是最大匹配数。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
int n;
long long ans;
long long a[maxn];
long long black,white;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> a[i];
        if(i & 1){
            black += a[i] / 2;
            white += (a[i] + 1) / 2;
        }
        else{
            black += (a[i] + 1) / 2;
            white += a[i] / 2;
        }
    }
    ans = min(black,white);
    cout << ans << endl;
    return 0;
}


继续阅读
icontofig | 发布于 2019-12-10 20:04:25 | 阅读量 566 | 并查集
发布于 2019-12-10 20:04:25 | 并查集

图的连通性问题 : 并查集的基础应用

提出背景

在图论问题中,我们经常性遇到一些关于两个点是否连通的问题。
比如在最小生成树kruskal算法中,我们在逐渐选取最小边的时候,我们需要判断当前要选的边的两个顶点是否已经在同一连通块中。
有基础的同学都知道,在大多数图论问题中,我们的图都是通过邻接表或点对表示边而非邻接矩阵存储的,这样能够提高遍历和存储的时间和空间效率。但实际上,这两种方式也有一个严重的缺陷:不方便查询、修改指定的两点u和v的关系。于是在这种情况下的这两种方式构成的图的连通性也非常难以判断。
这时我们需要一种数据结构能够方便的维护查询图的连通性。

并查集基本概念及操作介绍

所谓并查集,其实是相互连通的各点通过父节点表示法构成的森林(很多棵树的集合),我们判断两点是否相互连通,实际上就是通过他们是否在同一棵树内。很显然同一棵树内的所有点相互连通,这个通过刚才的定义就可以显然得出了,并不需要证明(实际上这里给出的定义是我个人对并查集的理解)。
由上面所说的父节点表示法,并查集这种数据结构自然而然地就是只需要一个一维数组表示就行了,被没有多么麻烦。我们假设为f[i]表示节点i在并查集构成的森林中的父节点。f[i]的初始值设定为i本身
通常来讲,并查集有两种基本操作:
1. 查询操作:查询当前点u的所在的并查集构成的树的根是哪个节点,具体代码实现为:

  1. int find(int x){
  2. if(x != f[x])
  3. return find(f[x]);//x == f[x]表示节点x即为本并查集的根
  4. return x;
  5. }
  1. 合并操作:将两个并查集(两个树)合并,其代表的是这两个连通块之间出现了一条连通边。我们只需要将这两个并查集的树的根进行合并即可,具体操作代码为:
  1. void merge(int u,int v){
  2. u = find(u);
  3. v = find(v);//分别寻找所在并查集的根
  4. f[v] = u;//f[u] = v也可以,通常来讲
  5. return;
  6. }

这两项就是并查集的基本操作了。


并查集构造、查询方式的优化

上面的并查

继续阅读