Stay hungry. Stay foolish.

0%

C++解题注意事项

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 6k 阅读时长 ≈ 5 分钟

记录用C++解题的一些基本注意事项(整理柳神笔记+自己遇到的坑)

DevC++的使用

  1. 让dev支持C++11特性：在编译选项里加上：-std=c++11

Tools->Complier Options

  1. 万能头文件: 

    1
    2
    #include<bits/stdc++.h> 
    using namespace std;

  2. 常用头文件(应对环境限制两手准备)：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <cctype>
    #include <cstring>
    #include <vector>
    #include <set>
    #include <map>
    #include <string>
    #include <stack>
    #include <queue>
    #include <bitset>
    using namespace std;

语法注意事项

  1. gets()禁用，替代品fgets(一个指针，长度，stdin),但是此方法会存入回车，注意长度也多了一个，前面有scanf也要getchar一下；要特别注意scanf(“%s”,a)会将空格作为结束标志
  2. 10的9次方以内用int,以上用long long
  3. double scanf中：%lf 输出：%f;long long 两者都是：%lld
  4. scanf(“%c”,&a)会读取上一次scanf的换行符，所以输入数字后若要再输入字符，应该加一个getchar(),循环中同；即连续输入时，%c会将空格、换行符读入，需要先用getchar接收后面的空格或者换行符，根据需要使用
  5. n位补码可以表示的数的范围：[-2的n-1次方，2的n-1次方)，发生正溢时的范围为：[-2的n-1次方，-2]，发生负溢的范围为[0, 2的n-1次方）
  6. 对于没有指明结束输入的题：用类似while(scanf(“%d”,&a)!=EOF)
  7. 整数除以二进行四舍五入的操作可以通过判断奇偶数来避免浮点数的介入
  8. 大的数组，常量定义在主函数之外
  9. 求绝对值：整数型用abs();浮点型用fabs()
  10. 如果要读入一整行，也可以用getline():char str[100];cin.getline(str,100);而如果用string容器，则string str;getline(cin,str);
  11. bool型默认初始化为false,因此bool hash[100]={true};入坑
  12. stl中是遍历queue和stack,不要用循环，用是否为空
  13. 特殊的vector需要初始化大小
  14. 注意memset和fill的区别,一律用fill(arr, arr + n, 要填入的内容);

STL等常规操作

string

1
2
3
4
5
string s; // 定义一个空字符串s
getline(cin, s); // 读取一行的字符串，包括空格
cout << s.length(); // 输出字符串s的长度
string s2 = s.substr(4); // 表示从下标4开始一直到结束
string s3 = s.substr(5, 3); // 表示从下标5开始，3个字符

vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//vector元素默认为0,bool为false
vector<int> a; // 定义的时候不指定vector的大小
cout << a.size() << endl; // 这个时候size是0
a.push_back(i); // 在vector a的末尾添加⼀个元素i
a.pop_back();//弹出末尾一个元素
vector<int> b(15); // 定义的时候指定vector的⼤小，默认b里面元素都是0
vector<int> c(20, 2); // 定义的时候指定vector的大⼩并把所有的元素赋一个指定的值
for (int i = 0; i < c.size(); i++) {//像数组一样访问
    cout << c[i] << " ";
}
for (auto it = c.begin(); it != c.end(); it++) { // 使⽤迭代器的方式访问vector
    cout << *it << " ";
}
for (auto it : c){
    cout << *it << " ";
}
//直接拿一个小容器来构造也行，.begin()-.end(),这里in是一个数组
vector<int> tin(in, in+n+1);

set

1
2
3
4
5
6
7
8
9
10
//有序，无重复
set<int> s; // 定义⼀个空集合s
s.insert(1); // 向集合s里面插入一个1
for (auto it = s.begin(); it != s.end(); it++) { 
// 用迭代器遍历集合s里面的每一个元素
    cout << *it << " ";
}
cout << (s.find(10) != s.end()) << endl; 
// s.find(10) != s.end()表示能找到10这个元素
s.erase(1); // 删除集合s中的1这个元素

map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//map 会自动将所有的键值对按照键从⼩小到大排序
map<string, int> m; // 定义⼀个空的map m，键是string类型的，值是int类型的
m["hello"] = 2; // 将key为"hello", value为2的键值对(key-value)存⼊map中
cout << m["hello"] << endl; // 访问map中key为"hello"的value, 如果key不存在，则返回0
m["world"] = 3; // 将"world"键对应的值修改为3
// 用迭代器遍历，输出map中所有的元素，键⽤it->first获取，值用it->second获取
for (auto it = m.begin(); it != m.end(); it++) {
    cout << it->first << " " << it->second << endl;
}
// 访问map的第⼀个元素，输出它的键和值
cout << m.begin()->first << " " << m.begin()->second << endl;
// 访问map的最后⼀个元素，输出它的键和值
cout << m.rbegin()->first << " " << m.rbegin()->second << endl;
// 输出map的元素个数
cout << m.size() << endl;

补充：unordered_map （或者unordered_set ）省去了排序的过程，如果偶尔刷题时候⽤map 或者set 超时了，可以考虑⽤unordered_map （或者unordered_set ）缩短代码运行时间、提⾼代码效率

stack

1
2
3
4
5
6
7
stack<int> s; // 定义⼀一个空栈s
for (int i = 0; i < 6; i++) {
    s.push(i); // 将元素i压⼊入栈s中
}
cout << s.top() << endl; // 访问s的栈顶元素
cout << s.size() << endl; // 输出s的元素个数
s.pop(); // 移除栈顶元素

queue

1
2
3
4
5
6
7
queue<int> q; // 定义⼀个空队列列q
for (int i = 0; i < 6; i++) {
    q.push(i); // 将i的值依次压⼊队列q中
}
cout << q.front() << " " << q.back() << endl; // 访问队列的队首元素和队尾元素
cout << q.size() << endl; // 输出队列的元素个数
q.pop(); // 移除队列的队首元素

位运算bitset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bitset<5> b("11"); //5表示5个二进位
// 初始化⽅方式：
// bitset<5> b; 都为0
// bitset<5> b(u); u为unsigned int，如果u = 1，则输出b的结果为00001
// bitset<8> b(s); s为字符串，如"1101"，则输出b的结果为00001101，在前⾯面补0
// bitset<5> b(s, pos, n); 从字符串的s[pos]开始，n位长度
// 注意，bitset相当于一个数组，但是它是从二进制的低位到高位分别为b[0]、b[1]……的
// 所以按照b[i]⽅方式逐位输出和直接输出b结果是相反的
cout << b << endl; // 如果bitset<5> b("11"); 则此处输出00011(即正常二进制顺序)
for(int i = 0; i < 5; i++)
cout << b[i]; // 如果bitset<5> b("11"); 则此处输出11000(即正常⼆进制顺序的倒序)
cout << endl << b.any(); //b中是否存在1的⼆进制位
cout << endl << b.none(); //b中不存在1吗？
cout << endl << b.count(); //b中1的二进制位的个数
cout << endl << b.size(); //b中⼆进制位的个数
cout << endl << b.test(2); //测试下标为2处是否⼆进制位为1
b.set(4); //把b的下标为4处置1
b.reset(); //所有位归零
b.reset(3); //b的下标3处归零
b.flip(); //b的所有⼆进制位逐位取反
unsigned long a = b.to_ulong(); //b转换为unsigned long类型

排序问题常用sort()

1
2
3
4
5
6
7
8
sort(v.begin(), v.end());// 因为这里没有传⼊参数cmp，所以按照默认，v从小到大排列列
sort(arr, arr + 10, cmp); // arr从⼤到小排列列，因为cmp函数排序规则设置了了从大到小
bool cmp(stu a, stu b) { // cmp函数，返回值是bool，传⼊的参数类型应该是结构体stu类型
    if (a.score != b.score) // 如果学⽣分数不同，就按照分数从大到小排列
        return a.score > b.score;
    else // 如果学⽣分数相同，就按照学号从⼩到⼤排列
        return a.number < b.number;
}

其他常用函数

  • isalpha 字⺟（包括⼤写、小写）
  • islower （⼩写字母）
  • isupper （大写字母）
  • isalnum （字母⼤写小写+数字）
  • isblank （space和\t ）
  • isspace （ space 、\t 、\r 、\n ）
  • tolower （将字母变为小写）
  • toupper （将字母变为大写）
  • reverse (反转)
  • sort(a,a+1000,greater())

    C++11新特性

  1. auto 可以代替⼀大⻓串的迭代器类型声明
  2. for循环
1
2
3
4
5
6
7
8
9
10
11
12
int arr[4] = {0, 1, 2, 3};
for (int i : arr)  
    cout << i << endl; // 输出数组中的每⼀个元素的值，每个元素占据⼀行
int arr[4] = {0, 1, 2, 3};
for (int &i : arr) // i为引⽤变量 
    i = i * 2; // 将数组中的每⼀个元素都乘以2，arr[4]的内容变为了{0, 2, 4, 6}
// v是⼀个int类型的vector容器
for (auto i : v)
cout << i << " ";
// 上面的写法等价于
for (int i = 0; i < v.size(); i++)
    cout << v[i] << " ";
  1. to_string()&&string.c_str()
1
2
3
4
5
6
string s1 = to_string(123); // 将123这个数字转成字符串
cout << s1 << endl;
string s2 = to_string(4.5); // 将4.5这个数字转成字符串
cout << s2 << endl;
cout << s1 + s2 << endl; // 将s1和s2两个字符串拼接起来并输出
printf("%s\n", (s1 + s2).c_str()); // 如果想⽤printf输出string，得加⼀个.c_str()
  1. 将字符串转化为其他类型
1
2
3
4
5
6
7
string str = "123";
int a = stoi(str);
cout << a;
str = "123.44";
double b = stod(str);
cout << b;
return 0;

不不仅有stoi、stod两种，相应的还有：

  • stof (string to float)
  • stold (string to long double)
  • stol (string to long)
  • stoll (string to long long)
  • stoul (string to unsigned long)
  • stoull (string to unsigned long long)

题解注意事项

  1. 背包问题：注意背包容量边界要取到，背包容积比较为实际值
  2. 字符串处理：可以考虑正则表达式
  3. dfs+cin真的可以超时
  4. 排序传参用引用传参
  5. 结构体可以通过{}直接构造

常用算法

  1. 判断素数：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    bool isPrime(int a){
        if(a <= 1) return false;
        else{
            int q = (int)sqrt(a*1.0);
            for(int i = 2; i <= q; i++){
                if(a % i == 0) return false;
            }
        }
        return true;
    }
  2. DFS: