第一题 打怪 题意：有两个怪，血量分别是 a 、 b 。你一次可以选择攻击其中一个造成 x 伤害，或者同时对两个造成 y 伤害。 这个题应该有O（1）的贪心做法，但是数据范围只有 20，所以直接dfs开剪~ #include<bits/stdc++.h> using namespace std; int res = 1000000000; void dfs(int a , int b ,int x ,int y,int cnt) { if (a <= 0 && b <= 0) { res = min(res,cnt); ...

时间最优 #include<stdio.h> inline int read(){ int x=0;char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x; } int main() { int res , n ; n = read(); for (int i = 1 ; i <= n ; i ++) { ...

前缀和做法 使用一个 dpdpdp 数组记录前缀和，dpidp_idpi​ 表示在 [0,i][0,i][0,i] 中有多少个点。 枚举起点 iii 即可得到线段终点 i+k−1i+k-1i+k−1 , 使用 dpi+k−1−dpi−1dp_{i+k-1}-dp_{i-1}dpi+k−1​−dpi−1​ 即可得到这段中的点的数量 本题做法很多，双指针也可做，随便乱搞就行，复杂度都一样 #include<bits/stdc++.h> using namespace std; int dp[1100000] , n , k; int main() { scanf("%d%d...

非树形DP做法 （贪心） 由于整个图是一个树形结构，且起点固定为 sss 那么与 sss 相邻的点就必然不去，于 sss 距离为 222 的点可选择是否去。 贪心的思路是叶子节点必选，往上可选节点必选一定可以构造出最优解（最优解不唯一但能保证是其中一个最优解）。 证明如下： ①树形结构中的叶子节点是必选的：如果叶子节点的父节点仅有一个子节点，那么选择叶子节点或他本身对结果不造成影响。如果父节点有多个子节点，那么就可以去所有叶子节点，如果去父节点就只能去一个节点。因此子节点必选。 ②去的城市尽量深一定能构造出最优解：把每个与起点 sss 距离为 222 的节点视为深度是 000 ，深度深的节点被...

非树形DP做法 知识点：DFS序维护子树信息，前缀和 由于DFS过程是遍历当前节点的全部子节点后返回当前节点，所以利用这个性质可以有效维护子树信息。 DFS过程中使用一个时间戳 dfndfndfn 并记录进入某个节点的时间 ininin 和出这个节点的时间 outoutout 。我们记录一个DFS序数组记录所有节点，即 dfndfndfn 数组，（并不一定需要真正创建这个数组）， [dfnin,dfnout][dfn_{in} , dfn_{out}][dfnin​,dfnout​] 即是 ininin 节点的子树范围。我们只需将 colorcolorcolor 数组映射到 dfndfndfn...

这题好像卡了常数，我在使用cin和未在并查集find和merge方法中添加inline的情况下tle了，但是使用scanf或者find和merge方法添加inline则可以过时间分别是200ms-，800ms+。

瞎bb 这题在现场想到了贪心部分，也想到了优化要用到线段树/树状数组。时间不太够我 码了，就直接放弃思考了，现在看来当时想的思路是正确的，码一下树状数组说不定 能过2。赛后补题，思路代码几乎都对了，然后一个小细节给我绕进去了，卡了半 天，好歹最后和lzh讨论了一下，改了一个参数过了233，标程是差分数组，我采用了 线段树的做法。 题解 前置知识：树状数组，差分 贪心部分 1.从左开始遍历，遍历到第一个大于1（即需要跳跃的蹦床）则在这个蹦床开始跳一定是 最优解 证明：设开始跳的蹦床为第i个，左侧的所有蹦床都为1，右侧的未知，从右侧任何一个 蹦床开始跳跃都无...