预备役间学习记录9-创新互联

一、学习算法 1、字符串 (1)kmp(字符串比配)
  1. 主要运用到(第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;

  1. 在主串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$

  1. 并查集,我们定义一个结构体数组来存村庄关系,和之间的时间,定义一个数组记录集合;

  1. 按时间从小到大对结构体数组排序;

  1. 之后,对结构体从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

```

  1. 这题考二叉树的遍历计算深度,我们只需定义一个结构体数组来记录每个节点的两个子节点;

  1. 然后进行DFS递归,传(1,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-创新互联
本文URL:http://scyanting.com/article/djegji.html