力扣的板子

map 的用法

 auto it = info.lower_bound(left);
 vector<map<int, int>::iterator>v;

set的用法

题目传送门
技巧：
（1）删除时，将另一个set中的值插入后再处理新的值
（2）在循环开始前就构造好set,后面循环体里只处理滑动窗口的改动部分，这样更清晰，不要追求把所有逻辑都放在循环体里

auto cmp = [&](int a,int b)->bool{
    if(nums[a] == nums[b]){
        return a<b;  //必须有！
    }else{
        return nums[a] > nums[b];
    } 
};
//注意，set自带去重，必须设定值相等时区分开的cmp函数，或者使用multiset才可以
 set<int,decltype(cmp)>s(cmp);

multiset用法

multiset支持相同key的多次插入
删除时的用法

s.erase(key);//删除所有值为key的元素
s.erase(s.find(key));//仅删除一个值为key的元素

class Solution {
    typedef long long ll;
public:
    long long minimumCost(vector<int>& nums, int k, int dist) {
        auto cmp = [&](int a,int b)->bool{
            return a >b;
        };
        multiset<int>s2;//保留其他的数据
        multiset<int,decltype(cmp)>s1(cmp);//记录最小的k-1个数据
        int n = nums.size();
        ll sum = 0;
        ll tot = 0;
        int n1 = k-2;
        for(int i = 2;i<=1+dist;i++){
            int m1 = s1.size();
            if(m1<n1){
                s1.insert(nums[i]);
                tot += nums[i];
            }else{
                int tmp = *s1.begin();
                if(tmp > nums[i]){
                    s1.erase(s1.begin());
                    s1.insert(nums[i]);
                    s2.insert(tmp);
                    tot -= tmp;
                    tot += nums[i];
                }else{
                    s2.insert(nums[i]);
                }
            }
        }
        sum = tot+nums[1];
        for(int i = 2;i<=n-k+1;i++){
            if(i+dist < n){
                int add = nums[i+dist];
                int tmp = *s1.begin();
                if(add < tmp){
                    s1.erase(s1.begin());
                    s1.insert(add);
                    tot -= tmp;
                    tot += add;
                    s2.insert(tmp);
                }else
                    s2.insert(add);
            }
            int del = nums[i];
            if(s1.find(del) != s1.end()){
                s1.erase(s1.find(del));
                tot -= del;
                int tmp = *s2.begin();
                s2.erase(s2.begin());
                s1.insert(tmp);
                tot += tmp;
            }else {
                s2.erase(s2.find(del));
            }
            sum = min(sum,tot+nums[i]);
        }
        return sum+nums[0];
    }
};
//leetcode submit region end(Prohibit modification and deletion)

日期计算

判断是否是闰年

bool isLeap = (y%4 == 0 && y%100 != 0) || y%400 == 0;

判断某个日期是星期几？

蔡勒公式

二维数组的差分

题目传送门

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
        int m = grid.size(),n = grid[0].size();
        vector<int>v(n+1,0);
        vector<vector<int>>presum(m+1,v);
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                presum[i+1][j+1] = presum[i][j+1]+presum[i+1][j]+grid[i][j]-presum[i][j]; 
            }
        }
        vector<vector<int>>diff(m+1,v);
        for(int i = 0;i<m-stampHeight+1;i++){
            for(int j = 0;j<n-stampWidth+1;j++){
                int x_end = i+stampHeight;
                int y_end = j+stampWidth;
                //cnt为起始点[i,j]到终止点[i+height-1][j+width-1]的长方形区域的和
                int cnt = presum[x_end][y_end]-presum[i][y_end]-presum[x_end][j]+presum[i][j];
                if(grid[i][j] == 0 && cnt == 0){
                    diff[i][j] += 1;
                    diff[i][y_end] -= 1;
                    diff[x_end][j] -= 1;
                    diff[x_end][y_end] += 1;
                }
            }
        }
        //还原数据
        for(int i = 0;i<m+1;i++){
            for(int j = 0;j<n+1;j++){
                presum[i][j] = 0;
            }
        }
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                presum[i+1][j+1] = presum[i][j+1]+presum[i+1][j]+diff[i][j]-presum[i][j];
                //presum[i+1][j+1]为最终进行邮票覆盖后点[i,j]的值
                if(presum[i+1][j+1] == 0 && grid[i][j] == 0){
                    return false;
                }
            }
        }
        return true;
    }
};

unordered_map使用pair作为key

题目传送门

class Solution {
    typedef long long ll;
    bool isyuan(char ch){
        if(ch == 'a' || ch == 'o' || ch == 'e' || ch == 'u' || ch == 'i'){
            return true;
        }
        return false;
    }
    int func(int k){
        for(int i = 1;i<=2*k;i++){
            if((i*i)%(4*k) == 0){
                return i;
            }
        }
        return 0;
    }
    struct hash_pair { 
        template <class T1, class T2> 
        size_t operator()(const pair<T1, T2>& p) const
        { 
            auto hash1 = hash<T1>{}(p.first); 
            auto hash2 = hash<T2>{}(p.second); 
            return hash1 ^ hash2; 
        } 
    }; 

public:
    long long beautifulSubstrings(string s, int k) {
        k = func(k);
        int n = s.size();
        unordered_map<pair<int,int>, int, hash_pair> info;
        //map<pair<int,int>,int>info;
        info[{0,k-1}] = 1;
        int val = 0;
        ll ret = 0;
        for(int i = 0;i<n;i++){
            if(isyuan(s[i])){
                val++;
            }else{
                val--;
            }
            ret += info[{val,i%k}];
            info[{val,i%k}]++;
        }
        return ret;
    }
};

字符串相关

将数字转换为二进制表示的字符串

string changeNum2Str(ll num){
    string ret = "";
    while(num > 0){
        ret += ('0'+(num&1));
        num >>= 1;
    }
    reverse(ret.begin(),ret.end());
    return ret;
}

字符串哈希 （双模哈希），求模式串中子串的个数

long mo1 = 1e9+7,mo2 = 4859634;
    long power = 12589634;
    vector<long>h1,h2,p1,p2;
    long mo = 1e9+7;
    typedef long long ll;
public:
    void calcHash(string s) {
        int n = s.size();
        p1.resize(n+5,0);
        p2.resize(n+5,0);
        h1.resize(n+5,0);
        h2.resize(n+5,0);
        p1[0] = p2[0] = 1;
        for(int i = 0;i<n;i++){
            p1[i+1] = p1[i]*power%mo1;
            h1[i+1] = (h1[i]*power+s[i]-'a'+1)%mo1;
            p2[i+1] = p2[i]*power%mo2;
            h2[i+1] = (h2[i]*power+s[i]-'a'+1)%mo2;
        }
    }
    //以0为下标起点的字符串中子串[j,i]的哈希值hash1与hash2的计算方式如下
    int d = i-j+1;
    ll hash1 = ((h1[i+1]-h1[j]*p1[d])%mo1+mo1)%mo1;
    ll hash2 = ((h2[i+1]-h2[j]*p2[d])%mo2+mo2)%mo2;
    //求字符串text中出现模式串pattern的个数，允许pattern重叠
    int findSameSubSting(string &text,string &pattern){
        int n = pattern.size();
        calcHash(pattern);
        long ph1 = h1[n],ph2 = h2[n];
        calcHash(text);
        int m = text.size();
        int ret = 0;
        for(int i = n;i<=m;i++){
            long th1 = ((h1[i]-h1[i-n]*p1[n])%mo1+mo1)%mo1;
            long th2 = ((h2[i]-h2[i-n]*p2[n])%mo2+mo2)%mo2;
            if(ph1 == th1 && ph2 == th2){
                ret++;
            }
        }
        return ret;
    }

KMP 求字符串str中包含子串s的个数

// KMP 模板
    vector<int> calc_max_match(string s) {
        vector<int> match(s.length());
        int c = 0;
        for (int i = 1; i < s.length(); i++) {
            char v = s[i];
            while (c && s[c] != v) {
                c = match[c - 1];
            }
            if (s[c] == v) {
                c++;
            }
            match[i] = c;
        }
        return match;
    }

    // KMP 模板
    // 返回 text 中出现了多少次 pattern（允许 pattern 重叠）
    int kmp_search(string text, string pattern) {
        vector<int> match = calc_max_match(pattern);
        int match_cnt = 0, c = 0;
        for (int i = 0; i < text.length(); i++) {
            char v = text[i];
            while (c && pattern[c] != v) {
                c = match[c - 1];
            }
            if (pattern[c] == v) {
                c++;
            }
            if (c == pattern.length()) {
                match_cnt++;
                c = match[c - 1];
            }
        }
        return match_cnt;
    }

因数

单纯求因数

// nlnn 求因数
  vector<vector<int>> fac(K + 1);
  for (int i = 1; i <= K; i++) for (int j = i << 1; j <= K; j += i) fac[j].push_back(i);

线性筛法求质因子的板子

int limit = 100000; //修改为题目中的数字的上限
bool isprime[100005] = {0}; //保存所有1~limit中的数字是不是质数
int myprime[100005] = {0};  //保存2~limit中所有数字的最小质因子
int primes[100000] = {0};   //保存所有1~limit中出现的质数
int tot = 0;                //1~limit中质数的总个数
//保存每一个下标为i的数字对应的质因子的种类个数
int scors[100005] = {0};
//计算阶乘的板子
int factorial[20005] = {0};
int mo = 1e9+7;
int init = [](){
    memset(isprime,1,sizeof(isprime));
    for(int i = 2;i<=limit;i++){
        if(isprime[i]){
            primes[tot++] = i;
            myprime[i] = i;
        }
        for(int j = 0;j<tot && primes[j]*i <= limit;j++){
            int val = primes[j];
            isprime[val*i] = 0;
            myprime[val*i] = val;
            if(i%val == 0){
                break;
            }
        }
    }
    isprime[1] = false;
    //计算1e5内的所有质数分数
    for(int i = 2;i<=limit;i++){
        int j = i;
        int cnt = 0;
        while(j!=1){
            cnt++;
            int div = myprime[j];
            while(j%div == 0){
                j /= div;
            }
        }
        scors[i] = cnt;
    }
    long res = 1;
    for(int i = 1;i<20005;i++){
        res = res*i%mo;
        factorial[i] = (int)res;
    }
    //0的阶乘为1
    factorial[0] = 1;
    return 0;
}();

树上倍增

LCA算法的核心思想。
适用范围：计算树上从叶子结点不断向上x个父节点的路径问题，可以求到达哪个父节点(LCA），可以求这个路径的和，可以求这个路径的绝对众数、这个路径上的最大值等等，总之和线段树有点像，可以求满足区间和性质的问题都能。
题目传送门
这道题目的板子没有考虑根节点是-1的情况，需要增加修改

class Solution {
    typedef long long ll;
    
public:
    long long getMaxFunctionValue(vector<int>& receiver, long long k) {
        int n = receiver.size();
        ll sum[n][40];
        int sons[n][40];
        for(int i = 0;i<n;i++){
            int next = receiver[i];
            sons[i][0] = next;
            sum[i][0] = next; 
        }
        int len = 64 - __builtin_clzll(k);
        for(int i = 1;i<=len;i++){
            for(int j = 0;j<n;j++){
                int son = sons[j][i-1];
                sons[j][i] = sons[son][i-1];
                sum[j][i] = sum[j][i-1]+sum[son][i-1];
            }
        }
        ll ret = 0;
        for(int i = 0;i<n;i++){
            ll tmp = i;
            int pos = i;
            for(int j = 0;j<=len;j++){
                if(((k>>j)&1) > 0){
                    tmp += sum[pos][j];
                    pos = sons[pos][j];
                }
            }
            ret = max(ret,tmp);
        }
        return ret;
    }
};

LCA

题目传送门

class Solution {
public:
    vector<int> minOperationsQueries(int n, vector<vector<int>> &edges, vector<vector<int>> &queries) {
        vector<vector<pair<int, int>>> g(n);
        for (auto &e: edges) {
            int x = e[0], y = e[1], w = e[2] - 1;
            g[x].emplace_back(y, w);
            g[y].emplace_back(x, w);
        }

        int m = 32 - __builtin_clz(n); // n 的二进制长度
        vector<vector<int>> pa(n, vector<int>(m, -1));
        vector<vector<array<int, 26>>> cnt(n, vector<array<int, 26>>(m));
        vector<int> depth(n);
        function<void(int, int)> dfs = [&](int x, int fa) {
            pa[x][0] = fa;
            for (auto [y, w]: g[x]) {
                if (y != fa) {
                    cnt[y][0][w] = 1;
                    depth[y] = depth[x] + 1;
                    dfs(y, x);
                }
            }
        };
        dfs(0, -1);

        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                int p = pa[x][i];
                if (p != -1) {
                    int pp = pa[p][i];
                    pa[x][i + 1] = pp;
                    for (int j = 0; j < 26; ++j) {
                        cnt[x][i + 1][j] = cnt[x][i][j] + cnt[p][i][j];
                    }
                }
            }
        }

        vector<int> ans;
        for (auto &q: queries) {
            int x = q[0], y = q[1];
            int path_len = depth[x] + depth[y]; // 最后减去 depth[lca] * 2
            int cw[26]{};
            if (depth[x] > depth[y]) {
                swap(x, y);
            }

            // 让 y 和 x 在同一深度
            for (int k = depth[y] - depth[x]; k; k &= k - 1) {
                int i = __builtin_ctz(k);
                int p = pa[y][i];
                for (int j = 0; j < 26; ++j) {
                    cw[j] += cnt[y][i][j];
                }
                y = p;
            }

            if (y != x) {
                for (int i = m - 1; i >= 0; i--) {
                    int px = pa[x][i], py = pa[y][i];
                    if (px != py) {
                        for (int j = 0; j < 26; j++) {
                            cw[j] += cnt[x][i][j] + cnt[y][i][j];
                        }
                        x = px;
                        y = py; // x 和 y 同时上跳 2^i 步
                    }
                }
                for (int j = 0; j < 26; j++) {
                    cw[j] += cnt[x][0][j] + cnt[y][0][j];
                }
                x = pa[x][0];
            }

            int lca = x;
            path_len -= depth[lca] * 2;
            ans.push_back(path_len - *max_element(cw, cw + 26));
        }
        return ans;
    }
};

取模运算

除法逆元

使用条件：
除数与mo互质。
当然最简单的办法是mo本身是一个质数，但是仅仅为质数不能保证一定与div互质，如果div=mo或者div%mo = = 0就不行了。
所以一般的使用场景为：分子的运算乘法过程中所有数字都必须小于mo，例如nums[i]<1e9，mo = 1e9+7。
否则会造成div%mo == 0时，乘积结果取模为0,0乘任何数还是0。

ll quickmul(ll a,ll b,int mo){
        if(b == 1){
            return a;
        }else{
            if(b % 2 == 0){
                ll tmp = quickmul(a,b/2,mo);
                return tmp*tmp%mo;
            }else{
                ll tmp = quickmul(a,b/2,mo);
                return ((tmp*tmp%mo)*a)%mo;
            }
        }
    }
    ll func(ll up,int div,int mo){
        return up*quickmul(div,mo-2,mo)%mo;
    }

#扩展中国剩余定理
目的：求对于很多数字取模后的结果为已知值的最小数字，这些很多数字可以互质，也可以不互质。
可用于求解非质数除法取模。
题目链接

ll exgcd(ll a, ll b, ll &x, ll &y){
        if(b==0){
            x = 1, y = 0;
            return a;
        }
        ll d, x1, y1;
        d = exgcd(b, a%b, x1, y1);
        x = y1, y = x1 - a/b*y1;
        return d;
    }

    ll excrt(vector<ll>& m, vector<ll>& r){
        int n = m.size();
        ll m1, m2, r1, r2, p, q;
        m1 = m[0], r1 = r[0];
        for(int i = 1; i < n; ++i){
            m2 = m[i], r2 = r[i];
            ll d = exgcd(m1, m2, p, q);
            if( (r2-r1)%d !=0 ) return -1; // 不能整除，说明无解
            p = p*(r2-r1)/d;
            p = (p%(m2/d) + (m2/d))%(m2/d);
            r1 = m1*p+r1;
            m1 = m1*m2/d;
        }
        return (r1%m1+m1)%m1;
    }

快速幂

普通快速幂

ll quickmul(ll a,ll b){
		if(b == 0)  return 1;
        if(b == 1){
            return a;
        }else{
            if(b % 2 == 0){
                ll tmp = quickmul(a,b/2);
                return tmp*tmp%mo;
            }else{
                ll tmp = quickmul(a,b/2);
                return ((tmp*tmp%mo)*a)%mo;
            }
        }
    }

矩阵快速幂

vector<vector<int>> matricMul(vector<vector<int>>&m1,vector<vector<int>>&m2){
        int n = m1.size();
        vector<int>v(n,0);
        vector<vector<int>>ret(n,v);
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                ll sum = 0;
                for(int k = 0;k<n;k++){
                    sum = (sum+1L*m1[i][k]*m2[k][j])%mo;
                }
                ret[i][j] = (int)sum;
            }
        }
        return ret;
    }
    vector<vector<int>> quickMatricMul(vector<vector<int>>&matric,ll k){
        if(k == 1)  return matric;
        int n = matric.size();
        vector<vector<int>>tmp = quickMatricMul(matric,k/2);
        vector<vector<int>>ret = matricMul(tmp,tmp);
        if(k%2 != 0){
            ret = matricMul(ret,matric);
        }
        return ret;
    }

预处理

处理出[1,1e9]范围内的所有回文数

共有109998个。
题目传送门

vector<int> pal;

auto init = [] {
    // 严格按顺序从小到大生成所有回文数(不包括0，全部为正整数)（不用字符串转换）
    //这里的10000是由于10的九次方中的9除2的下取整，思路是枚举前半部分的所有数字，然后拼接成回文数
    //如果是10的10次方范围内，那么就是100000。
    for (int base = 1; base <= 10000; base *= 10) {
        // 生成奇数长度回文数
        for (int i = base; i < base * 10; i++) {
            int x = i;
            for (int t = i / 10; t; t /= 10) {
                x = x * 10 + t % 10;
            }
            pal.push_back(x);
        }
        // 生成偶数长度回文数
        if (base <= 1000) {
            for (int i = base; i < base * 10; i++) {
                int x = i;
                for (int t = i; t; t /= 10) {
                    x = x * 10 + t % 10;
                }
                pal.push_back(x);
            }
        }
    }
    pal.push_back(1'000'000'001); // 哨兵，防止下面代码中的 i 下标越界
    return 0;
}();

作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimum-cost-to-make-array-equalindromic/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

组合数，求 C s u m k C_{sum}^k Csumk​

傻瓜式计算

func()函数可以进一步优化，采用预处理，求出所有的阶乘结果，直接调用即可，某些情况下，如果阶乘种类有限的话。

    const int mo = 1e9+7;
    typedef long long ll;
    ll quickmul(ll a,ll b){
        if(b == 1){
            return a;
        }else{
            if(b % 2 == 0){
                ll tmp = quickmul(a,b/2);
                return tmp*tmp%mo;
            }else{
                ll tmp = quickmul(a,b/2);
                return ((tmp*tmp%mo)*a)%mo;
            }
        }
    }

    ll func(int sum,int k){
        ll a = 1;
        int t = k;
        while(k--){
            a = (a*sum)%mo;
            sum--;
        }
        ll b = 1;
        for(int i = 1;i<=t;i++){
            b = (b*i)%mo;
        }
        return a*quickmul(b,mo-2)%mo;
    }

预处理所有阶乘

//计算阶乘的板子
int fact[100005] = {0};
typedef long long ll;
const int mo = 1e9+7;
int init = [](){
    ll res = 1;
    for(int i = 1;i<100005;i++){
        res = res*i%mo;
        fact[i] = (int)res;
    }
    //0的阶乘为1
    fact[0] = 1;
    return 0;
}();

class Solution {
    
    
    ll quickmul(ll a,ll b){
        if(b == 0)  return 1;
        if(b == 1){
            return a;
        }else{
            if(b % 2 == 0){
                ll tmp = quickmul(a,b/2);
                return tmp*tmp%mo;
            }else{
                ll tmp = quickmul(a,b/2);
                return ((tmp*tmp%mo)*a)%mo;
            }
        }
    }

    ll C(int sum,int k){
        ll a = fact[sum];
        ll b = fact[k];
        ll c = fact[sum-k];
        ll bc = b*c%mo;
        return a*quickmul(bc,mo-2)%mo;
    }

树状数组

区间查询和单点修改，都为log(n)复杂度
处理区间和和最大值的流程都一样，只是循环内是计算最大值和区间和的区别

查询区间和

希望得到有序map中新插入元素的rank
如果原数组长度为n,那么树状数组长度为n+1
两个操作:
(1)query(i+1),结果为数组下标【0，i】的前缀和
(2)add(int x,int u),给数组下标为x-1的值加u
题目链接：
https://leetcode.cn/problems/range-sum-query-mutable/
板子：

class NumArray {
public:
    vector<int> tree;

    int lowbit(int x) {
        return x & -x;
    }
    //求区间【0，x】的和
    int query(int x) {
        int ans = 0;
        for(int i = x; i > 0; i -= lowbit(i))
            ans += tree[i];
        return ans;
    }
    
    void add(int x, int u) {
        for(int i = x; i <= n; i += lowbit(i))
            tree[i] += u;
    }

    vector<int> nums;
    int n;

    NumArray(vector<int>& nums) {
        this->nums = nums;
        n = nums.size();
        tree.resize(n+1, 0);
        for(int i = 0; i < n; i++)
            add(i+1, nums[i]);
    }
    
    void update(int index, int val) {
        add(index+1, val-nums[index]);
        nums[index] = val;
    }
    
    int sumRange(int left, int right) {
        return query(right+1) - query(left);
    }

};

查询区间最大值

// 树状数组模板（维护前缀最大值）
class BIT {
    vector<long long> tree;
public:
    BIT(int n) : tree(n, LLONG_MIN) {}

    void update(int i, long long val) {
        while (i < tree.size()) {
            tree[i] = max(tree[i], val);
            i += i & -i;
        }
    }

    long long pre_max(int i) {
        long long res = LLONG_MIN;
        while (i > 0) {
            res = max(res, tree[i]);
            i &= i - 1;
        }
        return res;
    }
};

DP

二分+DP（最长递增子序列）

//dp[i] 为以下标i为结尾的递增子序列的最大长度
    vector<int>dp;
    //存放递增子序列的数字，v的长度即为结果
    vector<int>v;
    //搜索v中第一个大于等于val的位置，如果没有返回-1
    int search(int val){
        int n = v.size();
        if(n == 0 || v[n-1] < val){
            return -1;
        }
        int l = 0,r = n-1;
        while(l<r){
            int mid = (l+r)>>1;
            if(v[mid] >= val){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return l;
    }
    void func(vector<int>& nums){
        int n = nums.size();
        dp.resize(n,0);
        for(int i = 0;i<n;i++){
            int idx = search(nums[i]);
            if(idx == -1){
                v.emplace_back(nums[i]);
                int m = v.size();
                dp[i] = m; 
            }else{
                v[idx] = nums[i];
                dp[i] = idx+1;
            }
        }
    }

数位DP

模版1 ，需要考虑前导0不能参与数字

class Solution {
    string str;
    int m = 0;
    int dp[11][1<<10] = {0};
    int dfs(int id,int mask,bool islimit,bool isnum){
        //cout<<id<<" "<<mask<<endl;
        if(id == m) return isnum;
        if(!islimit && isnum && dp[id][mask] != -1) return dp[id][mask];
        int ans = 0;
        if(!isnum)
            ans = dfs(id+1,mask,false,false);
        int up = islimit ? str[id]-'0' : 9;
        for(int i = !isnum;i<=up;i++){
            int new_mask = mask&(1<<i);
            if(new_mask>0) continue;
            ans += dfs(id+1,mask|(1<<i),islimit && i == up,true);
        }
        if(!islimit && isnum){
            dp[id][mask] = ans;
        }
        return ans;
    }
public:
    int numDupDigitsAtMostN(int n) {
        str = to_string(n);
        m = str.size();
        memset(dp,-1,sizeof(dp));
        return n-dfs(0,0,true,false);
    }
};

模版2 不需要考虑前导0

auto s = to_string(n);
int m = s.length(), dp[m][m];
memset(dp, -1, sizeof(dp));
function<int(int, int, bool)> f = [&](int i, int cnt1, bool is_limit) -> int {
    if (i == m) return cnt1;
    if (!is_limit && dp[i][cnt1] >= 0) return dp[i][cnt1];
    int res = 0;
    for (int d = 0, up = is_limit ? s[i] - '0' : 9; d <= up; ++d) // 枚举要填入的数字 d
        res += f(i + 1, cnt1 + (d == 1), is_limit && d == up);
    if (!is_limit) dp[i][cnt1] = res;
    return res;
};
return f(0, 0, true);

作者：灵茶山艾府
链接：https://leetcode.cn/problems/number-of-digit-one/solutions/1750339/by-endlesscheng-h9ua/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

离散化模版

流程： 复制、排序、去重。
使用时，二分查找后+1即为该值的rank
题目链接

// 离散化 nums[i]-i
//复制
auto b = nums;    
for (int i = 0; i < n; i++) {
    b[i] -= i;
}
//排序
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end()); // 去重
//使用
long long ans = LLONG_MIN;
for (int i = 0; i < n; i++) {
    // j 为 nums[i]-i 离散化后的值（从 1 开始）
    int j = lower_bound(b.begin(), b.end(), nums[i] - i) - b.begin() + 1;
}

线段树

题目传送门

普通线段树

使用说明:
1、下标从1开始
2、使用多少，我们就划分多少空间，不要每次直接按照最大数据范围开辟tree数组
可以使用tree = vector<node>(n*4);

typedef long long ll;
    int ret = 0;
    ll MN = 1L*INT_MIN*100000,MX = 1l*INT_MAX*100000;
    struct node{
        int l,r;
        ll sum = 0;
        int mx = 0,mn = 0;
    };
    vector<node>tree;
    void insert(int k,int l,int r,int idx,int val){
        tree[k].l = l;
        tree[k].r = r;
        if(l != r){
            ll mid = (l+r)>>1;
            if(mid >= idx){
                insert(2*k,l,mid,idx,val);
            }else{
                insert(2*k+1,mid+1,r,idx,val);
            }
            tree[k].sum = tree[2*k].sum+tree[2*k+1].sum;
            tree[k].mx = max(tree[2*k].mx,tree[2*k+1].mx);
            tree[k].mn = min(tree[2*k].mn,tree[2*k+1].mn);
        }else{
            tree[k].sum++;
            tree[k].mx = val;
            tree[k].mn = val;
        }
    }
    //求区间[left,right]内的区间和
    int query(int k,int l,int r,int left,int right){
        if(l>=left && r<=right){
            return tree[k].sum;
        }
        int ans = 0;
        ll mid = (l+r)>>1;
        if(mid >= left){
            ans += query(2*k,l,mid,left,right);
        }
        if(mid < right){
            ans += query(2*k+1,mid+1,r,left,right);
        }
        return ans;
    }
    void build(int k,int l,int r){
        tree[k].l = l;
        tree[k].r = r;
        if(l == r)  return;
        int mid = (l+r)>>1;
        build(2*k,l,mid);
        build(2*k+1,mid+1,r);
    }
    //找出[left,right]范围内第一个值小于等于minVal的下标，找不到返回-1
    int find_mn(int k,int left,int right,int minVal){
        if(tree[k].mn > minVal) return -1;
        if(tree[k].l > right)   return -1;
        if(tree[k].r < left)    return -1;
        if(tree[k].l == tree[k].r){
            return tree[k].l;
        }
        int mid = (tree[k].l+tree[k].r)>>1;
        int ret = find_mn(k*2,left,right,minVal);
        if(ret == -1){
            return find_mn(k*2+1,left,right,minVal);
        }
        return ret;
    }
    //找出[left,right]范围内第一个值大于maxVal的下标，找不到返回-1
    int find_mx(int k,int left,int right,int maxVal){
        if(tree[k].mx <= maxVal) return -1;
        if(tree[k].l > right)   return -1;
        if(tree[k].r < left)    return -1;
        if(tree[k].l == tree[k].r){
            return tree[k].l;
        }
        int mid = (tree[k].l+tree[k].r)>>1;
        int ret = find_mx(k*2,left,right,maxVal);
        if(ret == -1){
            return find_mx(k*2+1,left,right,maxVal);
        }
        return ret;
    }

动态开点

这里使用了离散化优化空间，如果不用离散化就只能动态开点，用了离散化可以使用普通线段树，因为已经确定了区间范围。
使用方法:
使用说明，下标从0开始
在调用时，设定整个线段树空间的下标的范围l,r文章来源地址https://www.toymoban.com/news/detail-648045.html

ll l = INT_MIN,r = INT_MAX;
//查看区间【left,right】范围内的最大值
ll tmp = query_mx(0,l,r,left,right);
//查看区间【left,right】范围内的和
ll sum = query(0,l,r,left,right);
insert(0,l,r,val,dp[i]);

int n;
    typedef long long ll;
    int ret = 0;
    static const ll MN = 1L*INT_MIN*100000;
    static const ll MX = 1l*INT_MAX*100000;
    struct node{
        ll l,r;
        int left_son = -1,right_son = -1;
        ll sum = 0;
        ll mx = MN;
    };
    int id = 1;
    vector<node>tree = vector<node>(1,node());
    void pushup(int k){
        ll ans = 0;
        if(tree[k].left_son != -1){
            ans += tree[tree[k].left_son].sum;
            tree[k].mx = max(tree[k].mx,tree[tree[k].left_son].mx);
        }
        if(tree[k].right_son != -1){
            ans += tree[tree[k].right_son].sum;
            tree[k].mx = max(tree[k].mx,tree[tree[k].right_son].mx);
        }
        tree[k].sum = ans;
    }
    //修改下标为id的值为val
    void insert(int k,ll l,ll r,ll idx,ll val){
        tree[k].l = l;
        tree[k].r = r;
        if(l != r){
            ll mid = (l+r)>>1;
            if(mid >= idx){
                if(tree[k].left_son == -1){
                    tree.emplace_back(node());
                    tree[k].left_son = id++;
                }
                insert(tree[k].left_son,l,mid,idx,val);
            }else{
                if(tree[k].right_son == -1){
                    tree.emplace_back(node());
                    tree[k].right_son = id++;
                }
                insert(tree[k].right_son,mid+1,r,idx,val);
            }
            pushup(k);
        }else{
            tree[k].sum = val;
            tree[k].mx = val;
        }
    }
    //求区间[left,right]内的区间和
    ll query(int k,ll l,ll r,int left,int right){
        if(k == -1)    return 0;
        if(l>=left && r<=right){
            return tree[k].sum;
        }
        ll ans = 0;
        ll mid = (l+r)>>1;
        if(mid >= left){
            ans += query(tree[k].left_son,l,mid,left,right);
        }
        if(mid < right){
            ans += query(tree[k].right_son,mid+1,r,left,right);
        }
        return ans;
    }
    //求区间[left,right]内的最大值
    ll query_mx(int k,ll l,ll r,int left,int right){
        if(k == -1)    return MN;
        if(l>=left && r<=right){
            return tree[k].mx;
        }
        ll ans = MN;
        ll mid = (l+r)>>1;
        if(mid >= left){
            ans = max(ans,query_mx(tree[k].left_son,l,mid,left,right));
        }
        if(mid < right){
            ans = max(ans,query_mx(tree[k].right_son,mid+1,r,left,right));
        }
        return ans;
    }

lazy tag

const int mo = 1e9+7;
    typedef long long ll;
    struct node{
        int l,r;
        int len;  //表示区间长度
        ll sum=0;
        int lazy_tag = 0;  //必须保证区间加的数字不能为0,不能为-1,因为lazy_tag都是+=操作。
    }tree[400005];
    void pushup(int k){
        tree[k].sum = tree[2*k].sum+tree[2*k+1].sum;
    }
    void pushdown(int k){
        if(tree[k].lazy_tag == 0)   return;
        int val = tree[k].lazy_tag;
        tree[2*k].sum += 1L*tree[2*k].len*val;
        tree[2*k].lazy_tag += val;
        tree[2*k+1].sum += 1L*tree[2*k+1].len*val;
        tree[2*k+1].lazy_tag += val;
        tree[k].lazy_tag = 0;
    }
    //这里创建线段树，每个叶子结点的sum为val;
    void build(int k,int left,int right,int val){
        tree[k].l = left;
        tree[k].r = right;
        tree[k].len = right-left+1;
        if(left == right){
            tree[k].sum = val;
        }else{
            int mid = (left+right)>>1;
            build(k*2,left,mid,val);
            build(k*2+1,mid+1,right,val);
            pushup(k);
        }
    }
    //给区间[left,right]内的所有数字加val
    void add(int k,int left,int right,int val){
        if(tree[k].l >= left && tree[k].r <= right){
            tree[k].sum += 1L*tree[k].len*val;
            tree[k].lazy_tag += val;
        }else{
            pushdown(k);
            int mid = (tree[k].l+tree[k].r)>>1;
            if(mid >= left){
                add(2*k,left,right,val);
            }
            if(mid < right){
                add(2*k+1,left,right,val);
            }
            pushup(k);
        }
    }
    //查询区间[left,right]内和所有数字的和
    ll query(int k,int left,int right){
        if(tree[k].l >= left && tree[k].r <= right){
            return tree[k].sum;
        }else{
            ll sum = 0;
            pushdown(k);//容易丢
            int mid = (tree[k].l+tree[k].r)>>1;
            if(mid >= left){
                sum += query(2*k,left,right);
            }
            if(mid < right){
                sum += query(2*k+1,left,right);
            }
            return sum;
        }
    }

最短路径

floyd

const int inf = 0x3f3f3f3f;
int A[MAXV][MAXV];  //记录点对之间的最短距离
 　　int path[MAXV][MAXV];   //记录两点之间的路径的中间经过节点
 　　vector<int>v(n,inf);
 　　vector<vector<int>>dist(n,v);
 　　for(int i = 0;i<n;i++){
		dist[i][i] = 0;
	}
 　　for(int i = 0;i<m;i++){
 　　		auto e = edge[i];
            int id = e[0];
            int next = e[1];
            if(id == next)  continue;
            dist[id][next] = min(dist[id][next],1LL*e[2]);
            //如果是无向图加上下面这个
            //dist[next][id] = min(dist[next][id],1LL*e[2]);
        }
        for(int k=0;k<n;k++)   //注意这一步是枚举中间结点！！！
 　　   { 
      　　for(int i=0;i<n;i++)
         　　for(int j=0;j<n;j++)
             　　if(dist[i][j]>(dist[i][k]+dist[k][j]))
             　　{
                   　　dist[i][j]=dist[i][k]+dist[k][j];
              　 } 
    　   }

到了这里，关于力扣的板子的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！