[57] (多校联训) A层冲刺NOIP2024模拟赛15

A.追逐游戏

一个非常暴力的想法是直接求出最短路径 \(S\)，然后对 \(S\) 上的点，比较 \(dis_{s,S_i}\) 和 \(dis_{s',S_i}\) 的大小，如果抓捕的人先到就符合条件

实际上，这个符合条件的路径是单调的，即在最短路径上存在一个断点，断点靠近起点的一侧总不可达，靠近终点的一侧总是可达的

证明：如果 \(p\) 可达，考虑由 \(p\) 在最短路径上走一步，被追捕者也走一步，因此仍然是可达的

所以可以对内层二分答案，复杂度单次询问是二分套 LCA 的，总复杂度为 \(q\log^2 n\)

比较好的一个 trick 是用树剖求树上路径上的第 \(k\) 个点（特定点的第 \(k\) 级祖先），比较目标点是否在当前链上即可，知道这个就能快速求最短路径上的特定点了，因为这个最短路径本质是 \(x,lca,y\) 的树上简单路径，只需要维护一下深度差然后做分讨就行了

还有一个比较好的 trick

int dis(int x,int y){
	int p=lca(x,y);
	return deep[x]+deep[y]-2*deep[p];
} 

此外这个题可以通过分讨砍掉二分

如果追捕者更晚到达目标，那么答案一定是终态

否则，直接考虑两人路径的重合点，抓捕者直接在此段开始时选择向着被抓捕者走，需要的时间除二，在中点处相遇，需要处理一些特殊情况

#include<bits/stdc++.h>
using namespace std;
vector<int>e[200001];
int dfn[200001];
int size[200001],deep[200001],top[200001],fa[200001],maxson[200001];
int dfsorder[200001];
int cnt;
int n,q;
void dfs1(int now,int last){
	size[now]=1;
	deep[now]=deep[last]+1;
	fa[now]=last;
	for(auto i:e[now]){
		if(i!=last){
			dfs1(i,now);
			size[now]+=size[i];
			if(size[i]>size[maxson[now]]){
				maxson[now]=i;
			}
		}
	}
}
void dfs2(int now,int nowtop){
	dfn[now]=++cnt;
	dfsorder[cnt]=now;
	top[now]=nowtop;
	if(maxson[now]){
		dfs2(maxson[now],nowtop);
	}
	for(auto i:e[now]){
		if(i!=fa[now] and i!=maxson[now]){
			dfs2(i,i);
		}
	}
}
int lca(int a,int b){
	while(top[a]!=top[b]){
		if(deep[top[a]]<deep[top[b]]) swap(a,b);
		a=fa[top[a]];
	}
	if(deep[a]<deep[b]) swap(a,b);
	return b;
}
int lca(int a,int b,int c){
	int x1=lca(a,b),x2=lca(a,c),x3=lca(b,c);
	if(deep[x1]<deep[x2]) swap(x1,x2);
	if(deep[x1]<deep[x3]) swap(x1,x3);
	return x1;
}
int dis(int x,int y){
	int p=lca(x,y);
	return deep[x]+deep[y]-2*deep[p];
} 
int getfa(int u,int k){
	int D=deep[u]-k;
	while(deep[fa[top[u]]]>=D) u=fa[top[u]];
	return dfsorder[dfn[u]-(deep[u]-D)];
}
int getfa(int a,int b,int k){
	int p=lca(a,b);
	int d1=deep[a]-deep[p],d2=deep[b]-deep[p];
	if(d1>=k) return getfa(a,k);
	return getfa(b,d1+d2-k);
}
signed main(){
	freopen("chase.in","r",stdin);
	freopen("chase.out","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=n-1;i++){
		int a,b;cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs1(1,0);dfs2(1,1);
	while(q--){
		int u,v,x;
		cin>>u>>v>>x;
		int p=lca(u,v,x);
		int d1=dis(x,p),d2=dis(u,p),d3=dis(p,v);
		if(d2<d1){
			cout<<d1+d3<<" "<<v<<"\n"; 
		}
		else{
			cout<<(d1+d2+1)/2<<" "<<getfa(u,x,(d1+d2+1)/2)<<"\n";
		}
	}
}

C.软件工程

发动了从暑假传到现在的传统艺能，打一堆假做法然后取 \(\max\)

赛后发现自己打的并不是假做法，而是分讨中的其中一种情况

首先有一种非常好想的，就是你对区间长度排序，然后考虑到对每个线段放一个集合里非常省事，这样它的贡献就是它自己，因此挑出最长的 \(k-1\) 个区间，每个分配一个集合，然后剩下的全丢到最后一个集合里

这个做法适用的情况是存在完全没有交集的线段时，此时假设线段 \(a,b,c\) 互相无交集，那么把它们都堆到一起是最优情况，否则总是可能会占用更多的集合导致答案变小

另一种

首先发现题目里的不超过 \(k\) 完全没有用，因为当你从划分 \(k-1\) 段改到划分 \(k\) 段的时候，要么把两个有交的线段拆开了，要么无变化，总之贡献一定是单调不减的，所以你只需要考虑划分 \(k\) 段时候的答案就行了

一种比较正常的转移一定是形如 \(f_i=\max_j (f_j+cost)\) 的，因此你直接去维护这个 \(f\)

换一种思路，设 \(f_{i,k}\) 是枚举前 \(i\) 位，第 \(i\) 位放 \(k\) 集合时 \(k\) 这单个集合的的贡献，按题意枚举最值暴力转移，复杂度 \(nk\)，同时第一维可以压掉

说一下这个转移，我定义 \(cost\) 是加入这个线段对区间长度的贡献，比如加入 \([1,3]\) 到空集贡献为 \(2\)，\([1,2]\) 加入 \([1,3]\) 贡献为 \(-1\)，通过这个来进行转移，写起来挺像贪心的

不知道能不能再优化，我赛后就没试了

封了个类用来转移集合，应该挺好懂的

#include<bits/stdc++.h>
using namespace std;
#define int long long
template<typename T>void ignored(T x){}
struct line{
    int l,r;
    inline bool operator >(const line&A)const{
        return r-l>A.r-A.l;
    }
};
struct area{
    int l,r;
    area(){
        l=-1,r=-1;
    }
    inline int len()const{
        return l==-1ll?0ll:max(0ll,r-l);
    }
    inline area operator+(line a){
        area ans;
        if(l==-1){
            ans.l=a.l;
            ans.r=a.r;
        }
        else{
            ans.l=max(l,a.l);
            ans.r=min(r,a.r);
        }
        return ans;
    }
};
int n,m;
line a[5001];
area p[5001];
area np[5001];
signed main(){
    ignored(freopen("se.in","r",stdin));
    ignored(freopen("se.out","w",stdout));
    ignored(scanf("%lld %lld",&n,&m));
    for(int i=1;i<=n;++i){
        ignored(scanf("%lld %lld",&a[i].l,&a[i].r));
    }
    sort(a+1,a+n+1,greater<line>());
    int ans2=0;
    for(int i=1;i<=m;++i){  //策略1
        np[i]=np[i]+a[i];
    }
    for(int i=m+1;i<=n;++i){
        np[m]=np[m]+a[i];
    }
    for(int i=1;i<=m;++i){
        ans2+=np[i].len();
    }
    for(int i=1;i<=n;++i){   //策略2
        int mindx=0x3f3f3f3f,mindxid=1;
        for(int j=1;j<=m;++j){
            int tmp=p[j].len()-(p[j]+a[i]).len();//这里找的是对贡献减小量最少的
            if(tmp<mindx){
                mindx=tmp;
                mindxid=j;
            }
            else if(tmp==mindx){
                if(p[mindxid].len()>p[j].len()){
                    mindxid=j;
                }
            }//寻找最值
        }
        p[mindxid]=p[mindxid]+a[i];
    }
    int ans=0;
    for(int i=1;i<=m;++i){
        ans+=p[i].len();
    }
    cout<<max(ans,ans2);
}