道路和航线 本质就是一个最短路，有负边，题目保证无环 直接跑的正确性就不用证明了 这道题卡掉了朴素的，用双端队列优化即可？ Code #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 10; const int inf = 0x3f3f3f3f; inline int __read() { int x(0), t(1); char o (getchar()); while (o < '0' || o > '9'...

Working Out 题目大意: 给定一个矩阵，每个点都有一个点权，让你求从矩阵中某一点到矩阵四个顶点的权值之和减去自己的四倍的值最大(就是这个点没有贡献) 分析： 我们画两张图，看看他们的路径，就会发现其实只有两种情况一:二：就是说其实只有两种转移的方式那么我们用4个数组分别记录到四个顶点的最大距离然后再枚举每个点作为交点时的答案，不断更新 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3 + 10; int dp[5][maxn][maxn];...

摆渡车 题意 你可以操控一辆车的发车时间，你也知道跑一次往返的时间，你还知道每一个人到达车站的时间让你找到一种方案使得所有人的等待时间之和最少，求这个最小时间 分析 第一反应是把到达车站的人作为一个整体然后我们可以枚举最近的一次发车时间假设现在的时间是，最近的一次发车时间是那么从的等待时间可以表示为那么我们把这个拆开来看 貌似变得友好了呢直观感觉一下，我们有效的最近的发车时间应该是不能小于()的那么其实就是有一部分人在上一次发车时就开始等待了那么这个也是要加入贡献的 Code #include <bits/stdc++.h> using namespace std; typed...

Tree 题目大意： 首先，我们有次操作 操作：在节点下面再加一个权值为的点 操作：询问从点开始往上走，（每次遇到权值大于当前选过的最后一个点的点必定会选），问最多能选多少点 分析 我们可以很容易的发现，我们选中的点一定是一个单调不下降序列 那么就是说，我们可以稍微改动一下操作一，让每一条链都一定是单调不上升的（从根出发的链） 然后，我们每次加入的点必定不会是已经存在的某个点的祖先，所以我们改变他的位置对原来的树是没有影响的 若有节点成为了这个被我们认为操作的节点的儿子，它的值依赖于我们人为操作的那个点，所以这个答案也不会因为我们的操作出现问题 那么我们就可以在加入节点的时候，找到...

选择客栈 这个题，因为他没有说两个人的顺序对答案有影响，所以我们可以考虑固定一个人为右端点，记录最靠近这个右端点的人的可以去的咖啡店 如果说这个点大于这种颜色的客栈，那么就可以在之前的颜色中乱选，就是可以把之前有的所有这个颜色的客栈记为贡献 好像就口胡完了 #include <cstdio> const int Maxn = 2e5 + 5; int N, K, P, Now; int Ans, Color, Price; int Last[Maxn], Sum[Maxn], Cnt[Maxn]; int main() { scanf("%d %d %d", &...

MooFest 题目大意 分析 其实我们发现这个十分不好维护 就是说，如果已经保证了，那么原式可以写为 这个按照从大到小就可以了吧 那么就是的问题了 这个看看数据，这个大概是需要一个的复杂度 那么发现像什么线段树，树状数组之类的高级数据结构就可以维护 就分成两种情况，一种是的，一种是的 那就分别求和，那么就可以写成这样 细节 这个用了一个十分易懂的方式来维护 那就是先按照从小到大排序 用树状数组一个点一个点插入，记录一下每头牛的的排序，方便下文的删除操作 然后再按从大到小排序 然后每次就查询完了就从树状数组中把这头牛删掉 然后重载了一下运算符，操作可能会方便一些吧 #include <c...

[HEOI2014]南园满地推轻絮 思路： 就是二分去找, 满足 那么就是要让尽可能小的满足，然后在保证单调不下降的情况下，不等式是否成立 易证： ​ 当时，若数组满足条件且单调不下降，那么数组也一定满足且单调不下降 ​ 那么有了这个性质就可以二分答案了，因为当小的取值成立时，大的取值一定成立 Code #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e6 + 10; int n, sa, sb, sc, sd...