核心思路对于相同颜色且相邻的点合并。若不在同一集合，则0若在同一集合，同色1异色0AC代码#include<bits/stdc++.h>usingnamespacestd;intfa[1145141];charcol[1145141];intn,m;intfind(intx){ if(x==fa[x]) returnx; returnfa[x]=find(fa[x]);}v

原题传送门思路只用堆每一个点跑一边最短路，在用当前点到点\(n\)的距离，再用当前点的\(f\)乘上\(10^6\)除以刚刚算出的值即可。代码#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<queue>usingnamespacestd;#defin

n,m较小，同时又是区间问题，可以考虑区间dp。设定\(f[i][j]\)为只在i~j范围内操作的最大贡献，为了将操作表示出来可以设g[k][i][j]为在i~j内操作一次的包括k点最大贡献。通过这些可以推出：\(f[i][j]=max_{k=i}^jf[i][k-1]+f[k+1][j]+g[k][i][j]\)，这样一来两边的操作也不会冲突

GreedyPieEatersP有\(m\)头奶牛，\(n\)个派。选择一个奶牛序列\(\{c_k\}\)，从\(1\)到\(k\)，奶牛\(c_i\)会吃掉\([l_i,r_i]\)的所有派（\([l_i,r_i]\)不能已经全部吃完）。求\(\sumw_{c_i}\)的最大值。\(n\le300\)，\(m\le\frac{n(n-1)}{2}\)，\(1\lew_i\le10^6\)，

题目背景FarmerJohnhasMMcows,convenientlylabeled1…M1…M,whoenjoytheoccasionalchangeofpacefromeatinggrass.Asatreatforthecows,FarmerJohnhasbakedNNpies(1≤N≤3001≤N≤300),labeled1…N1…N.Cowiienjoyspieswithlabelsinther

P5838[USACO19DEC]MilkVisitsGLuoguP5838Solution提供一种奇特的\(\mathcalO(\dfrac{n\sqrtn\logn}{\omega})\)的做法。树链剖分转化成序列问题。然后变成了询问一个区间\(l,r\)是否存在一个颜色\(k\)，显然可以\(\mathcalO(n)\)预处理\(\mathcalO(\sqrtn)\)

 题目链接：[P5836] USACO19DEC] MilkVisitsS-洛谷|计算机科学教育新生态(luogu.com.cn)这道题可以用并查集来解决。题目中每个结点只有两个状态：H和G。那么我们可以推断出，只有当起点和终点间每个结点的状态相同但是起点（或者终点或起点到终点之间的某一点）与所需状态不同