筱玛爱线段树 思路 比较容易想到离线后从后向前处理，所以我们只要维护两个差分数组即可了，一个是答案数组，从前向后的，一个是当编号被操作了几次的数组，从后向前的，然后只需要按照要求模拟即可。 代码 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10, mod = 1e9 + 7; ll op[N], l[N], r[N], ans[N], res[N], n, m; int main() { // freo...

Angry Cows(Silver) 思路 套路二分，我们枚举左端点，把炸弹放到中间，然后check右端点是否在区间， 如果不在区间就重新确定一个爆炸区间范围，投放次数加一， 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; const int N = 5e4 + 10; int a[N], k, n; bool judge(int x) { int sum = 0, last = -2 *...

华华和月月种树 思路 树上对整颗子树进行操作，容易想到用序，但是这是一颗动态变化的树，所以我们可以考虑离线操作。 既然是离线操作，那就简单了，先存下一整棵树以及所有的操作，然后按照要求模拟即可：  对于操作二我们直接以最终一整颗树中形态来进行差分。 对于操作一这里就有有一个关键点了，这个时候刚好有一个点加入树里面，因此我们需要记录这个节点初始的，方便后面输出单个节点的权值。 操作三，我们就可以直接输出这个时候第一步记录的值在这里就排上用场了。  代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3)...

装货物 思路 显然对每个物品我们有两种操作，与已经放好了的放在一起，或者新开一个盒子来放，由于数据比较小，我们可以直接稍加剪纸的爆搜即可。 第一个优化，当的时候立即返回。第二个优化，给定的序列从大到小排个序，这样我们就能保证后面的决策会较少的重复利用前面已经放号的盒子，减少回溯成本。 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define ...

MMSet2 思路 这道题目显然能够通过的复杂度来暴力，这显然不能达到题目要求的复杂度，因此我们可以对题目要求我们计算的东西进行转换。 某个点到所有点集的最大距离最小，这就有点像是重心的求法了，但是这题又有所不同，如果这是在一颗树上，显然我们可以很快的得到答案，，所以这题我们也可以转换思想，每次求解得到点集中两点之间最长的距离，然后再对他向上取整。 问题转换为求解点集中得直径了，所以我们可以找到点集中的深度最大的点，然后通过这个点去求得点集的直径。 代码(事实证明树剖求lca是真的快) /* Author : lifehappy */ #pragma GCC optimize(2) #prag...

[SCOI2009]生日礼物 思路 如果没有记错的话，这题跟某次多校的题几乎一模一样。区间问题的最小值，有一个最简单的办法就是尺取法了，只要通过两个指针的扫描就可以以线性的复杂度简单的实现，这里我们按照每个物品属于的种类作为我们num数组记录的值，然后再通过一次扫描就可以得到答案了。 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define ...

[SCOI2010]游戏 思路 很容易看出这是一个二分图匹配问题，对于每一种属性，我们必须找到一个与之可以相应匹配的物品，所以我们建立的两条边，然后从开始匹配，当遇到第一个无法匹配的属性时我们即可输出答案，因为题目要求所有的攻击必选是连续递增的属性。 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n' #define...

地斗主 思路 看到这非常大，感觉一定是个结论公式题，但是感觉又不像是排列组合，于是可以考虑矩阵快速幂了，所以关键就是得得到递推公式了。 我们将棋盘分成两部分我们假定显然对分别有种分法，对应到原来一整块的部分上也就是,并且后面的变化是由不断循环下去的，所以我们只要将即可得到递推式 接下来就是这么一个简单的矩阵乘法了 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb pus...

Mr. Kitayuta, the Treasure Hunter 思路 一眼看过去感没跑了，但是这个的数组着实开不下，但是我们不难发现有用的状态并不是太多，所以想想有没有什么方法来进行一下空间的优化，最多500个上下移动的步数我就不证明了。 我们定义，表示我们从某个位置走了步到这里，所以我们有状态转移方程。 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_...

矩阵消除游戏 思路 直接进行二进制枚举我们要选定的行，然后再贪心地选了，列，这样我们即可以保证我们都选择是最优的，然后取这些选择值里面的最优值就🆗了，具体看代码注释吗。 代码 #include <bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) typedef long long ll; ll a[20][20]; int n, m, k; vector<ll> add; int judge(int x) { int ...

没有上司的舞会 思路 树形dp入门经典题 里面的关系是一个树状的无环图，每个节点我们显然有两种取法，参加派对，不参加派对，所以状态转移方程就出来了  参加派对 ，上司参加了舞会，其直系下属不能参加舞会 不参加派对 ，上司没有参加舞会，其直系下属可以参加，也可以不参加。  代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\...

二叉苹果树 思路 一般的树都是对节点进行统计或者计算，但是这题是对边进行统计计算，所以要稍加特殊处理，貌似我这种方法处理的比较微妙。 我们按照传统定义表示节点连接了条边的果子数量最大值，所以我们显然可以对当前节点进行统计枚举： for(int i) for(int j) 两重循环，表示的是该节点当前已经统计的子树节点个数，表示改节点当前正在枚举的子树节点，然后通过加减组合来更新我们的答案，这个地方有一个特殊处理，具体看代码。 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include ...

小G有一个大树 思路 树的重心，经典的问题了，我们只要用一个数组来统计当前节点的儿子个数即可，然后按照题目更新答案。 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n' #define mid (l + r >> 1) #define lson rt << 1, l, mid #define ...

排座椅 思路 直接贪心，看哪个位置隔开得人多就在这个地方开一条路，所以我们只要统计一下每条道路隔开得人数，然后按照这个作为关键字，从大到小排序，然后就可以得到我们得答案了。 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n' #define mid (l + r >> 1) #define lson rt...