^-^
人工智能、计算机、机器学习、linux、程序员
浙大PAT考试数据结构与算法模板整理
最近更新：2022-02-26   |   字数总计：15.9k   |   阅读估时：80分钟   |   阅读量：次
  1. 字符串
    1. 字符串类型转换
      1. 01 to_string()
      2. 02 stoi()和atoi()
      3. 03 string类的方法c_str()
      4. 04 string类的方法find()
      5. 05 string类的方法substr()
    2. KMP
  2. 排序
    1. 堆排序
    2. 快速排序
    3. 线性第K大(快排思想应用)
    4. 归并排序
    5. 判断插入排序
  3. 二分
    1. 整数二分
  4. 链表
    1. 单链表
    2. 双链表
  5. 栈和队列
    1. 单调栈
    2. 单调队列
  6. 树
    1. 反转二叉树
    2. 构建二叉搜索树
    3. 判断完全二叉树
    4. 二叉树遍历
      1. 01 先序遍历
      2. 02 中序遍历
      3. 03 后序遍历
    5. 重建二叉树
      1. 01 先序+后序(不唯一)
      2. 02 先序+中序(唯一)
      3. 03 后序+中序(唯一)
    6. 手动实现AVL树插入
    7. 判断红黑树
    8. DFS判断一个先序遍历是否为堆
    9. 最低公共祖先
    10. 并查集
      1. 01 朴素版本
      2. 02 合并时更新额外信息
  7. 图
    1. 最短路径与扩展问题
      1. 01 朴素dijkstra
      2. 02 堆优化版dijkstra
      3. 03 对最短路选择的扩展
      4. 04 对最短路信息的扩展
    2. 判断哈密顿回路
    3. 欧拉路径
    4. 顶点覆盖
    5. 最大团
    6. 拓扑排序
    7. 染色问题
      1. 01 二分图染色
      2. 02 判断染色方案
  8. 数学
    1. 高精度
      1. 01 高精度加法
      2. 02 高精度减法
      3. 03 高精度乘法
      4. 04 高精度除法*
    2. 分解质因子
    3. 分数运算(和差积商)
    4. 素数筛
      1. 01 朴素筛法
      2. 02 埃氏筛法
      3. 03 线性筛
    5. 快速幂
  9. 动态规划
    1. 背包问题
      1. 01背包
      2. 02 硬币找零
      3. 03 完全背包
      4. 04 整数分解
      5. 05 多重背包*
    2. 最大子序列和
    3. 最长公共子序列
      1. 01 最长公共子序列
      2. 02 变种(一个字符匹配多个字符)
    4. 状态机模型

之前把浙大PAT甲级题库刷完了，整理一下PAT的考点

题目来源于ACwing网站

字符串

字符串类型转换

01 to_string()

这个太常用了不多说了

1
2
3
4
5
6
7
int a = 4;
double b = 3.14;
string str1, str2;
str1 = to_string(a);
str2 = to_string(b);
cout << str1 << endl;
cout << str2 << endl;

02 stoi()和atoi()

C++11包含在#include。作用是将字符串转化为int型。区别是stoi的形参直接传入string类型即可，而atoi的形参是const char*

1
2
3
4
5
6
string s1("1234567");
char* s2 = "1234567";
int a = stoi(s1);
int b = atoi(s2);
cout << a << endl;
cout << b << endl;

进化版：stol(),stoll(),stoul(),stoull(),atol(),atoll(),atoul(),atoull()

l为long int，ll为long long，ul为unsigned long int，ull为unsigned long long

03 string类的方法c_str()

c_str()就是将C++的string转化为C的字符串数组，c_str()生成一个const char *指针，指向字符串的首地址。

1
2
3
4
char *p=s[10];
string a=“welcome”;
strcpy(p,a.c_str());
cout<<p;

如果需要使用C语言printf的格式化输出string时可以使用，很方便，比如

1
2
string name="PAT";
printf("%s\n",name.c_str());

04 string类的方法find()

在string中找到目标字符的位置，返回数组下标

1
2
string s = "hello world";
cout << s.find("e") << endl;//结果为1

未找到会返回一个特殊的标志npos(一个很大的数字)

1
2
3
string s = "hello world";
if (s.find("a") == s.npos)
    cout << "not found" << endl;

从指定位置开始查找

1
2
3
string s = "hello world";
//从下标为5的数组位置开始查找(也就是忽略前面的)
cout << s.find("l",5) << endl;//结果为9

05 string类的方法substr()

截取子串

单参数形式(给出截取开始的位置，末尾默认为原string末尾)

1
2
3
string s("12345abcd");
string a = s.substr(5);//获得字符串s中从下标为5开始一直到末尾的字符串
cout << a << endl;//结果为abcd

双参数形式(给出截取开始的位置，并给出截取长度)

1
2
3
string s("12345abcd");
string a = s.substr(0,5);//获得字符串s中从下标为0开始的长度为5的字符串
cout << a << endl;//结果为12345

KMP

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式

第一行输入整数N，表示字符串P的长度。

第二行输入字符串P。

第三行输入整数M，表示字符串S的长度。

第四行输入字符串S。

输出格式

共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。

数据范围

1≤N≤10^5
1≤M≤10^6

输入样例

1
2
3
4
3
aba
5
ababa

输出样例

1
0 2

代码

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 <iostream>
using namespace std;
const int N=1e6+10,M=1e5+10;

char t[N],p[M];
int n,m;

int* build(char *p){
    int *ne=new int[m];
    int i=0,j=-1;
    ne[0]=-1;
    while(i<m-1){
        if(j<0||p[i]==p[j]){
            i++,j++;
            ne[i]=j;
        }
        else j=ne[j];
    }
    return ne;
}

void match(char *t,char* p){
    int *ne=build(p);
    int i=0,j=0;
    while(i<n){
        while(j<m&&i<n)
            if(j<0||t[i]==p[j])
                i++,j++;
            else j=ne[j];
        if(j==m){    
            printf("%d ",i-j);
            i--;
            j=ne[j-1];
        }
    }
}

int main(){
    scanf("%d%s%d%s",&m,p,&n,t);
    match(t,p);
}

排序

PAT常考的排名方式(同分布排名)

1
2
3
4
5
6
sort(a.begin(),a.end());
for(int i=0;i<a.size();i++){
    if(!i||a[i].grade!=a[i-1].grade)
      a[i].rank=i+1;
   else a[i].rank=a[i-1].rank;
}

堆排序

输入一个长度为n的整数数列，从小到大输出前m小的数。

输入格式

第一行包含整数n和m。

第二行包含n个整数，表示整数数列。

输出格式

共一行，包含m个整数，表示整数数列中前m小的数。

输入样例

1
2
5 3
4 5 1 3 2

输出样例

1
1 2 3

代码

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
#include <iostream>
using namespace std;
const int maxn=1e5+10;

int h[maxn],size;

void down(int x){
    int t=x;
    if(2*x<=size&&h[2*x]<h[t]) t=2*x;
    if(2*x+1<=size&&h[2*x+1]<h[t]) t=2*x+1;
    if(t!=x){
        swap(h[t],h[x]);
        down(t);
    }
}

void up(int x){
    while(x/2&&h[x]<h[x/2]){
        swap(h[x],h[x/2]);
        x/=2;
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    size=n;
    for(int i=1;i<=n;i++)
        scanf("%d",&h[i]);
    for(int i=n/2;i>0;i--)
        down(i);
    while(m--){
        printf("%d ",h[1]);
        h[1]=h[size--];
        down(1);
    }
    return 0;
}

快速排序

这里默认为升序排序，降序只要对比较的符号进行调整就可以了

快速排序分为三个过程：

  1. 将数列划分为两部分（不是直接分，要求保证相对大小关系）
  2. 递归到两个子序列中分别进行快速排序
  3. 不用合并，因为此时数列已经完全有序

首先对于第一步来说我们需要先找到一个基准值（基准值用于将整个数组切分成小和大两部分）

然后使用两个指针和来进行操作，大概原理就是先将指向的位置，指向的位置，然后使用do while循环使i指针疯狂向前直到遇到第一个比基准值大的数字停下，接下来对j指针也同样操作使其停在第一个比基准值小的数值上，然后互换，的数字。一直操作到ij指针相遇，那么由于对一路上不符合条件的数字都进行了互换，所以i和j相遇的就是整个数组的切分点。

OK我们找到了切分点，接下来就是递归操作(l,j),(j+1,r)了

注意事项：当切分点取a[l]时，递归取(l,j),(j+1,r)。当切分点取a[r]时，递归取(l,i-1),(i,r)。当切分点其余数字时，递归二者皆可(避免出现死循环)

每个递归直到l>=r停止，因为一个点是不需要再“划分”的

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 <iostream>
using namespace std;
const int maxn=1e5+10;

int a[maxn],n;

void quick_sort(int l,int r){
    if(l>=r) return;
    int x=a[l],i=l-1,j=r+1;
    while(i<j){
        do i++; while(a[i]<x);
        do j--; while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    quick_sort(l,j);
    quick_sort(j+1,r);
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    quick_sort(0,n-1);
    for(int i=0;i<n;i++) printf("%d ",a[i]);
    return 0;
}

线性第K大(快排思想应用)

找第 k 大的数（K-th order statistic），最简单的方法是先排序，然后直接找到第 k 大的位置的元素。这样做的时间复杂度是O(nlogn)，对于这个问题来说很不划算。事实上，我们有时间复杂度 的解法。

考虑快速排序的划分过程，在快速排序的“划分”结束后，我们会将数组分成两部分，我们可以通过检查k是否落在左边的范围内来减少复杂度，在排序的途中解决这个问题，当然这时候快排就不会全部排完了，而是找到了k就中途退出

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 <iostream>
using namespace std;
const int maxn=1e5+10;

int a[maxn];

int quick_sort(int l,int r,int k){
    if(l==r&&l==k) return a[k];
    int x=a[l],i=l-1,j=r+1;
    while(i<j){
        do i++; while(a[i]<x);
        do j--; while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    if(l<=k&&k<=j) quick_sort(l,j,k);
    else quick_sort(j+1,r,k);
}

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    printf("%d\n",quick_sort(0,n-1,k-1));
    return 0;
}

归并排序

归并排序是一种采用了 分治 思想的排序算法，其本质是一种 CDQ 分治。

归并排序分为三个过程：

  1. 将数列随意划分为两部分（在均匀划分时时间复杂度为 O(nlogn)）
  2. 递归地分别对两个子序列进行归并排序
  3. 合并两个子序列

不难发现，归并排序的核心是如何合并两个子序列，前两步都很好实现。

其实合并的时候也不难操作。注意到两个子序列在第二步中已经保证了都是有序的了，第三步中实际上是想要把两个 有序 的序列合并起来。

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 <iostream>
using namespace std;
const int maxn=1e5+10;

int a[maxn],t[maxn];

void merge_sort(int l,int r){
    if(l>=r) return;
    int mid=l+r>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]) t[k++]=a[i++];
        else t[k++]=a[j++];
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    for(int i=l,j=0;j<k;i++,j++)
        a[i]=t[j];
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    merge_sort(0,n-1);
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}

判断插入排序

PAT出过两次的考点，判断一个排到一半的排序是否是插入排序还是别的排序（PAT会保证答案唯一）

一般可以使用这个方法，将数组分成两段，一段是排好序的（非降序），另一段是没有排好序的，我们找到没排序的那一段的起点，往下比对是否与原数组相同即可，不同就不是插入排序（因为插入排序是不会改变未排序的数组元素的顺序的）

1
2
3
4
5
6
7
8
9
10
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
int p=2;
while(p<=n&&b[p]>=b[p-1]) p++;
int k=p;
while(p<=n&&a[p]==b[p]) p++;
if(p==n+1){
  puts("Insertion Sort");
  while(k>1&&b[k]<b[k-1]) swap(b[k],b[k-1]),k--;
}

二分

整数二分

二分搜索，也称折半搜索、二分查找，是用来在一个有序数组中查找某一元素的算法。

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需要到右侧去找就好了；如果中间元素大于所查找的值，同理，右侧的只会更大而不会有所查找的元素，所以只需要到左侧去找。

在二分搜索过程中，每次都把查询的区间减半，因此对于一个长度为n的数组，至多会进行O(logn)次查找。

下面是第一种整数二分形式，用于找到>=x的区间的第一个数

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

下面是第二种整数二分形式，用于找到<=x的最后一个数

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

链表

单链表

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 <iostream>
using namespace std;
const int maxn=1e5+10;

int e[maxn],ne[maxn],head,idx;

void init(){
    head=-1;
    idx=0;
}

void add_to_head(int x){
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}

void add(int k,int x){
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}

void remove(int k){
    ne[k]=ne[ne[k]];
}

int main(){
    int n,k,x;
    char c;
    init();
    cin>>n;
    while(n--){
        cin>>c;
        if(c=='H'){
            cin>>x;
            add_to_head(x);
        }
        else if(c=='I'){
            cin>>k>>x;
            add(k-1,x);
        }
        else{
            cin>>k;
            if(!k) head=ne[head];
            else remove(k-1);
        }
    }
    for(int i=head;i!=-1;i=ne[i]){
        if(i!=head) cout << ' ';
        cout << e[i];
    }
    cout << endl;
    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
#include <iostream>
using namespace std;
const int maxn=1e5+10;

int l[maxn],r[maxn],e[maxn],idx;

void init(){
    r[0]=1;
    l[1]=0;
    idx=2;
}

void insertR(int k,int x){
    e[idx]=x;
    l[idx]=k;
    r[idx]=r[k];
    l[r[k]]=idx;
    r[k]=idx++;
}

void insertL(int k,int x){
    insertR(l[k],x);
}

void addL(int x){
    insertR(0,x);
}

void addR(int x){
    insertL(1,x);
}


void remove(int k){
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}

int main(){
    int n,k,x;
    string s;
    init();
    cin>>n;
    while(n--){
        cin>>s;
        if(s=="L"){
            cin>>x;
            addL(x);
        }
        else if(s=="R"){
            cin>>x;
            addR(x);
        }
        else if(s=="D"){
            cin>>k;
            remove(k+1);
        }
        else if(s=="IL"){
            cin>>k>>x;
            insertL(k+1,x);
        }
        else{
            cin>>k>>x;
            insertR(k+1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i]){
        if(i!=r[0]) cout << ' ';
        cout << e[i];
    }
    cout << endl;
    return 0;

栈和队列

单调栈

给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。

输入格式

第一行包含整数N，表示数列长度。

第二行包含N个整数，表示整数数列。

输出格式

共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。

输入样例

1
2
5
3 4 2 7 5

输出样例

1
-1 3 -1 2 2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int maxn=1e5+10;

int s[maxn],t;

int main(){
    int n,x;
    cin>>n;
    while(n--){
        cin>>x;
        while(t&&s[t-1]>=x) t--;
        if(t) printf("%d ",s[t-1]);
        else printf("-1 ");
        s[t++]=x;
    }
    puts("");
    return 0;
}

单调队列

给定一个大小为n≤10^6的数组。

有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为[1 3 -1 -3 5 3 6 7]，k为3。

窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7

您的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数n和k，分别代表数组长度和滑动窗口的长度。

第二行有n个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例

1
2
8 3
1 3 -1 -3 5 3 6 7

输出样例

1
2
-1 -3 -3 -3 3 3
3 3 5 5 6 7

代码

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 <iostream>
using namespace std;
const int maxn=1e6+10;

int a[maxn],q[maxn],head,rear;

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++){
        if(rear>head&&i-k+1>q[head]) head++;
        while(rear>head&&a[q[rear-1]]>=a[i]) rear--;
        q[rear++]=i;
        if(i-k+1>=0) printf("%d ",a[q[head]]);
    }
    puts("");
    head=rear=0;
    for(int i=0;i<n;i++){
        if(rear>head&&i-k+1>q[head]) head++;
        while(rear>head&&a[q[rear-1]]<=a[i]) rear--;
        q[rear++]=i;
        if(i-k+1>=0) printf("%d ",a[q[head]]);
    }
    puts("");
    return 0;
}

树

反转二叉树

很简单了不多解释

1
2
3
4
5
6
void dfs_reverse(int u){
    if(u==-1) return;
    dfs_reverse(l[u]);
    dfs_reverse(r[u]);
    swap(l[u],r[u]);
}

构建二叉搜索树

这里指的是从空树一个个插入结点构建二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
const int maxn=1010;

int l[maxn],r[maxn],e[maxn],idx;

void insert(int& u,int x){
    if(!u){
        u=++idx;
        e[u]=x;
    }
    else if(x<=e[u]) insert(l[u],x);//注意题干中是小于还是小于等于
    else insert(r[u],x);
}

判断完全二叉树

用数组存储，看n个结点是否分布在1到n的位置，如果没有就不是完全二叉树

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
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn=1010;

int l[maxn],r[maxn],cnt[maxn];
int maxk,maxid;

void dfs(int u,int k){
    if(u==-1) return;
    if(k>maxk){
        maxk=k;
        maxid=u;
    }
    dfs(l[u],k*2);
    dfs(r[u],k*2+1);
}

int main(){
    int n;
    string x,y;
    memset(l,-1,sizeof l);
    memset(r,-1,sizeof r);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        if(x!="-") l[i]=stoi(x),cnt[l[i]]++;
        if(y!="-") r[i]=stoi(y),cnt[r[i]]++;
    }
    int root=0;
    while(cnt[root]) root++;
    dfs(root,1);
    if(maxk==n) printf("YES %d\n",maxid);
    else printf("NO %d\n",root);
    return 0;
}

二叉树遍历

首先是固定的套路

1
2
3
4
5
6
7
8
#include <iostream>
#include <stack>
using namespace std;

struct Node{
    int val;
    Node* lchild,*rchild;
};

01 先序遍历

(三种方法，难度从低到高，性能从劣到优)

第一种：使用递归的方法

1
2
3
4
5
6
7
8
9
void preorder1(Node *node){
    if(node==NULL)
        return;
    printf("%d\n",node->val);
    if(node->lchild!=NULL)
        preorder1(node->lchild);
    if(node->rchild!=NULL)
        preorder1(node->rchild);
}

第二种：使用栈辅助递归降低复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
void preorder2(Node *node){
    stack<Node*> sta;
    if(node!=NULL)
        sta.push(node);
    while(!sta.empty()){
        Node* p=sta.top();sta.pop();
        printf("%d\n",p->val);
        if(node->rchild!=NULL)
            sta.push(p->rchild);
        if(node->lchild!=NULL)
            preorder2(node->lchild);
    }
}

第三种：纯用栈遍历，沿左子树链下行，途中将右子树压栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void visitAlongLeftBranch(Node* node,stack<Node*>& sta){
    while(node!=NULL){
        printf("%d\n",node->val);
        sta.push(node->rchild);
        node=node->lchild;
    }
}

void preorder3(Node* node){
    stack<Node*> sta;
    while(true){
        visitAlongLeftBranch(node,sta);
        if(sta.empty())
            break;
        node=sta.top();
        sta.pop();
    }
}

02 中序遍历

(两种方法，难度从低到高，性能从劣到优)

第一种：使用递归的方法

1
2
3
4
5
6
7
8
9
void inorder1(Node* node){
    if(node==NULL)
        return;
    if(node->lchild!=NULL)
        inorder1(node->lchild);
    printf("%d\n",node->val);
    if(node->rchild!=NULL)
        inorder1(node->rchild);
}

第二种：纯用栈遍历，将左子树压栈，一直到最左边的叶子节点，从栈中弹出节点访问并进入右子树，反复该过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void goAlongLeftBranch(Node* node,stack<Node*>& sta){
    while(node!=NULL) {
        sta.push(node);
        node=node->lchild;
    }
}

void inorder2(Node* node){
    stack<Node*> sta;
    while(true){
        goAlongLeftBranch(node,sta);
        if(sta.empty())
            break;
        node=sta.top();
        sta.pop();
        printf("%d\n",node->val);
        node=node->rchild;
    }
}

03 后序遍历

(后序的栈辅助比较复杂，不写了)

使用递归的方法

1
2
3
4
5
6
7
8
9
void postorder(Node *node){
    if(node==NULL)
        return;
    printf("%d\n",node->val);
    if(node->rchild!=NULL)
        postorder1(node->rchild);
    if(node->lchild!=NULL)
        postorder1(node->lchild);
}

重建二叉树

01 先序+后序(不唯一)

假设一个二叉树上所有结点的权值都互不相同。

我们可以通过后序遍历和中序遍历来确定唯一二叉树。

也可以通过前序遍历和中序遍历来确定唯一二叉树。

但是，如果只通过前序遍历和后序遍历，则有可能无法确定唯一二叉树。

现在，给定一组前序遍历和后序遍历，请你输出对应二叉树的中序遍历。

如果树不是唯一的，则输出任意一种可能树的中序遍历即可。

输入格式

第一行包含整数 N，表示结点数量。

第二行给出前序遍历序列。

第三行给出后序遍历序列。

一行中的数字都用空格隔开。

输出格式

首先第一行，如果树唯一，则输出 Yes，如果不唯一，则输出 No。

然后在第二行，输出树的中序遍历。

注意，如果树不唯一，则输出任意一种可能的情况均可。

数据范围

1≤N≤30

输入样例1

1
2
3
7
1 2 3 4 6 7 5
2 6 7 4 5 3 1

输出样例1

1
2
Yes
2 1 6 4 7 3 5

输入样例2

1
2
3
4
1 2 3 4
2 4 3 1

输出样例2

1
2
No
2 1 3 4

代码

直接暴力枚举左子树和右子树的长度即可

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
#include <iostream>
using namespace std;
const int maxn=40;

int pre[maxn],post[maxn];

int dfs(int l1,int r1,int l2,int r2,string& s){
    if(l1>r1) return 1;
    if(pre[l1]!=post[r2]) return 0;
    int cnt=0;
    for(int i=l1;i<=r1;i++){
        string ls,rs;
        int lcnt=dfs(l1+1,i,l2,l2+i-l1-1,ls);
        int rcnt=dfs(i+1,r1,l2+i-l1-1+1,r2-1,rs);
        if(lcnt&&rcnt){
            s=ls+to_string(pre[l1])+' '+rs;
            cnt+=lcnt*rcnt;
            if(cnt>1) break;
        }
    }
    return cnt;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>pre[i];
    for(int i=0;i<n;i++) cin>>post[i];
    string s;
    int cnt=dfs(0,n-1,0,n-1,s);
    if(cnt>1) puts("No");
    else puts("Yes");
    s.pop_back();
    cout << s << endl;
    return 0;
}

02 先序+中序(唯一)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int pre[maxn],in[maxn];
unordered_map<int,int> pos,l,r;

int build(int pl,int pr,int il,int ir){
    int root=pre[pl],k=pos[root];
    if(k>il) l[root]=build(pl+1,pl+k-il,il,k-1);
    if(k<ir) r[root]=build(pl+k-il+1,pr,k+1,ir);
    return root;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>pre[i];
    for(int i=0;i<n;i++) cin>>in[i],pos[in[i]]=i;
    int root=build(0,n-1,0,n-1);
    return 0;
}

03 后序+中序(唯一)

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 <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

unordered_map<int,int> l,r,pos;
int post[maxn],in[maxn];

int build(int il,int ir,int pl,int pr){
    int root=post[pr];
    int k=pos[root];
    if(k>il) l[root]=build(il,k-1,pl,pl+k-1-il);
    if(k<ir) r[root]=build(k+1,ir,pl+k-1-il+1,pr-1);
    return root;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>in[i],pos[in[i]]=i;
    for(int i=0;i<n;i++) cin>>post[i];
    int root=build(0,n-1,0,n-1);
    return 0;
}

手动实现AVL树插入

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>
using namespace std;
const int maxn=50;

int l[maxn],r[maxn],e[maxn],h[maxn],idx;

void update(int u){
    h[u]=max(h[l[u]],h[r[u]])+1;
}

void L(int& u){
    int p=r[u];
    r[u]=l[p],l[p]=u;
    update(u),update(p);
    u=p;
}

void R(int& u){
    int p=l[u];
    l[u]=r[p],r[p]=u;
    update(u),update(p);
    u=p;
}

int get_balance(int u){
    return h[l[u]]-h[r[u]];
}

void insert(int& u,int x){
    if(!u) u=++idx,e[u]=x;
    else if(x<e[u]){
        insert(l[u],x);
        if(get_balance(u)==2){
            if(get_balance(l[u])==1)
                R(u);
            else L(l[u]),R(u); 
        }
    }
    else{
        insert(r[u],x);
        if(get_balance(u)==-2){
            if(get_balance(r[u])==-1)
                L(u);
            else R(r[u]),L(u);
        }
    }
    update(u);
}

int main(){
    int n,x,root=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        insert(root,x);
    }
    return 0;
}

判断红黑树

数据结构中有一类平衡的二叉搜索树，称为红黑树。

它具有以下 5 个属性：

  • 节点是红色或黑色。
  • 根节点是黑色。
  • 所有叶子都是黑色。（叶子是 NULL节点）
  • 每个红色节点的两个子节点都是黑色。
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

现在，对于每个给定的二叉搜索树，请你判断它是否是合法的红黑树。

注意

给定的前序遍历序列可能不合法，即无法构建出合法二叉搜索树。

输入格式

第一行包含整数 K，表示共有 K 组测试数据。

每组测试数据，第一行包含整数 N，表示二叉搜索树的节点数量。

第二行给出了这个二叉搜索树的前序遍历。

注意，虽然所有节点的权值都为正，但是我们使用负号表示红色节点。

各节点权值互不相同。

输入样例与题目中三个图例相对应。

输出格式

对于每组数据，如果是合法红黑树则输出一行 Yes，否则输出一行 No。

数据范围

1≤K≤30
1≤N≤30

输入样例

1
2
3
4
5
6
7
3
9
7 -2 1 5 -4 -11 8 14 -15
9
11 -2 1 -7 5 -4 8 14 -15
8
10 -7 5 -6 8 15 -11 17

输出样例

1
2
3
Yes
No
No

代码

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 <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int maxn=50;

int pre[maxn],in[maxn];
bool ans;
unordered_map<int,int> pos;

int build(int il,int ir,int pl,int pr,int& sum){
    int root=pre[pl];
    int k=pos[abs(root)];
    if(k<il||k>ir){
        ans=false;
        return 0;
    }
    int l=0,r=0,ls=0,rs=0;
    if(k>il) l=build(il,k-1,pl+1,pl+1+k-1-il,ls);
    if(k<ir) r=build(k+1,ir,pl+1+k-1-il+1,pr,rs);
    if(ls!=rs) ans=false;
    sum=ls;
    if(root<0){
        if(l<0||r<0) ans=false;
    }
    else sum++;
    return root;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        int n,sum=0;
        pos.clear();
        ans=true;
        cin>>n;
        for(int i=0;i<n;i++) cin>>pre[i],in[i]=abs(pre[i]);
        sort(in,in+n);
        for(int i=0;i<n;i++) pos[in[i]]=i;
        int root=build(0,n-1,0,n-1,sum);
        if(root<0) ans=false;
        if(ans) puts("Yes");
        else puts("No");
    }
    return 0;
}

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
28
29
30
31
32
33
#include <iostream>
#include <vector>
using namespace std;
const int maxn=1010;

int h[maxn],n,gt,lt;
vector<int> v;

void dfs(int u){
    v.push_back(h[u]);
    if(u*2>n){
        cout << v[0];
        for(int i=1;i<v.size();i++){
            cout << ' ' << v[i];
            if(v[i]<=v[i-1]) gt=1;
            else lt=1;
        }
        cout << endl;
    }
    if(u*2+1<=n) dfs(u*2+1);
    if(u*2<=n) dfs(u*2);
    v.pop_back();
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    dfs(1);
    if(lt&&gt) cout << "Not Heap" << endl;
    else if(lt) cout << "Min Heap" << endl;
    else if(gt) cout << "Max Heap" << endl;
    return 0;
}

最低公共祖先

树中两个结点 U 和 V 的最低公共祖先（LCA）是指同时具有 U 和 V 作为后代的最深结点。

给定二叉树中的任何两个结点，请你找到它们的 LCA。

输入格式

第一行包含两个整数 M 和 N，分别表示询问结点对数以及二叉树中的结点数量。

接下来两行，每行包含 N 个不同的整数，分别表示二叉树的中序和前序遍历。

保证二叉树可由给定遍历序列唯一确定。

接下来 M 行，每行包含两个整数 U 和 V，表示一组询问。

所有结点权值均在 int 范围内。

输出格式

对于每对给定的 U 和 V，输出一行结果。

如果 U 和 V 的 LCA 是 A，且 A 不是 U 或 V，则输出 LCA of U and V is A.。

如果 U 和 V 的 LCA 是 A，且 A 是 U 或 V 中的一个，则输出 X is an ancestor of Y.，其中 X 表示 A，Y 表示另一个结点。

如果 U 或 V 没有在二叉树中找到，则输出 ERROR: U is not found. 或 ERROR: V is not found. 或 ERROR: U and V are not found.。

数据范围

1≤M≤1000
1≤N≤10000

输入样例

1
2
3
4
5
6
7
8
9
6 8
7 2 3 4 6 5 1 8
5 3 7 2 6 4 8 1
2 6
8 1
7 9
12 -3
0 8
99 99

输出样例

1
2
3
4
5
6
LCA of 2 and 6 is 3.
8 is an ancestor of 1.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

代码

PAT不会要求用倍增的LCA算法，基本上只要朴素的往上爬的算法就可以了

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
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int maxn=1e4+10;

int f[maxn],pre[maxn],in[maxn],s[maxn],d[maxn];
unordered_map<int,int> pos;

int build(int il,int ir,int pl,int pr,int x){
    int root=pre[pl],k=root;
    d[root]=x;
    if(k>il) f[build(il,k-1,pl+1,pl+1+k-1-il,x+1)]=root;
    if(k<ir) f[build(k+1,ir,pl+1+k-1-il+1,pr,x+1)]=root;
    return root;
}

int main(){
    int n,m,a,b;
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
        pos[s[i]]=i;
        in[i]=i;
    }
    for(int i=0;i<n;i++){
        cin>>pre[i];
        pre[i]=pos[pre[i]];
    }
    build(0,n-1,0,n-1,0);
    while(m--){
        cin>>a>>b;
        if(!pos.count(a)&&!pos.count(b)) printf("ERROR: %d and %d are not found.\n",a,b);
        else if(pos.count(a)&&pos.count(b)){
            int x=pos[a],y=pos[b];
            while(x!=y){
                if(d[x]>d[y]) x=f[x];
                else y=f[y];
            }
            if(x==pos[a]) printf("%d is an ancestor of %d.\n",a,b);
            else if(x==pos[b]) printf("%d is an ancestor of %d.\n",b,a);
            else printf("LCA of %d and %d is %d.\n",a,b,s[x]);
        }
        else if(!pos.count(a)) printf("ERROR: %d is not found.\n",a);
        else printf("ERROR: %d is not found.\n",b);
    }
    return 0;
}

并查集

01 朴素版本

一共有n个数，编号是1~n，最开始每个数各自在一个集合中。

现在要进行m个操作，操作共有两种：

  1. “M a b”，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
  2. “Q a b”，询问编号为a和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
#include <iostream>
using namespace std;
const int maxn=1e5+10;

int p[maxn];

int find(int x){
    return p[x]=x==p[x]?x:find(p[x]);
}

int main(){
    int n,m,a,b;
    char op[2];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        p[i]=i;
    while(m--){
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='M') p[find(a)]=find(b);
        else
            find(a)==find(b)?puts("Yes"):puts("No");
    }
    return 0;
}

02 合并时更新额外信息

其实就是写一个merge函数，更新一些题目中要求的信息，比如说下面就是更新并查集中结点个数的merge函数

1
2
3
4
5
6
7
8
9
10
11
12
void init(){
    for(int i=0;i<maxn;i++)
        f[i]=i,cnt[i]=1;
}

void merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx!=fy){
        f[fx]=fy;
        cnt[fy]+=cnt[fx];
    }
}

图

最短路径与扩展问题

01 朴素dijkstra

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
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=510,inf=0x3f3f3f3f;

int g[maxn][maxn],vis[maxn],d[maxn],m,n;

void dijkstra(){
    d[1]=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&(t==-1||d[t]>d[j]))
                t=j;
        vis[t]=1;
        for(int j=1;j<=n;j++)
            d[j]=min(d[j],d[t]+g[t][j]);
    }
}

int main(){
    memset(g,0x3f,sizeof g);
    memset(d,0x3f,sizeof d);
    int a,b,c;
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }
    dijkstra();
    if(d[n]==inf) puts("-1");
    else printf("%d\n",d[n]);
    return 0;
}

02 堆优化版dijkstra

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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=3e5+10,inf=0x3f3f3f3f;
typedef pair<int,int> P;

int h[maxn],e[maxn],ne[maxn],w[maxn],d[maxn],vis[maxn],idx,n,m;
priority_queue<P,vector<P>,greater<P>> que;

void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dijkstra(){
    d[1]=0;
    que.push({0,1});
    while(!que.empty()){
        P p=que.top();que.pop();
        int u=p.second;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=h[u];i!=-1;i=ne[i]){
            int v=e[i];
            if(d[v]>d[u]+w[i]){
                d[v]=d[u]+w[i];
                que.push({d[v],v});
            }
        }
    }
}

int main(){
    int a,b,c;
    memset(h,-1,sizeof h);
    memset(d,0x3f,sizeof d);
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    dijkstra();
    if(d[n]==inf) puts("-1");
    else printf("%d\n",d[n]);
    return 0;
}

03 对最短路选择的扩展

在满足最短路的条件下继续追加条件，比如说下面的dijkstra代码就追加了两个数组cnt和sum，cnt用于统计最短路的数量，sum用于统计路径上累计的一个量(比如说路上遇到的人数啊、路上所需要的花费啊等等，就是题目会给的除了路径长度之外用于最短路选择的变量，这时候只需要在dijkstra松弛操作d[j]==d[t]+g[t][j]时对另一个量进行更新即可)

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 <iostream>
#include <cstring>
using namespace std;
const int maxn=1010;

int g[maxn][maxn],d[maxn],vis[maxn],w[maxn],cnt[maxn],sum[maxn],st,ed,n,m;

void dijkstra(){
    d[st]=0,sum[st]=w[st],cnt[st]=1;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=0;j<n;j++)
            if(!vis[j]&&(t==-1||d[t]>d[j]))
                t=j;
        vis[t]=1;
        for(int j=0;j<n;j++){
            if(d[j]>d[t]+g[t][j]){
                d[j]=d[t]+g[t][j];
                cnt[j]=cnt[t];
                sum[j]=sum[t]+w[j];
            }
            else if(d[j]==d[t]+g[t][j]){
                cnt[j]+=cnt[t];
                sum[j]=max(sum[j],sum[t]+w[j]);
            }
        }
    }
}

int main(){
    int a,b,c;
    memset(g,0x3f,sizeof g);
    memset(d,0x3f,sizeof d);
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int i=0;i<n;i++) scanf("%d",&w[i]);
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    dijkstra();
    printf("%d %d\n",cnt[ed],sum[ed]);
    return 0;
}

04 对最短路信息的扩展

比如下面这题是要求在选择最短路的前提下选择花费最小的一条，同时要求输出最短路的路径，这个也不是太难，只需要每次最短路松弛操作的时候把路径记录到pre数组即可，最后将pre倒着输出就是路径

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 <cstring>
#include <vector>
using namespace std;
const int maxn=510;

int g[maxn][maxn],val[maxn][maxn],d[maxn],cost[maxn],vis[maxn],pre[maxn],n,m,st,ed;

void dijkstra(){
    d[st]=0,cost[st]=0,pre[st]=-1;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=0;j<n;j++)
            if(!vis[j]&&(t==-1||d[t]>d[j]))
                t=j;
        vis[t]=1;
        for(int j=0;j<n;j++){
            if(d[j]>d[t]+g[t][j]){
                d[j]=d[t]+g[t][j];
                cost[j]=cost[t]+val[t][j];
                pre[j]=t;
            }
            else if(d[j]==d[t]+g[t][j]&&cost[j]>cost[t]+val[t][j]){
                cost[j]=cost[t]+val[t][j];
                pre[j]=t;
            }
        }
    }
}

int main(){
    memset(g,0x3f,sizeof g);
    memset(val,0x3f,sizeof val);
    memset(cost,0x3f,sizeof cost);
    memset(d,0x3f,sizeof d);
    int a,b,x,y;
    cin>>n>>m>>st>>ed;
    while(m--){
        cin>>a>>b>>x>>y;
        g[a][b]=g[b][a]=min(g[a][b],x);
        val[a][b]=val[b][a]=min(val[a][b],y);
    }
    dijkstra();
    vector<int> ans;
    for(int i=ed;i!=-1;i=pre[i]) ans.push_back(i);
    for(int i=ans.size()-1;i>=0;i--){
        if(i!=ans.size()-1) cout << ' ';
        cout << ans[i];
    }
    cout<< ' ' << d[ed] << ' ' << cost[ed] << endl;
    return 0;
}

判断哈密顿回路

哈密顿回路的四个条件

  • 起点与终点相同
  • 每一步都有边
  • 所有点都被访问
  • 总共访问n+1次点(起点访问两次)

DFS时判断这四个条件即可

下面这题a数组就是题目给出的访问序列，判断是否是哈密顿回路

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
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=310;

int g[maxn][maxn],a[maxn],vis[maxn],n,m,k;

bool check(int cnt){
    memset(vis,0,sizeof vis);
    if(a[cnt-1]!=a[0]||cnt!=n+1) return false;
    for(int i=0;i<cnt-1;i++){
        vis[a[i]]=1;
        if(!g[a[i]][a[i+1]]) return false;
    }
    vis[a[cnt-1]]=1;
    for(int i=0;i<cnt;i++)
        if(!vis[a[i]]) return false;
    return true;    
}

int main(){
    int x,y,cnt;
    cin>>n>>m;
    while(m--){
        cin>>x>>y;
        g[x][y]=g[y][x]=1;
    }
    cin>>k;
    while(k--){
        cin>>cnt;
        for(int i=0;i<cnt;i++) cin>>a[i];
        if(check(cnt)) puts("YES");
        else puts("NO");
    }
    return 0;
}

欧拉路径

在图论中，欧拉路径是图中的一条路径，该路径满足恰好访问每个边一次。

而欧拉回路是一条在同一顶点处开始和结束的欧拉路径。

它们最早由欧拉于 17361736 年解决著名的哥尼斯堡七桥问题时提出。

事实证明，如果一个连通图的所有顶点的度数都为偶数，那么这个连通图具有欧拉回路，且这个图被称为欧拉图。

如果一个连通图中有两个顶点的度数为奇数，其他顶点的度数为偶数，那么所有欧拉路径都从其中一个度数为奇数的顶点开始，并在另一个度数为奇数的顶点结束。

具有欧拉路径但不具有欧拉回路的图被称为半欧拉图。

现在，给定一个无向图，请你判断它是欧拉图、半欧拉图还是非欧拉图。

思路就是迭代判断度数，DFS或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
#include <iostream>
using namespace std;
const int maxn=510;

int g[maxn][maxn],d[maxn],vis[maxn],n,m;

int dfs(int u){
    vis[u]=1;
    int res=1;
    for(int i=1;i<=n;i++)
        if(!vis[i]&&g[u][i])
            res+=dfs(i);
    return res;        
}

int main(){
    int a,b;
    cin>>n>>m;
    while(m--){
        cin>>a>>b;
        g[a][b]=g[b][a]=1;
        d[a]++,d[b]++;
    }
    int cnt=dfs(1);
    for(int i=1;i<=n;i++){
        if(i!=1) cout << ' ';
        cout << d[i];
    }
    cout << endl;
    if(cnt==n){
        int sum=0;
        for(int i=1;i<=n;i++)
            if(d[i]&1) sum++;
        if(sum==0) puts("Eulerian");
        else if(sum==2) puts("Semi-Eulerian");
        else puts("Non-Eulerian");
    }
    else puts("Non-Eulerian");
    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
#include <iostream>
#include <unordered_set>
using namespace std;
const int maxn=1e4+10;

struct edge{
    int from,to;
}e[maxn];
int vis[maxn],n,m,k;
unordered_set<int> s;

bool check(){
    for(int i=0;i<m;i++)
        if(!s.count(e[i].from)&&!s.count(e[i].to))
            return false;
    return true;        
}

int main(){
    int a,b;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        e[i]={a,b};
    }
    cin>>k;
    while(k--){
        int cnt,x;
        cin>>cnt;
        s.clear();
        while(cnt--){
            cin>>x;
            s.insert(x);
        }
        if(check()) puts("Yes");
        else puts("No");
    }
    return 0;
}

最大团

在一个无向图中，如果一个顶点子集满足子集内的任意两个不同顶点之间都是相连的，那么这个顶点子集就被称为一个团。

如果一个团不能通过加入某个新的顶点来扩展成一个更大的团，那么该团就被称为最大团。

现在，你需要判断给定顶点子集能否构成一个最大团。

也是比较简单的图论题目了，因为PAT的数据很小所以直接在给出的集合内部两两之间判断是否有边即可，如果有两点之间没有边那么就不是团。在接下来判断外面的点是否与集合中每个点都有边，如果有的话说明当前的集合不是最大团

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 <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
const int maxn=210;

int g[maxn][maxn],n,m,k;
unordered_set<int> s;

int check(vector<int>& v){
    s.clear();
    for(int i=0;i<v.size();i++)
        for(int j=i+1;j<v.size();j++)
            if(!g[v[i]][v[j]]){
                return 0;
            }
    for(int i=0;i<v.size();i++) s.insert(v[i]);
    for(int i=1;i<=n;i++)
        if(!s.count(i)){
            int flag=1;
            for(auto j:v)
                if(i!=j&&!g[i][j])
                    flag=0;
            if(flag) return 1;        
        }
    return 2;    
}

int main(){
    int a,b;
    cin>>n>>m;
    while(m--){
        cin>>a>>b;
        g[a][b]=g[b][a]=1;
    }
    cin>>k;
    while(k--){
        int cnt,x;
        cin>>cnt;
        vector<int> v;
        while(cnt--) cin>>x,v.push_back(x);
        if(check(v)==2) puts("Yes");
        else if(check(v)==1) puts("Not Maximal");
        else puts("Not a Clique");
    }
    return 0;
}

拓扑排序

给出一个图和一堆序列，问序列是不是拓扑排序，输出不是拓扑排序的序列的编号

因为已经给出了序列，只需要每次判断点是不是入度为0，如果是的话就将其所有的连接的点的入度-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
48
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=100010;

int h[maxn],e[maxn],ne[maxn],d[maxn],back[maxn],n,m,k,idx;

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++,d[b]++;
}

bool check(vector<int>& v){
    for(auto x:v){
        if(d[x]!=0) return false;
        for(int i=h[x];i!=-1;i=ne[i]){
            int y=e[i];
            d[y]--;
        }
    }
    return true;
}

int main(){
    memset(h,-1,sizeof h);
    int a,b;
    cin>>n>>m;
    while(m--){
        cin>>a>>b;
        add(a,b);
    }
    memcpy(back,d,sizeof d);
    cin>>k;
    vector<int> ans;
    for(int i=0;i<k;i++){
        memcpy(d,back,sizeof back);
        int x;
        vector<int> v;
        for(int i=0;i<n;i++) cin>>x,v.push_back(x);
        if(!check(v)) ans.push_back(i);  
    }
    for(int i=0;i<ans.size();i++){
        if(i) cout << ' ';
        cout << ans[i];
    }
    cout << endl;
    return 0;
}

染色问题

01 二分图染色

给定一个n个点m条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

使用DFS，一边遍历一边染色(标记1或者2，使用3-c进行颜色转换)，如果没有冲突就说明染色成功了，那么就是二分图

1
2
3
4
5
6
7
8
9
10
11
12
bool dfs(int u,int c){
    color[u]=c;
    for(int i=h[u];i!=-1;i=ne[i]){
        int v=e[i];
        if(!color[v]){
            if(!dfs(v,3-c))
                return false;
        }
        if(color[v]==c) return false;
    }
    return true;
}

02 判断染色方案

一个合适的顶点着色是指用各种颜色标记图中各个顶点，使得每条边的两个端点的颜色都不相同。

如果一种合适的顶点着色方案使用了一共 kk 种不同的颜色，则称其为合适的 kk 着色（k-coloring)。

现在，你需要判断给定的着色方案是否是合适的 kk 着色方案。

只需要将二分图染色的代码修改一番，将染色的代码删掉即可，判断的原理是一样的

1
2
3
4
5
6
7
8
9
bool dfs(int u){
    vis[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(color[u]==color[v]) return false;
        if(!vis[v]&&!dfs(v)) return false;
    }
    return true;
}

数学

高精度

01 高精度加法

注意在vector中数字是倒着存的(方便遍历)

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
#include <iostream>
#include <vector>
using namespace std;

vector<int> add(vector<int>& a,vector<int>& b){
    int t=0;
    vector<int> ans;
    for(int i=0;i<a.size()||i<b.size();i++){
        if(i<a.size()) t+=a[i];
        if(i<b.size()) t+=b[i];
        ans.push_back(t%10);
        t/=10;
    }
    if(t) ans.push_back(1);
    return ans;
}

int main(){
    string sa,sb;
    vector<int> a,b;
    cin>>sa>>sb;
    for(int i=sa.length()-1;i>=0;i--) a.push_back(sa[i]-'0');
    for(int i=sb.length()-1;i>=0;i--) b.push_back(sb[i]-'0');
    vector<int> ans=add(a,b);
    for(int i=ans.size()-1;i>=0;i--)
        cout << ans[i];
    cout << endl;
    return 0;
}

02 高精度减法

注意在vector中数字是倒着存的(方便遍历)，cmp函数用于比较大小(重要！！！)

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 <iostream>
#include <vector>
using namespace std;

bool cmp(vector<int>& a,vector<int>& b){
    if(a.size()!=b.size()) return a.size()>b.size();
    for(int i=a.size()-1;i>=0;i--)
        if(a[i]!=b[i])
            return a[i]>b[i];
    return true;
}

vector<int> sub(vector<int>& a,vector<int>& b){
    vector<int> ans;
    int t=0;
    for(int i=0;i<a.size();i++){
        t=a[i]-t;
        if(i<b.size()) t-=b[i];
        ans.push_back((t+10)%10);
        if(t<0) t=1;
        else t=0;
    }
    while(ans.size()>1&&ans.back()==0) ans.pop_back();
    return ans;
}

int main(){
    string sa,sb;
    vector<int> a,b,ans;
    cin>>sa>>sb;
    for(int i=sa.length()-1;i>=0;i--) a.push_back(sa[i]-'0');
    for(int i=sb.length()-1;i>=0;i--) b.push_back(sb[i]-'0');
    if(cmp(a,b))
        ans=sub(a,b);
    else
        ans=sub(b,a),cout << '-';
    for(int i=ans.size()-1;i>=0;i--)
        cout << ans[i];
    cout << endl;
    return 0;
}

03 高精度乘法

注意在vector中数字是倒着存的(方便遍历)

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
#include <iostream>
#include <vector>
using namespace std;

vector<int> mul(vector<int>& a,int b){
    vector<int> ans;
    int t=0;
    for(int i=0;i<a.size();i++){
        t+=a[i]*b;
        ans.push_back(t%10);
        t/=10;
    }
    while(t) ans.push_back(t%10),t/=10;
    return ans;
}

int main(){
    string s;
    vector<int> a;
    int b;
    cin>>s>>b;
    for(int i=s.length()-1;i>=0;i--)
        a.push_back(s[i]-'0');
    vector<int> ans=mul(a,b);
    for(int i=ans.size()-1;i>=0;i--)
        cout << ans[i];
    cout << endl;
    return 0;
}

04 高精度除法*

注意在vector中数字是倒着存的(方便遍历)，r是余数，使用引用传递

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> div(vector<int>& a,int b,int &r){
    r=0;
    vector<int> ans;
    for(int i=a.size()-1;i>=0;i--){
        r=r*10+a[i];
        ans.push_back(r/b);
        r%=b;
    }
    reverse(ans.begin(),ans.end());
    while(ans.size()>1&&ans.back()==0)
        ans.pop_back();
    return ans;
}

int main(){
    string s;
    vector<int> a;
    int b,r;
    cin>>s>>b;
    for(int i=s.length()-1;i>=0;i--)
        a.push_back(s[i]-'0');
    vector<int> ans=div(a,b,r);
    for(int i=ans.size()-1;i>=0;i--)
        cout << ans[i];
    cout << endl << r << endl;
    return 0;
}

分解质因子

给定一个整数 N，找出它的所有质因子，并输出。

思路：能除就一直除，但是不要忘记输出最后剩下来的n

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 <iostream>
using namespace std;

void divide(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            int s=0;
            while(n%i==0){
                s++;
                n/=i;
            }
            printf("%d %d\n",i,s);
        }
    }
    //注意不要忘记这里
    if(n>1) printf("%d %d\n",n,1);
    printf("\n");
}

int main(){
    int n,x;
    scanf("%d",&n);
    while(n--){
        scanf("%d",&x);
        divide(x);
    }
    return 0;
}

分数运算(和差积商)

给定两个有理数，你的任务是实现基本算术，即计算它们的和，差，积和商。

输入格式

共一行，以 a1/b1 a2/b2 的形式给出两个有理数。

分子和分母都在 long int 范围内，如果存在负号，则只能出现在分子前面，分母保证为非零数字。

输出格式

分别在四行输出两个有理数的和，差，积和商。

每行的格式为 number1 operator number2 = result。

请注意，所有有理数都必须采用最简形式，k a/b，其中 kk 是整数部分，而 a/ba/b 是最简分数部分。

如果数字为负，则必须将其包含在一对括号中。

如果除法中除数为 00，则输出 Inf 作为结果。

确保所有输出整数都在 long int 范围内。

输入样例1

1
2/3 -4/2

输出样例1

1
2
3
4
2/3 + (-2) = (-1 1/3)
2/3 - (-2) = 2 2/3
2/3 * (-2) = (-1 1/3)
2/3 / (-2) = (-1/3)

输入样例2

1
5/3 0/6

输出样例2

1
2
3
4
1 2/3 + 0 = 1 2/3
1 2/3 - 0 = 1 2/3
1 2/3 * 0 = 0
1 2/3 / 0 = Inf

代码

由于数据不是很变态，所以打印的时候约分就可以了，如果数据很大那么需要在计算过程中进行约分

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
#include <iostream>
using namespace std;
typedef long long ll;

ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}

void print(ll a,ll b){
    ll t=gcd(a,b);
    a/=t,b/=t;
    if(b<0) a*=-1,b*=-1;
    bool flag=false;
    if(a<0) flag=true;
    if(flag) printf("(");
    if(b==1) printf("%lld",a);
    else if(abs(a)>b) printf("%lld %lld/%lld",a/b,abs(a-b*(a/b)),b);
    else printf("%lld/%lld",a,b);
    if(flag) printf(")");
}

ll add(ll a,ll b,ll c,ll d){
    print(a,b),cout << " + ",print(c,d),cout << " = ";
    a=a*d+b*c,b=b*d;
    print(a,b);
    cout << endl;
}

ll sub(ll a,ll b,ll c,ll d){
    print(a,b),cout << " - ",print(c,d),cout << " = ";
    a=a*d-b*c,b=b*d;
    print(a,b);
    cout << endl;
}

ll mul(ll a,ll b,ll c,ll d){
    print(a,b),cout << " * ",print(c,d),cout << " = ";
    a=a*c,b=b*d;
    print(a,b);
    cout << endl;
}

ll div(ll a,ll b,ll c,ll d){
    print(a,b),cout << " / ",print(c,d),cout << " = ";
    a*=d,b*=c;
    if(b==0) puts("Inf");
    else{
        print(a,b);
        cout << endl;
    }
}

int main(){
    ll a,b,c,d;
    scanf("%lld/%lld %lld/%lld",&a,&b,&c,&d);
    add(a,b,c,d);
    sub(a,b,c,d);
    mul(a,b,c,d);
    div(a,b,c,d);
    return 0;
}

素数筛

01 朴素筛法

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 <iostream>
#include <vector>
using namespace std;
const int maxn=1e6+10;

int flag[maxn];
vector<int> prime;

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!flag[i]){
            prime.push_back(i);
        }
        for(int j=i+i;j<=n;j+=i)
            flag[j]=true;
    }
}

int main(){
    int n;
    scanf("%d",&n);
    get_primes(n);
    printf("%d\n",prime.size());
    return 0;
}

02 埃氏筛法

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 <iostream>
#include <vector>
using namespace std;
const int maxn=1e6+10;

int flag[maxn];
vector<int> prime;

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!flag[i]){
            prime.push_back(i);
            for(int j=i+i;j<=n;j+=i)
                flag[j]=true;
        }
    }
}

int main(){
    int n;
    scanf("%d",&n);
    get_primes(n);
    printf("%d\n",prime.size());
    return 0;
}

03 线性筛

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 <iostream>
#include <vector>
using namespace std;
const int maxn=1e6+10;

int flag[maxn];
vector<int> prime;

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!flag[i]) prime.push_back(i);
        for(int j=0;prime[j]<=n/i;j++){
            flag[prime[j]*i]=true;
            if(i%prime[j]==0) break;
        }
    }
}

int main(){
    int n;
    scanf("%d",&n);
    get_primes(n);
    printf("%d\n",prime.size());
    return 0;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int qmi(int a,int b,int p){
    int ans=1;
    while(b){
        if(b&1) ans=1ll*ans*a%p;
        b>>=1;
        a=1ll*a*a%p;
    }
    return ans;
}

int main(){
    int n,a,b,p;
    scanf("%d",&n);
    while(n--){
        scanf("%d%d%d",&a,&b,&p);
        printf("%d\n",qmi(a,b,p));
    }
    return 0;
}

动态规划

背包问题

01背包

二维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
const int maxn=1010;

int v[maxn],w[maxn],dp[maxn][maxn];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=v[i])
                dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

滚动数组优化一维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int maxn=1010;

int v[maxn],w[maxn],dp[maxn];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

02 硬币找零

(01背包应用)

伊娃喜欢从整个宇宙中收集硬币。

有一天，她去了一家宇宙购物中心购物，结账时可以使用各种硬币付款。

但是，有一个特殊的付款要求：每张帐单，她都必须准确的支付所消费金额。

给定她拥有的所有硬币的面额，请你帮她确定对于给定的金额，她能否找到一些硬币来支付。

输入格式

第一行包含两个整数 N 和 M，分别表示硬币数量以及需要支付的金额。

第二行包含 N 个整数，表示每个硬币的面额。

输出格式

共一行，按照面额升序的顺序，输出用来支付的所有硬币的面额。

如果支付方式不唯一，则输出最小的支付面额序列。

如果无解，则输出 No Solution。

对于两个序列 {A[1], A[2], ...} 和 {B[1], B[2], ...}，如果存在 k≥1k≥1 使得所有 i<ki<k，满足 A[i]=B[i]A[i]=B[i] 成立，并且 A[k]<B[k]，则我们称序列 AA 小于序列 BB。

数据范围

1≤N≤10^4,
1≤M≤100,
硬币面值不超过 100100

输入样例1

1
2
8 9
5 9 8 7 2 3 4 1

输出样例1

1
1 3 5

输入样例2

1
2
4 8
7 2 4 3

输出样例2

1
No Solution

代码

为了保证最小的面额支付序列，需要将硬币面额从大到小进行dp，保证后面面额小的可以覆盖面额大的方案

输出路径的时候只需要从后往前沿着true的路径倒着回去即可，因为是bool数组所以只会存储一个支付方案

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
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e4+10,M=110;

bool f[N][M];
int a[N];

int main(){
    int n,m;
    cin>>n>>m;
    f[0][0]=true;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n,greater<int>());
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>=a[i]) f[i][j]|=f[i-1][j-a[i]];
        }
    if(!f[n][m]) puts("No Solution");
    else{
        bool flag=true;
        while(n){
            if(m>=a[n]&&f[n-1][m-a[n]]){
                if(flag) flag=false;
                else cout << ' ';
                cout << a[n];
                m-=a[n];
            }
            n--;
        }
    }
    return 0;
}

03 完全背包

朴素版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
const int maxn=1010;

int dp[maxn][maxn],v[maxn],w[maxn];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k*v[i]<=j;k++)
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
    cout << dp[n][m] << endl;
    return 0;
}

优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
const int maxn=1010;

int dp[maxn][maxn],v[maxn],w[maxn];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=v[i])
                dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

滚动数组终极优化版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
const int maxn=1010;

int dp[maxn],v[maxn],w[maxn];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    cout << dp[m] << endl;
    return 0;
}

04 整数分解

(完全背包应用)

正整数 NN 的 K−P 分解，是将 N 写为 K 个正整数的 P 次幂的和。

请你编写一个程序，给定 N,K,P 的情况下，找到 N 的 K−P 分解。

输入格式

共一行，包含三个整数 N,K,P。

输出格式

如果存在 N 的 K−P 分解，则以如下格式输出：

1
N = n[1]^P + ... n[K]^P

其中，n[i]是第 i 个因子，所有因子必须按照不升序顺序输出。

注意，答案也许不唯一。

例如，169的 5−2 分解共有 99 种，如 122+42+22+22+12，112+62+22+22+22 等等。

你需要输出各因子之和最大的一种解法。

如果仍不能确定唯一解法，则选择因子序列更大的解法。

我们称序列 {a1,a2,…,aK} 大于序列 {b1,b2,…,bK}，当且仅当存在 1≤L≤K，满足当 ibL。

如果无解，则直接输出 Impossible。

数据范围

1≤K≤N≤400,
2≤P≤7

输入样例1

1
169 5 2

输出样例1

1
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

输入样例2

1
169 167 3

输出样例2

1
Impossible

代码

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 <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=410;

int f[30][maxn][maxn];

int main(){
    int n,k,p,m;
    memset(f,-0x3f,sizeof f);
    cin>>n>>k>>p;
    f[0][0][0]=0;
    for(m=1;;m++){
        int val=pow(m,p);
        if(val>n) break;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=k;j++){
                f[m][i][j]=f[m-1][i][j];
                if(j&&i>=val) f[m][i][j]=max(f[m][i][j],f[m][i-val][j-1]+m);
            }
        }
    }
    m--;
    if(f[m][n][k]<0) puts("Impossible");
    else{
        bool flag=true;
        printf("%d = ",n);
        while(m){
            int val=pow(m,p);
            while(f[m][n-val][k-1]+m>=f[m-1][n][k]){
                if(!flag) cout << " + ";
                else flag=false;
                printf("%d^%d",m,p);
                n-=val,k--;
            }
            m--;
        }
    }
    return 0;
}

05 多重背包*

PAT题目最多最多也只会涉及到01背包和完全背包了，多重背包不太可能，但是还是放一下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
const int maxn=110;

int dp[maxn][maxn],v[maxn],w[maxn],s[maxn];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
    cout << dp[n][m] << endl;
    return 0;
}

最大子序列和

给定一个包含 KK 个整数的序列 {N1,N2,…,NK}。

连续子序列定义为 {Ni,Ni+1,…,Nj}，其中 1≤i≤j≤K。

最大子序列是指序列内各元素之和最大的连续子序列。

例如，给定序列 {−2,11,−4,13,−5,−2}，它的最大子序列为 {11,−4,13}，其各元素之和为 20。

现在你需要求出最大子序列的各元素之和，并且输出最大子序列的第一个元素和最后一个元素的值。

输入格式

第一行包含一个整数 K。

第二行包含 K 个整数。

输出格式

输出一行三个整数，分别表示最大子序列的各元素之和以及最大子序列的第一个元素和最后一个元素的值。

设最大子序列为 {Ni,Ni+1,…,Nj}，如果答案不唯一，则选择 i 更小的解，如果仍不唯一，则选择 j 更小的解。

注意，我们规定，如果所有 KK 个数字均为负数，则其最大和定义为 0，并且应该输出整个序列的第一个数字和最后一个数字。

数据范围

1≤K≤10000,序列内元素的绝对值不超过 10^5。

输入样例

1
2
10
-10 1 2 3 4 -5 -23 3 7 -21

输出样例

1
10 1 4

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int maxn=10010;

int a[maxn];

int main(){
    int n,ans=-1,l,r;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0,f=-1,st;i<n;i++){
        if(f<0) f=0,st=i;
        f+=a[i];
        if(f>ans){
            ans=f;
            l=a[st],r=a[i];
        }
    }
    if(ans<0) ans=0,l=a[0],r=a[n-1];
    cout << ans << ' ' << l << ' ' << r << endl;
    return 0;
}

最长公共子序列

01 最长公共子序列

dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int maxn=1010;

char a[maxn],b[maxn];
int dp[maxn][maxn];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s%s",a+1,b+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
        }
    printf("%d\n",dp[n][m]);
    return 0;
}

02 变种(一个字符匹配多个字符)

a数组中的字符可以匹配多次b数组中的字符，所以dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1)要改成f[i][j]=max(f[i-1][j],f[i][j-1],f[i][j-1]+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
const int N=210,M=1e4+10;

int a[N],b[M];
int f[N][M];

int main(){
    int n,m,k;
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>a[i];
    cin>>k;
    for(int i=1;i<=k;i++) cin>>b[i];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=k;j++){
            if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i][j-1]+1);
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
    cout << f[m][k] << endl;    
    return 0;
}

状态机模型

字符串 APPAPT 中共包含两个 PAT 作为子串。

第一个子串由第二，第四和第六个字符组成，第二个子串由第三，第四和第六个字符组成。

现在给定一个字符串，请你求出字符串中包含的 PAT 的数量。

输入格式

共一行，包含一个由大写字母 P,A,T 构成的字符串。

输出格式

输出字符串中包含的 PAT 的数量。

由于结果可能很大，请你输出对 1000000007 取模后的结果。

数据范围

给定字符串的长度不超过 10^5。

输入样例

1
APPAPT

输出样例

1
2

代码

将初始状态设置为0，匹配P的状态设置为1，匹配P后又匹配了A的状态设置为2，匹配了P和A之后又匹配了T的状态设置为3

f[i][j]表示为只考虑给定字符串前i个字符且走到了状态j的所有路线的数量

2022-02-26

上一篇：ArcGIS Pro 功能介绍 下一篇：USD简介和各在DCC软件中的应用
© 1949-2025 China
🌊看过大海的人不会忘记海的广阔🌊 本站由Hexo驱动｜使用Hexo-theme-A4主题