蓝桥杯算法比赛笔记

递归与递推

递归实现指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

就是判断选和不选

92. 递归实现指数型枚举 - AcWing题库

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>

const int N=16;

int n;

int state[N];//0表示无数据,1表示×，2表示√

void dfs(int current)
{
    if(current>n)//边界判断，到边界了就把数据输出
    {
        for(int i=1;i<=current;i++)//注意等于号
        {
            if(state[i]==2)
                printf("%d ",i);//用i表示第i个数的状态
        }
        puts("");
        return;
    }
    
    state[current]=1;
    dfs(current+1);
    state[current]=0;
    
    state[current]=2;
    dfs(current+1);
    state[current]=0;
    
    return;
}

int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}

递归实现排列形枚举

把 1∼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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>

const int N=10;

int n;

int states[N];
bool used[N];

void dfs(int current)
{
    if(current>=n)
    {
       for(int i=1;i<=current;i++)
       {
                printf("%d",states[i]);
       }
       puts("");
       return;
    }
    
    fot(int i=1;i<=n;i++)
    {
        if(!used[i])
        {
            states[current]=i;
            used[i]=true;
            
            dfs(current+1);
            used[i]=flase;
            states[current]=0;
        }
    }
    
    return;

}
int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}

递归实现组合形枚举

从 1∼n 这 n 个整数中随机选出 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<iostream>

using namespace std;

const int N=99;

int n;
int m;

int stats[N];

void dfs(int current,int start)
{
    if(current-1 + n-start+1<m) return;//剪枝，例如抽到1，5，之后，后面不需要抽了
    if(current==m+1)
    {
        for(int i=1;i<current;i++)
        {
            printf("%d ",stats[i]);
        }
        puts("");
        return;
    }
    
    for(int i=start;i<=n;i++)
    {
        stats[current]=i;
        dfs(current+1,i+1);
        stats[current]=0;
    }
     return;
}

int main()
{
    scanf("%d %d",&n,&m);
    dfs(1,1);
    return 0;
}

二分

单调的函数都可以二分，可以二分的不一定单调（求数的根号三）

整数二分

整合二分最为复杂，因为有越界的问题

整数二分步骤:
1.找一个区间[L，R]，使得答案一定在该区间中
2找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点。

寻找的值是 符合判断条件时 的边界的值

及左区间（符合判断条件）的最大值，或者右区间（符合判断条件）的最小值

3.分析终点M在该判断条件下是否成立，如果成立，考虑答案在哪个区间;如果不成立，考虑答案在哪个区间;
4.如果更新方式写的是R = Mid（和L=Mid+1），则不用做任何处理;如果更新方式写的是L= Mid（和R=Mid-1），则需要在计算Mid时加上1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int l=0;
int r=n-1;//注意这个n-

//形式一
while(l<r)//注意这个s <
{
    int mid=l+r>>1;//>>1代表除以二
    if(a[mid]>=x)//注意这个>=
        r=mid;
    else l=mid+1;
}

//形式二
while(l<r)
{
    int mid=l+r+1>>1;
    if(a[mid]<=x)
        l=mid;
    else
        r=mid-1;
}

参考典型例题：

789. 数的范围 - AcWing题库

基础算法

得背下来

快排

分治思想

不同于常规的，不是一次排序一个数，而是直接将某个数的俩测排好

1258817-20190325195811497-310078615

5b56d02d73d145ca9be2c0431f1f6d68_tplv-k3u1fbpfcp-watermark (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
#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[],int left,int right)
{
	if(left>=right) return ;
    int x=q[(left+right+1)/2],i=left-1,j=right+1;//可换成x=q[(left+right)/2]
    while(i<j)
    {
    	do i++ ;while(q[i]<x);
    	do j-- ;while(q[j]>x); 
        if(i<j) swap(q[i],q[j]);
    }
    
    quick_sort(q,left,i-1);//可换成j
    quick_sort(q,i,right);//可换成j-1
    
}

int main()
{
	scanf("%d",&n);
    for(int i=0;i<n;i++) 
        scanf("%d",&q[i]);
    
    quick_sort(q,0,n-1);
    
   	for(int i=0;i<n;i++)
        printf("%d ",q[i]);
    
    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
#include<iostream>

using namespace std;

const int N=1000010;

int n;
int q[N],temp[N];


void merge_sort(int q[],int left,int right)
{
    if(left>=right) return ;
    @WWWWWWWW*x
    int mid=(left+right)/2;[p;'p-=l.;;;;76']
    
    merge_sort(q,left,mid), merge_sort(q,mid+1,right);
    
    int x=0,i=left,j=mid+1;
    
    while(i<=mid&&j<=right)//注意这里的  <=
        if(q[i]<=q[j]) temp[x++]=q[i++];//注意这里的  <=
        else temp[x++]=q[j++];
    while(i<=mid) temp[x++]=q[i++];//注意这里的  <=
    while(j<=right) temp[x++]=q[j++];//注意这里的  <=
    
    for(i=left,j=0;i<=right;i++,j++)//注意这里的  <=
        q[i]=temp[j];
    
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&q[i]);
    
    merge_sort(q,0,n-1);
    
    for(int i=0;i<n;i++)
        printf("%d ",q[i]);
}

二分

排列组合

排列：考虑顺序

组合：不考虑顺序

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
1插入排序

void insert_sort()
{
    for (int i = 1; i < n; i ++ )
    {
        int x = a[i];
        int j = i-1;

        while (j >= 0 && x < a[j])
        {
            a[j+1] = a[j];
            j -- ;
        }
        a[j+1] = x;
    }
}
2选择排序

void select_sort()
{
    for (int i = 0; i < n; i ++ )
    {
        int k = i;
        for (int j = i+1; j < n; j ++ )
        {
            if (a[j] < a[k])
                k = j;
        }
        swap(a[i], a[k]);
    }

}
3冒泡排序

void bubble_sort()
{
    for (int i = n-1; i >= 1; i -- )
    {
        bool flag = true;
        for (int j = 1; j <= i; j ++ )
            if (a[j-1] > a[j])
            {
                swap(a[j-1], a[j]);
                flag = false;
            }
        if (flag) return;
    }
}
4希尔排序

void shell_sort()
{
    for (int gap = n >> 1; gap; gap >>= 1)
    {
        for (int i = gap; i < n; i ++ )
        {
            int x = a[i];
            int j;
            for (j = i; j >= gap && a[j-gap] > x; j -= gap)
                a[j] = a[j-gap];
            a[j] = x;
        }
    }
}
5快速排序（最快）

void quick_sort(int l, int r)
{
    if (l >= r) return ;

    int x = a[l+r>>1], i = l-1, j = r+1;
    while (i < j)
    {
        while (a[++ i] < x);
        while (a[-- j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    sort(l, j), sort(j+1, r);
}
6归并排序

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

    }
    while (i <= mid) temp[k ++ ] = a[i ++ ];
    while (j <= r) temp[k ++ ] = a[j ++ ];
    for (int i = l, j = 0; i <= r; i ++ , j ++ ) a[i] = temp[j];
}
7堆排序（须知此排序为使用了模拟堆，为了使最后一个非叶子节点的编号为n/2，数组编号从1开始）
https://www.cnblogs.com/wanglei5205/p/8733524.html

void down(int u)
{
    int t = u;
    if (u<<1 <= n && h[u<<1] < h[t]) t = u<<1;
    if ((u<<1|1) <= n && h[u<<1|1] < h[t]) t = u<<1|1;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main()
{
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    for (int i = n/2; i; i -- ) down(i);
    while (true)
    {
        if (!n) break;
        cout << h[1] << ' ';
        h[1] = h[n];
        n -- ;
        down(1);
    }
    return 0;
}
8基数排序

int maxbit()
{
    int maxv = a[0];
    for (int i = 1; i < n; i ++ )
        if (maxv < a[i])
            maxv = a[i];
    int cnt = 1;
    while (maxv >= 10) maxv /= 10, cnt ++ ;

    return cnt;
}
void radixsort()
{
    int t = maxbit();
    int radix = 1;

    for (int i = 1; i <= t; i ++ )
    {
        for (int j = 0; j < 10; j ++ ) count[j] = 0;
        for (int j = 0; j < n; j ++ )
        {
            int k = (a[j] / radix) % 10;
            count[k] ++ ;
        }
        for (int j = 1; j < 10; j ++ ) count[j] += count[j-1];
        for (int j = n-1; j >= 0; j -- )
        {
            int k = (a[j] / radix) % 10;
            temp[count[k]-1] = a[j];
            count[k] -- ;
        }
        for (int j = 0; j < n; j ++ ) a[j] = temp[j];
        radix *= 10;
    }

}
9计数排序

void counting_sort()
{
    int sorted[N];
    int maxv = a[0];
    for (int i = 1; i < n; i ++ )
        if (maxv < a[i])
            maxv = a[i];
    int count[maxv+1];
    for (int i = 0; i < n; i ++ ) count[a[i]] ++ ;
    for (int i = 1; i <= maxv; i ++ ) count[i] += count[i-1];
    for (int i = n-1; i >= 0; i -- )
    {
        sorted[count[a[i]]-1] = a[i];
        count[a[i]] -- ;
    }
    for (int i = 0; i < n; i ++ ) a[i] = sorted[i];
}
10桶排序（基数排序是桶排序的特例，优势是可以处理浮点数和负数，劣势是还要配合别的排序函数）

vector<int> bucketSort(vector<int>& nums) {
    int n = nums.size();
    int maxv = *max_element(nums.begin(), nums.end());
    int minv = *min_element(nums.begin(), nums.end());
    int bs = 1000;
    int m = (maxv-minv)/bs+1;
    vector<vector<int> > bucket(m);
    for (int i = 0; i < n; ++i) {
        bucket[(nums[i]-minv)/bs].push_back(nums[i]);
    }
    int idx = 0;
    for (int i = 0; i < m; ++i) {
        int sz = bucket[i].size();
        bucket[i] = quickSort(bucket[i]);
        for (int j = 0; j < sz; ++j) {
            nums[idx++] = bucket[i][j];
        }
    }
    return nums;
}

细碎知识点

x的y次方

  • #include<math.h>中pow(x,y)表示x的y次方,exp(x)表示e的x次方
  • 100=1e2=1e+2

某些函数

  • memcpy(b,a,sezeof a) 作用是将a数组的数复制到到b数组里面
  • memset(a,0,sezeof a) 作用是将a数组所有字节都变成0

2的20次方

2^20^=2^10^ * 2^10^ =1024*1024=1048576≈10^6^=1M bit

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
#include <iostream>
#include<algorithm>
using namespace std;
int n,r,max_x,max_y;
const int N=7009;
int sum[N][N];
void print()
{
    /*for(int i=5;i<=5;i++)
    {
        for(int j=5;j<=5;j++)
        {
           cout<<sum[i][j]<<" ";
        }
        cout<<endl;
    }*/
    cout<<endl;
    for(int i=max_x-10;i<=max_x+10;i++)
    {
        for(int j=max_x-10;j<=max_x+10;j++)
        {
           cout<<sum[i][j]<<" ";
        }
        
        cout<<endl;
    }
}
int main()
{
    scanf("%d %d",&n,&r);
    r=min(5001,r);
    max_x=r;
    max_y=r;
    while(n--)
    {
        int x,y,w;
        scanf("%d %d %d",&x,&y,&w);
        
        sum[x+1][y+1]+=w;
        max_x=max(max_x,x+1);
        max_y=max(max_y,y+1);
    }
    //print();
    for(int i=1;i<=5000;i++)
        for(int j=1;j<=5000;j++)
        {
            //sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
        
    //print();
    int res=0;
    for(int i=1;i<=5000;i++)
    {
        for(int j=1;j<=5000;j++)
        {
            int x1=i,y1=j,x2=i+r-1,y2=j+r-1;
            //if(x2>(max_x)||y2>(max_y)) continue;
            res=max(sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1],res);
            //if(x2>5001||y2>5001) continue;
            //res = max(res, sum[i][j] - sum[i - r][j] - sum[i][j - r] + sum[i - r][j - r]);
            //printf("max=%d,x1=%d,y1=%d,x2=%d,y2=%d\n",max,x1,y1,x2,y2);
            
        }
        
    }
   /* printf("max_x=%d,max_y=%d\n",max_x,max_y);
    printf("sum[max_x][max_y]=\n%d \n",sum[max_x][max_y]);
    printf("sum[5000][5000]=\n%d \n",sum[5000][5000]);*/
    printf("%d",res);
    //print();
    return 0;
}

绝对值

abs()函数

向上取整

floor(a/b) 和 a/b向下取整

ceil(double(a/b) 和 (a+b-1)/b 是向上取整

a%b 返回正数值

当a,b>0时，a%b<0，(a%b+b)%b>0

1
2
cout <<-4%3<<endl;//结果是-1
cout << (-4 % 3+3)%3;//结果是2

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！