好用算法 Trick

很大的数

表示一个很大的数，看类型包含多少字节写多少个 3f。

info

$(3f)_{16}=(0111\ 1111)_2$

const int N = 0x3f3f3f3f;

判断是否为奇数

利用位运算判断奇数，因为奇数的二进制首位都是 1，和 1 相与后必定是 1，否则是 0。

• 结果为 true：是奇数
• 结果为 false：是偶数

bool isEven(int num) {
    return num & 1;
}

建图

邻接表

法一：

const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], idx;

void add (int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}   

法二：

typedef pair<int, int> PII; // first 为权，second 为连接的节点编号
vector<PII> h[N];

while (m --) {
    int a, b, c;
    cin >> a >> b >> c;
    h[a].push_back({c, b});
    h[b].push_back({c, a});
}

邻接矩阵

int g[N][N];

for (int i = 0; i < m; i++) {
    g[a][b] = g[b][a] = min(g[a][b], c); // 无向图
    g[a][b] = min(g[a][b], c); // 有向图
}

DFS（深度优先遍历）

tip

遍历不需要恢复现场，因为遍历完就结束了，不需要进行下一步操作

void dfs(int u, ...) { // ... 处可以加入下一层更新的参数
    st[u] = true;
    // ... 可填代码（往下层遍历之前的操作，可计数blahblah等操作）
    for (int i = 0;i < v[u].size(); i++) {
        int j = v[u][i]; //邻接表存，其值表示节点编号
        if (!st[u]) {
            // ... 前序
            dfs(j, ....);
            // ... 后序
        }
    }
    // ... 如果有返回值可以在这里返回
}

DFS（深度优先搜索）

tip

搜索需要恢复现场，因为搜索完之后后续可能需要用到这些元素，所以要恢复

void dfs(int u, ...) {
    if (u == n) return ; // 结束条件不唯一
    
    // ... 可做遍历前预处理，例如剪枝等
    
    for (int i = 0; i < n; i ++) {
        int j = g[u][i]; // 邻接矩阵存，值代表边权，i为节点编号
        if (!st[i] && ...) { // ... 处代表满足什么条件才往下搜
            // 记录现场，表示访问过，下次不在访问
            st[u] = true;
            dfs(i, ...);
            // 上一次的遍历结束了，开始遍历下一种情况，恢复现场
            st[u] = false;
        }
    }
}

BFS（广度优先遍历 / 广度优先搜索）

tip

BFS 需要用到队列，因为队列的特点就是有先后顺序（先进先出）的，而 BFS 遍历的过程中也是有先后顺序的，恰巧能够满足这一个特点。

在同一层中一般先遍历左边的节点，同时把要遍历的下一层节点加入到队列当中，然后再遍历右边的，然后再把下一层需要遍历的节点加入到队列中，很自然形成了一个先后顺序关系。

int bfs()
{
    queue<int> q;
    q.push(1); // 初始化队列，从根节点开始层序遍历...

    while (!q.empty())
    {
        int t = q.front();
        q.pop();  // 拿到之后将遍历之后的出队
        
        // 对节点 t 进行相应的操作，如打印等 ...
        
        // ... 将下一层要遍历的节点加入到队列当中
        if (...) q.push(...)
        if (...) q.push(...)
    }
    // ... 如果有返回值可以在这里返回
}

判断素数

bool isPrime(int x) {
    if (x == 2 || x == 3) 
        return true;
 
    if (x % 6 != 1 && x % 6 != 5)
        return false;

    for (int i = 5; i <= sqrt(x); i += 6) {
        if (x % i == 0 || x % (i + 2) == 0)
            return false;
    }
    return true;
}

STL

vector

vector<int> a(10); 

vector<int> a(10,0); 

vector<vector<int>> dp( 3 ,vector<int> (5,0));      //定义一个3X5的二维数组

vector<int> b(a); //用b向量来创建a向量，整体复制性赋值

vector<int> a(b.begin(),b.begin()+3); //定义了a值为b中第0个到第2个（共3个）元素

int b[7]={1,2,3,4,5,9,8};
vector<int> a(b,b+7); //从数组中获得初值

map

// map 转 vector
unordered_map<string, int> m;
vector<pair<string, int>> a(m.begin(), m.end());

string

//寻找子串: 在str寻找是否有curStr，返回下标
str.find(curStr) == string::npos
    
//截取子字符串: 从str中截取从下标0开始，length长度的字符串
resStr = str.substr(0,length);