差别

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

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest21 [2021/10/02 19:38]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest21 [2021/10/04 17:04] (当前版本)
jxm2001 [题解]
@@ 行 4: / 行 4: @@
 ^  题目  ^  蒋贤蒙  ^  王赵安  ^  王智彪  ^
-|  B  |  0  |  0  |  0  |
+|  B  |  2  |  0  |  0  |
 |  E  |  0  |  0  |  0  |
 |  F  |  0  |  0  |  0  |
 |  G  |  2  |  0  |  0  |
-|  H  |  0  |  0  |  0  |
+|  H  |  2  |  0  |  0  |
 |  K  |  0  |  0  |  0  |
 ====== 题解 =====
+===== B. discount =====
+==== 题意 ====
+给定 $n$ 种商品，对于每个商品 $i$，有两种策略，一种是花费 $a_i$ 购买同时赠送商品 $j$，一种是花费 $b_i$ 购买。$(b_i\le a_i)$
+问至少获得所有商品各一种的最小费用。
+==== 题解 ====
+假定花费 $a_i$ 购买商品 $i$ 可以赠送商品 $j$，则连边 $j\to i$，其中 $i$ 是 $j$ 的儿子结点。
+于是可以得到基环树森林，定义每个结点的状态 $0/1/2$ 表示不购买该结点/以 $b_i$ 购买该结点/以 $a_i$ 购买该结点。
+于是原问题等价于使得每个结点的状态如果为 $0$ 则至少有一个儿子状态为 $2$ 的最小费用。
+先考虑树的解法，设 $\text{dp}(u,0/1/2)$ 为只考虑子树 $u$ 的情况下的最小费用，不难得到状态转移方程。
+接下来考虑每个基环树上的环，任取一个点，枚举该点在环上的子节点状态是否为 $2$，然后进行线性 $\text{dp}$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+const LL inf=1e18;
+struct Edge{
+	int to,next;
+}edge[MAXN];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int fa[MAXN],a[MAXN],b[MAXN];
+bool inque[MAXN],node_vis[MAXN],node_cyc[MAXN];
+LL dp[MAXN][3];
+vector<int> cyc;
+void dfs(int u){
+	LL s1=0,s2=inf;
+	node_vis[u]=true;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(node_cyc[v])continue;
+		dfs(v);
+		LL w=min({dp[v][0],dp[v][1],dp[v][2]});
+		s1+=w;
+		s2=min(s2,dp[v][2]-w);
+	}
+	dp[u][0]=s1+s2;
+	dp[u][1]=b[u]+s1;
+	dp[u][2]=a[u]+s1;
+}
+LL dp2[MAXN][3];
+LL cal1(){
+	int u=cyc[0];
+	dp2[u][0]=min({dp[u][0],dp[u][1]-b[u],dp[u][2]-a[u]});
+	dp2[u][1]=dp[u][1];
+	dp2[u][2]=dp[u][2];
+	_for(i,1,cyc.size()){
+		int u=cyc[i],p=cyc[i-1];
+		dp2[u][0]=dp2[p][2]+min({dp[u][0],dp[u][1]-b[u],dp[u][2]-a[u]});
+		dp2[u][0]=min(dp2[u][0],dp[u][0]+min(dp2[p][0],dp2[p][1]));
+		dp2[u][1]=dp[u][1]+min({dp2[p][0],dp2[p][1],dp2[p][2]});
+		dp2[u][2]=dp[u][2]+min({dp2[p][0],dp2[p][1],dp2[p][2]});
+	}
+	return dp2[*cyc.rbegin()][2];
+}
+LL cal2(){
+	int u=cyc[0];
+	dp2[u][0]=dp[u][0];
+	dp2[u][1]=dp[u][1];
+	dp2[u][2]=dp[u][2];
+	_for(i,1,cyc.size()){
+		int u=cyc[i],p=cyc[i-1];
+		dp2[u][0]=dp2[p][2]+min({dp[u][0],dp[u][1]-b[u],dp[u][2]-a[u]});
+		dp2[u][0]=min(dp2[u][0],dp[u][0]+min(dp2[p][0],dp2[p][1]));
+		dp2[u][1]=dp[u][1]+min({dp2[p][0],dp2[p][1],dp2[p][2]});
+		dp2[u][2]=dp[u][2]+min({dp2[p][0],dp2[p][1],dp2[p][2]});
+	}
+	return min({dp2[*cyc.rbegin()][0],dp2[*cyc.rbegin()][1],dp2[*cyc.rbegin()][2]});
+}
+LL solve(int u){
+	cyc.clear();
+	stack<int> st;
+	int pos=u;
+	while(!inque[pos]){
+		inque[pos]=true;
+		st.push(pos);
+		pos=fa[pos];
+	}
+	node_cyc[pos]=true;
+	cyc.push_back(pos);
+	while(st.top()!=pos){
+		int tmp=st.top();
+		node_cyc[tmp]=true;
+		cyc.push_back(tmp);
+		st.pop();
+	}
+	reverse(cyc.begin(),cyc.end());
+	for(int u:cyc)
+	dfs(u);
+	return min(cal1(),cal2());
+}
+int main()
+{
+	int n=read_int();
+	_rep(i,1,n)
+	a[i]=read_int();
+	_rep(i,1,n)
+	b[i]=a[i]-read_int();
+	_rep(i,1,n){
+		fa[i]=read_int();
+		Insert(fa[i],i);
+	}
+	LL ans=0;
+	_rep(u,1,n){
+		if(!node_vis[u])
+		ans+=solve(u);
+	}
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
 ===== G. transform =====
 二分答案 $+$ 滑动窗口，赛后一分钟过样例 $\to$ 过题，乐。
+===== H. travel =====
+==== 题意 ====
+给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。
+==== 题解 ====
+设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树，结点 $u$ 的状态为 $0/1/2$ 时，已经选中了 $i$ 条链此时的最大路径权值和。
+我们需要维护一条正在生成的链，这条链不包含在已经选中的 $i$ 条链当中，如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。
+如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。
+考虑状态转移，利用生成链的合并，不难有
+$$
+\text{dp}(u,0,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,0,j)\\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,1,j)+a_u\\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,0,j)\\
+\text{dp}(u,2,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,1,j)\\
+\text{dp}(u,2,i+j)\gets \text{dp}(u,2,i)+\text{dp}(v,0,j)
+$$
+注意上式的 $\gets$ 表示取最大值，另外为了防止选中复数条从 $v$ 生成的链，需要开一个临时数组存储中间量。
+初始状态为 $\text{dp}(u,1,0)=a_u$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有
+$$
+\text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1))
+$$
+最终答案为 $\text{dp}(1,0,k)$，时间复杂度 $O(nk^2)$，其中 $k$ 表示最多能选中的链的个数。本题 $k=3$。
+[[http://tokitsukaze.live/2018/07/24/2018niuke2.H/|参考资料]]
+<hidden 查看代码>
+<code cpp>
+const int MAXN=4e5+5,MAXK=4;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int a[MAXN],head[MAXN],edge_cnt;
+LL dp[MAXN][3][MAXK],tmp[3][MAXK];
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+void Max(LL &a,LL b){
+	if(b>a)
+	a=b;
+}
+void dfs(int u,int fa){
+	dp[u][1][0]=a[u];
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs(v,u);
+		_for(i,0,3)_for(j,0,MAXK)
+		tmp[i][j]=dp[u][i][j];
+		_for(i,0,MAXK)_for(j,0,MAXK-i){
+			Max(tmp[0][i+j],dp[u][0][i]+dp[v][0][j]);
+			Max(tmp[1][i+j],dp[u][0][i]+dp[v][1][j]+a[u]);
+			Max(tmp[1][i+j],dp[u][1][i]+dp[v][0][j]);
+			Max(tmp[2][i+j],dp[u][1][i]+dp[v][1][j]);
+			Max(tmp[2][i+j],dp[u][2][i]+dp[v][0][j]);
+		}
+		_for(i,0,3)_for(j,0,MAXK)
+		dp[u][i][j]=tmp[i][j];
+	}
+	_for(i,1,MAXK)
+	Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1]));
+}
+int main()
+{
+	int n=read_int();
+	_rep(i,1,n)
+	a[i]=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	dfs(1,0);
+	enter(dp[1][0][3]);
+	return 0;
+}
+</code>
+</hidden>
 ===== J. farm ====

CVBB ACM Team

用户工具

站点工具

差别

页面工具