预备役间学习记录9-创新互联
主要运用到(第0位-1)从第二位开始对每位的前字符串求大前缀和后缀的相同子串长度;
创新互联公司网站建设公司一直秉承“诚信做人,踏实做事”的原则,不欺瞒客户,是我们最起码的底线! 以服务为基础,以质量求生存,以技术求发展,成交一个客户多一个朋友!专注中小微企业官网定制,成都网站设计、网站建设,塑造企业网络形象打造互联网企业效应。
方法:
列如:主串:a b a a c a b a b c a c
子串:a b a b c
next : -1 0 0 1 2
下标 值 串
0 0 空
1 0 a b
2 1 a b a
3 2 a b a b
4 0 a b a b c
next[i]的值为:0--i构成的字符串中出现首尾相同的字串的大长度;
当无首尾相同的子串时next[i]的值为0;
在主串i++和子串j++比较过程中当不一样时,j=next[j];
就像这种第一次不同时i=3,j=3,执行后j=2;
i
a b a a c a b a b c a c
a b a b c
j
往后执行第二次不同i=4,j=3,不同j=next[j],j=2;
i
a b a a c a b a b c a c
a b a b c
j
往后执行第三次不同i=4,j=2,不同j=next[j],j=1;
i
a b a a c a b a b c a c
a b a b c
j
往后执行第四次不同i=4,j=1,不同j=next[j],j=0
i
a b a a c a b a b c a c
a b a b c
j
往后执行第五次不同i=4,j=0,此时注意是在j=0情况下不同,就这样执行i++,j=0;
i
a b a a c a b a b c a c
a b a b c
j
往后执行子串结束,代表比配成功,有这个子串结束循环;
附代码(next数组求法;kmp匹配方法)
#includeusing namespace std;
int net[1001000];
char z[1001000];
char f[1001000];
int j,zc,fc;
main()
{
cin>>z+1;
cin>>f+1;
zc=strlen(z+1);
fc=strlen(f+1);
for(int i=2;i<=fc;i++)
{while(j&&f[i]!=f[j+1])j=net[j];
if(f[j+1]==f[i])j++;
net[i]=j;
}
j=0;
for(int i=1;i<=zc;i++)
{while(j>0&&f[j+1]!=z[i])j=net[j];
if (f[j+1]==z[i]) j++;
if (j==fc) {cout<
二、刷题题解
1、# 修复公路## 题目背景
$A$地区在地震过后,连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
## 题目描述
给出A地区的村庄数$N$,和公路数$M$,公路是双向的。并告诉你每条公路的连着哪两个村庄,并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车,即最早什么时候任意两条村庄都存在至少一条修复完成的道路(可以由多条公路连成一条道路)
## 输入格式
第$1$行两个正整数$N,M$
下面$M$行,每行$3$个正整数$x, y, t$,告诉你这条公路连着$x,y$两个村庄,在时间t时能修复完成这条公路。
## 输出格式
如果全部公路修复完毕仍然存在两个村庄无法通车,则输出$-1$,否则输出最早什么时候任意两个村庄能够通车。
## 样例 #1
### 样例输入 #1
```
4 4
1 2 6
1 3 4
1 4 5
4 2 3
```
### 样例输出 #1
```
5
```
## 提示
$N \le 1000,M \le 100000$
$x \le N,y \le N,t \le 100000$
并查集,我们定义一个结构体数组来存村庄关系,和之间的时间,定义一个数组记录集合;
按时间从小到大对结构体数组排序;
之后,对结构体从i=1;i<=n;i++开始检索,并进行并查,到查到所有村庄都到一个集合时,此时检索到的关系时间就是最短时间,如果i>n还没到一个集合则输出-1
附代码
#include#include
using namespace std;
struct jh
{int x;
int y;
int t;
}zj[100000];
int jl[100000];
int bj(const jh &a,const jh &b){return a.t>n>>m;
for(int i=0;i>zj[i].x>>zj[i].y>>zj[i].t;if(zj[i].x>maxx)maxx=zj[i].x;if(zj[i].y>maxx)maxx=zj[i].y;}
sort(zj,zj+m,bj);
if(n==1){cout<<0;k=2;}
else
for(int i=0;imaxt){maxt=zj[i].t;}
if(jl[zj[i].x]==0&&jl[zj[i].y]==0)
{jl[zj[i].x]=jl[zj[i].y]=i+1;}
else
if(jl[zj[i].x]!=0&&jl[zj[i].y]==0)
{jl[zj[i].y]=jl[zj[i].x];}
else
if(jl[zj[i].x]==0&&jl[zj[i].y]!=0)
{jl[zj[i].x]=jl[zj[i].y];}
else
{int z=jl[zj[i].x];
int x=jl[zj[i].y];
for(int i=0;i<=maxx;i++)
if(jl[i]==z)jl[i]=x;
}
int j,js=1;
for(j=2;j<=maxx;j++)
{if(jl[j]!=jl[1]||jl[1]==0)break;else js++;}
if(js==n&&jl[1]!=0){cout<
2、# 【深基16.例3】二叉树深度## 题目描述
有一个 $n(n \le 10^6)$ 个结点的二叉树。给出每个结点的两个子结点编号(均不超过 $n$),建立一棵二叉树(根节点的编号为 $1$),如果是叶子结点,则输入 `0 0`。
建好这棵二叉树之后,请求出它的深度。二叉树的**深度**是指从根节点到叶子结点时,最多经过了几层。
## 输入格式
第一行一个整数 $n$,表示结点数。
之后 $n$ 行,第 $i$ 行两个整数 $l$、$r$,分别表示结点 $i$ 的左右子结点编号。若 $l=0$ 则表示无左子结点,$r=0$ 同理。
## 输出格式
一个整数,表示大结点深度。
## 样例 #1
### 样例输入 #1
```
7
2 7
3 6
4 5
0 0
0 0
0 0
0 0
```
### 样例输出 #1
```
4
```
这题考二叉树的遍历计算深度,我们只需定义一个结构体数组来记录每个节点的两个子节点;
然后进行DFS递归,传(1,1)上去代表从第一个节点的左右节点开始;
递归前判断是否到叶子节点0 0,是就直接return;没有到就记深度的变量++,然后先左节点dfs(传左节点的值,层数+1),在右节点dfs();
附代码
#include#include
using namespace std;
struct tree
{int z;
int y;
}jl[1000010];
int max1,n;
void zhao(int jd,int cs)
{if(jl[jd].z==0&&jl[jd].y==0)
{max1=max1>n;
for(int i=1;i<=n;i++)
{cin>>jl[i].z>>jl[i].y;}
zhao(1,1);
cout<
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站题目:预备役间学习记录9-创新互联
文章位置:http://pwwzsj.com/article/djegji.html