题意 给定n个点，m条路径。每个点有个高度h，i可以到j，当且仅当h[i] >= h[j]，i和j之间有路径。求从1出发，最多可以经过几个点，其最短路径长度。（使用时间胶囊可以回到之前经过的点） 思路 第一问简单bfs一下就行。第二问如果没有h的限制就是一个最小生成树，然而有高度的限制就不太行了。进一步分析好像是求一个有向图的最小生成树（大雾）。我们再来看看kruskal算法，每次都是贪心的选取最短的边，因为这里有高度的限制，每条从1出发的路径高度都是非递增的，我们显然不能这么做。那我们可不可以把这个限制“去掉”呢？好像是可以的，对于 按从大到小排序，再按路径长度从小到大排，每次选的都...

题意 给定序列，多次查询，每次查询一个区间内小于某个数的个数。 思路 题目疯狂暗示换个角度思考🤔，我就先姑且试试。开始先想到的是用一堆桶存对应数的下标，这样对于一次查询 我们只需要在那些<=k的桶里找下标处于 的个数，考虑到有多个查询，我们可以利用单调性先将查询排个序，离线处理。接下来就是数数的问题了，开始想的是用差分和前缀和，后来想想好像不太行（每得出一次查询都是），由于点进题目之前瞄到了一眼数状数组，遂尝试了一波，可（大雾）。 复杂度 代码 #include<bits/stdc++.h> using namespace std; #define ll long lon...

题意 n只糖糖分为两组，每只糖糖有一个能力值b[i]。第i秒时，第i只糖糖可以消灭排在他前面且和他不是一组的糖糖。娇姐可以法攻m次，每次发功给定时间t，第t秒后b[1]...b[t]的值都加1。问第n秒后还剩几只糖糖。 思路 理解题意理解了好一会~ ~ 。主要困难点在于m次发功操作，我们可以讨论下发功操作带来的影响。对于一次在第t秒的发功操作，并不会改变前t个糖糖的相对大小，只可能改变前t个糖糖和后面糖糖的相对大小。那么我们可不可以在开始的时候就把b[1]..b[t]先加上1呢？答案是肯定的（参考前面）。这样我们就可以先算出糖糖的最后的能力（可以差分处理），在从后往前处理，判定糖糖会不会被消灭...

题意 给定一棵n个节点的树，问路径长度为偶数的路径数（u->v 和 v-> u只算一次） 思路 刚开始想歪了，想了好久的树形dp，没想出来，就去看题解，看了第一行题（niu）解（bi）小姐姐说是水题就没脸往下看了QAQ。后面发现可以按深度做，先dfs一遍把把每个节点所处的深度处理出来（随便取一个点为根节点）。对于同深度的两个个节点，其最短路径必然是其中一个点到这两个点的最近公共祖先，再到另一个点，是对称的，因此路径长度是偶数。对于不在同一深度的两个节点，若在同一棵子树，最短路径就是深度相减取绝对值。若不在同一子树就把深度较大的节点移动到与深度较小的节点同一深度的节点上，然后就可以当...

题意 有N个给定长度的木棍，华华想得到K条长度(L)相同的木棍(给定的木棍可裁剪)，最大化L。 思路 容易想到可以二分长度，对于每个长度，暴力check一下能不能裁成大于等于K条木棍。 复杂度 代码 #include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; int n, k; int a[maxn]; bool check(int x){ int ans = 0; for(int i = 0; i < n; i++){ ans += a[i] / x;...

题意 给定n，求长度为n的01串的逆序对个数的和。 思路 设为长度为i的01串逆序对个数。则 所以 容易推出 复杂度 代码 #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define db double #define mp make_pair #define fi first #define se second #define de(a) cout << #a << " = " << a << end...

题意 有多少对区间，这对区间数的亦或和为0 思路 记录一个亦或前缀和，枚举i，i将区间分为半部分和右半部分，每次从左半部分和右半部分取一个凑一对。左半部分区间亦或和存在一个数组中。 复杂度 代码 #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define db double #define mp make_pair #define fi first #define se second #define de(a) cout << #a &lt...