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] =
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
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){
Stanford CS231n ,学习笔记一:图像分类(数据驱动方法、K近邻分类器kNN)
图像在计算机中一般是一个3维的0~255的矩阵序列(分别存储R\G\B三原色信道的值)。
在图像分类中需要注意的问题有:
* 视角、视点问题
* 照明度(曝光度、阻光度)问题
* 形态问题(变形、尺寸大小)
* 背景混淆
* 类内多样性
我们无法像排序一样设计一个具体的算法来解决这种问题。所以我们需要像教儿童一样,给出一定数量的照片,并标签上属于哪一类,以此来设计一种机器学习的方法,来学习每一类照片的综合视觉表征(特征)。 这样的一种方法就称为数据驱动方法。数据驱动方法依赖于首先给出的数据以及其分类标签。
图像分类的任务就是获取一个像素序列(代表一个单个的图像),并依据我们的学习结果给图像一个标签。完整的步骤可以格式化如下:
* 输入:输入N个图片以及其标签作为训练集
* 训练/学习:使用训练集来学习/训练每一类的图像特征。这一步骤也称为训练模型。
* 评估:我们使用一个训练模型从未见过的数据集作为测试集进行分类预测,得到预测结果,并和真正的分类结果进行比较,用准确率来进行模型优劣的评估。
最近邻分类器在实际中并不常用,目前只介绍其原理。
最近邻分类器训练模型时,单纯的将图像的R\G\B信道的像素值进行简单的记录。在进行预测图片分类时,找出图片在像素值上的最近邻,将最近邻的分类标签作为其分类标签。
最近邻分类器使用的近邻距离分为L1和L2两种,公式分别如下:
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'
其实就是每个字符串的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平衡树
维护一个多重集合,支持三种操作:
这题有线段树动态建点和离线离散化建线段树的做法,但是平衡树的做法一定是最好想的。
考虑查询操作我们可以假设下面两种情况:
第一种情况非常简单,直接用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加速
给出一个长为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 广义后缀自动机
对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
我记得当年我在考场上做这个题的时候想出了很多奇奇怪怪的思路……反正就是不会处理上下界的问题,然后就这个题爆零了
实际上我已经想明白是上下界的费用流了,但是并不会有上下界的情况,所以只能想各种奇技淫巧。
所以,此题的正解就是无源汇有上下界的最小费用可行流。
对于无源汇的网络流问题,我们通常会设置虚拟源点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