杂项

tip¶

命令行编译运行：gcc

输入输出重定向

    freopen("debug\\in.txt","r",stdin); //输入重定向，输入数据将从in.txt文件中读取 
    freopen("debug\\out.txt","w",stdout); //输出重定向，输出数据将保存在out.txt文件中 
    while(cin>>a>>b) 
    cout<<a+b<<endl; // 注意使用endl 
    fclose(stdin);//关闭文件 
    fclose(stdout);//关闭文件

1024mb内存~\(10^8\)int数组
万能头文件：#include <bits/stdc++.h>
pair#include<utility>
提升cin cout的性能：ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
关闭scanf报错#pragma warning(disable:4996)
使用c++11：-std=c++11
字符转化为数字并指定进制stoi(hexStr, nullptr, 16);
unsigned：ul
ll、ull
按行读取getline(cin, line);
使用lambda在函数内定义函数

```c++ //为了在lambda内递归调用，需要先声明，不然直接auto就行 // 定义 lambda 的类型 function parse;

// 定义 lambda，捕获 parse 的引用
parse = [&](const string& s, int l, int r, int id) -> bool {
    // 递归调用示例
    if (l < r) {
        return parse(s, l + 1, r, id); // 递归调用
    }
    return true; // 基本情况
};

```

字符判断
判断数字（isdigit）：isdigit(int ch)
判断字母（isalpha）：isalpha(int ch)
判断字母或数字（isalnum）：isalnum(int ch) 。
判断小写字母（islower）：islower(int ch)
判断大写字母（isupper）：isupper(int ch)
排列
获取下一个排列next_permutation(vec.begin(), vec.end())
如果存在下一个更大的排列，函数会修改序列并返回 true；如果这个排列已经是字典序中的最大排列，则它会重排为最小排列（即升序排列）并返回 false。

oj反馈¶

Compiling:代码正在后台编译 Restricted Function:代码中使用了不安全的函数 Compilation Error:代码编译错误，可以点击查看编译错误细节 Running:程序运行中 Time Limit Exceeded:程序超过了题目的时间限制 Memory Limit Exceeded:程序超过了题目的内存限制 Runtime Error:SIGFPE:程序运行时错误：浮点数异常 Runtime Error:SIGSEGV:程序运行时错误：段错误 Presentation Error:程序正确，但是输出格式有错误 Accepted:程序正确，题目已经正确解答 Wrong Answer:程序不正确

摩尔投票法¶

vote初始值为0，当vote为零时，选定当前元素为临时众数，vote+1，遇到其他数vote-1。循环进行，最后的临时众数就是答案。
剑指 Offer 39. 数组中出现次数超过一半的数字
（找众数）
229. 多数元素 II
拓展至n/3

stl¶

算法¶

unique
仅对相邻元素有效。因此，在使用之前，通常需要先对序列进行排序
c++ // 使用 std::unique 移除相邻的重复元素 auto newEnd = std::unique(v.begin(), v.end()); // 删除多余的元素 v.erase(newEnd, v.end());

集合¶

优先队列自定义比较
```c++ auto compare = { return a > b; // 小的数优先级高 };
```
// 创建优先队列
std::priority_queue<int, std::vector<int>, decltype(compare)> pq(compare);
```
//法2 struct Compare { bool operator()(const int& a, const int& b) { // 定义优先级，比如这里是小的数优先级高 return a > b; } }; std::priority_queue, Compare> pq; ```

数学¶

round() - 这个函数用于四舍五入一个浮点数到最接近的整数。
floor() - 将浮点数向下取整到最接近的整数。
ceil() - 将浮点数向上取整到最接近的整数。
fabs() - 计算一个浮点数的绝对值。
sqrt() - 计算一个数的平方根。
pow() - 用于计算一个数的指数幂。
exp() - 计算自然对数的底数（e）的指数幂。
log() - 计算一个数的自然对数（以e为底）。
log10() - 计算一个数的以10为底的对数。
sin(), cos(), tan() - 分别计算一个角度（以弧度为单位）的正弦、余弦和正切值。
asin(), acos(), atan() - 分别计算一个数的反正弦、反余弦和反正切值。
fmod() - 计算两个数的浮点余数。
hypot() - 计算直角三角形的斜边长度。

离散化¶

思想¶

把无限空间中的有限的个体映射到有限的空间中，提高时空效率（不改变数据相对关系的前提下对数据进行缩小，处理比较稀疏的数据），可以看作是一种哈希
如[100,200],[20,100000]->[2,3],[1,4]
如把一组数据转化为排序后与之相对应的下标
只关心数据之间的（大小）关系，不关心数据具体的值
stl实现：sort+unique+lower_bouond
c++ sort(X,X+num); int m=unique(X,X+num)-X;//离散化 for(int i=0; i<n; i++) { int l=lower_bound(X,X+m,li[i])-X;//寻找位置 int r=lower_bound(X,X+m,ri[i])-X; update(l,r,i,0,m,1); }
对区间进行离散化时可以如果两个区间之间不是连续的，应该插入额外元素
[1,100][200,500]->[1,2][4,5]（如区间覆盖问题，本来来没覆盖，变成覆盖了）
去重完毕后，进行一个处理,如果相邻数字间距大于1的话,在其中加上任意一个数字。这样会把原来的缝隙留出来.

例题¶

（难）1036. 逃离大迷宫
离散化处理加速bfs（因为大部分为空格，可以进行合并）

class Solution {
private:
    static constexpr int BOUNDARY = 1000000;
    static constexpr int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public:
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        if (blocked.size() < 2) {
            return true;
        }
        vector<int> rows, columns;//统计全部xy坐标
        for (const auto& pos: blocked) {
            rows.push_back(pos[0]);
            columns.push_back(pos[1]);
        }
        rows.push_back(source[0]);
        rows.push_back(target[0]);
        columns.push_back(source[1]);
        columns.push_back(target[1]);

        // 离散化
        sort(rows.begin(), rows.end());
        sort(columns.begin(), columns.end());
        rows.erase(unique(rows.begin(), rows.end()), rows.end());//去重
        columns.erase(unique(columns.begin(), columns.end()), columns.end());
        unordered_map<int, int> r_mapping, c_mapping;//哈希映射（离散化）（xy分别进行映射）

        int r_id = (rows[0] == 0 ? 0 : 1);//若原坐标不为0则要增加一个空行（列）
        r_mapping[rows[0]] = r_id;
        for (int i = 1; i < rows.size(); ++i) {
            r_id += (rows[i] == rows[i - 1] + 1 ? 1 : 2);
            r_mapping[rows[i]] = r_id;
        }
        if (rows.back() != BOUNDARY - 1) {//末尾增加空行（列）
            ++r_id;
        }

        int c_id = (columns[0] == 0 ? 0 : 1);
        c_mapping[columns[0]] = c_id;
        for (int i = 1; i < columns.size(); ++i) {
            c_id += (columns[i] == columns[i - 1] + 1 ? 1 : 2);
            c_mapping[columns[i]] = c_id;
        }
        if (columns.back() != BOUNDARY - 1) {
            ++c_id;
        }

        vector<vector<int>> grid(r_id + 1, vector<int>(c_id + 1));//压缩图
        for (const auto& pos: blocked) {
            int x = pos[0], y = pos[1];
            grid[r_mapping[x]][c_mapping[y]] = 1;
        }//障碍新坐标

        int sx = r_mapping[source[0]], sy = c_mapping[source[1]];
        int tx = r_mapping[target[0]], ty = c_mapping[target[1]];

        queue<pair<int, int>> q;//新目标点/起点
        q.emplace(sx, sy);
        grid[sx][sy] = 1;
        while (!q.empty()) {//bfs
            auto [x, y] = q.front();
            q.pop();
            for (int d = 0; d < 4; ++d) {
                int nx = x + dirs[d][0], ny = y + dirs[d][1];
                if (nx >= 0 && nx <= r_id && ny >= 0 && ny <= c_id && grid[nx][ny] != 1) {
                    if (nx == tx && ny == ty) {
                        return true;
                    }
                    q.emplace(nx, ny);
                    grid[nx][ny] = 1;
                }
            }
        }
        return false;
    }
};

随机算法¶

uniform_int_distribution<int> distribute(1, 6)获取一个范围在1~6的可以生成随机数的对象
distribute(gen)使用时要输入一个随机种子
mt19937 gen((unsigned int)time(NULL)); mt19937 gen{random_device{}()};几种生成随机数种子的方法
另一种随机方式:
int randomIndex = rand()%nums.size()
种子RandomizedSet() {srand((unsigned)time(NULL));}

池塘抽样¶

382. 链表随机节点

输入输出¶

cout控制实数输出位数
cout<<fixed<<setprecision(2)<<g[0][1]<<endl;
这是直接阶段，可能需要便宜用round舍入再还原

快速读取¶

c++ inline void read(int &x){ char ch=getchar();int f=1;x=0; while(!isdigit(ch) && ch^'-') ch=getchar(); if(ch=='-') f=-1,ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); x*=f; }
c++ inline ll readll() { register ll s = 0; register char ch = getchar(); while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch & 15), ch = getchar();//s*10+ch-'0'，对于大整数可以在这个位置取余，避免使用高精度计算 return s; }
P2613 【模板】有理数取余
通用快读
c++ template<typename T> inline void read(T &a) { T s = 0, w = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); } while(c >= '0' && c <= '9') { s = (s << 1) + (s << 3) + (c ^ 48); c = getchar(); } a = s*w; }

printf¶

printf("<格式化字符串>", <参量表>);

格式字符¶

数据类型

格式字符	意义
a, A	以十六进制形式输出浮点数(C99 新增)。实例 printf("pi=%a\n", 3.14); 输出 pi=0x1.91eb86p+1。
d	以十进制形式输出带符号整数(正数不输出符号)
o	以八进制形式输出无符号整数(不输出前缀0)
x,X	以十六进制形式输出无符号整数(不输出前缀Ox)
u	以十进制形式输出无符号整数
f	以小数形式输出单、双精度实数
e,E	以指数形式输出单、双精度实数
g,G	以%f或%e中较短的输出宽度输出单、双精度实数
c	输出单个字符
s	输出字符串
p	输出指针地址
lu	32位无符号整数
llu	64位无符号整数

flags（标识）	描述
-	在给定的字段宽度内左对齐，默认是右对齐（参见 width 子说明符）。
+	强制在结果之前显示加号或减号（+ 或 -），即正数前面会显示 + 号。默认情况下，只有负数前面会显示一个 - 号。
(space)	如果没有写入任何符号，则在该值前面插入一个空格。
#	与 o、x 或 X 说明符一起使用时，非零值前面会分别显示 0、0x 或 0X。与 e、E 和 f 一起使用时，会强制输出包含一个小数点，即使后边没有数字时也会显示小数点。默认情况下，如果后边没有数字时候，不会显示显示小数点。与 g 或 G 一起使用时，结果与使用 e 或 E 时相同，但是尾部的零不会被移除。
0	在指定填充 padding 的数字左边放置零（0），而不是空格（参见 width 子说明符）。

width（宽度）	描述
(number)	要输出的字符的最小数目。如果输出的值短于该数，结果会用空格填充。如果输出的值长于该数，结果不会被截断。
*	宽度在 format 字符串中未指定，但是会作为附加整数值参数放置于要被格式化的参数之前。

.precision（精度）

描述

.number

对于整数说明符（d、i、o、u、x、X）：precision 指定了要写入的数字的最小位数。如果写入的值短于该数，结果会用前导零来填充。如果写入的值长于该数，结果不会被截断。精度为 0 意味着不写入任何字符。对于 e、E 和 f 说明符：要在小数点后输出的小数位数。对于 g 和 G 说明符：要输出的最大有效位数。对于 s: 要输出的最大字符数。默认情况下，所有字符都会被输出，直到遇到末尾的空字符。对于 c 类型：没有任何影响。当未指定任何精度时，默认为 1。如果指定时不带有一个显式值，则假定为 0。

.*

精度在 format 字符串中未指定，但是会作为附加整数值参数放置于要被格式化的参数之前。

length（长度）	描述
h	参数被解释为短整型或无符号短整型（仅适用于整数说明符：i、d、o、u、x 和 X）。
l	参数被解释为长整型或无符号长整型，适用于整数说明符（i、d、o、u、x 和 X）及说明符 c（表示一个宽字符）和 s（表示宽字符字符串）。
L	参数被解释为长双精度型（仅适用于浮点数说明符：e、E、f、g 和 G）。

输出格式
%-10s：左对齐并占用宽度为 10 的字符串；
%5.2f：右对齐并占用宽度为 5，保留两位小数的浮点数；
%#x：输出带有 0x 前缀的十六进制数。

sprintf¶

将格式化字符串输出到str字符串而不是控制台
sprintf(char *str, const char *format, ...)

scanf¶

补充
%d%d%d 是按十进值格式输入三个数值。输入时，在两个数据之间可以用一个或多个空格、tab 键、回车键分隔。如果使用 , 来分隔输入的 %d, 相应的输入时也需要添加 ,

gets¶

gets()函数用来从标准输入设备(键盘)读取字符串直到回车结束, 但回车符不属于这个字符串。
可以用于处理包含空格的字符串
类似scanf("%s", &s)但是结束方式不同

puts¶

puts()函数用来向标准输出设备(屏幕)写字符串并换行, 其调用格式为:puts(s);
相当于printf("%s\n",s)

getline¶

istream& getline ( istream &is , string &str [, char delim ]);
is常用cin
delim表示读取到该字符串时停止，默认为\n回车

模板¶

输入¶

多组输入数据，不说明多少组，直到读至输入文件末尾为止
c #include <stdio.h> int main() { int a,b; while (scanf("%d %d",&a, &b) != EOF) printf("%d\n",a+b); }
多组输入数据，不说明多少组，以某特殊输入为结束标志。
c #include <stdio.h> int main() { int a,b; while(scanf("%d %d",&a, &b) &&(a||b)) printf("%d\n",a+b); }
每个字符串中不含空格、制表符及回车
c char str1[1000], str2[1000]; scanf("%s%s", str1, str2);
字符串中含有空格、制表符，但不含回车
c char str[1000]; gets(str);
因为scanf用空格、制表符及回车作为字符串的分界符;gets函数用回车作为字符串的分界符

输出¶

每当处理完一组测试数据，就应当按题目要求进行相应的输出操作。而不必将所有结果储存起来一起输出。在处理输出时，一般要注意：每行输出均以回车符结束，包括最后一行。
很多题目都要求在输出数据的恰当位置加空行。一个空行就是一个单独的"\n"。这里，有的题目说：“After each test case, you should output one blank line”，而有的题目说：“Between each test case, you should ouput one blank line”。要注意After和Between的区别，因为如果多了一或少了空行，将导致Presentation Error甚至Wrong Answer。
after
- c int i; for (i = 0; i < 10; i++) { printf("%d\n", a); printf("\n"); }
between
- c int i; for (i = 0; i < 10; i++) { printf("%d\n", a); if (i != 9) printf("\n"); }
带格式的字符串输出,有些题目要求输出这样的字符串：abc*****de****f，其中“*”代表空格。要求是这样的：str1在前5个字符中左对齐，str2在第6到第10个字符中右对齐，str3在第11到第15个字符中右对齐。可行的做法是，先初始化一个数组，用' '（空格）填充，再在相应的位置填相应的内容。
c char str[1000]; char str1[] = "abc", str2[] = "de", str3[] = "f"; memset(str, ' ', 1000 * sizeof(char)); sprintf(str, "%s", str1);//把字符串输出到结果字符串的指定位置 str[strlen(str1)] = ' '; sprintf(str + 5, "%5s", str2); str[10] = ' '; sprintf(str + 10, "%5s", str3); str[15] = '\0'; puts(str);

特殊¶

按行读入不定数目的元素：
c++ string line, token; getline(cin, line); stringstream ss(line); while (ss >> token) { ... }
使用getchar的方法
cin >> num 读取输入时，会自动跳过空格、制表符和换行符等空白字符，直到找到一个可以转换为整数的字符序列。(scanf也是如此)
cin 读取完一个整数后，会停留在该整数后面的字符（通常是一个空格或换行符）上。
注意getchar是c风格，如果已经sync_with_stdio(0)则不能和cin混用。可以使用cin>>ws消除空白符
当在 cin 后使用 std::ws 时，它会不断地读取并丢弃空白字符，直到遇到第一个非空白字符为止。这样可以确保后续的输入操作从一个非空白字符开始。
```
while(cin >> num) {
    nums.push_back(num);
    // 读到换行符，终止循环
    if(getchar() == '\n') {
        break;
    }
}
```
指定位数浮点数输出
printf(".2f")是四舍五入输出
cout << fixed << setprecision(2) << num << endl;是直接阶段，需要先手动进行四舍五入num = round(num * 100.0) / 100.0;
非空格分隔符如,
使用stringstream结合重载的getline，即getline中指定分割符号
c char delimiter = ','; stringstream ss(str); string token; // 使用 getline 从 stringstream 中读取子字符串，直到遇到分割符 while (getline(ss, token, delimiter)) { tokens.push_back(token); }

stl¶

迭代器使用¶

251. 展开二维向量
使用迭代器可以避免拷贝，减少额外空间占用

补充¶

万能头文件 #include <bits/stdc++.h>
String 查询操作
find()：返回搜索字符串在目标字符串中第一次出现的位置。如果未找到，则返回 string::npos
find_first_of() 函数从字符串的开头开始查找指定字符集合中的任意一个字符，并返回第一个匹配字符的位置。如果未找到匹配字符，则返回 string::npos。
find_last_of() 函数从字符串的结尾开始查找指定字符集合中的任意一个字符，并返回最后一个匹配字符的位置。如果未找到匹配字符，则返回 string::npos。
参数 char_set, pos（可以指定起始位置）
返回值是下标不是迭代器/指针
set 与 map 迭代器的更多用法

set 的迭代器不支持许多操作，可以用以下方法操作

*begin 获取第一个元素，*rbegin 获取最后一个元素

用 prev (), next ()实现++--等操作

如 prev (it, 2)可以指定移动的数目

struct Node {
    int cnt, time;
    bool operator < (const Node& rhs) const {
        return cnt == rhs.cnt ? time < rhs.time : cnt < rhs.cnt;
    }
};
set<Node> S;//就会按照自定义比较规则进行排序。

逆序访问 map

      map<int, int> mymap;
      map<int, int>::reverse_iterator it;
      for(it=mymap.rbegin();it!=mymap.rend();it++){
        cout << it->first << " " << it->second << endl;
      }

快速填充fill(val.begin(),val.end(),0);

自定义哈希

    struct Line{
        int x,y,dic;
        Line(int x,int y,int dic):x(x),y(y),dic(dic){};
        bool operator==(const Line& other) const {
            return x == other.x && y == other.y && dic == other.dic;
        }
    };
    namespace std {
        template <>
        struct hash<Line> {
            size_t operator()(const Line& line) const {
                return ((hash<int>()(line.x) ^ (hash<int>()(line.y) << 1)) >> 1) ^ (hash<int>()(line.dic) << 1);//借助内置的哈希函数使用左右移动以及异或进行组合可以减少哈希冲突

            }
        };
    }

需要重写比较及哈希函数

c风格¶

数组¶

memset(a,num,sizeof(a))
要注意的是num并不能取任意值，通常只能为0、-1、0x3f（接近INT_MAX）