[整理]qbxt周末刷题班 Day2总结
跑路
Description:有一棵无根树，给定一个温泉，问至少再添加多少温泉，使得所有叶节点（度为1）到温泉的距离不超过\(k\)。
Solution:我们考虑贪心地放温泉。一个简单的思路是对于一个节点\(x\)，总是放到它的祖先处。但是这样做有一个问题：如果一个兄弟子树中的节点\(y\)原本被\(t\)覆盖，但是挪到\(LCA(x,t)\)之后覆盖不到了怎么办？其实解决办法很简单，我们按照深度从大到小排即可。
Implementation:有了贪心策略的证明后实现就很简单了：每次放到\(k\)级祖先，然后标记能覆盖到的点。
Code:
#define N 1010
int T,n,s,k;
int fa[N],ind[N],cov[N];
vectorp[N];//p[dep][i]:person at level dep
struct Edge {
int to,nxt;
}e[N<<1];
int head[N],cnt;
inline void ade(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt,ind[v]++;
}
void DFS(int now,int ff,int dep){
fa[now]=ff;
if(ind[now]==1&&dep>k)p[dep].pub(now);
for(rg int i=head[now];i;i=e[i].nxt){
int v=e[i].to;
if(v!=ff)DFS(v,now,dep+1);
}
}
void Cover(int now,int ff,int step){
cov[now]=1;
if(step==k)return;
for(rg int i=head[now];i;i=e[i].nxt){
int v=e[i].to;
if(v!=ff){
Cover(v,now,step+1);
}
}
}
int main(){
Read(T);
while(T--){
memset(fa,0,sizeof(fa)),memset(ind,0,sizeof(ind));
memset(head,0,sizeof(head)),cnt=0;
memset(cov,0,sizeof(cov));
for(rg int i=0;ik;i--){
for(rg int j=0;j 卡牌
Description:有\(n\)个元素，每个元素有三个属性\(A,B,C\)，规定偏序关系\(p_i
两部分数据：Part 1满足\(n,B,C\le 10^6\& C=0\)，Part 2满足\(n\le 10^3\& A,B,C\le10^6\)。
Solution:对于\(C=0\)的情况，可以套用二位偏序的做法，此处不再赘述。对于\(C\ne0\)的情况，我们把两个元素之间的偏序关系连成有向边，然后在这个图里求最长路即可。
Code:
#define N 1010
#define Nmax 1000010
int n;
struct Card {
int a,b,c;
Card(int _a=0,int _b=0,int _c=0){
a=_a,b=_b,c=_c;
}
}cd[Nmax];
bool operator < (Card x,Card y){
return (x.a<=y.a)&&(x.b<=y.b)&&(x.c<=y.c);
}
namespace Case2 {
int ind[N],dis[N],ans=0;
struct Edge {
int to,nxt;
}e[N*N];
int head[N],cnt;
inline void ade(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u];
head[u]=cnt,ind[v]++;
}
void Topo(){
queueq;
for(rg int i=1;i<=n;i++){
if(!ind[i]){
q.push(i),dis[i]=1;
}
}
while(!q.empty()){
int u=q.front();q.pop();
for(rg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
dis[v]=dis[u]+1;
ans=max(ans,dis[v]);
if(!--ind[v]){
q.push(v);
}
}
}
}
void main(){
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=n;j++){
if(i!=j&&cd[i] 数列
Description:有一个数列\(\{a_i\}\)满足：
\[a_i=\begin{cases}i,(i\le 2)\\2a_{i-1},(i>2,2\nmid i)\\a_{i-1}+b{i-1},(i>2,2|i)\end{cases} \]其中\(b_k=mex\{|a_i-a_j|\}(1\le i,j\le k)\)。
Solution:我们算出这个奇怪的数列的前几项会发现一个规律：它增长得非常快而且对于前\(k\)项来说，它与之后的项无法贡献有用的差值，而能影响答案的差值只能是\(+b_{i-1}\)时贡献的。
根据\(mex\)的定义，我们可以形象地认为，每贡献一个新的差值，就是在填补之前的缺口。那么假设我们询问的是\(x\)，前\(k\)项里出现的所有差值为\(S\)，那么新的\(mex\)就要先填补\(S\)中那些不到\(x\)的差值（设为\(d\)个），而\(mex\)隔项出现，最终答案即为\(k+2d+1\)和\(k+2d+2\)。
Code:代码又咕咕了
火锅
Description:有\(n\)盘肉，每盘肉有两个参数\(a_i,b_i\)分别代表了出锅时间和食用时间。对于每个\(k\le n\)，求出在挑\(k\)盘肉自定顺序吃掉时的最短时间。
Solution:本题重点是按照\(a_i\)排序的贪心，有了这个贪心后就可以使用各种奇奇怪怪的方法A掉本题。
Implementation:使用小根堆维护\(b_i\)，然后根据需要更新下一盘吃的肉。
Code:
#define N 300010
int n;
struct Meat {
int ok,eat;
}m[N];
bool operator < (Meat a,Meat b){
return a.ok,greater >q;
int now=0,nxt=1,tim=0;
q.push(INF),m[n+1].ok=INF;
while(now=m[nxt].ok){
q.push(m[nxt++].eat);
}
int u=q.top();q.pop();
if(m[nxt].ok-tim>=u){
now++,tim+=u;
cout<