基础算法

1、二分
2、前缀和与差分
3、STL
4、双指针
5、离散化
6、位运算

二分

在一个有序的序列上通过不断的缩小区间减少查找的时间
基础二分：有序的序列上查找 >X, ≥X, ≤X, <X 的最小数或最大数
二分答案：答案单调且有范围，二分答案模拟过程来逼近最优答案

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;

int n, m;
int a[N], b[N];

bool check(int x)
{
    
    int ans = 0;
    for(int i = 1; i <= n; i ++ )
    {
    
        if(a[i] < x )
        {
    
            if(b[i] < x - a[i]) return false;
            ans += x - a[i];
        }
    }
    if(ans > m) return false;
    return true;
}

signed main()
{
    
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= n; i ++ ) cin >> b[i];
    int l = 0, r = n * 2;
    while(l < r)
    {
    
        int mid = (l + r + 1) / 2;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
}

一维前缀和与一维差分

一维前缀和：实现快速查询区间 [l , r] 的和
预处理前缀和数组sum：O(n)
查询区间 [l , r] 的和：O(1)

sum[i] = sum[i - 1] + a[i]
sum[r] - sum[l - 1]

一维差分：实现快速对区间 [l , r] + k
预处理差分数组b：O(n)
对区间 [l , r] + k：O(1)

b[i] = a[i] - a[i - 1]
b[l] += k, b[r + 1] -= k

二维前缀和与二维差分

二维前缀和：快速查询子矩阵和，子矩阵左上角[x1, y1]，子矩阵右下[x2, y2]
预处理二维前缀和数组sum：O(n $\ast$ m)

sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]

查询子矩阵和：O(1)

sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]

二维差分：快速对子矩阵内所有元素 + k，子矩阵左上角[x1, y1]，子矩阵右下[x2, y2]
预处理二维差分数组b：O(n $\ast$ m)

b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]

对子矩阵所有元素 + k：O(1)

b[x1][y1] += k , b[x1][y2 + 1] -= k, b[x2 + 1][y1] -= k, b[x2 + 1][y2 + 1] += k

STL

栈，队列，优先队列通用方法：push，pop，size，empty

stack：top
queue：front，back
priority_queue：top

vector，map，哈希表，set通用方法：size，clear，erase，begin，end

vector：push_back，pop_back，rbegin，rend
map：count，insert ，lower_bound，upper_bound
unordered_map
set：lower_bound upper_bound

双指针

用两个不同速度或不同方向的指针对数组或对象进行访问，通过两个不同指针的碰撞从而达到特定的目的
最长连续不重复子序列

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
// 维护一个合法的 [j , i] 的区间，保证区间内所有元素不重复
int a[N];
int st[N]; // 记录 [j , i] 区间内元素出现次数

int main()
{
    
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    int ans = 0;
    for(int i = 1, j = 1; i <= n; i ++ ) //每次将右区间扩大 1， 同时更新 st 数组使 st[i]++，根据新添加的元素 a[i] 判断 st[a[R]] 是否 > 1
    {
    
        st[a[i]] ++ ;
        while(st[a[i]] > 1)//持续扩大左区间，同时更新 st 数组使 st[j] -- ，直到 st[i] == 1，说明找到合法区间
        {
    
            st[a[j]] -- ;
            j ++ ;
        }
        ans = max(ans, i - j + 1);
    }
    cout << ans << endl;
}

离散化

把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
区间和

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 1e9 + 10;
typedef long long LL;
typedef pair<int, int> PII;

vector<PII> a;
map<int, int> mp;

int main()
{
    
    int n, m;
    cin >> n >> m;
    while(n --)
    {
    
        int x, c;
        cin >> x >> c;
        mp[x] += c;
    }
    int sum = 0;
    for(auto x : mp)
    {
    
        a.push_back({
    x.first, sum});  //这里的sum不包含x.first上的值，方便使用upper_bound()
        sum += x.second;
    }
    a.push_back({
    INF, sum});  //最后加一个无穷大的点，方便处理
    while(m --)
    {
    
        int l, r;
        cin >> l >> r;
        auto p1 = upper_bound(a.begin(), a.end(), (PII){
    l , -INF}); //找到第一个大于等于l的点
        auto p2 = upper_bound(a.begin(), a.end(), (PII){
    r , INF});  //找到第一个大于r的点
        cout << p2 -> second - p1 -> second << endl;
    }
    return 0;
}

位运算

lowbit定义：
对于任意一个非 0 的正整数 x，lowbit(x) 为 x 二进制中最低位 1 对应的值
例如：12 的二进制位 1100，lowbit(12) = 4，4 二进制位 0100
lowbit 实现：

int lowbit(int x)
{
    
    return x & -x;
}

二进制中1的个数

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int lowbit(int x)
{
    
    return x & -x;
}

int main()
{
    
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
    
        int x, ans = 0;
        cin >> x;
        while(x)
        {
    
            x -= lowbit(x);
            ans ++ ;
        }
        cout << ans << " ";
    }
}

codeforce讲题

Required Length

题意：给定一个 $n$ 和 $x$，每次更新 $x$，使 $x$ 十进制的位数 == $n$，输出最小的更新次数，若无法达到目标，输出 -1
更新 $x$ 的规则：定义 y 是 $x$ 十进制中其中一位，令 $x$ 更新为 $x$ * $y$
数据范围：$2\le n\le 19;1\le x<10^{n-1}$
样例输入：3 2
$x$ 更新过程：2，4，16，96，576或864
bfs直接模拟过程，同时标记已经进入过队列的值，保证不会有点重复进队，第一个位数到达 n 的值的深度就是答案，类似于最短路

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
typedef pair<int, int> PII;

int n, x;
// unordered_map<int, bool> mp; 注意：用c++20交会T，因为数据卡c++20的哈希表，建议用稳定查询logn的map
map<int, int> mp;

int size(int x)
{
    
    int cnt = 0;
    while(x)
    {
    
        x /= 10;
        cnt ++ ;
    }
    return cnt;
}

int bfs()
{
    
    queue<PII> q;
    q.push({
    x, 1});
    mp[x] = true;
    while(q.size())
    {
    
        PII t = q.front();
        q.pop();
        if(size(t.first) == n) return t.second;
        int tmp = t.first;
        while(tmp)
        {
    
            int y = t.first * (tmp % 10);
            if(!mp.count(y)) q.push({
    y, t.second + 1});
            mp[y] = true;
            tmp /= 10;
        }
    }
    return 0;
}

signed main()
{
    
    cin >> n >> x;
    cout << bfs() - 1 << endl;
}

Where is the Pizza?

题意：给定一个 $n$，给定三个长度为 $n$ 的数组 $a,b,c$，输入的 $a$，$b$ 数组保证都是 $1n$ 的，不存在重复元素，$c$ 数组是一个残缺的数组，由若干个 $0$ 和 部分 $1$ 到 $n$ 的数组成，除了 $0$ 保证其他数不重复，现在你需要把 $c$ 数组补全，将 $c$ 数组里 $0$ 改成同位置的 $ai$ 或 $bi$ 且补全后的 $c$ 数组没有重复元素，问 c 数组的构造方案数，答案取模 $10^9+7$。
数据范围：$1\le n\le 10^5$
样例输入：
8
1 6 4 7 2 3 8 5
3 2 8 1 4 5 6 7
1 0 0 7 0 3 0 5
样例解释：
模拟一下过程：
如果令 c[2] = 2，那 c[5] = 4，c[3] = 8，c[7] = 6，c[2] = 2
如果令 c[2] = 6，那 c[7] = 8，c[3] = 4，c[5] = 2，c[2] = 6
可以发现这是一个环，如果环内的一个点被确定，那么整个环都会被确定，对于一个环，最多可以活动两个点，所以一个环可以使答案 $\ast 2$
所以题目转化成找环，如果一对 a[i] 和 b[i] 已经相连，说明这条边就是成环的边

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10, mod = 1e9 + 7;
typedef pair<int, int> PII;

int n;
int a[N], b[N], c[N], g[N];

void init(int n)
{
    
    for(int i = 1; i <= n; i ++ ) g[i] = i;
}

int find(int x)
{
    
    if(x != g[x]) g[x] = find(g[x]);
    return g[x];
}

signed main()
{
    
    int t;
    cin >> t;
    while(t -- )
    {
    
        int n;
        cin >> n;
        init(n);
        for(int i = 1; i <= n; i ++ ) cin >> a[i];
        for(int i = 1; i <= n; i ++ ) cin >> b[i];
        for(int i = 1; i <= n; i ++ ) cin >> c[i];
        int ans = 1;
        for(int i = 1; i <= n; i ++ )
        {
    
            if(c[i] == 0 && a[i] != b[i])
            {
    
                int ga = find(a[i]);
                int gb = find(b[i]);
                if(ga == gb) ans = ans * 2 % mod;
                else g[gb] = ga;
            }
        }
        cout << ans << endl;
    }
}

Tokitsukaze and Good 01-String (hard version)

题意：给定 01 串，保证串长度使偶数，把串分解成若干个连续且相同的子串，如果子串长度都是偶数，那么这个串是好的，否则就是坏的，有任意次操作，操作规则是把 0 变成 1，或者把 1 变成 0，问把给定串变成好的串需要的最少操作数和操作后的最少子串数
首先最少操作数很好求，将串分解成 $n/2$ 个串，也就是两两一对，如果当前两个不一致就说明这个位置必须更改，但是我们不知道需要把 1 变成 0 还是把 0 变成 1，所以具体的方法需要看前后两个合法子串的值
例如：
00001000
01 不合法，因为前后合法子串都是00，所以应该把 1 变成 0，这样才是要求的最小段数
那么其实不需要考虑不合法对，如果前后合法子串一样或不一样都和这个不合法对无关

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

vector<int> h;

int main()
{
    
    int t;
    cin >> t;
    while(t -- )
    {
    
        int n;
        string a;
        cin >> n >> a;
        h.clear();
        int ans = 0, res = 1;
        for(int i = 0; i < n; i += 2)
        {
    
            if(a[i] != a[i + 1]) ans ++ ;
            else h.push_back(a[i]);
        }
        for(int i = 1; i < h.size(); i ++ )
        {
    
            if(h[i] != h[i - 1]) res ++ ;
        }
        cout << ans << " " << res << endl;
    }
}