吐槽 本人感觉题目十分有坑。。。就是因为没有理解真正的题意。。。  两人只能相遇一次 从下边上来的人只能从上边出这个点，从左边进来的人只能从右边出这个点  分析 因为我们需要两个人走对角线，并且复杂度允许所以我们可以直接从4个顶点暴力DPDP[1/2/3/4][i][j]表示从某个顶点到的最大权值和求出之后，我们可以直接枚举相遇点计算到达最终点的权值和最大即可Res=max(Res,DP[1][X-1][Y]+DP[3][X][Y-1]+DP[2][X][Y+1]+DP[4][X+1][Y]);Res=max(Res,DP[1][X][Y-1]+DP[3][X+1][Y]+DP[2][X-1]...

前言 作为NOIP-J的T3，这道题在一定程度上是会有区分度的。。。比如说这道题就有一堆解法：  剪枝优化状态 斜率优化DP 的神级DP 某位大佬说的算法但我这里就主要讲一下斜率优化DP吧，相信大部分都是这种做法吧  分析 我们考虑枚举设DP[i]表示在时回到人大附中的最少总时间Pre[i]表示及之前的时间前缀Cnt[i]表示及之前的人数前缀所以我们可以列出一个朴素的DP方程： 看到这个类似于直线方程的转移方式，我们开始考虑斜率优化设当优于时 所以，我们就得到了斜率优化的比较方式。这道题也就Okay了！ 代码 //P5017 #include <iostream> #include...

分析 首先，此题需要加点和查询操作我们可以想到倍增但由于对于祖先的选择有要求所以我们需要修改对于倍增数组的表示Anc[i][j]表示从点向上走个满足要求的点之后，到达的点Sum[i][j]表示从点向上走个满足要求的点得权值之和这样我们就可以查询了至于插入操作我们需要先求出此点祖先中第一个满足要求的祖先我们也可以直接得到 时间复杂度： 代码 //CF932D #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring...

分析 由于我们需要求出符合要求的，但感觉比较繁琐所以我们考虑求补集，即不符合要求的发现，不符合要求，当且仅当：两个客栈位于两个的客栈之间所以，我们类似一个滑动窗口向右滑动，记录各种颜色的个数当遇到满足要求的客栈时，立马统计答案即可最后用总方案数不符合要求的方案数即可 代码 //P1311 #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define LL long long #define L...

分析 排序之后可以证明，枚举最后无法凑出的数然后统计答案一定是OK的比它值小的必须选所以可以直接暴力背包背出方案数暴力加上答案即可时间复杂度： 代码 //Newcoder 18 D #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define LL long long #define Lowbit(X) (X&(-X)) #define Lson (X<<1) #defin...

分析 BFS出到每一个点的（距离Limit）最短路径将收到的宝藏sort+unique然后再暴力max一下，即可 代码 //Newcoder 18 C #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #include <cstring> #define LL long long #define Lowbit(X) (X&(-X)) #define Lson (X<<1...

分析 首先这道题是可以用的时间复杂度过的所以我们可以考虑使用数据结构优化一下所以我们选择可以直接获得区间信息的树状数组将所有区间按排序之后，依次遍历将前一个出现当前颜色的将当前位置即可统计区间答案 代码 //Newcoder 18 B #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define LL long long #define Lowbit(X) (X&(-X)) #defi...

分析 作为签到题，好像就没什么好说的了。。。排个序，直接求出4个数即可 代码 //Newcoder 18 A #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define LL long long #define Lowbit(X) (X&(-X)) #define Lson (X<<1) #define Rson (X<<1|1) #define Cl(X,Y...

分析 作为一名OIer，当看到最大值最小时一定可以想到二分答案所以可以顺着这个思路往下由于最后需要的结果是单调不下降的所以我们可以考虑贪心设当前二分答案为Temp  若当前在，若 那么可以直接break掉，因为无解return false 若当前那么A[i]=min(A[i-1],A[i]+Temp) else可得A[i]=max(A[i]-Temp,A[i-1])  进而就OKay了。。。 代码 //P4105 #include <iostream> #include <cstdio> #include <algorithm> #include <c...