Hihocoder 1887 2018-2019ICPC北京H Approximate Matching AC自动机+DP
AC自动机 字符串    发布于 2020-10-04   939人围观   0条评论

题目大意

给出一个模式串n为01串，求问长度为m的所有文本串中有多少长度为n的子串能做到与模式串近似匹配。

近似匹配的意思为：最多只有一个字符与模式串不同。

题解

我们是无法在短时间内强行进行近似匹配的，所以只能转化成完全匹配来做。

最多只有一个字符与模式串不同，这样我们就可以把模式串写成n+1个不同的模式串，即原模式串每个字符都变换一次，作为一个新的模式串。

多模式串匹配问题，一定是AC自动机。

我们把所有的模式串合起来建立一个AC自动机，在上面跑DP就可以了。

我们设dp[i][j]表示当前遍历文本串的第i位，到达AC自动机状态j的方案数。

 

当然这样空间是不够用的，所以需要用滚动数组优化掉第一维的空间。

对于上一位的状态j，假设当前位到达状态为next[j][k]，k为枚举的第i位的字符；

若当前状态为终结状态，则总方案数ans += dp[i-1&1][j] * (1ll << (m-i))

若当前状态非终结状态，则有转移dp[i&1][next[j][k]] += dp[i-1&1][j];

直接DP即可。

代码

#include <bits/stdc++.h>
const int maxn = 2e3 + 5;
using namespace std;
typedef long long ll;
int nex[maxn][2], fail[maxn], ed[maxn], flag[maxn];
int root, p;
inline int newnode() {
    for (int i = 0; i < 2; ++i) {
        nex[p][i] = -1;
    }
    ed[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]-'0'] == -1) 
            nex[now][buf[i]-'0'] = newnode();
        now = nex[now][buf[i]-'0'
查看更多
后缀自动机模板2 统计某一子串出现次数
后缀自动机    发布于 2020-10-04   965人围观   0条评论

题解

其实就是每个字符串的endpos集的大小，无非就是同长度取max而已

我们注意到，如果一个字符串在st状态中出现，其必在trans决定的后续状态中继续出现。且每次在st状态中新出现的字符串，一定是以转移过来的节点的字符串做前缀的。

所以我们把每个非clone节点的位置的值设为1，clone节点的位置的值设为0，直接用后缀链link构成的DAG上跑拓扑DP就可以了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
char ss[maxn];
typedef long long ll;
int len;
struct SAM{
    int tot;
    int pos[maxn],link[maxn],trans[maxn][26],maxlen[maxn];
    queue<int>q;
    vector<int>g[maxn];
    int indeg[maxn];
    ll ans1;
    ll ans[maxn],endpos[maxn];
    int last;
    void init(){
        last = tot = 1;
        return;
    }
    int extend(int ch){
        int x,y,z = ++tot;
        int p = last;
        endpos[z] = 1;
        maxlen[z] = maxlen[last] + 1;
        while(p && !trans[p][ch])
            trans[p][ch] = z,p = link[p];
        if(!p){
            link[z] = 1;
        }
        else{
            x = trans[p][ch];
            if(maxlen[p] + 1 == maxlen[x])
                link[z] = x;
            else{
                y = ++tot;
查看更多
Nowcoder Muti-School Training 2 H Happy Triangle multiset + splay平衡树
splay STL    发布于 2020-09-19   567人围观   0条评论

题目大意

维护一个多重集合，支持三种操作：

  • 1 ： 加入一个x
  • 2 ： 删除一个x
  • 3 ： 询问当前在多重集中，是否存在两个数a，b，使得x能与a，b组成一个合法的三角形

题解

这题有线段树动态建点和离线离散化建线段树的做法，但是平衡树的做法一定是最好想的。

考虑查询操作我们可以假设下面两种情况：

  1. x为唯一最大边，则要a,b都小于x，于是只需要找比x更小的两个前驱作为a,b，判断a+b>x是否成立即可。
  2. x不是唯一最大边，假设b≥a，于是我们需要b≥x && b - a < x，而b-a最小的条件一定是b确定的情况下，a是b的一个非严格前驱，这样我们只需要找x的后缀最小值就行了。

第一种情况非常简单，直接用multiset维护、查询就行了，只需要注意一下边界问题。

第二种情况比较麻烦，没法用STL做，所以就用平衡树维护。平衡树维护的信息为子树内相邻两数差的最小值，排序的键值为当前数的大小，查询答案的时候，找到x的后缀节点，然后判断此节点与前一个节点的差mnval和其右子树中的相邻两数差的最小值mn中的最小值是否＜x即可。

需要注意考虑边界问题。

最后提示的一点，s.lower_bound(x)和s.upper_bound(x)是比lower_bound(s.begin(),s.end(),x)和upper_bound(s.beign(),s.end(),x)要快不少的。我就被坑了……。

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
multiset<int>s;
const int maxn = 2e5+5;
typedef pair<int,int> PI;
struct splay_node{
    int siz;
    PI val;
    int mn;
    splay_node *fa,*ch[2];
    void update(){
        mn = min(val.second,min(ch[0]->mn,ch[1]->mn));
    }
    void set_ch(int type,splay_node *child);
    int get_wh(){
        return (this == this->fa->ch[0]) ? 0 : 1;
查看更多
Nowcoder Muti-School Training 2 G Greater and Greater bitset加速
bitset    发布于 2020-09-16   691人围观   0条评论

题目大意

给出一个长为n的数列A,一个长为m的数列B

求问A中有多少个长度为m的子区间S，满足S中的元素全都不小于B中下标对应的元素

题解

说实话真的还是对bitset的应用不熟悉。

这题bitset只是最后用来优化的。

首先我们假定一个tmp数组，其中tmp[i][j]表示对Ai是否≥Bj。

如果一个长度为m的子区间要成为满足题目条件的S，那么和tmp[i]数组有什么关系？

一定是要求：对于区间内每一个i及其对应位置的j，tmp[i][j]都为1.这是显然的。

考虑如何优化这个问题。

首先，大小关系其实本质上来说只有m+1种，也就是对于tmp[i]的取值最多有m+1种，所以我们可以将B数组内的数全部排序，然后用m+1个bitset（假设为s）逐位去置1，然后九不需要算tmp数组了，我们需要取用tmp的时候，只需要找到最后一个小于等于A[i]的B[j]（这里的B已经排序好了），然后取s[j]就可以了。而且bitset也会在我们接下来的做法中发挥很重要的作用。预处理这些bitset的复杂度是O(m2/W)的（W为bitset优化的效果）

之后考虑如何去搞这个题。

新设一个新的m位bitset，假设为curi，其中curi[j] = 1当且仅当对于所有的k∈[j，m]，Ai+k-j >= Bk，这样只需要求有多少curi[1] = 1即可。

首先可以确定A数组的后m-1个数是肯定不可以作为区间点的，毕竟区间长度都不够，所以我们可以按照下面的公式来做：

curi = ((curi+1 >> 1) | Im) & sposi。posi表示最后一个小于等于A[i]的B[posi]。

这样通过右移位来进行对齐,可以达到我们预期的效果。

而且，我们可以不用开n个cur，只需要开一个进行滚动就可以了。

最终的时间复杂度是O(nm/W)

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PI;
const int maxn = 150005;
const int maxm = 40005;
PI a[maxn],b[maxm];
bitset<maxm>s[maxm];
bitset<maxm>cur,upd;
const int INF = 1e9+7;
int n,m;
int p;
int main(){
    ios_ba
查看更多
Nowcoder Mutischool-training 4 C Counting New String 广义后缀自动机
字符串 Trie 后缀自动机    发布于 2020-09-14   663人围观   0条评论

题目大意

对S串做两次f变换，得到一个字符串集A，求A中本质不同的字符串数量。

题解

其实不管是观察，还是拿样例手算，最后一定能得出一个结论：

其实两次f变换和一次f变换的作用是一样的。

所以只需要看一下一次f变换就行了。

f其实是对子串的变换，后面被变换的字符只跟其前面的字典序比他大的字符有关。

先看题目要求，求A中本质不同的字符串数量。

前面说了A实际上是S的所有子串做了变换而已。所以也就是本质不同的类子串数量（这个说法大概可以吧）。所以很自然想到这是一个后缀自动机。

但是这里的要求的并不是简单的子串，需要做变化。

前面说了，被变换的字符只跟其前面的字典序比他大的字典序最大的字符有关，只要出现一个比他大的字符就要重新更新字符串。

于是我们可以这样搞：

我们考虑将原串倒过来，然后按照题目的要求去建一个Trie，具体建法比较麻烦，如果当前字符的上一个比他大的字符没有出现，则需要从根开始往下重新建一条链，否则就继续往下建，复杂度最大为O(10n)，但实际上肯定到不了。

然后对Trie静态建广义后缀自动机，直接跑本质不同子串数量即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6+5;
string s;
char ss[maxn];
int len;
int son[maxn][10],fa[maxn],cl[maxn];
int now = 1;
int root = 1;
struct SAM{
    int tot;
    int pos[maxn],link[maxn],maxlen[maxn],trans[maxn][10];
    queue<int>q;
    ll ans;
    void init(){
        tot = 1;
        return;
    }
    int extend(int ch,int last){
        int x,y,z = ++tot;
        int p = last;
        maxlen[z] = maxlen[last]+1;
        while(p && !trans[p][ch])
            trans[p][ch] = z
查看更多
CSP201812-05 管道清洁
网络流 费用流    发布于 2020-09-12   488人围观   0条评论


题解

我记得当年我在考场上做这个题的时候想出了很多奇奇怪怪的思路……反正就是不会处理上下界的问题，然后就这个题爆零了

实际上我已经想明白是上下界的费用流了，但是并不会有上下界的情况，所以只能想各种奇技淫巧。

所以，此题的正解就是无源汇有上下界的最小费用可行流。

对于无源汇的网络流问题，我们通常会设置虚拟源点S和虚拟汇点T。然后再在图上进行构建。

对于这个题也是一样，只是因为有上下界所以我们需要对图进行一下改进。

我们考虑一条边一定会流下界那么多的流，这样整张图的残量网络就构成了一个流量不平衡的图。我们需要构建另外一张流量不平衡的图，使得原始图和我们构建的图互补成为一张流量平衡的图。

我们考虑对于原图中进行统计，一个点每流出1流量，度数du[x]-1，流入1流量，度数du[x]+1。

如果最终一个点的度数<0（流出大于流入），则其在互补图中流入就要大于流出，这样我们就需要给他添加一些流出渠道来疏通这些多余的流入流量，这样就从点x向虚拟汇点T连一条容量为-du[x]的边。反之同理。

如果我们能找到一个流满足新加的边都满流,这个流在原图上的部分就是我们需要的与原图互补的附加流。

那么怎样找出一个新加的边都满流的流呢?可以发现假如存在这样的方案,这样的流一定是我们所建出的图的S-T最大流,所以跑S到T的最大流即可.如果最大流的大小等于S出发的所有边的流量上限之和(此时指向T的边也一定满流,因为这两部分边的流量上限之和相等)，则说明此图是有可行流的.

在此题中也是如此，只是原图上的边加上了费用而已，而新加的边费用为0，直接跑有上下界最大费用可行流即可。

代码

#include <bits/stdc++.h>
using namespace std;
int T,S,E;
const int maxn = 205;
const int INF = 2e9;
struct edge{
    int fr,to,next,cap,dis;
}e[maxn<<3];
int h[maxn];
int cnt = 0;
void add(int u,int v,int cap,int d){
    e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = cap;e[cnt].dis = d;e[cnt].next = h[u];h[u] = cnt++;
    e[cnt].fr
查看更多
ZOJ 4086 Little Sub and a Game 线性基博弈
线性基    发布于 2020-08-18   257人围观   0条评论

题目大意

玩家Little Sub和lqybzx分别有N、M个数对(xi,yi)、(x'i,y'i),且双方都知道对方的数对中的数是什么，Little Sub先从自己的N个数对中的每个数对中选取1个数z，并且ans = ans xor z,之后lqybzx会对自己的M个数对做相同的操作。

Little Sub(A)希望最终结果更大，而lqybzx(B)希望最终结果更小，且双方均采取最优策略，问最终答案是多少。

题解

对于博弈的题目来说，我们其实不是好知道双方的脑回路是怎么想的。有时候我们能猜到有时候我们猜不到。

所以不妨我们先来假设两个人每个数对都选第一个数字，先把一个答案ans算出来，然后我们来根据每个人的数对再来进行调整。

由于是二进制的运算所以我们考虑对每个答案ans的每个二进制位上是否为1来讨论两个玩家的策略。

因为我们需要对二进制位进行讨论，所以我们需要讨论两个玩家的数对(x,y)中x xor y对答案的控制能力。所以我们需要对两个玩家的数对(x,y)进行x xor y的线性基的构造。

假设构造的两个x xor y的线性基分别为A、B。

如果在某个位bit上我们取了线性基X中在bit位上的元素，我们相当于在总答案的上面对某一组数对(x,y)的选择进行改变(ans xor(x xor y),本来ans中有x或y，选择这一次相当于换成另外一个)

我们从高位到低位逐一进行扫描，对于第i位，分为以下八种情况：

ans[i] = 0,A[i] = 0,B[i] = 0,双方都对这个位无法操作

ans[i] = 0,A[i] = 0,B[i] = 1,只有B对这个位可以操作，但由于B想要答案更小，所以他不会对这一位进行操作。

ans[i] = 0,A[i] = 1,B[i] = 0,只有A对这个位可以操作，由于A想要答案更大，所以他会选择对这一位进行操作，ans ^= A[i]。

ans[i] = 0,A[i] = 1,B[i] = 1,A与B都可对这个位操作，而且如果A对这个位操作的话，B一定也会对这个位操作，所以我们可以把A[i] xor B[i]加入到线性基A中，表示A和B同时选/不选。

ans[i] = 1,A[i] = 0,B[i] = 0,双方都对这个位无法操作

ans[i] = 1,A[i] = 0,B[i] = 1,只有B对这个位可以操作，由于B想要答案更小，所以他会选择对这一位进行

查看更多
Luogu P2495 [SDOI2011]消耗战 虚树+树形DP
DP 虚树    发布于 2020-07-12   199人围观   0条评论

 

题解

本人的虚树入门题。

基础思想

题目意思相当于m次询问，每次询问给出一些点，要我们付出一定代价断边使得给出的这些点与根节点1不连通.

首先肯定能确定这个题是一个树形DP。转移方程也非常好写。

考虑对于单次询问，我们设f[x]为处理完以x为子树的最小的代价。

那么转移无非是两种情况：

1.断开与父亲的连接，代价为从x到根1的路径上的最小值。

2.当该点不是询问点的时候，把子树内所有询问点都与根节点断开的代价。

但是这样有一个问题，每次询问都是O(n)的，来看一下数据范围：

很明显O(nm)的做法是无法处理的。

进阶优化 & 虚树的引出

但实际上，我们在对每一次询问的处理中，考虑了很多无用点的信息。

考虑一下，很容易能够明白，实际上，只有询问点、其LCA、其LCA的LCA及其三次LCA……等，对这些点和上面的根进行断开是实际在最小答案中有效的，处理其他的点实际上无效。

所以虚树就应运而生了。

虚树是主要运用在树形DP中的一类构造方法，旨在只将对答案有用的点拿出来构造一棵虚拟的新的树，以此来降低算法的复杂度。

举个栗子，在本题的样例中有这样的数据。

对于样例中的询问数据

3
2 10 6
4 5 7 8 3
3 9 4 6

其对应的虚树分别是以下的形式

第二个询问中，由于点7、8均在5的子树内，故断开5以及根节点的连接即可，7、8实际上是无用点（仅对此题而言，不同题目要考虑不同的构造）

虚树的构建

现在需要考虑的是如何构建虚树。

首先我们要先对整棵树dfs一遍，求出他们的dfs序，然后对每个节点以dfs序为关键字从小到大排序(本人比较喜欢用树链剖分里面的那种形式)

同时维护一个栈，表示从根到栈顶元素这条链

假设当前要加入的节点为pp，栈顶元素为x=s[top]x=s[top]，lcalca为他们的最近公共祖先

因为我们是按照dfs序遍历，因此lcalca不可能是pp

那么现在会有两种情况

  1. lcalca是xx，直接将
查看更多
2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest C. Carpet
树链剖分    发布于 2020-04-16   484人围观   0条评论

题目大意

给出一棵n个节点的树，要求将这个树的所有节点映射到一张1000000*20的横向表格里，要求保持原先的连边映射成的相连线段不能有交叉。

输出一种方案，要求将所有的树上节点的坐标输出。

题解

行数最多只有20行，所以要考虑最大行数控制在log2n以内。所以就要想树上的什么东西一定小于小于等于log2n。

学过树链剖分的话不难想到，对一个树进行重链剖分的话，所有点向下的轻链长度一定小于等于log2n，树链剖分的复杂度就是基于这个性质证明的。这个性质的证明并不难想，因为对于一个节点x，其轻儿子的子树大小一定不会超过siz[x]/2，否则这个儿子就是重儿子了。

然后就可以明白，要先对树进行重链剖分，对每个节点now把重儿子和自己放在同一行上，轻儿子放在下一行，重儿子和自己的距离间隔为siz[now]-siz[son[now]]，第一个轻儿子v1放在(x[now],y[now]+1)，第二个轻儿子v2放在(x[now]+siz[v1],y[now]+1),第三个轻儿子v3放在(x[now]+siz[v1]+siz[v2],y+1)，以此类推。

因为横向的列数极多，所以横向不会出现问题，又由轻链长度的性质，纵向不会不会超过20.上述的放节点的留空就是为了使得边不会交叉采取的方案。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5+5;
vector<int>g[maxn];
int son[maxn],siz[maxn],f[maxn];
struct point{
    int x,y;
}p[maxn];
void dfs(int now,int fa){
    siz[now] = 1;
    son[now] = 0;
    f[now] = fa;
    for(auto it : g[now]){
        if(it == fa)continue;
        dfs(it,now);
        siz[now] += siz[it];
        if(siz[it] > siz[son[now]])
            son[now] = it;
    }
    return;
}
void work(int now,int
查看更多
2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest I . Infinite Gift
高斯消元 bitset    发布于 2020-04-16   571人围观   0条评论

题目大意

给出n个k维向量vi，对于k维空间中所有点a，将点a与点a+vi连边，求问全部连接完的图能否完成黑白染色。

题解

黑白染色是判断二分图的方法。所以就是要判断所有向量影响后的k维空间中的点是否会形成二分图。

考虑二分图形成的条件：不能出现奇环。

于是问题就转变成了如何判断图中是否会存在奇环。

但是这个题目明显不能用通常的搜索判环解决。

考虑一个点通过这些向量能够通过奇数条边回到自己的等价情况。

假设n个未知数xi，假设一个点想要回到自身，需要使用第i个向量xi次。

于是要形成环即向量方程：

x1v1 + x2v2 + ... + xnvn = 0有解。

所以如果要保证形成奇数环的话，就是加入以下一个方程

x1 xor x2 xor ... xor xn = 1

联立来解一个n元k+1维方程组。

将上面的向量方程拆分到k维k个方程，并将所有运算全都mod 2处理，即可让整个方程组变成一个异或方程组。

能形成二分图的条件就是方程组不存在解，否则就说明构成的图不是二分图。

使用高斯消元解决方程组判断解的问题。

但是高斯消元有一个问题，就是复杂度不对，为O(nk2)

不过由于这道题的方程组的运算只与二进制异或有关，所以可以把方程的参数放入bitset加速，最终复杂度为O(nk2/64)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1505;
bitset<maxn>g[maxn];
int n,k,now,x;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= k;++j){
            cin >> x;
            g[j][i] = abs(x) % 2;
        }
    }
    for(int i = 1;i <= n+1;++i){
        g[k+1][i] = 1;
    }
    now = 0;
    for(int i = 1;i <= n;++i){
        int j
查看更多