2021-01-16 21:50:05 |  0 Comments  |  后缀自动机

ICPC2019 Xuzhou L.Loli, Yen-Jen, and a cool problem

题目大意

给定一棵树,每个节点上有一个大写字母,共q次询问,每次询问包含两个参数X,L,表示求这个树中(由底向上)的字符串有多少和从X向上L的字母拼接成的字符串相同。

题解

广义后缀自动机模板题。

实际上就是求一个子串在所有的字符串中出现的次数,也就是endpos集大小。

注意在找这个具体的字符串对应的状态节点时,要倍增的在后缀树中往上跳。

剩下的就真的只是模板。

代码

#include <bits/stdc++.h>
using namespace std;
struct SAM_node{
	int len,endpos,trans[26],link;
};
const int maxn = 3e5+5;
int tr[maxn][26],tot = 0,trie_id[maxn],sam_pos[maxn],cnt[maxn],root;
string s;
int n,q;
int x,l;
struct SAM{
	SAM_node s[maxn<<1];
	int h[maxn<<1],next[maxn<<1],to[maxn<<1];
	int siz,sum,f[maxn<<1][21];
	void add(int u,int v){
		to[sum] = v;next[sum] = h[u];h[u] = sum++;
		return;
	}
	void init(){
		siz = 1;
		sum = 0;
		memset(h,-1,sizeof(h));
		return;
	}
	int extend(int last,int c,int num){
		int z = ++siz;
		int p = last;
		s[z].len = s[p].len + 1;
		s[z].endpos = num;
		while(p && !s[p].trans[c]){
			s[p].trans[c] = z,p = s[p].link;
		}
		if(!p)
			s[z].link = 1;
		else{
			int x = s[p].trans[c];
			if(s[x].len == s[p].len + 1)
				s[z].link = x;
			else{
				int y = ++siz;
				s[y] = 
 2021-01-15 20:44:17 |  0 Comments  |  线段树

Codeforces Educational Round 102 D.Program 线段树合并

题目大意

给出一个字符串序列,字符串仅由-和+组成,一开始有个初始的值x为0,-表示x = x-1,+表示x = x+1。

每次询问给出一个l和r,表示忽视[l,r]区间内的字符串,剩下的操作进行执行,求问x在操作过程中不同的值的个数。

题解

一开始看成区间内不同数的个数了,十分钟打完板子才发现不对。

虽然不是区间内不同数的个数,但是也是一道线段树的题目,且看下面的分析。

首先我们注意到,数x每次无论变大还是变小,每次变化的绝对值一定为1。这样我们就能够用x到达的最大值mx减去x的最小值mi,之后加上1,即为最终的答案。

于是我们只需要维护某一段区间操作使x能够变到的最大值和最小值分别是多少。

但是这样会出现一个问题,区间合并的时候应该怎么做。因为左侧区间得出的最终值一定会影响右侧区间的结果,所以这给我们的合并造成了一定的麻烦的影响。

但是影响是能解决的,因为产生影响的只有区间操作产生的对于这个区间的x最终结果的影响,所以我们只需要记录一下区间操作对x的最终结果的影响就好了。

这样我们就需要记录以下三个参数:

struct tree{
    int l,r,rval,mx,mi;
    tree operator + (const tree &x)const{
        tree res;
        res.mx = max(mx,rval + x.mx);
        res.mi = min(mi,rval + x.mi);
        res.rval = rval + x.rval;
        return res;
    }
    void init(){
        mx = 0;
        mi = INF;
        rval = 0;
    }
}tr[maxn<<2];

重载的operator +,就是区间的合并操作。

然后我们用线段树求解即可,具体求解方法就是,分别求出忽视的区间的左边和右边的操作区间的影响(struct结构),然后进行合并即可。

注意最小值小于0或者最大值大于0的情况,需要给答案+1,因为一开始x就是0。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int t
 2021-01-15 19:36:41 |  0 Comments  |  bitset 高斯消元

2020ICPC 济南site A Matrix Equation bitset + 异或高斯消元

题目大意

求矩阵C的个数,满足A×C = B·C。其中×表示矩阵乘(模数为2,也即矩阵的异或乘),·表示矩阵元素与。

题解

博主在正式赛的时候执着于找规律,最后才看到高斯消元,所以最后就白给了,拿了个铜滚粗了。

其实没必要去算什么规律的,我们直接设C的元素为c11 ……cnn,然后直接按照两种操作的定义展开即可。

之后我们可以发现c中的元素的每一列都构成了一组n元的异或方程组,而不同列之间的元素是没有相互影响的。这样我们就可以应用高斯消元,求解自由元的个数,计算出每一列自由元个数xi,最后结果就是Πxi。算法的总复杂度是O(n4)的

但是这个题目的数据是N ≤ 200,所以算法O(n4)的时间复杂度是无法接受的,但是我们又无法做到在指数级上进行优化,所以考虑常数优化。考虑到异或方程组的行间计算实际上都是异或操作,所以我们可以考虑用bitset代替自己写的数组式矩阵。这样最终算法的时间复杂度为O(n4/64)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll quick_pow(ll x,ll y){
	ll res = 1;
	while(y){
		if(y & 1)
			res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
const int maxn = 205;
int a[maxn][maxn],b[maxn][maxn];
bitset<maxn>bs[maxn],bd[maxn],t;
int n;
ll ans;
void swap(bitset<maxn> &x,bitset<maxn> &y){
	t.reset();
	t |= y;
	y.reset();
	y |= x;
	x.reset();
	x |= t;
	return;
}
int Guass(){
	int maxrow,row = 0,col = 0,num = 0;
	for(row = 0;row < n && col < n;row++,col++){
		maxrow = row;
		for(int i = row + 1;i < n;++i){
 2021-01-15 01:08:37 |  0 Comments  |  机器学习

Stanford CS231n ,学习笔记一:图像分类(数据驱动方法、K近邻分类器kNN)

图像在计算机中的存储形式和分类需要注意的问题

    图像在计算机中一般是一个3维的0~255的矩阵序列(分别存储R\G\B三原色信道的值)。
    在图像分类中需要注意的问题有:
* 视角、视点问题
* 照明度(曝光度、阻光度)问题
* 形态问题(变形、尺寸大小)
* 背景混淆
* 类内多样性

数据驱动方法

    我们无法像排序一样设计一个具体的算法来解决这种问题。所以我们需要像教儿童一样,给出一定数量的照片,并标签上属于哪一类,以此来设计一种机器学习的方法,来学习每一类照片的综合视觉表征(特征)。 这样的一种方法就称为数据驱动方法。数据驱动方法依赖于首先给出的数据以及其分类标签。

图像分类的步骤

    图像分类的任务就是获取一个像素序列(代表一个单个的图像),并依据我们的学习结果给图像一个标签。完整的步骤可以格式化如下:
* 输入:输入N个图片以及其标签作为训练集
* 训练/学习:使用训练集来学习/训练每一类的图像特征。这一步骤也称为训练模型。
* 评估:我们使用一个训练模型从未见过的数据集作为测试集进行分类预测,得到预测结果,并和真正的分类结果进行比较,用准确率来进行模型优劣的评估。

最近邻分类器

    最近邻分类器在实际中并不常用,目前只介绍其原理。
    最近邻分类器训练模型时,单纯的将图像的R\G\B信道的像素值进行简单的记录。在进行预测图片分类时,找出图片在像素值上的最近邻,将最近邻的分类标签作为其分类标签。
    最近邻分类器使用的近邻距离分为L1和L2两种,公式分别如下:

L1p|I1pI2p|

L2p(I1pI2p)2
 2020-10-04 22:22:06 |  0 Comments  |  AC自动机 字符串

Hihocoder 1887 2018-2019ICPC北京H Approximate Matching AC自动机+DP

题目大意

给出一个模式串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'
 2020-10-04 22:00:01 |  0 Comments  |  后缀自动机

后缀自动机模板2 统计某一子串出现次数

题解

其实就是每个字符串的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;
            
 2020-09-19 14:42:30 |  0 Comments  |  splay STL

Nowcoder Muti-School Training 2 H Happy Triangle multiset + splay平衡树

题目大意

维护一个多重集合,支持三种操作:

  • 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;
 2020-09-16 20:28:10 |  0 Comments  |  bitset

Nowcoder Muti-School Training 2 G Greater and Greater bitset加速

题目大意

给出一个长为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
 2020-09-14 20:27:32 |  0 Comments  |  字符串 Trie 后缀自动机

Nowcoder Mutischool-training 4 C Counting New String 广义后缀自动机

题目大意

对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
 2020-09-12 15:19:46 |  0 Comments  |  网络流 费用流

CSP201812-05 管道清洁


题解

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

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

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

对于无源汇的网络流问题,我们通常会设置虚拟源点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
Title - Artist
0:00