前言
高中打NOIP时，这部分是让我最头疼的地方，怎么也学不会。看着老师在上面写代码，我只能感到深深的迷茫，后来才发现原来是因为跳过了数据结构的基础直接开始编程。现在就来完成一下三年前留下的遗憾
数据范围
- int：约 ±2×10^9
- long long：约 ±9×10^18
- int 是 4 字节，long long 是 8 字节，char 是 1 字节
- 一维数组：1e7 安全，5e7约200MB，接近上限
- 二维数组：5000×5000安全，7000×7000接近上限
数组
基础知识
定义
数组是物理意义上连续的一组数据，创建时确定容量，之后就不能改变。因此要对数组存放的数据进行约束防止溢出。数组通过索引进行查找，复杂度O(1)，插入和删除需要移动后续数据，复杂度O(n)
初始化
-
a是数组名称，5是大小
-
总内存 = 元素个数 × 每个元素字节数
b是二维数组，可以理解成一个100*100矩阵
数组元素的访问与修改
-
数组括号中的数字就是索引，直接访问到的就是值
-
索引从0开始
-
如果不加索引会报错
在数组中插入元素
复杂度O(n)
1
2
3
4
5
|
int n=5,a[10]，v=1;
for(int i=9;i>n;i--){
a[i]=a[i-1];
}
a[n]=v;
|
在数组中删除元素
复杂度O(n)
1
2
3
4
|
int n=5,a[10];
for(int i=n;i<9;i++){
a[i]=a[i+1];
}
|
数组的查找
复杂度O(n)
1
2
3
4
5
6
|
int data=10,a[10];
int i=0;
while(i<10&&a[i]!=data){
i++;
}
if(i<10) printf("%d\n",a[i])
|
数组的反转
复杂度O(n)
1
2
3
4
5
6
|
int a[10],n=9;
for(int i=0;i<10/2;i++){
int x=a[i];
a[i]=a[n-i];
a[n-i]=x;
}
|
指针数组
数组大小由数据量决定，不由下标范围决定。如果在一个下标范围内，并不是数组的每一个空间都占满，而是只有小部分，就需要用到指针数组
首先进行定义，这一句意思是定义一个指针数组a，存储的是10000个int*指针，这里的10000可以改成下标范围，初始情况下元素都是NULL
1
2
3
4
|
int *a[10000];
for(int i=0;i<=n;i++){
a[i]=NULL;
}
|
需要用到某一行，就将其初始化
这一句意思是给第 i 行分配一段连续内存，可以放10000个int，并且全部初始化为 0，然后把这段内存的地址交给 a[i]
- (int*)：将指针转换为
int*类型
- calloc：元素初始化为0
- 10000：元素个数
- sizeof(int)：每个元素大小
1
2
3
|
if(a[i]==NULL){
a[i]=(int*)calloc(10000,sizeof(int));
}
|
题目练习
P3156 【深基15.例1】询问学号
基础的数组应用题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <stdio.h>
#include <stdlib.h>
int m,n,s;
int a[2000001];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<m;i++){
scanf("%d",&s);
printf("%d\n",a[s]);
}
return 0;
}
|
P3613 【深基15.例2】寄包柜
高中就经常被内存空间困扰，这次抱着侥幸心理定义了一个二维数组int a[100001][100001];，结果果然炸了，而使用链表的话查询时间复杂度过大。查看题解提示可以用map，询问ai提示可以用指针数组或者哈希表，我用的是指针数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <stdio.h>
#include <stdlib.h>
int q,n,s,k;
int *a[100001];
int main(){
scanf("%d%d",&n,&q);
for(int i=0;i<=n;i++){
a[i]=NULL;
}
for(int i=0;i<q;i++){
scanf("%d",&s);
if(s==1){
int i,j,k;
scanf("%d%d%d",&i,&j,&k);
if(a[i]==NULL){
a[i]=(int*)calloc(100001,sizeof(int));
}
a[i][j]=k;
}else if(s==2){
int i,j;
scanf("%d%d",&i,&j);
printf("%d\n",a[i][j]);
}
}
return 0;
}
|
P1160 队列安排
数组实现这道题的方法是让数组模拟链表，存储左右的索引，注意需要初始化，还有就是删除时更新头节点
做题的时候有一种熟悉的感觉，想当年我就特别喜欢用这种方法，只不过做的题目更简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <stdio.h>
#include <stdlib.h>
int n,k,p,m,x;
typedef struct node{
int l,r;
}node;
int main(){
node a[100001];
scanf("%d",&n);
for(int i=0;i<=n;i++){
a[i].l=a[i].r=0;
}
int b=1;
for(int i=2;i<=n;i++){
scanf("%d%d",&k,&p);
if(p==0){
a[i].r=k;
a[i].l=a[k].l;
if(a[k].l!=0){
a[a[k].l].r=i;
}else b=i;
a[k].l=i;
}else if(p==1){
a[i].l=k;
a[i].r=a[k].r;
if(a[k].r!=0){
a[a[k].r].l=i;
}
a[k].r=i;
}
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d",&x);
if(a[x].l!=0||a[x].r!=0){
if(a[x].l!=0){
a[a[x].l].r=a[x].r;
}
if(a[x].r!=0){
a[a[x].r].l=a[x].l;
}
if(x==b) b=a[x].r;
a[x].l=a[x].r=0;
}
}
while(a[b].r!=0){
printf("%d ",b);
b=a[b].r;
}
printf("%d ",b);
printf("\n");
return 0;
}
|
链表
基础知识
定义
链表也就是靠链连接起来的一些节点，所谓的链就是指针。每一个节点里面存放着指针和数据，指针指向它的下一个节点，这种特性让链表在物理上可以不连续。如果直接引用指针变量，得到的是地址而不是数据。单链表只有一个指针，双链表有两个
初始化链表
struct link*next;就是定义next指针- 这里是创建一个结构体，一个结构体中可以有多个相同结构的链表
1
2
3
4
|
typedef struct link{
int data;
struct link*next;
}link;
|
初始化头节点
link*head=(link*)malloc(sizeof(link));意思是：在堆上新开辟一个 link 结构体节点，并用指针 head 指向它
- sizeof(link)：link结构体的大小
- (link*)：将指针转换为link类型指针
- malloc：申请一块内存，但不会初始化
- 等号前的指针指向等号后的节点，不能调转方向
1
2
|
link*head=(link*)malloc(sizeof(link));
head->next=NULL;
|
在头节点后新增节点
节点的连接需要先接后面再接前面，否则会导致断链
1
2
3
4
|
link*new=(link*)malloc(sizeof(link));
new->next=head->next;
head->next=new;
new->data=1;
|
在链表尾部新增节点
如果知道链表尾部地址，复杂度O(1)，否则这里就需要对链表进行遍历，复杂度O(n)
1
2
3
4
5
6
7
8
|
link*s=head->next;
while(s->next!=NULL){
s=s->next;
}
link*new=(link*)malloc(sizeof(link));
new->next=NULL;
s->next=new;
new->data=1;
|
在链表中某个位置插入节点
知道位置的地址，复杂度是O(1)，不知道的话复杂度O(n)
1
2
3
4
5
6
7
8
9
|
int n=10,data=1;
link*s=head->next;
while(s!=NULL&&s->data!=n){
s=s->next;
}
link*new=(link*)malloc(sizeof(link));
new->next=s->next;
new->data=data;
s->next=new;
|
在链表中某个位置删除节点
复杂度同上，free(p);就是释放节点内存，p相当于存储需要删除节点的地址
1
2
3
4
5
6
7
8
|
int n=10;
link*s=head->next;
while(s->next!=NULL&&s->next->data!=n){
s=s->next;
}
link*p=s->next;
s->next=p->next;
free(p);
|
链表的倒置
复杂度O(n)，核心原理是三个指针分别存储主节点、倒置前主节点的下一个节点、倒置后主节点的下一个节点，然后修改next指针指向
1
2
3
4
5
6
7
8
9
10
|
link*i=head->next;
link*j=NULL;
link*k=NULL;
while(i!=NULL){
k=i->next;
i->next=j;
j=i;
i=k;
}
head->next=j;
|
释放内存
程序运行结束以后需要手动释放链表占用的内存，否则内存会被一直占用，同时不能直接释放前序节点，这会导致内存泄漏，继续占用内存但无法访问，这里为了调用方便一般是写一个封装
1
2
3
4
5
6
7
8
9
|
void freel(link*fr){
link*head=fr;
link*next;
while(head!=NULL){
next=head->next;
free(head);
head=next;
}
}
|
题目练习
链表通讯录
我的逻辑就是通过不同输入对应不同的操作，从而对链表进行增删改等操作，整体不难，属于熟悉语法的题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct student{
char name[20];
char number[20];
struct student*next;
}student;
int main()
{
student*head=(student*)malloc(sizeof(student));
head->next=NULL;
student* prev=head;
while(1){
char search;
scanf(" %c",&search);
if(search=='a'){
prev = head;
while(prev->next != NULL) {
prev = prev->next;
}
printf("输入姓名电话：");
student*nw=(student*)malloc(sizeof(student));
nw->next=NULL;
scanf("%19s",nw->name);
scanf("%19s",nw->number);
prev->next=nw;
prev=nw;
printf("添加成功");
printf("\n");
}
else if(search=='d'){
printf("输入需要删除的姓名或电话：");
char a[20];
int found=0;
scanf("%19s",a);
student*i=head;
while(i->next!=NULL){
if(strcmp(i->next->name, a) == 0){
student*p=i->next;
i->next=p->next;
found=1;
free(p);
break;
}
else if(strcmp(i->next->number, a) == 0){
student*p=i->next;
i->next=p->next;
found=1;
free(p);
break;
}
else{
i=i->next;
}
}
if(!found) printf("无此信息");
else printf("删除成功");
printf("\n");
}
else if(search=='c'){
printf("输入需要更改和更改后的信息：");
char b[20],c[20];
int found=0;
scanf("%19s %19s",b,c);
student* j=head;
while(j->next!=NULL){
if(strcmp(j->next->name, b) == 0){
strcpy(j->next->name, c);
found=1;
break;
}
else if(strcmp(j->next->number, b) == 0){
strcpy(j->next->number, c);
found=1;
break;
}
else{
j=j->next;
}
}
if(!found) printf("无此信息");
else printf("更改成功");
printf("\n");
}
else if(search=='f'){
printf("输入查找的信息：");
char d[20];
int found=0;
scanf("%19s",d);
student*k=head;
while(k->next!=NULL){
if(strcmp(k->next->name, d) == 0){
printf("号码：%19s ",k->next->number);
found=1;
break;
}
else if(strcmp(k->next->number, d) == 0){
printf("姓名：%19s ",k->next->name);
found=1;
break;
}
else{
k=k->next;
}
}
if(!found) printf("无此信息");
printf("\n");
}
else if(search=='i'){
student*l=head;
printf("通讯录信息:\n");
while(l->next!=NULL){
printf("姓名：%19s ",l->next->name);
printf("电话：%19s\n",l->next->number);
l=l->next;
}
printf("\n");
}
else if(search=='q'){
break;
}
}
return 0;
}
|
链表的多项式运算
这里我的思路是创建两个链表分别存储两个多项式，然后进行运算。但我使用了两个结构体，正确写法应该是定义一个结构体，在这个结构体下创建两个链表
点击查看错误代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <stdio.h>
#include <stdlib.h>
typedef struct p{
int a;
int b;
struct p*next;
}p;
typedef struct q{
int a;
int b;
struct q*next;
}q;
char c1[10001];
char c2[10001];
int main()
{
p*head=(p*)malloc(sizeof(p));
head->next=NULL;
p*prev=head;
q*head=(q*)malloc(sizeof(q));
head->next=NULL;
q*prev=head;
scanf("%10000s",c1);
scanf("%10000s",c2);
|
最开始的逻辑是找到x，然后从x向左右遍历来找到两个系数，但这样很难处理没有x和各种边界情况，就改成了取运算符号分隔的式子进行存储，然后分离其中的系数
点击查看错误代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct node{
int a;
int b;
struct node*next;
}node;
char c1[10001];
char c2[10001];
int main()
{
node*p=(node*)malloc(sizeof(node));
p->next=NULL;
node*pn=p;
node*q=(node*)malloc(sizeof(node));
q->next=NULL;
node*qn=q;
scanf("%10000s",c1);
scanf("%10000s",c2);
int i=0;
while(c1[i]!='\0'){
while(c1[i]!='x'&&c1[i]!='0'){
i++;
}
if(c1[i]=='\0') break;
int n=1,m=2,a=0,b=0,c=1;
while(c1[i-n]>='0'&&c1[i-n]<='\9'){
a+=(c1[i-n]-'0')*c;
c*=10;
n++;
}
if(n==1) a=1;
if(c1[i-n]=='-') a*=-1;
while(c1[i+m]>='0'&&c1[i+m]<='9'){
b=b*10+(c1[i+m]-'0');
m++;
}
if(m==2) b=1;
node*new=(node*)malloc(sizeof(node));
new->next=pn->next;
new->a=a;
new->b=b;
pn->next=new;
pn=new;
}
return 0;
}
|
这部分解决以后就是处理加减法，虽然没有遇到什么大的逻辑错误，但小毛病比如语法错误，边界错误或者死循环就没断过，最后靠大模型一点点讲解纠错才改好，完整代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct node{
int a;
int b;
struct node*next;
}node;
char c1[10001];
char c2[10001];
node*add_char_to_node(char cc[10001],node*nn){
int i=0;
while(cc[i]!='\0'){
int x=1;
if(cc[i]=='-'){
x=-1;
i++;
}else if(cc[i]=='+'){
x=1;
i++;
}
char c[1000];
int j=0;
while(cc[i]!='+'&&cc[i]!='-'&&cc[i]!='\0'){
c[j]=cc[i];
j++;
i++;
}
c[j]='\0';
int k=0,a=0,b=0,r=0;
while(c[k]!='x'&&c[k]!='\0'){
a=a*10+(c[k]-'0');
k++;
r=1;
}
if(c[k]=='x'&&r==0) a=1;
a*=x;
if(c[k]=='x'){
k++;
while(c[k]!='\0'){
b=b*10+(c[k]-'0');
k++;
}
}
node*new=(node*)malloc(sizeof(node));
new->next=NULL;
new->a=a;
new->b=b;
nn->next=new;
nn=new;
}
return nn;
}
void freee(node*fr){
node*head=fr;
node*next;
while(head!=NULL){
next=head->next;
free(head);
head=next;
}
}
int main()
{
node*p=(node*)malloc(sizeof(node));
p->next=NULL;
node*pn=p;
node*q=(node*)malloc(sizeof(node));
q->next=NULL;
node*qn=q;
scanf("%10000s",c1);
scanf("%10000s",c2);
pn=add_char_to_node(c1,pn);
qn=add_char_to_node(c2,qn);
node*r=(node*)malloc(sizeof(node));
r->next=NULL;
node*rn=r;
node*ps=p->next;
node*qs=q->next;
while(ps!=NULL&&qs!=NULL){
if(ps->b==qs->b){
int aa=ps->a+qs->a;
if(aa!=0){
node*new=(node*)malloc(sizeof(node));
new->next=NULL;
new->a=ps->a+qs->a;
new->b=ps->b;
rn->next=new;
rn=new;
}
ps=ps->next;
qs=qs->next;
}else if(ps->b>qs->b){
node*new=(node*)malloc(sizeof(node));
new->next=NULL;
new->a=ps->a;
new->b=ps->b;
rn->next=new;
rn=new;
ps=ps->next;
}else if(ps->b<qs->b){
node*new=(node*)malloc(sizeof(node));
new->next=NULL;
new->a=qs->a;
new->b=qs->b;
rn->next=new;
rn=new;
qs=qs->next;
}
}
if(ps!=NULL) rn->next=ps;
else if(qs!=NULL) rn->next=qs;
node*print=r->next;
while(print!=NULL){
if(print->a>0&&print!=r->next) printf("+");
if(print->b==0) printf("%d",print->a);
else printf("%dx%d",print->a,print->b);
print=print->next;
}
printf("\n");
freee(p);
freee(q);
freee(r);
return 0;
}
|
之后是乘法，主要逻辑如下，这里感觉到这些年自己变得很浮躁，没有原来那种自己一行行读程序，自己修改逻辑问题的能力了，而是稍微有点问题就问大模型，就比如这里面三个指针的移动最开始没写，我都并不是靠自己发现的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
node*ps=p->next;
node*qs=q->next;
while(ps!=NULL){
qs=q->next;
while(qs!=NULL){
int aa=ps->a*qs->a;
int bb=ps->b+qs->b;
int e=0;
node*s=r->next;
while(s!=NULL){
if(s->b==bb){
s->a+=aa;
e=1;
break;
}
s=s->next;
}
if(e==0){
node*new=(node*)malloc(sizeof(node));
new->next=NULL;
new->a=aa;
new->b=bb;
rn->next=new;
rn=new;
}
qs=qs->next;
}
ps=ps->next;
}
|
P1996 约瑟夫问题
逻辑是回环链表的删除，注意删除后需要将指针定位到下一个循环的开头，也就是当前节点的下一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <stdio.h>
#include <stdlib.h>
int m,n,a;
typedef struct node{
int data;
struct node *next;
}node;
int main(){
node *head=(node*)malloc(sizeof(node));
head->next=NULL;
node *prev=head;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
node *new=(node*)malloc(sizeof(node));
new->next=NULL;
new->data=i;
prev->next=new;
prev=new;
}
prev->next=head->next;
node *c=prev->next;
for(int j=0;j<n;j++){
for(int i=1;i<m-1;i++){
c=c->next;
}
printf("%d ",c->next->data);
node *d=c->next;
c->next=d->next;
free(d);
c=c->next;
}
printf("\n");
return 0;
}
|
P1160 队列安排
这道题用数组做的话，在入列的插入删除过程中可能时间复杂度过高，用链表做的话，又在找到出入列位置的部分复杂度更高。我用两种方法都做了一遍
链表方法是创建一个动态数组作为链表的索引，这样就不需要每次查找位置都遍历，这里还是遇到了边界问题，没有考虑到左右有NULL的情况，导致引用了空节点，要不是问ai，我至少需要半小才能看出来，不过粗心导致的小问题几乎都自己解决了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include <stdio.h>
#include <stdlib.h>
int n,k,p,m,x;
typedef struct node{
int data;
struct node *l;
struct node *r;
}node;
int main(){
node *a[100001];
node *first=(node*)malloc(sizeof(node));
first->l=NULL;
first->r=NULL;
a[1]=first;
first->data=1;
node *begin=first;
scanf("%d",&n);
for(int i=2;i<=n;i++){
scanf("%d%d",&k,&p);
if(p==0){
node *new=(node*)malloc(sizeof(node));
new->r=a[k];
new->l=a[k]->l;
if(a[k]->l!=NULL){
a[k]->l->r=new;
}else begin=new;
a[k]->l=new;
a[i]=new;
new->data=i;
}else if(p==1){
node *new=(node*)malloc(sizeof(node));
new->l=a[k];
new->r=a[k]->r;
if(a[k]->r!=NULL){
a[k]->r->l=new;
}
a[k]->r=new;
a[i]=new;
new->data=i;
}
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d",&x);
if(a[x]!=NULL){
node *d=a[x];
if(d->l!=NULL){
d->l->r=d->r;
}
if(d->r!=NULL){
d->r->l=d->l;
}
if(d==begin) begin=d->r;
a[x]=NULL;
free(d);
}
}
node*p=begin;
while(p!=NULL){
printf("%d ",p->data);
p=p->r;
}
printf("\n");
return 0;
}
|
B3630 排队顺序
和上一道类似是动态数组加链表，思路就是数组存储序号，链表存储指向
这题纯靠自己写出，没有参考任何大模型，就是最开始不小心在程序名里加了一个空格，在编译上面卡了半天，我还以为是代码的问题
第一次的代码最后一个测试re了，也就是内存有问题，加了for(int i=0;i<=n;i++) b[i]=NULL;解决，这里提醒我如果后面的判断中有关于某个数组或者节点的状态，那么创建时一定记得初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
}node;
int n,a,c;
int main(){
scanf("%d",&n);
node *b[1000001];
for(int i=0;i<=n;i++) b[i]=NULL;
for(int i=1;i<=n;i++){
scanf("%d",&a);
if(a==0){
continue;
}
if(b[i]==NULL){
node *new=(node*)malloc(sizeof(node));
b[i]=new;
new->next=NULL;
}
if(b[a]==NULL){
node *new=(node*)malloc(sizeof(node));
b[a]=new;
new->next=NULL;
}
b[i]->data=i;
b[a]->data=a;
b[i]->next=b[a];
}
scanf("%d",&c);
node *pr=b[c];
while(pr!=NULL){
printf("%d ",pr->data);
pr=pr->next;
}
printf("\n");
return 0;
}
|
栈
基础知识
定义
类似一头关闭一头开启的数组，数据存储的过程叫push，只能从开口进入，弹出叫pop,只能弹出栈最上层的数据。这样的结构让栈有先进后出的特点。栈涉及到前中后缀表达式，前缀表达式就是将运算符放在两个运算数之前，中缀表达式就是我们熟悉的计算，后缀表达式就是将运算符放在两个运算数之后。虽然答案相同，但表达式格式不一样
栈的写法
栈一般用数组模拟，需要初始化一个数组和栈顶标记，可以用int也可以用指针
入栈就是将栈顶标记加一，然后栈顶元素赋值为入栈的数，出栈则是将栈顶标记减一
1
2
3
4
5
6
7
8
9
|
for(int i=0;i<10;i++){
top++;
a[top]=i;
}
for(int i=0;i<10;i++){
x=a[top];
top--;
}
|
顺序表达式的计算
前缀表达式：从右到左遍历算式，遍历到运算符以后，将它右边两个数进行运算，然后弹出这两个数和运算符，用运算结果代替这个位置，直到获得最终结果
后缀表达式：从左到右遍历算式，遍历到运算符以后，将它左边两个数进行运算，然后弹出这两个数和运算符，用运算结果代替这个位置，直到获得最终结果
中缀表达式转前缀表达式：按照平常的运算顺序，以两个数一个符号为一组，将前面的数和符号交换位置写下，然后将这一组转换完成的视为一个数，遍历直到获得最终表达式
中缀表达式转后缀表达式：按照平常的运算顺序，以两个数一个符号为一组，将后面的数和符号交换位置写下，然后将这一组转换完成的视为一个数，遍历直到获得最终表达式
题目练习
1449 后缀表达式
说真的感觉栈比链表数组那些简单很多，这题的逻辑一遍过，就是犯了个粗心的小问题，但这次我没有让大模型直接分析，而是让它生成了一些测试数据，我自己dbg
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <stdio.h>
#include <stdlib.h>
char s[101];
int n,top,num,a[100000];
int main(){
scanf("%s",s);
while(s[n]!='@'){
num=0;
if(s[n]>='0'&&s[n]<='9'){
while(s[n]!='.'){
num=num*10+s[n]-'0';
n++;
}
top++;
a[top]=num;
}else if(s[n]=='+'){
num=a[top-1]+a[top];
a[top]=0;
top--;
a[top]=num;
}else if(s[n]=='-'){
num=a[top-1]-a[top];
a[top]=0;
top--;
a[top]=num;
}else if(s[n]=='*'){
num=a[top-1]*a[top];
a[top]=0;
top--;
a[top]=num;
}else if(s[n]=='/'){
num=a[top-1]/a[top];
a[top]=0;
top--;
a[top]=num;
}
n++;
}
printf("%d\n",num);
return 0;
}
|
P4387 【深基15.习9】验证栈序列
这题的逻辑更复杂一些，需要同时处理出入栈加判断。最开始有不少小错误和逻辑问题，但靠自己一点点改掉了，只有最后一个逻辑问题是让大模型隐晦的提示才找到的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <stdio.h>
#include <stdlib.h>
int n,q,ps[100001],pop[100001],push[100001];
int main(){
scanf("%d",&q);
for(int i=0;i<q;i++){
scanf("%d",&n);
for(int j=0;j<=n;j++) ps[j]=pop[j]=push[j]=0;
int top=0,topp=1,y=0;
for(int j=1;j<=n;j++){
scanf("%d",&ps[j]);
}
for(int j=1;j<=n;j++){
scanf("%d",&pop[j]);
}
for(int j=1;j<=n;j++){
if(push[top]==pop[j]){
push[top]=0;
top--;
continue;
}else while(push[top]!=pop[j]&&topp<=n){
top++;
push[top]=ps[topp];
topp++;
}
if(push[top]!=pop[j]){
y=1;
}else {
push[top]=0;
top--;
}
}
if(y==0){
printf("Yes\n");
}else printf("No\n");
}
return 0;
}
|
P1241 括号序列
感觉题目怪怪的，没看懂…看了题解才隐隐约约有点头绪，做起来卡手，也不知道是因为我没理解栈这一块还是题目太烂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int y;
char c;
}node;
char s[101],a[100];
node p[101];
int n,top,x[101];
int main(){
scanf("%s",s);
for(int i=0;i<=100;i++) p[i].y=0;
while(s[n]){
p[n].c=s[n];
if(s[n]=='('||s[n]=='['||s[n]=='{'){
top++;
a[top]=s[n];
x[top]=n;
}else if(s[n]==')'){
if(a[top]=='('){
p[x[top]].y=1;
p[n].y=1;
top--;
}
}else if(s[n]==']'){
if(a[top]=='['){
p[x[top]].y=1;
p[n].y=1;
top--;
}
}else if(s[n]=='}'){
if(a[top]=='{'){
p[x[top]].y=1;
p[n].y=1;
top--;
}
}
n++;
}
for(int i=0;i<n;i++){
if(p[i].y==1){
printf("%c",p[i].c);
}else if(p[i].c=='('||p[i].c==')'){
printf("()");
}else if(p[i].c=='['||p[i].c==']'){
printf("[]");
}else if(p[i].c=='{'||p[i].c=='}'){
printf("{}");
}
}
return 0;
}
|
P1165 日志分析
最开始的思路是将最大值做一个链表，但这样每次加入都要排序，复杂度就爆了，后面经过提示想到栈可以作为一个轨迹的作用，于是创建了一个最大值的栈。感觉很精妙啊，喜欢这道题
第一次写了两个栈，一个存储x一个存储当前最大值，虽然ac了，但发现第一个貌似根本没用上
点击查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <stdio.h>
#include <stdlib.h>
int n,q,x,a[200001],top,max[200001];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&q);
if(q==0){
scanf("%d",&x);
if(x>max[top]){
max[top+1]=x;
}else max[top+1]=max[top];
top++;
a[top]=x;
}else if(q==1&&top!=0){
a[top]=0;
max[top]=0;
top--;
}else if(q==2){
printf("%d\n",max[top]);
}
}
return 0;
}
|
经过优化后的最终代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <stdio.h>
#include <stdlib.h>
int n,q,x,top,max[200001];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&q);
if(q==0){
scanf("%d",&x);
top++;
if(x>=max[top-1]){
max[top]=x;
}else max[top]=max[top-1];
}else if(q==1&&top!=0){
top--;
}else if(q==2){
if(top==0) printf("0\n");
else printf("%d\n",max[top]);
}
}
return 0;
}
|
进出栈与后序运算
作业题，就是基本的栈实现与简单运算，这里知道了后序运算并不是将全部数字和符号分类入队以后再计算，而是每读到一个运算符就计算一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#include <stdio.h>
#include <stdlib.h>
int x,y;
typedef struct zhan{
int data[10001];
int top;
int bottom;
}zhan;
zhan a,n,f;
char d[10001]="\0";
void push (int x,zhan *s){
if(s->top==20){
printf("full,failed to ");
return;
}
s->top++;
s->data[s->top]=x;
}
void pop (zhan *s){
if(s->top<s->bottom){
printf("empty,failed to ");
return;
}
s->top--;
}
void show(zhan s){
if(s.top<s.bottom){
printf("empty");
return;
}
for(int i=s.bottom;i<=s.top;i++){
printf("%d ",s.data[i]);
}
}
void hx(char g[10001]){
int ans,e=0;
while(d[e]!='\0'){
if(d[e]>='0'&&d[e]<='9'){
push(d[e]-48,&n);
}else if(d[e]=='+'||d[e]=='-'||d[e]=='*'||d[e]=='/'){
if(d[e]=='+'){
ans=n.data[n.top-1]+n.data[n.top];
pop(&n);
pop(&n);
push(ans,&n);
}else if(d[e]=='-'){
ans=n.data[n.top-1]-n.data[n.top];
pop(&n);
pop(&n);
push(ans,&n);
}else if(d[e]=='*'){
ans=n.data[n.top-1]*n.data[n.top];
pop(&n);
pop(&n);
push(ans,&n);
}else if(d[e]=='/'){
ans=n.data[n.top-1]/n.data[n.top];
pop(&n);
pop(&n);
push(ans,&n);
}
}
e++;
}
printf("%d\n",n.data[n.top]);
}
int main(){
a.top=n.top=f.top=-1;
a.bottom=n.bottom=f.bottom=0;
scanf("%d",&x);
while(x!=22){
if(x==1){
scanf("%d",&y);
push(y,&a);
printf("push %d\n",y);
}else if(x==2){
pop(&a);
printf("pop \n");
}else if(x==3){
show(a);
printf("\n");
}else if(x==4){
scanf("%1000s",&d);
hx(d);
}
scanf("%d",&x);
}
printf("end\n");
return 0;
}
|
队列
基础知识
定义
队列一般情况下是用数组来实现。队列在逻辑上是连续的，先进入队列的先被取出，就像平时的排队一样
循环队列
首先定义数组与头尾。设队列长度为m，用取模来实现循环
-
定义：int head=0,tail=0,q[m];
-
入队： tail=(tail+1)%m;
-
出队： head=(head+1)%m;
-
队空： tail=head
-
队满： (tail+1)%m=head
-
队列长度：size=(tail-head+m)%m
入队，注意如果将tail定义为最后一个元素，那么就应该先增加tail再入队，如果定义为最后一个元素后面的第一个空位，那么就是先入队再增加tail。规范的写法中tail指向空位
1
2
|
q[tail]=s;
tail=(tail+1)%m;
|
队满则出队
1
2
3
|
if((tail+1)%m==head){
head=(head+1)%m;
}
|
单调队列
要学单调队列，首先就要知道滑动窗口。滑动窗口就是数组上固定长度的区间，这个区间会进行移动，单调队列就是有规律的队列，用来存储滑动窗口中的元素索引，这个队列并不需要循环
举例P2251 质量检测，目的是找滑动窗口中的最小值
尾部处理的思路是遍历数组，每次将所有队列尾部索引对应值大于当前值的弹出，因为更大并且入队更早，不可能成为最小值。然后将当前值的索引加入队尾
头部的处理就是当滑动窗口前进，头部小等于遍历次数减窗口长度时，头部弹出一个失效的最小值
1
2
3
4
5
6
7
8
|
for(int i=1;i<=n;i++){
while(head<=tail&&nx[min[tail]]>nx[i]){
tail--;
}
min[++tail]=i;
if(min[head]<=i-m) head++;
if(i>=m) printf("%d\n",nx[min[head]]);
}
|
题目练习
P1540 [NOIP 2010 提高组] 机器翻译
题目不难，逻辑并不绕，就是要注意队列长度是tail-head+1而不是tail-head，在这里卡了好久始终找不到问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <stdio.h>
#include <stdlib.h>
int m,n,q[1001],s,head,tail,ans,y;
int main(){
scanf("%d%d",&m,&n);
for(int i=0;i<=n;i++) q[i]=0;
for(int i=0;i<n;i++){
scanf("%d",&s);
y=0;
for(int j=head;j<=tail;j++){
if(q[j]==s){
y++;
}
}
if(y==0){
ans++;
if(tail-head+1==m){
head++;
tail++;
q[tail]=s;
}else if(head==tail&&q[head]==0){
q[head]=s;
}else{
tail++;
q[tail]=s;
}
}
}
printf("%d\n",ans);
return 0;
}
|
P2058 [NOIP 2016 普及组] 海港
最开始思路是两个数组分别存储船和国家，但是这样出队的时候就没法处理国家，而且时间复杂度极高。
实在没有头绪，问了一下大模型，经过提示我改成了创建一个队列存储乘客信息。写的比较顺畅，只有最后出现了一个粗心导致的数组命名问题，是大模型帮我找出来的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int time;
int ctry;
}node;
int k,n,head=1,tail=1,t,x,c[100001],ans;
int main(){
node kk[300001];
scanf("%d",&n);
for(int i=0;i<=n;i++) kk[i].time=0;
for(int i=0;i<n;i++){
scanf("%d%d",&t,&k);
for(int j=1;j<=k;j++){
scanf("%d",&x);
if(head==tail&&kk[head].time==0){
kk[tail].time=t;
}else{
tail++;
if(tail==300001) tail=1;
kk[tail].time=t;
}
kk[tail].ctry=x;
if(c[x]==0) ans++;
c[x]++;
}
while(t-kk[head].time>=86400){
c[kk[head].ctry]--;
if(c[kk[head].ctry]==0) ans--;
head++;
if(head==300001) head=1;
}
printf("%d\n",ans);
}
return 0;
}
|
P1996 约瑟夫问题
写是写出来了，就是总感觉非常屎山啊
点击查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <stdio.h>
#include <stdlib.h>
int m,n,a,head=1,tail,s[1000];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) s[i]=i;
for(int j=0;j<n;j++){
for(int i=1;i<m;i++){
while(s[head]==0){
head++;
if(head>n) head=1;
}
head++;
if(head>n) head=1;
}
while(s[head]==0){
head++;
if(head>n) head=1;
}
printf("%d ",s[head]);
s[head]=0;
}
printf("\n");
return 0;
}
|
重新学了一下然后重构一遍，这次整洁多了。之前是不知道队列的循环需要取模而且逻辑想复杂了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <stdio.h>
#include <stdlib.h>
int m,n,a,head,tail,s[1000];
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n-1;i++) s[i]=i+1;
for(int j=0;j<n;j++){
for(int i=0;i<m-1;i++){
s[tail]=s[head];
tail=(tail+1)%n;
head=(head+1)%n;
}
printf("%d ",s[head]);
head=(head+1)%n;
}
printf("\n");
return 0;
}
|
P5661 [CSP-J 2019] 公交换乘
写的极其痛苦极其折磨，逻辑一错再错，这道题涉及出入队还有元素的查找删除，只能用标记来删，而且边界难处理。不过学到了队列为空的入队，和队列为1的出队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int time;
int pr;
}node;
int n,head,tail,car,ans,p,t,s;
int main(){
node k[100001];
scanf("%d",&n);
for(int i=0;i<=n;i++) k[i].time=0;
for(int i=0;i<n;i++){
scanf("%d%d%d",&car,&p,&t);
while(t-k[head].time>45&&head!=tail){
head=(head+1)%n;
}
if(head==tail&&t-k[head].time>45){
k[tail].time=0;
k[tail].pr=0;
}
if(car==1){
s=head;
int found=-1;
while(s!=(tail+1)%n){
if(k[s].pr!=0&&k[s].pr>=p){
found=s;
break;
}
s=(s+1)%n;
}
if(found>=0){
k[found].pr=0;
}else{
ans+=p;
}
}else if(car==0){
ans+=p;
tail=(tail+1)%n;
k[tail].time=t;
k[tail].pr=p;
}
}
printf("%d\n",ans);
return 0;
}
|
P2032 扫描
最简单的单调队列题目。我真的不擅长处理队列的边界问题，总是写乱，这道题也是磕磕绊绊，从存储到边界出了无数问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <stdio.h>
#include <stdlib.h>
int n,k,head=0,tail=-1,nx[2000001],max[2000001];
int main(){
scanf("%d%d",&n,&k);
for(int j=1;j<=n;j++){
scanf("%d",&nx[j]);
}
for(int i=1;i<=n;i++){
while(head<=tail&&nx[max[tail]]<nx[i]){
tail--;
}
tail++;
max[tail]=i;
if(max[head]<=i-k) head++;
if(i>=k){
printf("%d\n",nx[max[head]]);
}
}
return 0;
}
|
P2251 质量检测
和上一题逻辑一模一样，换皮题目。在了解逻辑以后自己写了一遍，相当于重构上一题的代码，但还是在头尾初始化上出现了一点点问题。做完以后自认为基本掌握这类题目的做法了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <stdio.h>
#include <stdlib.h>
int n,m,head=1,tail=0,nx[100001],min[100001];
int main(){
scanf("%d%d",&n,&m);
for(int j=1;j<=n;j++){
scanf("%d",&nx[j]);
}
for(int i=1;i<=n;i++){
while(head<=tail&&nx[min[tail]]>nx[i]){
tail--;
}
min[++tail]=i;
if(min[head]<=i-m) head++;
if(i>=m) printf("%d\n",nx[min[head]]);
}
return 0;
}
|
P1638 逛画展
最开始的思路是尾指针向右遍历直到找到所有的画，然后头指针也向右缩小范围。问题是这样会导致输出第一个符合要求的区间，如果第一个不是最优区间，就错误了。所以后面又加了一个while循环，让尾指针可以遍历到数组尾部。尾指针走一步头指针就缩小一次范围，也就是一种长度不固定的滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <stdio.h>
#include <stdlib.h>
int n,m,head=1,tail=1,nx[1000001],pr[10001],p,x,y,min;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) pr[i]=0;
for(int j=1;j<=n;j++){
scanf("%d",&nx[j]);
}
while(p<m){
if(pr[nx[tail]]==0){
p++;
}
pr[nx[tail]]++;
tail++;
}
while(pr[nx[head]]>1){
pr[nx[head]]--;
head++;
}
min=tail-head-1;
x=head;
y=tail-1;
while(tail<=n){
pr[nx[tail]]++;
while(pr[nx[head]]>1){
pr[nx[head]]--;
head++;
}
if(tail-head<min){
x=head;
y=tail;
min=tail-head;
}
tail++;
}
printf("%d %d\n",x,y);
return 0;
}
|
基本操作与循环队列
简单的循环队列实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <stdio.h>
#include <stdlib.h>
int x,y,a[10001],cnt;
int head=-1,tail=-1;
void push (int n){
if(cnt==10000){
printf("full,failed to ");
return;
}
tail=(tail+1)%10000;
a[tail]=n;
cnt++;
}
void pop (){
if(cnt==0){
printf("empty,failed to ");
return;
}
head=(head+1)%10000;
cnt--;
}
void show(){
if(cnt==0){
printf("empty");
return;
}
for(int i=1;i<=cnt;i++){
printf("%d ",a[(head+i)%10000]);
}
}
int main(){
scanf("%d",&x);
while(x!=22){
if(x==1){
scanf("%d",&y);
push(y);
printf("push %d\n",y);
}else if(x==2){
pop();
printf("pop \n");
}else if(x==3){
show();
printf("\n");
}
scanf("%d",&x);
}
return 0;
}
|
树
基础知识
树也就是一个扩展结构，第一个节点是根节点，根节点以下是子节点，最末端没有子节点的是叶节点，比如计算机里面的文件目录就是一种树
二叉树
二叉树也就是每个节点最多有两个子节点的树，这两个子节点分别是左节点和右节点。二叉树的遍历方法分为前序、中序、后序
1
2
3
4
5
6
7
8
|
C
/ \
/ \
B G
/ \ /
A D H
/ \
E F
|
前序遍历：CBADEFGH 按照根，左子树，右子树的顺序访问节点，第一个节点一定是根节点
中序遍历：ABEDFCHG 按照左子树，根，右子树的顺序访问节点
后序遍历：AEFDBHGC 按照左子树，右子树，根的顺序访问节点，最后一个节点一定是根节点
二叉树的建立可以用传统的结构体，定义左右子节点来存储，但更建议用下面记录的邻接表来存储
1
2
3
|
typedef struct node{
int l,r;
}node;
|
DFS
dfs就是深度优先搜素，比如某个地点有多条路可以走到，先走完其中一条，然后返回岔路口走另一条，直到遍历完所有路径
代码逻辑就是从某个节点出发，一般按照从左到右的顺序，找到第一个子节点，然后子节点进行递归，用相同的方法进行遍历直到到达边界返回，然后寻找下一个子节点继续这个操作，直到子节点全部遍历完成，返回
代码中sy是节点的索引，d是深度，w是宽度，每次遍历会导致深度增加，当前深度的宽度加一，同时开始遍历a的左右子节点，没有子节点就停止遍历
1
2
3
4
5
6
7
|
void dfs(int sy,int d){
if(sy==0) return;
if(d>ansd) ansd=d;
w[d]++;
dfs(m[sy].l,d+1);
dfs(m[sy].r,d+1);
}
|
邻接表
用于记录两个点之间有边连接，在树中非常常见。一般用c++的vector实现
需要引用vector的头文件
定义一个数组记录每个节点的连接状态
1
|
vector<int> adj[100001];
|
主要实现，原理就是输入两个节点，分别将数组中这两个节点对应的数组中加入另一个节点
1
2
3
4
|
void tree(int u,int v){
adj[u].push_back(v);
adj[v].push_back(u);
}
|
使用时只需要遍历某个节点的所有相邻节点即可
1
2
3
|
for(int v:adj[sy]){
}
|
树的质心
树的质心也就是树上某一个节点，使其他节点到这个节点的距离最小，增加一个树的叶节点，重心最多移动一个位置。实现它有两种方法
暴力：
计算距离，从某个节点出发遍历所有节点，然后将每个节点的距离加起来
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void far(int a,int way,int last){
if(a==0) return;
ans+=m[a].data*way;
if(last!=m[a].l){
far(m[a].l,way+1,a);
}
if(last!=m[a].r){
far(m[a].r,way+1,a);
}
if(last!=m[a].f){
far(m[a].f,way+1,a);
}
}
|
遍历整棵树，找到最短路径
1
2
3
4
5
6
7
8
|
void dfs(int a){
if(a==0) return;
ans=0;
far(a,0,0);
if(ans<aaa) aaa=ans;
dfs(m[a].l);
dfs(m[a].r);
}
|
换根DP：
首先计算出根节点的距离，和所有节点的子树大小加一
1
2
3
4
5
6
7
8
9
10
11
|
void lon(int sy,int way,int f){
if(sy==0) return;
ans+=way;
int size=1;
for(int v:adj[sy]){
if(v==f) continue;
lon(v,way+1,sy);
size+=sizee[v];
}
sizee[sy]=size;
}
|
从根节点开始遍历整棵树。如果节点向下移动一位，那么新节点的子树和它本身的距离减一，其他节点距离加一。利用这个规律，可以得到下一个节点对应的距离是当前节点的距离减去下一个节点的sizee，再加上总结点数n减去sizee，也就是as-sizee[v]*2+n
1
2
3
4
5
6
7
|
void dfs(int sy,int as,int f){
if(sy==0) return;
for(int v:adj[sy]){
if(v==f) continue;
dfs(v,as-sizee[v]*2+n,sy);
}
}
|
二叉搜索树
二叉搜索树的定义就是对于任何一个节点，左子树的所有节点值都小于它，右子树的所有节点值都大于它
首先定义一个结构体，里面有5个变量，还要定义两个全局变量
-
l、r：记录当前节点的左右节点
-
data：记录节点的值
-
cnt：记录这个值出现了几次
-
size：记录子树的大小
-
ct：全局变量，记录节点总数
-
gen：全局变量，记录根节点的索引值
1
2
3
4
5
|
int ct,gen;
typedef struct node {
int l,r,cnt,data,size;
}node;
node m[1000001];
|
在树中添加节点：
-
遍历：从根节点开始，如果x大于当前节点的值就向右遍历，并将下一个节点的索引赋值给当前节点的r，小于就向左遍历，赋值用相同方法，等于就将这个节点的cnt加一然后返回，因为如果值重复了就不需要新增一个节点来存储
-
添加新节点：遍历直到找到空节点也就是sy=0，总节点数加一，这一步是创建索引为cn的新节点。将新节点的值设为x，大小和次数都设为1，然后返回这个节点的索引值。返回是为了让上一步的节点将新节点设置成左或者右子节点。
-
记录根节点：在函数的最后返回当前索引，引用时将根赋值为返回的值，来记录根节点对应的索引，这一步是为了哪怕树被删除，根节点也能实时更新
-
记录子树大小：这一步是为了之后快速查找排名做准备，某个节点的子树大小就是它的左子树大小加右子树大小，再加上这个节点的cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int add(int sy,int x){
if(sy==0){
ct++;
m[ct].data=x;
m[ct].size=m[ct].cnt=1;
return ct;
}
if(x==m[sy].data){
m[sy].cnt++;
}else if(x<m[sy].data){
m[sy].l=add(m[sy].l,x);
}else m[sy].r=add(m[sy].r,x);
m[sy].size=m[m[sy].l].size+m[m[sy].r].size+m[sy].cnt;
return sy;
}
gen=add(gen,x);
|
寻找x的前驱和后继：
-
前驱：比x小的数中最大的数，若找不到则输出-2147483647。这个定义翻译成程序也就是找到x的左子树，这个子树里面的最大值就是前缀，而这个最大值要去右子树里面找
对根节点和x进行遍历。当节点不为空时，若当前节点的值大等于x则继续递归当前节点的左子节点，小于x说明找到x的左子树，那么递归当前节点的右子节点，ans记录其中的最大节点值，递归完成后返回ans
-
后继：比x大的数中最小的数，若找不到则输出2147483647。逻辑和上面的一模一样，最大改成了最小，前改成了后，因此程序实现时应该先找右子树再找里面的最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
int qx(int sy,int x){
int ans=-2147483647;
while(sy!=0){
if(m[sy].data<x){
ans=m[sy].data;
sy=m[sy].r;
}else sy=m[sy].l;
}
return ans;
}
int hx(int sy,int x){
int ans=2147483647;
while(sy!=0){
if(m[sy].data>x){
ans=m[sy].data;
sy=m[sy].l;
}else sy=m[sy].r;
}
return ans;
}
|
寻找排名：
-
x的排名：从根节点开始遍历。如果当前节点的值等于x，由节点的左子树中所有值都比它小这个定律可知，左子树的size就是x前面的数的个数，因此加一即是排名。如果当前节点的值大于x，那么向当前节点的左子节点遍历。如果当前节点的值小于x，那么向当前节点的右子节点遍历，并且既然当前值小于x了，那么当前的左子树一定也都小于x，结果需要额外加上当前左子树的size和当前的cnt
-
排名为x的数：从根节点开始遍历。如果当前节点的size大等于x，说明当前节点排名更靠后，因此向左遍历。否则如果当前节点的size小于x，size加cnt大等于x，说明当前节点的值等于x节点的值，找到答案。否则说明当前排名小于x的排名，向右遍历并将x减去左子树的size和当前节点cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int xpm(int sy,int x){
if(sy==0) return 1;
if(x==m[sy].data) return m[m[sy].l].size+1;
if(x<m[sy].data){
return xpm(m[sy].l,x);
}else{
return xpm(m[sy].r,x)+m[m[sy].l].size+m[sy].cnt;
}
}
int pmx(int sy,int x){
if(sy==0) return 0;
if(x<=m[m[sy].l].size) return pmx(m[sy].l,x);
else if(x<=m[m[sy].l].size+m[sy].cnt) return m[sy].data;
else return pmx(m[sy].r,x-m[m[sy].l].size-m[sy].cnt);
}
|
题目练习
P4913 【深基16.例3】二叉树深度
二叉树模板题目，我看着题解做的，主要是为了了解标准写法。之前的队列直接上手做，结果边界处理出了好多问题，最后才发现是因为写法太不标准，这次不能重蹈覆辙。写完这道题才知道原来二叉树的遍历就是用dfs实现的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <stdio.h>
#include <stdlib.h>
int n,ans;
typedef struct node {
int l,r;
}node;
node m[1000001];
void dfs(int a,int d){
if(a==0) return;
if(d>ans) ans=d;
d++;
dfs(m[a].l,d);
dfs(m[a].r,d);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&m[i].l,&m[i].r);
}
dfs(1,1);
printf("%d\n",ans);
return 0;
}
|
P4715 【深基16.例1】淘汰赛
我将比赛的过程通过递归模拟了一下，这个写法个人感觉不太好，因为m数组在调用自己的同时写入自己，而且没有清除不需要的数据。虽然对这题来说完全没影响，但还是觉得应该有更好的写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <stdio.h>
#include <stdlib.h>
int n=1,ans,ni;
typedef struct node {
int bh,sz;
}node;
node m[1000001];
void dfs(node m[1000001],int fw){
if(fw==1) return;
int c=1;
for(int i=1;i<=fw;i++){
if(m[c].sz<m[c+1].sz){
m[i].sz=m[c+1].sz;
m[i].bh=m[c+1].bh;
}else{
m[i].sz=m[c].sz;
m[i].bh=m[c].bh;
}
c+=2;
}
fw/=2;
dfs(m,fw);
}
int main(){
scanf("%d",&ni);
for(int i=1;i<=ni;i++) n*=2;
for(int i=1;i<=n;i++){
scanf("%d",&m[i].sz);
m[i].bh=i;
}
dfs(m,n/2);
if(m[1].sz>m[2].sz) printf("%d\n",m[2].bh);
else printf("%d\n",m[1].bh);
return 0;
}
|
P1305 新二叉树
这里唯一难点就是处理字母到数字的映射，方法是字母减去a的ascll码再加一，这样a就是1,b就是2,以此类推，然后在结构体里面增加一个变量专门存储字母
1
|
m[s[0]-'a'+1].data=s[0];
|
需要注意这一题不需要记录深度信息，但需要记录根节点的索引，我是看了题解才发现这个问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <stdio.h>
#include <stdlib.h>
int n,ans,st;
typedef struct node {
int l,r;
char data;
}node;
node m[1000001];
char s[4];
void dfs(int a){
if(a==0) return;
printf("%c",m[a].data);
dfs(m[a].l);
dfs(m[a].r);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
if(i==1) st=s[0]-'a'+1;
m[s[0]-'a'+1].data=s[0];
m[s[0]-'a'+1].l=s[1]-'a'+1;
m[s[0]-'a'+1].r=s[2]-'a'+1;
if(s[1]=='*') m[s[0]-'a'+1].l=0;
if(s[2]=='*') m[s[0]-'a'+1].r=0;
}
dfs(st);
printf("\n");
return 0;
}
|
P1030 [NOIP 2001 普及组] 求先序排列
根据中序和后续排列求前序的题型，思路是首先通过后序找到根节点，然后中序中根节点左右的部分，就分别是左子树和右子树，然后分别对左右子树用相同的方法进行递归
最开始是这样写的，但草稿纸上面模拟以后，发现我把中序和后序的r搞混了
点击查看错误代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <stdio.h>
#include <stdlib.h>
int n,x,m;
char middle[1000001],behind[1000001];
void dfs(int l,int r){
for(int i=l;i<=r;i++){
if(middle[i]==behind[r]) m=i;
}
printf("%c",behind[r]);
if(m>l) dfs(l,m-1);
if(m<r) dfs(m+1,r-1);
}
int main(){
scanf("%s%s",middle,behind);
while(behind[x]>='A'&&behind[x]<='Z') x++;
dfs(0,x-1);
printf("\n");
return 0;
}
|
之后的思路是分别记录中序与后序树的左右节点，初始值是0到字符串长度减一，首先找到根节点m并输出
判断如果m大于中序的左边，说明有左树，左树的中序左不变，中序右是m-1，左树对应的后序范围是后序左不变，后续右是后序左加上左树的字符数，也就是中序右减中序左
判断如果m小于中序的右边，说明有右树，右树的中序右不变，中序左是m+1，右树对应的后序范围是后序右减一，后续左是原本的后序左加上左树的字符数和根，也就是中序右减中序左加一
注意m需要定义成局部变量，全局会导致报错
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <stdio.h>
#include <stdlib.h>
int n,x;
char middle[1000001],behind[1000001];
void dfs(int zl,int zr,int hl,int hr){
int m;
for(int i=zl;i<=zr;i++){
if(middle[i]==behind[hr]) m=i;
}
printf("%c",behind[hr]);
if(m>zl) dfs(zl,m-1,hl,hl+m-1-zl);
if(m<zr) dfs(m+1,zr,hl+m-zl,hr-1);
}
int main(){
scanf("%s%s",middle,behind);
while(behind[x]>='A'&&behind[x]<='Z') x++;
dfs(0,x-1,0,x-1);
printf("\n");
return 0;
}
|
做完这题感觉大脑一片清澈，虽然坐牢了挺长时间，但思路对了写的就很顺畅，而且debug也可以进行模拟，比较方便，比起队列的焦头烂额我还是喜欢递归。做题过程中有参考题解和ai的思路，不过主体还是自己想出来的
P1827 [USACO3.4] 美国血统 American Heritage
上一题是中后转前，这次是中前转后，思路差不多，就是顺序不一样
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <stdio.h>
#include <stdlib.h>
int n,x;
char middle[1000001],front[1000001];
void dfs(int zl,int zr,int ql,int qr){
int m;
for(int i=zl;i<=zr;i++){
if(middle[i]==front[ql]) m=i;
}
if(m>zl) dfs(zl,m-1,ql+1,ql+m-zl);
if(m<zr) dfs(m+1,zr,ql+m-zl+1,qr);
printf("%c",front[ql]);
}
int main(){
scanf("%s%s",middle,front);
while(front[x]>='A'&&front[x]<='Z') x++;
dfs(0,x-1,0,x-1);
printf("\n");
return 0;
}
|
差异在这几句，左右子树的范围根据样例推断即可，上一题要前序所以将输出语句放在左右递归前，这次是后序所以放在最后
1
2
3
|
if(m>zl) dfs(zl,m-1,ql+1,ql+m-zl);
if(m<zr) dfs(m+1,zr,ql+m-zl+1,qr);
printf("%c",front[ql]);
|
P1364 医院设置
没思路…看了一下题解，知识点是树的重心。经过大模型讲解，我的想法是每个节点计算一遍距离，然后找到最小的。需要写两个dfs函数，一个遍历树的每一个节点，另一个计算当前节点距离
难点在于需要记录父节点，同时定义一个last变量防止死循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include <stdio.h>
#include <stdlib.h>
int n,ans,aaa=1000000000;
typedef struct node {
int l,r,data,f;
}node;
node m[1000001];
void far(int a,int way,int last){
if(a==0) return;
ans+=m[a].data*way;
if(last!=m[a].l){
far(m[a].l,way+1,a);
}
if(last!=m[a].r){
far(m[a].r,way+1,a);
}
if(last!=m[a].f){
far(m[a].f,way+1,a);
}
}
void dfs(int a){
if(a==0) return;
ans=0;
far(a,0,0);
if(ans<aaa) aaa=ans;
dfs(m[a].l);
dfs(m[a].r);
}
int main(){
scanf("%d",&n);
for(int i=0;i<=n;i++){
m[i].data=m[i].l=m[i].r=m[i].f=0;
}
for(int i=1;i<=n;i++){
scanf("%d%d%d",&m[i].data,&m[i].l,&m[i].r);
m[m[i].l].f=m[m[i].r].f=i;
}
dfs(1);
printf("%d\n",aaa);
return 0;
}
|
P1229 遍历问题
又是经典的两眼一黑。看了题解得知，当某个节点只有一个子节点时，生成的树有两种可能，那么题目就是找到只有一个子节点的节点个数n，答案就是2的n次方。在前序和后序的规律就是假如前序出现ab,后序出现ba,也就是说后序出现了前序连续两个字母的倒置，说明这是一个目标节点（我的大脑不够用，自己真看不出来这个规律）。这题的代码非常简单，主要是思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <stdio.h>
#include <stdlib.h>
int n=1,x;
char front[1000001],behind[1000001];
int main(){
scanf("%s%s",front,behind);
while(behind[x]>='a'&&behind[x]<='z') x++;
for(int i=0;i<x-1;i++){
for(int j=0;j<x-1;j++){
if(front[i]==behind[j+1]&&front[i+1]==behind[j]) n*=2;
}
}
printf("%d\n",n);
return 0;
}
|
P3884 [JLOI2009] 二叉树问题
宽度又没头绪了，经过大模型指点，创建一个宽度数组，每次遍历将数组索引为深度的值加一
我理解的距离是x走到y要经过的边数，看样例发现对不上，我才发现没好好读题，节点 u,v 之间的距离表示从 u 到 v 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。保证 u 是 v 的父结点。这两个没认真看导致两处小错误
点击查看错误代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <stdio.h>
#include <stdlib.h>
int n,ansd,answ,a,b,x,y,w[100001],ansjl=1000000000;
typedef struct node {
int l,r,f;
}node;
node m[1000001];
void dfs(int sy,int d){
if(sy==0) return;
if(d>ansd) ansd=d;
w[d]++;
dfs(m[sy].l,d+1);
dfs(m[sy].r,d+1);
}
void dist(int sy,int last,int mb,int jl){
if(sy==0) return;
if(sy==mb){
if(jl<ansjl) ansjl=jl;
return;
}
if(last!=m[sy].l) dist(m[sy].l,sy,mb,jl+1);
if(last!=m[sy].r) dist(m[sy].r,sy,mb,jl+1);
if(last!=m[sy].f) dist(m[sy].f,sy,mb,jl+1);
}
int main(){
scanf("%d",&n);
for(int i=0;i<=n;i++){
m[i].l=m[i].r=m[i].f=0;
}
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
if(a<b){
m[b].f=a;
if(m[a].l==0) m[a].l=b;
else m[a].r=b;
}else{
m[a].f=b;
if(m[b].l==0) m[b].l=a;
else m[b].r=a;
}
}
scanf("%d%d",&x,&y);
dfs(1,1);
dist(x,0,y,0);
for(int i=1;i<=ansd;i++) if(w[i]>answ) answ=w[i];
printf("%d\n%d\n%d\n",ansd,answ,ansjl);
return 0;
}
|
修改后通过评测
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include <stdio.h>
#include <stdlib.h>
int n,ansd,answ,a,b,x,y,w[1000001],ansjl=1000000000;
typedef struct node {
int l,r,f;
}node;
node m[1000001];
void dfs(int sy,int d){
if(sy==0) return;
if(d>ansd) ansd=d;
w[d]++;
dfs(m[sy].l,d+1);
dfs(m[sy].r,d+1);
}
void dist(int sy,int last,int mb,int jl){
if(sy==0) return;
if(sy==mb){
if(jl<ansjl) ansjl=jl;
return;
}
if(last!=m[sy].l) dist(m[sy].l,sy,mb,jl+1);
if(last!=m[sy].r) dist(m[sy].r,sy,mb,jl+1);
if(last!=m[sy].f) dist(m[sy].f,sy,mb,jl+2);
}
int main(){
scanf("%d",&n);
for(int i=0;i<=n;i++){
m[i].l=m[i].r=m[i].f=0;
}
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
m[b].f=a;
if(m[a].l==0) m[a].l=b;
else m[a].r=b;
}
scanf("%d%d",&x,&y);
dfs(1,1);
dist(x,0,y,0);
for(int i=1;i<=ansd;i++) if(w[i]>answ) answ=w[i];
printf("%d\n%d\n%d\n",ansd,answ,ansjl);
return 0;
}
|
P5076 【深基16.例7】普通二叉树（简化版）
二叉搜索树的模板，写的焦头烂额，基本流程是大模型给我讲一遍，自己写出来稀烂的代码，对着题解进行优化，然后丢给大模型找错误再照着修改。从逻辑到边界到判断问题全出了无数遍，最后代码写出来了，逻辑也懂，但再让我写一次就写不出来了。挫败感最强的一题
第一次经过大模型指点我写出来的代码是这样，定义一个总节点数变量ct,找到空节点就赋值并ct加一，然后设置为父节点的左或右子节点
问题来了，我这种写法会将树变成一个链表，解决方法是最后加上一行return sy;，也就是返回父节点，这样下次添加就会从根节点开始遍历
点击查看错误代码
1
2
3
4
5
6
7
8
9
10
|
int add(int sy,int x){
if(sy==0){
ct++;
m[ct].data=x;
return ct;
}
if(x<m[sy].data) m[sy].l=dfs(m[sy].l,x);
else if(x>m[sy].data) m[sy].r=dfs(m[sy].r,x);
}
add(ct,x);
|
这里是自己写的错误逻辑，错的没边
点击查看错误代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
//第一次
void qh(int sy,int x){
if(sy==0) return;
if(m[sy].data==x){
ansq=m[m[sy].l].data;
if(ansq==2147483647) ansq*=-1;
ansh=m[m[sy].r].data;
anspm=m[sy].pm+1;
return;
}
if(x<m[sy].data) qh(m[sy].l,x);
if(x>m[sy].data) qh(m[sy].r,x);
}
//第二次
int qx(int sy){
if(m[sy].r==0) return m[sy].data;
qx(m[sy].r);
}
int hx(int sy){
if(m[sy].l==0) return m[sy].data;
hx(m[sy].l);
}
int search(int sy,int x){
if(sy==0) return -1;
if(m[sy].data==x){
return sy;
}
if(x<m[sy].data) search(m[sy].l,x);
if(x>m[sy].data) search(m[sy].r,x);
}
//第三次
int qx(int sy,int x,int ans){
if(sy==0) return;
if(m[sy].data<x){
if(m[sy].data>ans) ans=m[sy].data;
qx(m[sy].l,x,ans);
}else qx(m[sy].l,x,ans);
}
|
最后的完整代码如下，之后如果用到这个题型，我大概也只能套模板来写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
#include <stdio.h>
#include <stdlib.h>
int q,op,ct,gen,x,ansq,ansh,anspm,qq,hh;
typedef struct node {
int l,r,cnt,data,size;
}node;
node m[1000001];
int add(int sy,int x){
if(sy==0){
ct++;
m[ct].data=x;
m[ct].size=m[ct].cnt=1;
return ct;
}
if(x==m[sy].data){
m[sy].cnt++;
}else if(x<m[sy].data){
m[sy].l=add(m[sy].l,x);
}else m[sy].r=add(m[sy].r,x);
m[sy].size=m[m[sy].l].size+m[m[sy].r].size+m[sy].cnt;
return sy;
}
int qx(int sy,int x){
int ans=-2147483647;
while(sy!=0){
if(m[sy].data<x){
ans=m[sy].data;
sy=m[sy].r;
}else sy=m[sy].l;
}
return ans;
}
int hx(int sy,int x){
int ans=2147483647;
while(sy!=0){
if(m[sy].data>x){
ans=m[sy].data;
sy=m[sy].l;
}else sy=m[sy].r;
}
return ans;
}
int xpm(int sy,int x){
if(sy==0) return 1;
if(x==m[sy].data) return m[m[sy].l].size+1;
if(x<m[sy].data){
return xpm(m[sy].l,x);
}else{
return xpm(m[sy].r,x)+m[m[sy].l].size+m[sy].cnt;
}
}
int pmx(int sy,int x){
if(sy==0) return 0;
if(x<=m[m[sy].l].size) return pmx(m[sy].l,x);
else if(x<=m[m[sy].l].size+m[sy].cnt) return m[sy].data;
else return pmx(m[sy].r,x-m[m[sy].l].size-m[sy].cnt);
}
int main(){
scanf("%d",&q);
for(int i=0;i<=q;i++){
m[i].l=m[i].r=m[i].cnt=0;
m[i].data=2147483647;
}
for(int i=1;i<=q;i++){
scanf("%d%d",&op,&x);
if(op==1){
anspm=xpm(gen,x);
printf("%d\n",anspm);
}else if(op==2){
anspm=pmx(gen,x);
printf("%d\n",anspm);
}else if(op==3){
ansq=qx(gen,x);
printf("%d\n",ansq);
}else if(op==4){
ansh=hx(gen,x);
printf("%d\n",ansh);
}else if(op==5){
gen=add(gen,x);
}
}
return 0;
}
|
P1395 会议
又是一道树的重心题目，这回重点理解了邻接表存储，然后把之前的暴力搜索优化了一些
在读入树的部分出了问题。一直以来我的想法是先输入的节点为父，后输入为子，或者值更小的为父，更大的为子，但实际上输入只代表两个节点之间有边连接
点击查看错误代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
if(a<b){
m[b].f=a;
if(m[a].l==0){
m[a].l=b;
}else m[a].r=b;
if(i==1) gen=a;
}else {
m[a].f=b;
if(m[b].l==0){
m[b].l=a;
}else m[b].r=a;
if(i=1) gen=b;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,x,y,a,b,ansy;
vector<int> adj[100001];
long long sizee[100001],ans,anss=10000000000000000;
void tree(int u,int v){
adj[u].push_back(v);
adj[v].push_back(u);
}
void lon(int sy,int way,int f){
if(sy==0) return;
ans+=way;
int size=1;
for(int v:adj[sy]){
if(v==f) continue;
lon(v,way+1,sy);
size+=sizee[v];
}
sizee[sy]=size;
}
void dfs(int sy,int as,int f){
if(sy==0) return;
if(as<anss) anss=as,ansy=sy;
else if(as==anss){
if(ansy>sy){
ansy=sy;
}
}
for(int v:adj[sy]){
if(v==f) continue;
dfs(v,as-sizee[v]*2+n,sy);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
tree(a,b);
}
lon(1,0,0);
dfs(1,ans,0);
printf("%d %d\n",ansy,anss);
return 0;
}
|
图
基础知识
图的存储
一般我们使用邻接表来存储图
1
2
3
4
5
6
7
|
#include <vector>
vector<int> adj[10000];
void map(int u,int v){
adj[u].push_back(v);
adj[v].push_back(u);
}
|
图分为有向图和无向图，无向图就是所有边连通的两个点可以互相走到对方，而有向图记录方向，只能按照方向走，不能反走。上面是无向图的存法，有向图将其中的反向push_back语句删除，只保留一个语句即可
BFS
bfs也就是广度优先搜索，一般用队列模拟。和dfs类似，假设某个地点有多条路可以走到，bfs就是先遍历当前节点下一步所有可能的节点，然后一层层遍历下去直到找到目标或者到达尽头。如果说dfs的查找方式是一条条的，那么bfs就是一层层。这里就是高中怎么也看不懂的部分，这次一定要攻克
代码逻辑就是从某个节点出发，一般按照从左到右的顺序，将它的所有子节点依次入队，然后不断取出队首的节点，遍历当前节点进行入队子节点的操作，直到队列变空
1
2
3
4
|
#include<queue>
void bfs(){
queue[int] p;
}
|
题目练习
P5318 【深基18.例3】查找文献
图的dfs和bfs,学会了如何在遍历图的时候不遍历重复节点，以及bfs原理和实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,a,b,aaa[1000001],dl[1000001];
vector<int> adj[100001];
void tree(int u,int v){
adj[u].push_back(v);
}
void dfs(int sy,int f){
if(sy==0) return;
printf("%d ",sy);
aaa[sy]=1;
for(int v:adj[sy]){
if(v==f||aaa[v]==1) continue;
dfs(v,sy);
}
}
void bfs(int sy){
int head=0,tail=0;
aaa[sy]=1;
dl[tail]=sy;
tail++;
while(head!=tail){
int u=dl[head];
printf("%d ",u);
for(int v:adj[u]){
if(aaa[v]==1) continue;
dl[tail]=v;
tail++;
aaa[v]=1;
}
head++;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
tree(a,b);
}
for(int i=1;i<=n;i++){
sort(adj[i].begin(),adj[i].end());
}
for(int i=0;i<=n;i++) aaa[i]=0;
dfs(1,0);
printf("\n");
for(int i=0;i<=n;i++) aaa[i]=0;
bfs(1);
printf("\n");
return 0;
}
|
P3916 图的遍历
最开始的逻辑是每个节点遍历一次，也就是暴力搜索，但这样只过了一半样例就超时了
最开始优化的思路是新建一个队列，存储每个节点对应的最大值，和之前利用队列找最大值是一样的逻辑，但经过思考发现不知道怎么实现，询问GPT后得知我的思路是错误的
点击查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,a,b,aaa[1000001],dl[1000001];
vector<int> adj[100001];
void map(int u,int v){
adj[u].push_back(v);
}
void bfs(int sy){
int head=0,tail=0,ans=0;
aaa[sy]=1;
dl[tail]=sy;
tail++;
while(head!=tail){
sy=dl[head];
if (sy>ans) ans=sy;
for(int v:adj[sy]){
if(aaa[v]==1) continue;
dl[tail]=v;
tail++;
aaa[v]=1;
}
head++;
}
printf("%d ",ans);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
map(a,b);
}
for(int i=1;i<=n;i++){
for(int i=0;i<=n;i++) aaa[i]=0;
bfs(i);
}
printf("\n");
return 0;
}
|
这道题的思路是反向图加染色。既然想找当前能走到的最大值，那么干脆反向建立图，然后从最大值开始遍历，被遍历到的节点的答案就是起点节点的值。然后将节点状态设置为已遍历，之后不再更新这个节点的答案，这就是染色。从最大值到最小值递减，每个值判断一下对应的节点是否被染色，没有的话就遍历并赋值一遍，最终得到答案。重点是if(aaa[v]==1) continue;这一句，作用是跳过已染色节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,a,b,aaa[1000001],maxx[100001];
vector<int> adj[100001];
void map(int u,int v){
adj[v].push_back(u);
}
void dfs(int sy,int ans){
aaa[sy]=1;
maxx[sy]=ans;
for(int v:adj[sy]){
if(aaa[v]==1) continue;
dfs(v,ans);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
map(a,b);
}
for(int i=n;i>=1;i--){
if(aaa[i]==1) continue;
dfs(i,i);
}
for(int i=1;i<=n;i++){
printf("%d ",maxx[i]);
}
printf("\n");
return 0;
}
|
P4017 最大食物链计数
这道题的核心是找到所有从开头节点到结尾节点的路径数量，而这里有一个规律，后一个节点的路径数量是它的所有前驱节点路径数量和。因此首先需要增加两个数组存储每个节点的出度和入度，入度为0的就是生产者也就是开头，出度为0就是消费者也就是结尾，然后用删除节点的方法来计算
将所有头节点依次加入队列，这时每个头节点到它自己的路径数量是1。出队一个节点，找到它的后继节点，将这些节点的路径数量加上当前出队节点的路径数。然后删除节点，也就是将后继节点的入度减一，入度为0的就是新头节点，将它们入队。就这样一直遍历完成整个图，最终所有尾节点的路径和就是答案
这里一定注意在所有可能超过数组边界的地方取模，否则看起来逻辑没问题但还是无法通过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n,m,r[1000001],c[1000001],aaa[1000001],a,b,ans;
vector<int> adj[100001];
void map(int u,int v){
adj[u].push_back(v);
c[u]++;
r[v]++;
}
void bfs(){
queue<int> q;
for(int i=1;i<=n;i++){
if(r[i]==0){
q.push(i);
aaa[i]=1;
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int v:adj[u]){
aaa[v]=(aaa[v]+aaa[u])%80112002;
r[v]--;
if(r[v]==0) q.push(v);
}
}
for(int i=1;i<=n;i++){
if(c[i]==0){
ans=(aaa[i]+ans)%80112002;
}
}
}
int main(){
// 输入建图
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
map(a,b);
}
bfs();
printf("%d\n",ans);
printf("\n");
return 0;
}
|
排序
学习记录
d1
总体感觉非常浮躁，写代码遇到很多粗心导致的小问题、大量边界问题和一点逻辑问题，都没有耐心去读，而是直接问ai。数组和链表的基本框架可以写出来了，但进阶一点的写法还是极其不熟练
d2
浮躁的问题好了很多，小问题大概减少了一半，但还有一些边界问题，大部分问题可以靠自己解决，但还是有一半是依靠ai。学会了动态数组、数组模拟链表和链表模拟数组的写法，基本框架已经可以几乎无障碍写出。当天的最后一道已经可以纯靠自己写出链表加动态数组
d3
数组和链表学差不多了，这一天学栈。状态不好所以学习时间不多，好在栈比较简单，写法上完全没有卡住我，逻辑上面有两题稍稍有点绕。现在基本不像第一天那么浮躁了，会出一点粗心导致的小问题，出现最多的是scanf输入没有加&，但基本都能自己解决。大模型只起到给我测试样例，偶尔小提示的作用。看来之前的浮躁应该是基础太薄弱加上没进入状态的缘故
d4
今天学队列，理解不难，但真正用到逻辑的时候有点想不明白，在边界上经常犯错。今天用大模型比昨天多，因为好几次被逻辑问题卡住半小时，可能还没有彻底掌握吧，明天应该还要继续学一天
d5
之前确实低估队列了，这部分的逻辑是我的弱项，每道题几乎都卡半小时以上，然后焦头烂额的找大模型给我指点来解决问题。但了解原理并记住模板后，之后的题目就是套路了。明天准备开始学树
d6
昨天休息了一天，今天继续。树并没有想象中那么难，递归听起来吓人，实际debug比之前的队列还简单，也许是因为之前ctf做过涉及树的题目，或者是树只做了几个入门题目的缘故。现在才知道树的遍历就是dfs,看来高中没学会纯纯吃了没有理论基础的亏。今天有点偷懒了效率不高，只做了三道入门题目，准备明天死磕中等难度的题目
d7
今天写的是难一点的模板题，题目看到了就两眼一黑，完全不知道怎么实现。有几道题哪怕规律找到了代码都不知道怎么写，所以参考了题解和大模型，debug也因此有一半交给大模型解决了。不过基本原理搞明白以后写代码还是比较顺的。感觉今天又有点浮躁起来，也许是熟练度问题？希望如此吧
d8
树的题型是真的多，已经是第三天了，还是能见到新题型。每次见到新题型我就会选择查看题解来掌握算法，最后靠大模型的少量辅助自己写出来。一直重复这种模式导致我的心有点虚，不知道是不是真的学会了。今天学习时间不多，只写完一道半题目，二叉搜索树实在有点难
d9
二叉搜索树太难，卡了两天还是没法靠自己写出来，只能了解了一下原理，靠大模型辅助写完了，学力竭了。这三天难度太高，挫败感太强，学习意愿和效率严重下降
after
回学校了，进入了零散学习的状态，效率极差，因为有作业和课程，还有马上截止的实验，所以一直没怎么学，一周才写完一道题。而且学的特别难受，经常是写几句就要下课了，我只好停下来。之后还要优先学操作系统，也不知道最后留给数据结构的时间有多少
week2
这周零散的学图，还在算法学习过程中，因此需要大模型给一些参考和模板。我上课时并不听课，而是自己在下面写代码，可当被叫上去画线索树时我完全不会，问其他问题也经常答不上来，不禁让我对自己产生了一丝怀疑
week4
回校一个月了
