郭霖的博客

腾讯音乐实习ing

蓝桥杯常用技巧

发表于 更新于 分类于
本文字数： 8.7k 阅读时长 ≈ 8 分钟

万能头文件

1
#include＜bits/stdc++.h＞

加快输入输出

1
2
3
4
main函数中加入以下代码，降低时长
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0)

常用变量定义

建议一些变量、数组、标记等定义在全局，这样就避免了初始化，因为放在全局的变量，系统自动初始化成0。

1
2
3
4
5
6
7
typedef long long LL;
const int inf = 0x3f3f3f3f;// 1061109567
const LL  INF = 0x3f3f3f3f3f3f3f3f;// 4557430888798830399
const double PI = acos(-1.0);// 3.14159
const double E = exp(1.0);// 2.71828
const int MOD = 1e9+7;
const int MAX = 1e5+5;

0x3f3f3f3f是一个很有用的数值，它是满足以下两个条件的最大整数。

1、整数的两倍不超过 0x7f7f7f7f，即int能表示的最大正整数。

2、整数的每8位（每个字节）都是相同的。(0011 1111 0011 1111 0011 1111 0011 1111)

我们在程序设计中经常需要使用 memset(a, val, sizeof a) 初始化一个数组a，该语句把数值 val（0x00~0xFF）填充到数组a 的每个字节上，所以用memset只能赋值出“每8位都相同”的 int。

当需要把一个数组中的数值初始化成正无穷时，为了避免加法算术上溢出或者繁琐的判断，我们经常用 memset(a, 0x3f, sizeof(a)) 给数组赋 0x3f3f3f3f的值来代替。

初始化数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstring>
using namespace std;
int main() {
    //a[10]的长度其实是40byte，因为每个int是4个byte
    int a[10],  b[10];
    memset(a, 0, 40);//cstring中的memset(要初始化的数组，初始化的值，要初始化的字节长度(byte))
    memset(b, 0, sizeof b);//sizeof可以用来求数组占用的字节数量
    for (int i = 0; i < 10; i++) {
        cout << a[i] << ' ';
    }
    cout << endl;
    for (int i = 0; i < 10; i++) {
        cout << b[i] << ' ';
    }
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <cstring>
using namespace std;
int main() {
    char data[]="This is a test of the memset function";
    printf("Before:%s\n",data);
    memset(data,'*',4);
    printf("After:%s\n",data);
    return 0;
}
输出：
    Before:This is a test of the memset function
	After:**** is a test of the memset function

atoi/stoi 字符串转换为整数

1
2
3
4
5
6
7
#include <iostream>
using namespace std;
int main() {
    int a = atoi("123");
    cout << a << endl;
    return 0;
}
1
2
3
4
5
6
7
#include <bits/stdc++.h>
using namespace std;
int main() {
    string s = "123";
    int n = stoi(s);
    cout << n << endl;
}

to_string

转字符串

bitset 字符串或者整数转二进制

用于将字符串或者整数转换成二进制数存储

bitset存储中下标是从右往左 从0开始计数的

1
2
头文件
#include <bitset>
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 <bits/stdc++.h>

using namespace std;

int main() {
    // 存储位数足够，前面多余位用0补足
    bitset <8>a(13);// 1101
    bitset <8>b(string("100101"));// 100101

    // 存储位数不够时，数字转换取后几位，字符串转换取前几位
    bitset <3>c(12);// 1100
    bitset <4>d(string("100111"));

    // 注 ：bitset的下标是从右往左数的
    cout << a[0] << a[1] << a[2] << a[3] << endl;
    cout << a << endl;
    cout << b << endl;
    cout << c << endl;
    cout << d << endl;
    return 0;
}
输出：
    1011
    00001101
    00100101
    100
    1001
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 <bits/stdc++.h>

using namespace std;

int main() {
    //*执行 flip 、set 和 reset函数 后都会覆盖原有值
    string str = "10010111";
    bitset <8> m(str);
    cout << m << endl;
    cout << m.count() << endl;// 返回m中1的个数
    cout << m.size() << endl;// 返回m的大小
    cout << m.test(2) << endl;// 检测下标为2的元素是否为1 若为1 则返回1
    cout << m.any() << endl;// 检测m中是否有1
    cout << m.none() << endl;// 检测m中是否没有1
    cout << m.all() << endl;// 检测m中是否全部为1
    cout << m.flip() << endl;// 所有位都取反
    cout << m.flip(0) << endl;// 下标为0的位置取反
    cout << m.set(2) << endl;// 将下标为2的元素置为1
    cout << m.set() << endl;// 所有位都置为1
    cout << m.set(1, 0) << endl;// 将下标为1的元素置为 0
    cout << m.reset() << endl;// 将所有位置为0
    return 0;
}
输出：
    10010111
    5
    8
    1
    1
    0
    0
    01101000
    01101001
    01101101
    11111111
    11111101
    00000000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;

int main() {
    string str = "10010111";
    bitset <8> n(str);
    string s = n.to_string();
    cout << s << endl;
    
    // 将bitset转换为无符号的long
    unsigned long h = n.to_ulong();
    cout << h << endl;
    return 0;
}
输出：
    10010111
    151
    151

next_permutation 全排列

prev_permutation前一个排列组合

1
2
头文件
#include <algorithm>

输出 n 个数的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int a[1005];
int main()
{
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        printf("\n");
        sort(a, a + n);
        do {
            for (int i = 0; i < n; i++) {
                printf("%d ", a[i]);
            }
            printf("\n");
        } while (next_permutation(a, a + n));
    }
    return 0;
}
1
2
3
关于while (~scanf("%d", &n))
    
其功能是循环从输入流读取n，直到遇到EOF为止，scanf()函数返回成功赋值的数据项数，出错时则返回，EOF定义为-1。~是按位取反，-1十六进制补码表示为0xffffffff，f是二进制的1111，取反后就全部变成0了，于是while结束。只有返回值为EOF（即-1）时，其取反的的值（即while循环的判断条件）才为0，才能结束循环，其它输入情况下（无论是否输入成功）while循环的判断条件为非0，即为真。

reverse 翻转函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>//算法库
#include <vector>
using namespace std;
int main() {
    vector<int> a({1, 2, 3, 4, 5});
    reverse(a.begin(), a.end());
    for (int x : a) {
        cout << x << ' ';
    }
    cout << endl;
    int b[] = {1, 2, 3, 4, 5};
    reverse(b, b + 5);
    for (int c : b) {
        cout << c << ' ';
    }
    cout << endl;
    return 0;
}

sort 排序函数

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>//算法库
#include <vector>
#include <ctime>
using namespace std;
int main() {
    vector<int> a{1, 1, 2, 2, 3, 3, 4};
    
    //传入一个随机准则，time(0)是现在到1970-1-1的秒数
    srand(time(0));
    
    //随机打乱顺序
    random_shuffle(a.begin(), a.end());
    for (auto x : a) {
        cout << x << ' ';
    }
    cout << endl;
    
    //从小到大排序
    sort(a.begin(), a.end());
    for (auto x : a) {
        cout << x << ' ';
    }
    cout << endl;
    
    //从大到小排序
    sort(a.begin(), a.end(), greater<int>());
    for (auto x : a) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}

reverse 翻转函数

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str = to_string(10);
    reverse(str.begin(), str.end());
    cout << str << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str = to_string(12321);
    // 翻转以后返回字符串
    string str2 = string(str.rbegin(), str.rend());
    cout << (str == str2) << endl;
    return 0;
}
输出：true

unique 去重函数

这是一个去重函数 （同时将数组从小到大排序 重复出现的元素放到容器尾部）

unique(num,mun+n)返回的是num去重后的尾地址，之所以说比不真正把重复的元素删除，其实是，该函数把重复的元素移到后面去了，然后依然保存到了原数组中，然后返回去重后最后一个元素的地址，因为unique去除的是相邻的重复元素，所以一般用之前都会要排一下序。

1
2
3
需要添加头文件：
#include <iostream>
#include <algorithm>
1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str = "abbbccbba";
    str.erase((unique(str.begin(), str.end())), str.end());
    cout << str << endl;
    return 0;
}
输出：abcba
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> res = {1, 1, 2, 3, 4, 1};
    res.erase((unique(res.begin(), res.end())), res.end());
    for (int i : res) {
        cout << i << ' ';
    }
    cout << endl;
    return 0;
}
输出：1 2 3 4 1

lower_bound

利用二分查找在已排序的数组中查找元素

lower_bound(begin,end,num) 找到第一个大于或等于num的数字 返回该数字的地址 否则返回end

通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。即 lower_bound(begin,end,num) - begin

upper_bound(begin,end,num) 找到第一个大于num的数字 返回该数字的地址 否则返回end

1
2
添加头文件
#include<algorithm>
1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> res = {1, 1, 2, 3, 3, 4, 1};
    // 通过返回的地址减去起始地址begin,得到找到数字在数组中的下标
    int idx = lower_bound(res.begin(), res.end(), 3) - res.begin();
    cout << idx << endl;
    return 0;
}
输出：3

格式化输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a = 10;
    float b = 5;
    printf("%5d\n", a);// 在左边补上空格
    printf("%-5d\n", a);// 在右边补上空格
    printf("%5.1lf\n", b);// 小数长度为5，并且保留一位小数，不够时前面补空格（小数点也算一位）
    printf("%05.1lf\n", b);// 小数长度为5，并且保留一位小数，不够时前面补0（小数点也算一位）
    return 0;
}
输出：
   10
10
  5.0
005.0

杂项

关于数据范围：大题的题目中会给出相应的数据范围，根据题目的数据范围来选择数据型是int 还是long long 还是其他类型，注意如果是使用long long的话，要用%i64d（i大写）进行输入输出，如果是平常做题过程中使用%lld进行输入输出。（用%i64d（i大写）还是%lld根据情况而定，如果Windows评测机采用%i64d（i大写）；如果Linux评测机采用%lld）

1
2
3
4
蓝桥杯输入/出 long long数据需要使用的是
long long x = 0;
scanf("%I64d", &x);
printf("%I64d", x);

蓝色桥杯最大栈空间为256MB，经过换算， 你最大可以开 1 * 10的7次方左右的数组空间。也就是1千万

1
2
3
4
5
6
7
8
9
10
11
12
unsigned int 0～4294967295 // 9及以下位数都可装
int -2147483648～2147483647 // 9及以下位数都可装
unsigned long 0～4294967295 // 9及以下位数都可装
long -2147483648～2147483647 // 9及以下位数都可装
long long的最大值：9223372036854775807 // 18及以下位数都可装 19位也差不多
long long的最小值：-9223372036854775808 // 18及以下位数都可装 19位也差不多
unsigned long long的最大值：18446744073709551615 //20位
// 下面用的可能没有接触过， 但存在， 有上面的就够了， 下面和上面的long long 是一样的。
__int64的最大值：9223372036854775807__

int64的最小值：-9223372036854775808
unsigned __int64的最大值：18446744073709551615
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
1. 
// 当需要多次使用一个表达式的值的时候， 可以存起来。 这样可以减少计算次数。
// 如：
int n = 10;
int b = 30;
for(int i = 0; i < n; i++){
	printf("%d", n * b * i);
}
// 更改为
int n  = 10;
int b = 30;
int t = n * b;
for(int i = 0; i < n; i++){
	printf("%d", t * i);
}
// 如：
// 计算一个数组 / 或者字符串长度的时候， 最后一直存着，以免多次计算。 

2. 
// 位运算符的应用
// 如:
int n = 30;
int i =  n* 2;
int c =  n / 16;
// 可以更改为
int i = n << 1; // 相信我会快。
int c =  n >> 4;

// 如：
int i = 100;
while(i % 2 == 1){// 对于for循环同样使用。
i--;
}
// 改为
while(i & 1){ // 用位运算代替
--i;// 前自减/增 比 后自减/增快。
}

// 如：
int i = 0;
int x = i--;
// 改为
int x = i;
--i;// 这样结果一样， 但编译后，会少一条汇编指令。
-------------本文结束感谢您的阅读-------------