算法题目模板

//nums 是节点数组
int n = nums.size();
vector<int> stk;
vector<int> right(n, -1), left(n, -1);
//vector<TreeNode*> nodes(n);
for(int i=0; i<n; ++i)
{
    //nodes[i] = new TreeNode(nums[i]);
		//标记左子树：将小于当前元素的值设为左子树
    while(!stk.empty() && nums[stk.back()] < nums[i]) 
    {
        right[stk.back()] = i;  // right[a] = b; 意味着序号a是序号b的左子树
        stk.pop_back();
    }
		//标记右子树：由于左子树在上一步已经标记完成了，所以只需要再标记一次右子树
    if(!stk.empty())
    {
        left[i] = stk.back(); // left[a] = b; 意味着序号a是序号b的右子树
    }
    stk.emplace_back(i);
}

//后面根据right和left的情况来构建这颗二叉树（以下只是看着程序叙述，并不一定好理解，如果以后需要理解，请重新表述）
/*
1. left 和 right 都为-1的时候，则此点为根
2. right 为 -1， 或者 left不为-1且 left对应的值小于right对应的值，则此点是left对应的节点的右子树
3. 其余情况为 此点是 right对应的节点的左子树
*/

	vector<int> tree;
	// 求最低位1
  int lowbit(int i)
  {
      return i&-i;
  }
	
	//向后更新
  void update(int p)
  {
      int n = tree.size();
      for(;p < n; p+=lowbit(p))
          ++tree[p];
  }
	
	//统计前缀和
  long long tsum(int p)
  {
      long long res = 0;
      int n = tree.size();
      for(;p >= 1; p-=lowbit(p))
          res += tree[p];
      return res;
  }

int n, m;
ll mat[5000][5000];

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

long long tsum(int x, int y) {
    ll res = 0;

    for (int i = x; i >= 1; i -= lowbit(i))
        for (int j = y; j >= 1; j -= lowbit(j)) {
            res += mat[i][j];
        }

    return res;
}

void update(int x, int y, int value) {
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            mat[i][j] += value;
        }
    }
}

//区域c 到 a， d 到 b， 闭区间
ll section_sum(int a, int b, int c, int d) {
    ll ans = tsum(c, d) - tsum(a - 1, d) - tsum(c, b - 1) + tsum(a - 1, b - 1);
    return ans;
}

//原始版本
int uf_find(vector<int>& parent, int a)
{
	if(parent[a] != a)
		parent[a] = uf_find(parent, parent[a]);
	return parent[a];
}

void uf_union(vector<int>& parent, int from, int to)
{
	parent[uf_find(parent,from)] = uf_find(parent,to);
}


//-1版本，正数表示下标，负数表示个数
int uf_find(vector<int>& parent, int a)
{
	//找到负数的前一个
	return parent[a] < 0 ? x : parent[a] = uf_find(parent, parent[a]);
}

void uf_union(vector<int>& parent, int a, int b)
{
	int p1 = uf_find(parent,b);
	int p2 = uf_find(parent,a);
	if(p1 != p2)
	{
		parent[p1] += parent[p2];
		parent[p2] = p1;
	}
}

string s;
int dp[10][1<<10][2][2];
int dfs(int p, int mask, int limit, int zero) {
	if (p == s.size()) return 1-zero;//全是前导零则不算答案。前导零，即前面全为0。zero=1，表示之前是前导零
	if (dp[p][mask][limit][zero] != -1) return dp[p][mask][limit][zero]; //遇到计算过的状态直接返回
	int res = 0;
	// 累计前导零的方案数
	// zero=1，limit=1,由于之前是存在前导零，所以构造的位数必定小于n的位数，第p+1位最多能取到9;
	// 现在也是填充0，所以第p+1位的zero=1
	if (zero == 1) res += dfs(p+1, mask, 0, 1);
	// 累计非前导零的方案方案数
	// 枚举的下限取决于zero。
	//      当存在前导零，由于当前统计非前导零的方案数，所以只能从1开始
	//      若不存在前导零，当前从0开始构造是可以满足最终构造的数<=n的枚举上限取决于limit。
	//      当limit存在说明p之前构造的数恰好是n的前缀，此时若超过n的第p位则不满足最终构造的数<=n。
	//      当limit不存在说明前p位构造的数已经在字典序上小于n的前p位了，第p位即使取9，最终构造的数也不会大于n
	for (int i=(zero?1:0); i<=(limit?s[p]-'0':9); i++) 
	{
		// 不设置当前位为前导零，若之前为前导零则当前可从0开始，否则是1，若limit存在当前值超过s[p]必定大于n
    if (mask>>i&1) continue; //前p个构造的数中已经有i，跳过。
    res += dfs(p+1, mask|1<<i, limit&&(i==s[p]-'0'), 0);
    // limit = limit&&(i==s[p]-'0'), 当前p个数是n的前缀，且第p个数也取到了n的第p位则形成了长度为p+1的前缀
    // zero = 0, 当前循环是统计非前导零的方案数。
	}
	return dp[p][mask][limit][zero] = res;
}

int countSpecialNumbers(int n) 
{
	s = to_string(n);
	memset(dp, -1, sizeof(dp));
	return dfs(0, 0, 1, 1);
	//limit=1，第一位的最大值最多不能超过s[0],否则大于n.
	//zero=1，前导零存在后续的前导零才可以存在
}

//问题：统计0~n中，数字1出现的个数
int bit_dp(int n) {
    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;  //统计到个位的后面 （个位是m-1）
        if (!is_limit && dp[i][cnt1] >= 0) return dp[i][cnt1];  //(1)
		//zeros
        int res = 0;
        int up = is_limit ? s[i] - '0' : 9;  //显然从最高位开始limit
        for (int d = 0; d <= up; ++d) // 枚举要填入的数字 d
            res += f(i + 1, cnt1 +(d==1), is_limit && d == up);
        if (!is_limit) dp[i][cnt1] = res;  //在limit上不能统计，(2)
        return res;
    };
    return f(0, 0, true);
}
//当 i = 0 表示 n 的最高位

/*
对于（1）（2）不理解的话可以这么想：
另 n=234, 有 m = 3，
如果去除（1）和（2），那么相当于遍历 0 到 234。加上（1）和（2）只是减少了重复遍历的情况。

（1）中的if相当于得到记录了每一位上所有非limit的答案，所以不需要重复遍历了直接返回即可。
（2）中的if相当于记录非 limit 情况下，第 i 位 0~9 的答案。

那么为什么只需要非 limit 的呢，因为对于 n=234
在十位上，0，1，2是非limit，所以这三者的答案一样，所以只需要记录一次，后面直接返回即可。而3是limit，所以需要遍历。

可得limit和非limit答案也是不一样的，所以做出区别。

为什么一开始 0 是 limit。
因为最高位必然有限制，不一定遍历到 9 。
*/

# 问题：至少有 1 位重复的数字
# 使用 @cache 能够简化 01dp 模板
def numDupDigitsAtMostN(self, n: int) -> int:
	s = str(n)
	m = len(s)
	@cache
	def f(i, dup, mask, is_limit):
		if i == m:
			if dup:
				return 1
			return 0
		ans = 0
		up = int(s[i]) if is_limit else 9
		for d in range(up+1):
			mask2 = mask if mask == 0 and d == 0 else mask | (1<<d)
			dup2 = dup or (mask & (1<<d))
			ans += f(i+1, dup2, mask2, is_limit and d == up)
		return ans
	return f(0, False, 0, True)

dp[0] = 1;
for(int num : nums) {
	for(int i = target; i >= num; i--) {
		dp[i] |= dp[i - num];	//遍历每个元素，如果选择该元素则在其他已选的元素后加上该元素。
	}
}
//dp[target] == 1 表示元素能够合成target

ll a[N];

struct Seg
{
	int l, r;
	ll val, tag;  //tag是懒标记
}seg[N<<2];

void push_up(Seg& u, const Seg& l, const Seg& r)
{
	u.val = max(l.val, r.val);   //比如说求最大值
	//u.val = l.val + r.val;   //比如说区间和
}

void push_down(Seg& u, const Seg& l, const Seg& r)
{
	l.val += u.tag * (l.r - l.l+1);
	l.tag += u.tag;

	r.val += u.tag * (r.r - r.l+1);
	r.tag += u.tag;
	u.tag = 0;
}

//建树，id=1，l左边界，r右边界
void seg_build(int id, int l, int r)
{
	seg[id].l = l;
	seg[id].r = r;
	if(l == r)
	{
		seg[id].val = a[l];  //a为原来数组，seg是线段树
		return ;
	}
	int m = l+r>>1;
	seg_build(id << 1, l, m);  //左子树
	seg_build(id << 1|1, m+1, r);  //右子树
	push_up(seg[id], seg[id<<1], seg[id<<1|1]);  //更新父节点
}

//更新
void seg_update(int id, int l, int r, ll val)
{
	if(l <= seg[id].l && seg[id].r <= r)
	{
		seg[id].val += val * (seg[id].r - seg[id].l +1);
		seg[id].tag += val;
		return;
	}
	push_down(seg[id], seg[id<<1], seg[id<<1|1]);
	int m = seg[id].l + seg[id].r >> 1; //先加再右移
	if(l <= m)seg_update(id<<1, l, r, val);
	if(m < r)seg_update(id << 1|1, l, r, val);
	push_up(seg[id], seg[id<<1], seg[id<<1|1]);
}

//查询，id为当前区间下标
ll seg_query(int id, int l, int r)
{
	if(l <= seg[id].l && seg[id].r <= r)
	{
		return seg[id].val;
	}
	push_down(seg[id], seg[id << 1], seg[id << 1|1]);
	ll rt = 0;
	int m = seg[id].l + seg[id].r >> 1;
	if(l <= m)rt += seg_query(id<<1, l, r);
	if(m < r)rt += seg_query(id << 1|1, l, r);
	return rt;
}

void seg_print()
{
	for(int i=1; i<(N<<2); ++i)
	{
		if(seg[i].l != 0)
			cout << "id:" << i << "[" << seg[i].l << "," <<\ 
			seg[i].r << "] val:" << seg[i].val << "tag:" <<\
			seg[i].tag << endl;
	}
}

vector<vector<int>> arr(nr, vector<int>(nc, 0));
for(int i=1; i<=nr; ++i)
{
    for(int j=1; j<=nc; ++j)
    {
        arr[i][j] = arr[i][j-1] + mat[i-1][j-1] + arr[i-1][j] - arr[i-1][j-1];
    }
}
//arr[i][j] 表示子矩阵mat[0-i][0-j]所有元素和

long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size()+1;
        vector<vector<int>> arr(n, vector<int>());
        for(auto& a:roads)
        {
            arr[a[0]].push_back(a[1]); 
            arr[a[1]].push_back(a[0]); 
        }
        long long ans = 0LL;
        function<int(int,int)> dfs = [&](int s, int fa) {
            int ret = 1;
            for(auto& v: arr[s])
            {
                if(v!=fa)
                {
                    int t = dfs(v, s);
                    ans += (t+seats-1)/seats; //t/seats向上取整
                    ret += t;
                }
            }
            return ret;
        };
        dfs(0,-1);
        return ans;
    }

//邻接图，包括边的长度。 g[0] = {1,4}//点0到点1的距离是4.
//返回从start到每个节点的最短距离
vector<int> djs(vector<vector<pair<int,int>>>& g, int start)
{
    vector<int> dist(g.size(), INT_MAX);
    dist[start] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.emplace(0, start);
    while(!pq.empty())
    {
        auto[d,x] = pq.top();
        pq.pop();
        if(d>dist[x]) continue; //
        for(auto[y,wt]: g[x])
        {
            int new_d = dist[x] + wt;
            if(new_d < dist[y]) //判断是否遍历过
            {
                dist[y] = new_d;
                pq.emplace(new_d, y);
            }
        }
    }
    return dist;
}

int fp(int a, int b)
{
	int ans = 1;
	while(b != 0)
	{
		if(b&1)
			ans *= a;
		a*=a;
		b>>1;
	}
	return ans;
}

typedef vector<vector<int>> mat;
mat mul(mat a, mat b)
{
	//矩阵乘法
}

int fm(mat m, int b)
{
	mat ans = E;  //单位矩阵, 未定义
	while(b != 0)
	{
		if(b&1)
			ans = mul(ans, m);
		mat = mul(mat, mat);
		b>>1;
	}
	return ans;
}

bool a[maxn];  //标记素数0，与合数1
int p[maxn],t; //记录素数数组，与素数个数
a[1]=1;//注意1不是质数；
for(int i=2; i <= n; i++)
{
	if( a[i] == 0 )
		p[++t]=i;//是质数就记录；
	for(int j=1; j<=t && i*p[j]<=n; j++)
	{
		a[ i*p[j] ]=1;//标记合数；
		if( i%p[j] == 0 )
			break;
			// p[j + 1] 一定不是 i * p[j + 1] 最小的因子了，停止继续往下筛，保证同一个合数不会被多个质数标记。
	}
}