差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest5 [2021/07/30 20:19]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest5 [2021/08/04 10:52] (当前版本)
jxm2001
@@ 行 2: / 行 2: @@
 ====== 题解 ======
+===== C. Cover the Paths =====
+==== 题意 ====
+给定一棵树和若干路径，要求选出最小的点集，使得每条路径上至少有一个点。
+==== 题解 ====
+强制以 $1$ 为根，根据每条路径两端点的 $\text{LCA}$ 深度从大到小排序。
+对于 $\text{LCA}$ 深度最大的路径，显然必须选择一个点，由于其他路径的 $\text{LCA}$ 深度都不小于该路径，显然选择该路径的 $\text{LCA}$ 最优。
+然后再考虑深度第二大的点，如果该路径上已经有点被选就不再选点，否则再选一个 $\text{LCA}$，不断贪心。
+贪心正确性是由于该决策顺序下路径 $\text{LCA}$ 深度递增，所以之前选的点深度越小越好，因此前面的路径的点只选 $\text{LCA}$，且尽量少选。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+#define lowbit(x) ((x)&(-x))
+namespace Tree{
+	int c[MAXN];
+	void add(int pos){
+		while(pos<MAXN){
+			c[pos]++;
+			pos+=lowbit(pos);
+		}
+	}
+	int query(int pos){
+		int ans=0;
+		while(pos){
+			ans+=c[pos];
+			pos-=lowbit(pos);
+		}
+		return ans;
+	}
+	int query(int L,int R){
+		return query(R)-query(L-1);
+	}
+}
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int d[MAXN],sz[MAXN],f[MAXN],dfn[MAXN],dfs_t;
+int h_son[MAXN],mson[MAXN],p[MAXN];
+void dfs_1(int u,int fa,int depth){
+	sz[u]=1,f[u]=fa,d[u]=depth,mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs_1(v,u,depth+1);
+		sz[u]+=sz[v];
+		if(sz[v]>mson[u]){
+			h_son[u]=v;
+			mson[u]=sz[v];
+		}
+	}
+}
+void dfs_2(int u,int top){
+	dfn[u]=++dfs_t,p[u]=top;
+	if(mson[u])
+	dfs_2(h_son[u],top);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==f[u]||v==h_son[u])
+		continue;
+		dfs_2(v,v);
+	}
+}
+int query(int u,int v){
+	int ans=0;
+	while(p[u]!=p[v]){
+		if(d[p[u]]<d[p[v]])
+		swap(u,v);
+		ans+=Tree::query(dfn[p[u]],dfn[u]);
+		u=f[p[u]];
+	}
+	if(d[u]>d[v])
+	swap(u,v);
+	ans+=Tree::query(dfn[u],dfn[v]);
+	return ans;
+}
+int lca(int u,int v){
+	while(p[u]!=p[v]){
+		if(d[p[u]]<d[p[v]])swap(u,v);
+		u=f[p[u]];
+	}
+	return d[u]<d[v]?u:v;
+}
+struct Node{
+	int u,v,p;
+	bool operator < (const Node b)const{
+		return d[p]>d[b.p];
+	}
+}node[MAXN];
+int main(){
+	int n=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	dfs_1(1,0,0);
+	dfs_2(1,1);
+	int m=read_int();
+	_for(i,0,m){
+		int u=read_int(),v=read_int(),p=lca(u,v);
+		node[i]=Node{u,v,p};
+	}
+	sort(node,node+m);
+	vector<int> ans;
+	_for(i,0,m){
+		if(query(node[i].u,node[i].v)==0){
+			ans.push_back(node[i].p);
+			Tree::add(dfn[node[i].p]);
+		}
+	}
+	enter(ans.size());
+	for(int u:ans)
+	space(u);
+	return 0;
+}
+</code>
+</hidden>
+===== G. Berland Post =====
+==== 题意 ====
+给定若干条形如 $x_v+b_i\le x_u+T$ 的限制，求最小的 $T$ 以及这种情况下的一组合法解 $(x_1,x_2\cdots x_n)$。
+其中，某些 $x_i$ 的值已经固定。
+==== 题解 ====
+将方程转化为 $x_v\le x_u+T-b_i$，考虑二分 $T$ 然后差分约束求解。
+设超级源点为 $s$。关于点权的限制，对于无限制的 $x_i$，连边 $(s,i,\infty),(i,s,\infty)$，表示 $-\infty\le x_i\le \infty$。
+对于固定的 $x_i$，连边 $(s,i,v),(i,s,-v)$，表示 $v\le x_i\le v$。时间复杂度 $O(nm\log V)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e3+5,MAXM=4e3+5,SPV=2e5;
+const double inf=1e15,infv=1e7,eps=1e-7,eps2=1e-9;
+int read_int(){
+	int t=0;bool sign=false;char c=getchar();
+	while(c==' '||c=='\r'||c=='\n')c=getchar();
+	if(c=='?')return SPV;
+	if(c=='-')sign=true,c=getchar();
+	while(isdigit(c)){
+		t=t*10+c-'0';
+		c=getchar();
+	}
+	return sign?-t:t;
+}
+struct Edge{
+	int to,next;
+	double w;
+}edge[MAXM<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,double w){
+	++edge_cnt;
+	edge[edge_cnt].to=v;
+	edge[edge_cnt].w=w;
+	edge[edge_cnt].next=head[u];
+	head[u]=edge_cnt;
+}
+namespace SPFA{
+	double dis[MAXN];
+	int len[MAXN];
+	bool inque[MAXN];
+	bool solve(int src,int n){
+		queue<int>q;
+		_rep(i,1,n){
+			inque[i]=false;
+			len[i]=0;
+			dis[i]=inf;
+		}
+		dis[src]=0;len[src]=1;
+		q.push(src);
+		inque[src]=true;
+		while(!q.empty()){
+			int u=q.front();q.pop();
+			inque[u]=false;
+			for(int i=head[u];i;i=edge[i].next){
+				int v=edge[i].to;
+				if(dis[v]>dis[u]+edge[i].w+eps2){
+					dis[v]=dis[u]+edge[i].w;
+					len[v]=len[u]+1;
+					if(len[v]>n)
+					return false;
+					if(!inque[v]){
+						q.push(v);
+						inque[v]=true;
+					}
+				}
+			}
+		}
+		return true;
+	}
+}
+struct Edge2{
+	int u,v,w;
+};
+vector<Edge2> edges;
+int a[MAXN];
+bool check(int n,double T){
+	int s=++n;
+	edge_cnt=0;
+	_rep(i,1,n)
+	head[i]=0;
+	_for(i,1,n){
+		if(a[i]==SPV){
+			Insert(s,i,infv);
+			Insert(i,s,infv);
+		}
+		else{
+			Insert(s,i,a[i]);
+			Insert(i,s,-a[i]);
+		}
+	}
+	for(Edge2 e:edges)
+	Insert(e.v,e.u,T-e.w);
+	return SPFA::solve(s,n);
+}
+int main(){
+	int n,m;
+	while(cin>>n>>m){
+		edges.clear();
+		_rep(i,1,n)
+		a[i]=read_int();
+		while(m--){
+			int u=read_int(),v=read_int(),w=read_int();
+			edges.push_back(Edge2{u,v,w});
+		}
+		double lef=0,rig=infv;
+		while(rig-lef>eps){
+			double mid=(lef+rig)/2;
+			if(check(n,mid))
+			rig=mid;
+			else
+			lef=mid;
+		}
+		printf("%.6lf\n",lef);
+		check(n,lef);
+		_rep(i,1,n)
+		printf("%.6lf ",SPFA::dis[i]);
+		puts("");
+	}
+	return 0;
+}
+</code>
+</hidden>
 ===== J. Subsequence Sum Queries =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具