题目链接 大意：给你一些2的幂次数，问你最少分解几次可以用一些2的幂次数得到n。 分解指的是:      2   x    −   >   2   ∗    2    x   −   1     ，   x   ≥   0    2^x->2*2^{x-1}，x\geq0   2x−>2∗2x−1，x≥0 思路：把n按二进制拆分，从小到大枚举每一位1：先看低位能不能凑齐，否则从高位拆。 细节见代码：（写的比较复杂，理解是很好理解的） #include <bits/stdc++.h> using namespace std; typedef long long LL...

题目链接 题意：给你两个字符串     s   ,   t    s,t   s,t，问你     t    t   t是否可以由     s    s   s的两个不相交子序列构成。 思路：显然我们应该枚举     t    t   t的断点     i    i   i，使得     [   1   ,   i   ]    [1,i]   [1,i]为一个子序列     [   i   +   1   ,   l   e    n   t    ]    [i+1,len_t]   [i+1,lent​]为第二个子序列。然后check这种情况是否合法.我们设前一半为     L    L...

题目链接 大意：让你输出走k步的方案. 思路：按如下方式构造即可.  注意合并相同的方案 细节见代码： #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back #define mp make_pair int n,m,k; int main() { ios::sync_with_stdio(false); cin>>n>>...

题目链接 题意：给你一个     n   ∗   m   ，   n   ,   m   ≤   500    n*m，n,m\leq500   n∗m，n,m≤500的有矩阵，问你每个子矩形中最大满足条件的正方形面积。 思路：显然答案最大不超过250，那我们枚举答案即可。设当前答案为     L    L   L.，用二维数组记录     s    s   s可行与否。 我们检查每个左端点的是否可以构成这个边长     L    L   L.,如果可以的话，这个左端点的值就是1，然后遍历所有询问看询问的二维区间是否有值是1即可。 #include <bits/stdc++.h> ...

题目链接 题目大意：给你一个     n   ∗   m    n*m   n∗m的矩阵，你可以在每行放置一个     2   ∗   k    2*k   2∗k的矩形框，问你被矩形框 ，框中的数的和最大值是多少。每个数只计算一次。 思路：用     d   p   [   i   ]   [   j   ]    dp[i][j]   dp[i][j]，表示第     i    i   i个矩形框放在第     j    j   j列的时候的最大值。 暴力的转移是很显然的：枚举上一次的所有情况即可。 优化的话可以用线段树优化成     l   o   g    log   log的转移复杂...

题目链接 大意：给你一个无向图，k个特殊点，你要在两个不同的特殊点直接连一条无向边，使得     1   −   >   n    1->n   1−>n的最短路最长。 思路：直观的想法肯定是枚举所有情况来找到最小值，显然复杂度不允许。我们思考一下： 不连边的最短路是     l   e   n    len   len，当前两个特殊点分别是     s   ,   t    s,t   s,t，那么这种情况下的最短路就是      m   i   n   (   l   e   n   ,   m   i   n   (   p   [   s   ]   +   q   ...

模板题： hdu5306 维护最大值，最大值个数，次大值，区间和即可。 区间更新k的时候，若当且节点最大值小于k则直接返回，k小于最大值且大于次大值时则可以直接更新区间和和最大值，否则继续递归左右儿子，注意要把信息更新到当前节点的所有祖先节点。 节点信息向下传递的时候，祖先的历史最小值显然大于等于当前的次小值，所以只要祖先的历史最小值小于当前节点的最大值，就要把当前节点更新一下。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e6 + 10; #define fi...

做法：区间线段树套权值线段树 本题细节有点多，调了一下午，心态爆炸。 修改操作：把区间>x的数全部拎出来并单点修改他们在整个树上的值,并修改x处的值(所有修改都要定位到区间内)，注意要更新到所有祖先节点。向下传标记的时候，就不用传到祖先节点了，只需要改自己的内层线段树。 查询操作：把所有子区间拎出来，然后在上面二分即可。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5 + 10; #define fi first #define se second #d...

题目链接 首先，如果k>=n的话，显然我们可以构造出所有状态，相当于n个相同球放到n个不同盒中，盒子可以空。 即     C    (    2   n   −   1     n   −   1     )    C(_{2n-1}^{n-1})   C(2n−1n−1​). k<n的情况即必须要有     n   −   k    n-k   n−k个盒子非空，我们把所有情况算出来去掉不合法情况即可。 不合法情况：仅有x个盒子非空     x   ∈   [   1   ,   n   −   k   −   1   ]    x\in[1,n-k-1]   x∈[1,n−k−...

树链剖分 考虑只枚举和父亲、重儿子的边，还差所有轻儿子的贡献。于是修改的时候，往根跳，在轻重链交替的时候往轻边父亲打标记即可根。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e6 + 10; #define fi first #define se second #define pb push_back int n; int siz[N],fa[N],son[N],a[N],cnt,to[N],de[N]; vector<pair<int,int&gt...

启发式合并即可  #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back vector<int>v[N]; int n,sz[N]; void dfs(int now){ sz[now]=1; for(auto k:v[now]){ dfs(k); sz[now]+=sz[k]; } } LL ans[N],MAX=1e18,MIN=...

比赛链接 A.分情况讨论一下即可 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back int t,a,b; int main() { ios::sync_with_stdio(false); for(cin>>t;t;t--){ cin>>a>>b; if(a==b)cout<<0<&lt...

思路： 根据异或的性质，可以把      ∑   l   r    i   ⊕   x    \sum_l^r i \oplus x   ∑lr​i⊕x划分成一些连续的区间，对每个区间计算答案。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back int a[N],n,q; int b[N]; LL sum[N]; int len; LL q...

题目链接 思路：给的一条路径，统计所有被奇数个路径包含的点的异或和。 路径上的点显然是深度连续递增的点，那么我们根据两端深度的奇偶情况就可以知道路径上的哪些点是有贡献的。 把路径剖出来，用bit维护一下异或和即可。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back int n,m,a[N],sz[N],df[N],to[N],son[N],...