​

常用语法

代码框架

#include 
using namespace std;
 
const int N = 1e5+5;
int n, a[N];
 
int main(){
    freopen("xxxx.in", "r", stdin);
    freopen("xxxx.out", "w", stdout);
    ios::sync_with_stdio(0);  // 加快读入（也可以用 scanf/printf）
    // 个人编写的常规代码
    return 0;
}
 

Copy

常用函数

// 求最大/小值、绝对值
double a, b;
int t = max(a, b);
int t = min(a, b);
int t = abs(a);
// 浮点数向上向下取整、四舍五入取整
int t = ceil(a);
int t = floor(a);
int t = round(a);
// 开根号和幂次
double t = sqrt(a);
double t = pow(x, y);  // x^y

Copy

格式控制

// 保留小数位(这里是2位)
double a;
cout << fixed << setprecision(2) << a;
print("%.2f", a);
// 位宽（CSP不考）
int a;
cout << setw(3) << a;

Copy

数据类型、溢出与转换

// int 的最大最小值
INT_MAX = 2147483647;   // 2^31 - 1, 约为 2e9;
INT_MIN = -2147483648;  // -2^31
// long long 的最大最小值
LLONG_MAX = 9223372036854775807; // 2^63-1, 约为 9e18
LLONG_MIN = -9223372036854775808; // -2^63
 
// float 精度： 6~7位
// double 精度： 15~16位
// 避免精度损失：1、使用 double   2、转整数运算
 
// 数字转字符: 'A'(65)  'a'(97)  '0'(48)
char A = char(65);
char a = char(97);
char c = 'a' + 2;      // 'c' = 'a' + 2
char seven = '0' + 7;  // '7' = '0' + 7
 
// 字符转数字
int a = 'a';    // a: 97
int A = 'A';    // A：65
int t = 't' - 'a';     // 计算字母间差值
int seven = '7' - '0';
 

Copy

数字处理

数位分离与反转

数位分离

int a;
cin >> a;
int ge = a % 10;
int shi = a /10 % 10;
int bai = a / 100 % 10;
......
while(a) {
    int x = a % 10;   // 当前位（从低到高）
    a /= 10;
}

Copy

判断回文数

// 判断回文
bool hw(int x) {
    int t = x, s = 0;
    while(t) {
        s = s * 10 + t % 10;
        t /= 10;
    }
    return s == x;
}

Copy

日期相关

// 判断闰年
int year;
if(year%4==0&&year%100!=0 || year%400==0) cout << "leap year";
// 天数计算
int days[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
// 如何求两个日期之间的天数之差？

Copy

字符串操作

字符串函数

// 最常用的操作
str.size();//返回字符串长度
str.length();//返回字符串长度
str.empty();//检查 str 是否为空，为空返回 1，否则返回 0
str[n];//存取 str 第 n + 1 个字符
str.at(n);//存取 str 第 n + 1 个字符（如果溢出会抛出异常）
// 反转
reverse(str.begin(), str.end());
// 查找
str.find("ab");//返回字符串 ab 在 str 的位置
str.find("ab", 2);//在 str[2]~str[n-1] 范围内查找并返回字符串 ab 在 str 的位置
str.rfind("ab", 2);//在 str[0]~str[2] 范围内查找并返回字符串 ab 在 str 的位置
if(str.find("ab")!=string::npos)
{    cout << "zhaodaole, xiabiao wei" << str.find("ab"); }
// 子串
str.substr(3);  // 返回 [3] 及以后的子串
str.substr(2, 4); // 返回 str[2]~str[2+(4-1)] 子串(即从[2]开始4个字符组成的字符串)
str.substring(5, 10);  // 返回 str[5]~str[9] 子串(不包含结尾)
// 插入
str.insert(2, "sz");//从 [2] 位置开始添加字符串 "sz"，并返回形成的新字符串
str.insert(2, "abcd", 3);//从 [2] 位置开始添加字符串 "abcd" 的前 3 个字符，并返回形成的新字符串
str.insert(2, "abcd", 1, 3);//从 [2] 位置开始添加字符串 "abcd" 的前 [2]~[2+(3-1)] 个字符，并返回形成的新字符串
// 删除
str.erase(3);//删除 [3] 及以后的字符，并返回新字符串
str.erase(3, 5);//删除从 [3] 开始的 5 个字符，并返回新字符串
// 替换
str.replace(2, 4, "sz");//返回把 [2]~[2+(4-1)] 的内容替换为 "sz" 后的新字符串
str.replace(2, 4, "abcd", 3);//返回把 [2]~[2+(4-1)] 的内容替换为 "abcd" 的前3个字符后的新字符串
// 追加
str = str + "abc";
str.push_back('a');//在 str 末尾添加字符'a'
str.append("abc");//在 str 末尾添加字符串"abc"
 

Copy

字符串回文

// 方法一、反转再判断(常数较大)
string s;
cin >> s;
string b = s;
reverse(b.begin(), b.end());
if(s == b) cout << "yes";
// 方法二、原地判断
for(int i = 0, j = s.size() - 1; i < j; i++, j--) {
    if(s[i] != s[j]) {
        cout << "no";
        return 0;
    }
}
cout << "yes";

Copy

二维字符数组 & 方向数组

char a[N][N];
// 方向数组：左、右、上、下
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

Copy

STL 函数

standard template library，锦上添花、如虎添翼的工具

sort();
reverse();
unique();
lower_bound();
upper_bound();
*max_element();
*min_element();

Copy

数组遍历类

连续性

// 连续最长相同、最长上升或下降： 相邻两项比较，并讨论即可
int a[N], s = 0;
int ans = 0;
 
for(int i = 1; i <= n; i++) {
    if(a[i] == a[i-1]) {  // a[i] < a[i-1]  或 a[i] > a[i-1]
        s++;
        ans = max(ans, s);
    } else {
        s = 1;
    }
}
cout << ans;

Copy

双指针

双指针是一种思想，一种技巧或一种方法，并不是什么特别具体的算法，在二分查找等算法中经常用到这个技巧。具体就是用两个变量动态存储两个或多个结点，来方便我们进行一些操作。通常用在线性的数据结构（数组、链表、队列等）中。

判断字符串回文就是一种最简单的双指针

// 方法二、原地判断
for(int i = 0, j = s.size() - 1; i < j; i++, j--) {
    if(s[i] != s[j]) {
        cout << "no";
        return 0;
    }
}
cout << "yes";

Copy

股票买卖 I - TopsCoding

int n, a[N];
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int minv = a[1], ans = 0;
for (int i = 2; i <= n; i++) {
    minv = min(minv, a[i]);
    ans = max(ans, a[i] - minv);
}
cout << ans;

Copy

归并数组 - TopsCoding

cin >> m;
for(int i=1; i <= m; i++)    cin >> a[i];
cin >> n;
for(int i=1; i <= n; i++)    cin >> b[i];
 
int pa = 1, pb = 1;
while(pa<=m && pb<=n) {
    if(a[pa]<=b[pb])  cout << a[pa++] << ' ';
    else cout << b[pb++] << ' ';
}
while(pa <= m)  cout << a[pa++] << ' ';
while(pb <= n)  cout << b[pb++] << ' ';

Copy

数组元素的目标和 - TopsCoding

cin >> n >> m >> k;
for (int i = 0; i < n; i ++ ) cin >> a[i];
for (int i = 0; i < m; i ++ ) cin >> b[i];
 
// i从 0开始 从前往后遍历
// j从 m - 1开始 从后向前遍历
for (int i = 0, j = m - 1; i < n; i ++) {
    // 当和大于 k 时，意味着 b[j] 不会有能和它匹配的 a[i]，所以 j 左移
    // 不将 i 后移，因为后移后的和仍旧大于 k
    while(j >= 0 && a[i] + b[j] > k) j --;
    if(j >= 0 && a[i] + b[j] == k) printf("%d %d\n", i, j);
}

Copy

双指针练习题

1. 统计回文子串 - TopsCoding
2. 归并数组 - TopsCoding
3. 判断子序列 - TopsCoding
4. 数组元素的目标和 - TopsCoding
5. 感应门 - TopsCoding
6. 游戏闯关 - TopsCoding

数组标记类

数组标记是指 用数组去存储问题中的输入数据或者中间数据，比如计数、判断有无，本质上是用空间换时间，最常见的好处就是降低代码的时间复杂度，不容易出现超时问题。

常用在：

1. 桶排序、桶计数
2. 状态标记
3. dfs()/bfs()中标记选择或状态

// 标记数组
int flag[N];  // flag[i] 用于标记状态或者计数
 
flag[i] = 1;  // 数组标记状态，选择 / 不选择

Copy

往年真题：直播获奖（live） - TopsCoding

函数定义

如果一个函数不是 void 类型，一定要保证在任何情况下都有返回值，否则可能爆零（尤其是dfs中）！！！

void/int hanshu(int a, int b, ...)
{
    ......
    return ...;
}

Copy

递归

递归有两个显著的特征,终止条件和自身调用:

• 自身调用：原问题可以分解为子问题，子问题和原问题的求解方法是一致的，即都是调用自身的同一个函数。
• 终止条件：递归必须有一个终止的条件，即不能无限循环地调用本身。

void/int digui(......)
{
    if(......) {    // 终止条件
        ......
        return ...;
    }
    ......
    digui(......);    // 缩小问题规模，调用自身
    return ...;
}

Copy

位运算符的应用*

// 判断奇数
if(t & 1) {
    cout << "是奇数";
}
// 乘2、除2、2 的整数幂次
int t = x << 1;    // t = x * 2
int t = x >> 1;    // t = x / 2
int t = 1 << x;    // t = 2 ^ x = pow(2, x)
 
// 判断一个非负整数是不是2的幂，注意运算符优先级
if((x&(x-1))==0)  cout<<"yes"<
 
/********以下不是重点*********/
// 交换两个数（实际效率并没有临时变量法高）
a = a ^ b;
b = a ^ b;
a = a ^ b;
// 取int型变量a的第k位
int t = a >> k & 1;
// 求两个变量的平均值（不会溢出）
int ave = (x&y)+((x^y)>>1);
// 求相反数 -x
int t = (~x+1);
// 判断x的n位（二进制中）是否为1
if(x&(1<"yes"<
// 将x的n位（二进制中）清0
x=x&~(1<

Copy

往年真题