思想 适用范围：拓扑序不会发生改变的，如trie，线段树 对于一棵树来讲，要建立一个新的路径 若新节点在原来的版本中已经有了，则把原来版本的这个点复制过来； 原来版本有的点但不在该路径上的点，就不需要新加一个点，直接将指针指向原来版本的点即可 trie树 P4735 最大异或和 题意： 给定一个非负数...

CF451E Devu and Flowers 题意： 有n个盒子，每个盒子Ai朵鲜花，相同盒子鲜花颜色相同，不同盒子颜色不同 问选m朵花有多少种方案 n<=20,m<=1e14,s<=1e12 思路： 如果一个花瓶有无限个，相当于把M+N分成N个的方案，即隔板法C(M+N-1,N-1) 将n个限制转化为没有限制，容斥原理 $ 设S_1=...

概念 残流网络 $ c’(u,v)=c(u,v)-f(u,v) $ $ c(v,u)=f(u,v) $(可以退回去) $ f+f’ = f + f’ ...

一般启发式合并本质 小集合合并到大集合 时间复杂度: $ O(nlogn) $ P3201 [HNOI2009] 梦幻布丁 题目描述 $n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。 例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色. 输入格式 第一行是两个整数，分别表示布丁个数 $n$ ...

用途 $ O(n)求最长回文串 $ 思路 在字符串前面加$#,后面加^,相邻字符之间添加# 可以发现原字符串的回文串都会转换为新字符串的奇数回文串 并且原回文串长度=新回文串半径-1 $ 定义p_i为以i为中心的回文串的半径 $ $ 假设已经找出一个回文串,中心为mid,mr为该半径+1 $ $ 若i<mr ,代表当前段在已经找到的回文串内 $ ...

C-Lexicographically Largest 题意： $ 给定一个数组a,每次可以将a_i+i拿出来扔到c数组，然后删除a_i,求字典序最大的c(c数组不能存在相同的数，为从大到小排列的集合) $ 思路： 思考可以发现不同的数( $ a_i+i $ )可以从后往前拿不影响，但如果有相同的数,比如3 3，先拿后再拿前得到的数组为3，先拿钱再拿后为3 2 因此对于相同的两个数看作一个区...

C - Vlad and a Sum of Sum of Digits 题意： $ 一个数n的贡献为n的数位和 $ $ 给定一个数n,求1 ~\ n的所有数的贡献,每个样例限制0.5s $ 思路： 预处理每个答案，$ O(1) $ 查询 一个数的贡献为 $ f_i=f_{i/10}+i \%\ 10 ,求出前缀和即可，时间复杂度O(n) $ 暴力...

F - Feed Cats 题意： 有多个区间，每个区间内只能选一个点，问最多可以选择多少个区间 思路： 考虑dp 差分，然后算前缀和可以判断选择当前点的贡献 预处理选择当前点后最右边的不能选的点 $ 不选i,则dp_i=max(dp_i,dp_{i-1}) $ $ 选i,则dp_{R_i+1}=max(dp_{R_i+1},dp_i+cnt) $ $ 答案为dp_{n...

C - Sasha and the Casino 题意： 赔率为k的赌场，保证至多连续输x次。求a元本金能否保证在有限时间内赢得任意金额 思路： 本质上是个博弈问题,赌场可以随意决定输赢 每一次下注都必须将本金全赚回来,否则赌场判赢连续输的次数重置,但是本金减少了,这样的话不能赢任意金额 撑x次后仍然有足够金额则算赢 void solve(){ ll k,x,a; ...

LCA模板 vector<int> adj[N]; void dfs(int u,int fa){ dep[u]=dep[fa]+1; par[u][0]=fa; for(int i=1;i<=log2(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1]; for(auto v:adj[u]){ if(v==fa)contin...