题目：https://ac.nowcoder.com/acm/problem/14506题目大意：思路：因为所有点的编号不同，那么我们考虑交换时，如果左子树的中序遍历的第一个编号>如果左子树的中序遍历的第一个编号。那么我们就交换。所以记录每个点为根的子树的中序遍历的第一个编号就可以了。 #include <bits/stdc++.h> using namespace std; int l[2000005], r[2000005]; int ans=0; int DFS(int u){ int lson=u, rson=u; if(l[u]) lson=DFS...

题目链接：https://nanti.jisuanke.com/t/48303题目大意：思路：区间可能重叠，普通的DP是不可行的。按B.染色（简单）是有问题的。给个样例： 7 3 6 1 -7 -2 -2 9 -4 7 -3 -3 -5 1 1 -6 2 2 4 0 1 4 6 7 1 2 5 5 正确的是14 2 1 1 1 1 1 1我们用f[i]:染完前i个能够得到的最大代价。用两棵线段树来维护区间[L, i]涂黑/白色的最大贡献。Ta：mx[L]:区间[L+1, i]全部涂黑的最大贡献。那么每到一个i。[0, i-1]的所有情况都应该加上b[i]。add(0, i-1, b[i])...

题目链接：https://nanti.jisuanke.com/t/42404题目大意：a[i]表示对手的每个队伍战斗力p[i]表示打败对手后获得的声望b[i]表示我方第一种人的战斗力c[i]表示我方第二种人的战斗力 定义我方一组选手的战斗力为b[i]+c[j]，第一种选手与第二种选手某种顺序两两组队后，与对方进行pk，共有n!种pk顺序，你选择最佳的匹配方案，求能够获得最大期望声望×n。 思路：我们假设b[i]和c[j]和组队，那么题目和对手然后一个打都是等可能的。能够获得的声望的期望为b[i]+c[j]>a[k]。的所有的p[k]的和/n。那么就可以把b[i]和c[j]建边直接跑KM...

题目链接：https://www.luogu.com.cn/problem/P1198题目大意：思路：每次修改都是在末尾，那么RMQ只会影响n结尾的区间，有logn个，直接修改就可以了。 #include <bits/stdc++.h> using namespace std; int dp[200005][22]; int main() { int m, d; scanf("%d%d", &m, &d); int t=0; int N=0; for(int i=1; i<=m; i++){ ...

题目链接：https://ac.nowcoder.com/acm/problem/20566题目大意： 思路：我们把属性值抽象为点，和每个装备，那么就是一个二分图。例如：题目的二分图。我们匈牙利匹配左点，因为要连续，如果开始不匹配，就break。 #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; struct Edge { int to,next; } edge[maxn << 1]; struct Hyali { int cnt,head[maxn]...

题目链接：https://ac.nowcoder.com/acm/problem/19833题目大意： 思路：一看就有递推关系：f[n]:填满n行的方案数把前几项画出来，就是：然后矩阵快速幂就可以了。 #include <bits/stdc++.h> #define LL long long using namespace std; int mod=1e9+7; struct mat { LL m[4][4]; }; struct mat_qpow { //矩阵乘法 //(AB)[i][j]=A[i][1]*B[1][j]+A[i][2]*B[2][j...

题目链接：https://ac.nowcoder.com/acm/problem/14700题目大意：思路”：我们用dis[u][i]：表示第i天到达u的最大费用。 #include <bits/stdc++.h> #define LL long long using namespace std; struct Edge{ int to, w, nxt; }e[30005]; int head[30005], cut=0; struct ZDL{ int dis[1005][15], vis[1005][15]; struct Node{ ...

题目链接：https://ac.nowcoder.com/acm/problem/14526题目大意：思路：我们预处理每天买i个的最小费用，然后直接分组DP就可以了。有个限制：第i天至少买i个。因为每天至少吃一个。 #pragma GCC optimize(3, "Ofast", "inline") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> u...

题目链接：https://ac.nowcoder.com/acm/problem/23482题目大意： 思路：我们直接得到或者u-x y-v, u-y x-v。这些都可以通过LCA搞定。 #pragma GCC optimize(3, "Ofast", "inline") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> using namespa...

题目链接：https://ac.nowcoder.com/acm/problem/20860题目大意：思路：我们从最高位开始考虑：如果L和R第i位的相同，那么对结果没有影响。如果不同。那么L的前i位取得(2^i)-1, R的第i位取2^i。结果就是2^(i+1)-1 #include<bits/stdc++.h> #define LL long long using namespace std; int main() { int t; scanf("%d", &t); while(t--) { LL l, r;...

题目链接：https://ac.nowcoder.com/acm/problem/20857 思路：我们考虑每个点的经过次数就可以了。1：u到其他所有点 n-12：u的子树之间3：u的子树到除u的其他点（父节点以上） #include<bits/stdc++.h> #define LL long long using namespace std; vector<int> G[500005]; int a[500005]; LL siz[500005]; int n, ans=0; void DFS(int u, int fa) { LL sum=n-1;/...

链接：https://ac.nowcoder.com/acm/problem/20663来源：牛客网 题目描述 小卤蛋刚把dnf的技能点重新洗了一遍,现在他要重新加点,假设他的技能树一共有n层，第i层有n-i+1个技能，每个技能只能够学习一次。除了第1层的技能可以直接学习外，其他技能学习都要学习前置技能，即你要学习第i(i>=2)层第j列的技能，那么你要先学习第i-1层的第j列和第j+1列的技能。每个技能学习后都会获得一定的战力加成。现在小卤蛋有m个技能点，一个技能点可以学习一个技能，他想知道加完点后他可以获得的最大战力加成为多少。 输入描述: 有多组样例输入，输入到文件结束.每组样...

题目大意：有一个加工厂里面有两个机器人，然后有一堆货物需要加工，这些货物加工必须按照顺序来，第n件物品能进行加工的前提条件是n-1件物品加工完成或正在加工。 思路： f[i][j]:第i个机器在加工时，A， B机器的要完成当前任务的时间差为j时。A， B机器的最大工作时长 考虑转移： j>=0。A的工作时长>=B的工作时长。 如果第i+1个任务放在A塔上，只有A开始做第i+1个任务时，B机器才可能开始做第i+2个任务。那么时间差为A[i+1]。 那么f[i+1][a[i+1]]=min(f[i+1][a[i+1]], f[i][j]+a[i+1]);//放A塔 如果第i+1...

题目链接：http://poj.org/problem?id=2609题目大意：有一个长度为m的两个车厢。有一排车，必须按顺序驶入车厢（左右任选）但是不能超过m长度。问最多装多少。如果第i辆车装不下，那么后面的车都不能再装。思路：用f[i][j][k]:表示前i辆车左车厢长度为j，右车厢长度为k的状态是否存在。因为j+k==sum[i]。所以可以降一维。 #include <map> #include <set> #include <cmath> #include <queue> #include <cstdio> #inc...