P3808 【模板】AC 自动机（简单版）
P3796 【模板】AC 自动机（加强版）
P5357 【模板】AC 自动机（二次加强版）
2023ccpc女生组：H. 字符串游戏
B3637 最长上升子序列
P1115 最大子段和
P8707 [蓝桥杯 2020 省 AB1] 走方格
P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles
P1020 [NOIP1999 普及组] 导弹拦截
【模板】AC 自动机（二次加强版）
题目描述
给你一个文本串 \(S\) 和 \(n\) 个模式串 \(T_{1 \sim n}\)，请你分别求出每个模式串 \(T_i\) 在 \(S\) 中出现的次数。
输入格式
第一行包含一个正整数 \(n\) 表示模式串的个数。
接下来 \(n\) 行，第 \(i\) 行包含一个由小写英文字母构成的非空字符串 \(T_i\)。
最后一行包含一个由小写英文字母构成的非空字符串 \(S\)。
数据不保证任意两个模式串不相同。
输出格式
输出包含 \(n\) 行，其中第 \(i\) 行包含一个非负整数表示 \(T_i\) 在 \(S\) 中出现的次数。
样例 #1
样例输入 #1
5
a
bb
aa
abaa
abaaa
abaaabaa
样例输出 #1
6
0
3
2
1
提示
对于 \(100 \%\) 的数据，\(1 \le n \le 2 \times {10}^5\)，\(T_{1 \sim n}\) 的长度总和不超过 \(2 \times {10}^5\)，\(S\) 的长度不超过 \(2 \times {10}^6\)。
题解
一般来说简单版的AC自动机就能过，但最坏情况时间复杂度是O(模式串总长度*文本串总长度)肯定过不了
因为一条fail路径可能经过多次，所以先存一下一条路径起始点的答案数，而不走fail路径
最后存一下每个点的入度（有几个点连过来）
入度为零的即为起始点
最后遍历一遍，将后一个点答案加上当前点答案数
在加答案之前，令当前节点对应的子串答案等于当前节点答案数
然后使下一个节点入度减 1，如果它的入度为零，也将它作为起始点（说白了就是按拓扑序排一次）
这样可以保证在进入下一个节点的下一个节点前，所有连到下一个节点的节点都被遍历过
需要注意的是一个模式串可能出现多次，所以记录一下第一个与当前子串相同的子串的的编号即可
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
int n,tot,ans[N],trie[N][26],fail[N],id[N],M,mp[N],ansx[N],in[N];
string s,a[N];
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void build(string x,int y)
{
int u=0,L=x.size();
for(int i=0;i<L;i++)
{
int v=x[i]-'a';
if(!trie[u][v])trie[u][v]=++tot;
u=trie[u][v];
}
if(!id[u])id[u]=y;
mp[y]=id[u];
}
void getfail()
{
int u=0;
queue<int> q;
for(int i=0;i<26;i++)
if(trie[u][i])
q.push(trie[u][i]);
while(!q.empty())
{
u=q.front();q.pop();
for(int i=0;i<26;i++)
{
if(trie[u][i])
fail[trie[u][i]]=trie[fail[u]][i],q.push(trie[u][i]);
else {trie[u][i]=trie[fail[u]][i];continue;}
in[fail[trie[u][i]]]++;
}
}
}
void solve(string x)
{
int u=0,L=x.size();
for(int i=0;i<L;i++)
{
int v=x[i]-'a';
u=trie[u][v];
ansx[u]++;
}
}
void Topu()
{
queue<int> q;
for(int i=0;i<=tot;i++)
if(!in[i])q.push(i);
while(!q.empty())
{
int u=q.front();q.pop();
ans[id[u]]=ansx[u];
ansx[fail[u]]+=ansx[u];
in[fail[u]]--;
if(!in[fail[u]])q.push(fail[u]);
}
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
{
cin>>a[i];
build(a[i],i);
}
getfail();
cin>>s;
solve(s);Topu();
for(int i=1;i<=n;i++)
cout<<ans[mp[i]]<<endl;
return 0;
}
//**月雩·薇嫭**
最长上升子序列
题目描述
这是一个简单的动规板子题。
给出一个由 \(n(n\le 5000)\) 个不超过 \(10^6\) 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。
最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。
输入格式
第一行，一个整数 \(n\)，表示序列长度。
第二行有 \(n\) 个整数，表示这个序列。
输出格式
一个整数表示答案。
样例 #1
样例输入 #1
6
1 2 4 1 3 4
样例输出 #1
4
提示
分别取出 \(1\)、\(2\)、\(3\)、\(4\) 即可。
题解
令f[i]表示以a[i]结尾的最长的上升子序列
那么如果\(j<i 并且a[j]<a[i]， 那么f[i]=max(f[i],f[j]+1)\)
最后答案就是max(f[i])
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
ll n,a[N],f[N],ans;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=read();
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)f[i]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
if(a[i]>a[j])
f[i]=max(f[i],f[j]+1);
for(int i=1;i<=n;i++)ans=max(ans,f[i]);
cout<<ans;
return 0;
}
//**月雩·薇嫭**
最大子段和
题目描述
给出一个长度为 \(n\) 的序列 \(a\)，选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数，表示序列的长度 \(n\)。
第二行有 \(n\) 个整数，第 \(i\) 个整数表示序列的第 \(i\) 个数字 \(a_i\)。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
7
2 -4 3 -1 2 -4 3
样例输出 #1
4
提示
样例 1 解释
选取 \([3, 5]\) 子段 \(\{3, -1, 2\}\)，其和为 \(4\)。
数据规模与约定
- 对于 \(40\%\) 的数据，保证 \(n \leq 2 \times 10^3\)。
- 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 2 \times 10^5\)，\(-10^4 \leq a_i \leq 10^4\)。
题解
令f[i]为以i结尾最大的字段和
f[i]=max(f[i-1]+a[i],a[i])
最后ans即为最大的f[i]
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
ll ans=-1e9,n,a[N],f[N];
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
f[i]=max(a[i],f[i-1]+a[i]);
ans=max(f[i],ans);
}
cout<<ans;
return 0;
}
//**月雩·薇嫭**
[蓝桥杯 2020 省 AB1] 走方格
题目描述
在平面上有一些二维的点阵。
这些点的编号就像二维数组的编号一样，从上到下依次为第 \(1\) 至第 \(n\) 行，从左到右依次为第 \(1\) 至第 \(m\) 列，每一个点可以用行号和列号来表示。
现在有个人站在第 \(1\) 行第 \(1\) 列，要走到第 \(n\) 行第 \(m\) 列。只能向右或者向下走。
注意，如果行号和列数都是偶数，不能走入这一格中。
问有多少种方案。
输入格式
输入一行包含两个整数 \(n\)，\(m\)。
输出格式
输出一个整数，表示答案。
样例 #1
样例输入 #1
3 4
样例输出 #1
2
提示
\(1\le n,m\le30\)。
蓝桥杯 2020 第一轮省赛 A 组 G 题（B 组 H 题）。
题解
很容易想到f[i][j]=f[i-1][j]+f[i][j-1]
再加上限定条件即可
即判断f[i-1][j]/f[i][j-1]是否可取
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=30+10;
ll n,m,f[N][N],vis[N][N];
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=read(),m=read();
for(int i=2;i<=n;i+=2)
for(int j=2;j<=m;j+=2)
vis[i][j]=-1;
f[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(vis[i][j]!=-1)
{
f[i+1][j]+=f[i][j];
f[i][j+1]+=f[i][j];
}
cout<<f[n][m];
return 0;
}
//**月雩·薇嫭**
[USACO1.5] [IOI1994]数字三角形 Number Triangles
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
在上面的样例中，从 \(7 \to 3 \to 8 \to 7 \to 5\) 的路径产生了最大权值。
输入格式
第一个行一个正整数 \(r\) ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行,包含那个可能得到的最大的和。
样例 #1
样例输入 #1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出 #1
30
提示
【数据范围】
对于 \(100\%\) 的数据，\(1\le r \le 1000\)，所有输入在 \([0,100]\) 范围内。
题目翻译来自NOCOW。
USACO Training Section 1.5
IOI1994 Day1T1
题解
与上一道题类似
易得f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j])
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e3+10;
int n,f[N][N],ans;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=read();int a;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
a=read();
f[i][j]=max(f[i-1][j]+a,f[i-1][j-1]+a);
}
}
for(int i=1;i<=n;i++)ans=max(f[n][i],ans);
cout<<ans;
return 0;
}
//**月雩·薇嫭**
[NOIP1999 普及组] 导弹拦截
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，若干个整数，中间由空格隔开。
输出格式
两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例 #1
样例输入 #1
389 207 155 300 299 170 158 65
样例输出 #1
6
2
提示
对于前 \(50\%\) 数据（NOIP 原题数据），满足导弹的个数不超过 \(10^4\) 个。该部分数据总分共 \(100\) 分。可使用\(\mathcal O(n^2)\) 做法通过。
对于后 \(50\%\) 的数据，满足导弹的个数不超过 \(10^5\) 个。该部分数据总分也为 \(100\) 分。请使用 \(\mathcal O(n\log n)\) 做法通过。
对于全部数据，满足导弹的高度为正整数，且不超过 \(5\times 10^4\)。
此外本题开启 spj，每点两问，按问给分。
\(\text{upd 2022.8.24}\)：新增加一组 Hack 数据。
题解
Problem 1：
建立一个栈，如果当前a[i]小于等于栈顶元素，则将栈数量+1，栈顶变成a[i]
如果栈顶大于a[i]，那么找到栈中第一个≤a[i]的元素，将它替换成a[i]
（可以模拟一下，这样可以保证答案正确，但数组中序列可能不正确）
Problem 2：
考虑贪心算法，f[i]表示第i个系统最小的元素
并且f[len]是f中最大的元素
如果当前元素a[i]大于flen，那么只能新增一个系统来存a[i]，即f[++len]=a[i]
反之，寻找第一个大于等于a[i]的f[x]，令f[x]=a[i]（第x个系统最小的变为a[i]）
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,a[N],Len,f[N];
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
while(scanf("%d",&a[++n])!=EOF);
n--;
f[0]=1e9;
for(int i=1;i<=n;i++)
{
if(a[i]<=f[Len])f[++Len]=a[i];
else
{
int l=1,r=Len;
while(l<r)
{
int mid=(l+r)>>1;
if(f[mid]>=a[i])l=mid+1;
else r=mid;
}
f[l]=a[i];
}
}
cout<<Len<<endl;
memset(f,0,sizeof(f));Len=0;
f[0]=-1e9;
for(int i=1;i<=n;i++)
{
if(a[i]>f[Len])f[++Len]=a[i];
else
{
int l=1,r=Len;
while(l<r)
{
int mid=(l+r)>>1;
if(a[i]<=f[mid])r=mid;
else l=mid+1;
}
f[l]=a[i];
}
}
cout<<Len;
return 0;
}
//**月雩·薇嫭**