差别

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

--- 2020-2021:teams:legal_string:jxm2001:contest:cf_699_div._2 [2021/02/07 22:25]
jxm2001 [题解]
+++ 2020-2021:teams:legal_string:jxm2001:contest:cf_699_div._2 [2021/02/12 15:42] (当前版本)
jxm2001 [题解]
@@ 行 13: / 行 13: @@
 ==== 题解 ====
-显然只需要在序列中选定一些位置，然后按特定顺序将他们移除就可以完成任务。定义 $\text{dp}(i)$ 表示不移动序列 $[i,n]$ 的位置的个数。
+显然只需要在序列中选定一些位置，然后按特定顺序将他们移除就可以完成任务。定义 $\text{dp}(i)$ 表示不选择序列 $[i,n]$ 中的位置个数的最大值。
 维护每个值 $v$ 的最靠左出现的位置 $l_v$，最靠右出现的位置 $r_v$，动态维护 $[i,n]$ 中出现的次数 $c_v$。
-于是如果选择保留位置 $i$，若 $i=l_{a_i}$，则需要移除 $[i,r_{a_i}]$ 中所有不等于 $a_i$ 的位置，即 $\text{dp}(i)=c_{a_i}+\text{dp}(r_{a_i}+1)$。
+如果保留位置 $i$ 。当 $i=l_{a_i}$ 时，需要移除 $[i,r_{a_i}]$ 中所有不等于 $a_i$ 的位置，即 $\text{dp}(i)\gets c_{a_i}+\text{dp}(r_{a_i}+1)$。
-若 $i\neq l_{a_i}$，则只考虑移除 $[i,n]$ 中所有不等于 $a_i$ 的位置，
+当 $i\neq l_{a_i}$ 时，若不保留 $l_{a_i}$ 的位置，则 $l_{a_i}$ 的位置的数会被加到位置 $n$ 后面。
+为了使得 $l_{a_i}$ 的位置的数与 $i$ 位置的数所在段相邻，需要移除 $[i,n]$ 中所有不等于 $a_i$ 的位置，于是 $\text{dp}(i)\gets c_{a_i}$。
+若保留 $l_{a_i}$ 的位置，则该情况会在计算 $\text{dp}(l_{a_i})$ 时考虑，此时不考虑。
+如果不保留位置 $i$，则 $\text{dp}(i)\gets \text{dp}(i+1)$。最终答案为 $n-\text{dp}(1)$。时间复杂度 $O(n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5;
+int a[MAXN],dp[MAXN],l[MAXN],r[MAXN],c[MAXN];
+int main()
+{
+	int n=read_int();
+	_rep(i,1,n)a[i]=read_int();
+	for(int i=n;i;i--){
+		l[a[i]]=i;
+		if(!r[a[i]])r[a[i]]=i;
+	}
+	for(int i=n;i;i--){
+		c[a[i]]++;
+		dp[i]=dp[i+1];
+		if(i==l[a[i]])dp[i]=max(dp[i],dp[r[a[i]]+1]+c[a[i]]);
+		else dp[i]=max(dp[i],c[a[i]]);
+	}
+	enter(n-dp[1]);
+	return 0;
+}
+</code>
+</hidden>
 ===== F. AB Tree =====
 ==== 题意 ====
+给定一棵以 $1$ 为根节点的有根树以及 $x$ 个字符 $a$ 和 $n-x$ 个字符 $b$。要求用所给字符对树上每个结点进行标注。
+给定每个节点代表一个字符串，该字符串由根节点到该节点路径上的所有字符依次拼接而成。
+要求最小化所有节点代表的字符串中的互异的字符串个数，同时输出任意一种方案。
 ==== 题解 ====
+设树的深度为 $d$，根节点深度为 $0$。于是答案一定不小于 $d+1$，因为一定有长度为 $1\sim d+1$ 的字符串。
+先考虑如何判定答案是否为 $d+1$ 以及如何构造方案。为了满足条件，必须满足每个长度的字符串只有一种，于是同一深度的节点字符一定相同。
+不妨设深度 $i$ 共有 $c_i$ 个节点，于是只需要从 $c_0,c_1\cdots c_d$ 中选出若干个数构成 $x$ 即可。
+这是一个背包 $\text{dp}$。考虑优化方案，首先由于 $\sum_{i=0}^d c_i=n$，所以 $c_i$ 最多只有 $O(\sqrt n)$ 个互异的值。
+考虑将所有值相同的 $c_i$ 放在一起考虑，本题转化为多重背包问题，且物品权值只有 $O(\sqrt n)$ 种。
+设 $\text{dp}(i,j)$ 表示只考虑前 $i$ 种权值物品是否存在权值和为 $j$ 的方案。
+设当前物品权值为 $\text{val}$，数量为 $\text{cnt}$。于是对 $\text{dp}(i,j)$，只需要找到 $0\le k\le \text{cnt}$ 使得 $\text{dp}(i-1,j-k*\text{val})=1$ 即可。
+不妨记 $k_j$ 表示满足上述条件的最小的 $k$，且如果不存在 $k$ 满足条件则 $k_j=-1$。
+于是有若 $\text{dp}(i-1,j)=1$ 则 $k_j=0$，否则 $k_j=k_{j-\text{val}}+1$，注意 $k_{j-\text{val}}=-1$ 和 $k_{j-\text{val}}+1\gt \text{cnt}$ 的情况。
+于是可以 $O(n)$ 维护每种权值，$O(n\sqrt n)$ 判定答案是否为 $d+1$。
+如果答案等于 $d+1$，则逆序暴力并输出方案，时间复杂度 $O(n)$。
+ps. 据说二进制优化 + $\text{bitset}$ 可以做到 $O\left(\frac {n\sqrt n}w\right)$
+否则，答案一定为 $d+2$，下面给出构造。
+首先假设当前层还剩下 $x$ 个字符 $a$ 和 $y$ 个字符 $b$，当前节点数为 $c_i$。
+若 $c_i$ 满足 $c_i\le \max(x,y)$，则直接将该层节点用一种字符覆盖即可。
+否则，考虑当前层的非叶子节点数。剩下的节点数总和为 $x+y$，而非叶子结点数总和一定不大于叶子结点数总和。
+于是当前层的非叶子节点数 $\le$ 叶子结点数总和 $\le \frac {x+y}2\le \max(x,y)$。
+不妨设 $\max(x,y)=x$，于是用全部 $a$ 覆盖当前层所有非叶子节点与部分叶子节点，其他剩余节点全部用 $b$ 覆盖，于是总答案仅 $+1$。
+总时间复杂度 $O(n\sqrt n)$。
 <hidden 查看代码>
 <code cpp>
+const int MAXN=1e5+5,MAXM=500;
+struct Edge{
+	int to,next;
+}edge[MAXN];
+int head[MAXN],edge_cnt;
+void AddEdge(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int sz[MAXN],last[MAXN],maxd;
+vector<int> node[MAXN],c[MAXN],cv;
+bool dp[MAXM][MAXN];
+char ans[MAXN];
+void dfs(int u,int d){
+	node[d].push_back(u);
+	sz[u]=1,maxd=max(maxd,d);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		dfs(v,d+1);
+		sz[u]+=sz[v];
+	}
+}
+bool cmp(int u,int v){
+	return sz[u]>sz[v];
+}
+int main()
+{
+	int n=read_int(),x=read_int();
+	_rep(i,2,n)
+	AddEdge(read_int(),i);
+	dfs(1,0);
+	_for(i,0,n)
+	c[node[i].size()].push_back(i);
+	_rep(i,1,n){
+		if(c[i].size()>0)
+		cv.push_back(i);
+	}
+	dp[0][0]=true;
+	_rep(i,1,cv.size()){
+		int val=cv[i-1],cnt=c[val].size();
+		mem(last,-1);
+		_for(j,0,val){
+			if(dp[i-1][j])
+			dp[i][j]=true,last[j]=0;
+			else
+			dp[i][j]=false,last[j]=-1;
+		}
+		_rep(j,val,n){
+			if(dp[i-1][j])
+			dp[i][j]=true,last[j]=0;
+			else if(last[j-val]!=-1&&last[j-val]+1<=cnt)
+			dp[i][j]=true,last[j]=last[j-val]+1;
+			else
+			dp[i][j]=false,last[j]=-1;
+		}
+	}
+	if(dp[cv.size()][x]){
+		enter(maxd+1);
+		_rep(i,1,n)ans[i]='b';
+		for(int i=cv.size(),j=x;i;i--){
+			int val=cv[i-1],pos=0;
+			while(!dp[i-1][j]){
+				j-=val;
+				int d=c[val][pos++];
+				_for(k,0,val)
+				ans[node[d][k]]='a';
+			}
+		}
+		puts(ans+1);
+	}
+	else{
+		enter(maxd+2);
+		pair<char,int> p1('a',x),p2('b',n-x);
+		_for(i,0,n){
+			if(p1.second<p2.second)swap(p1,p2);
+			sort(node[i].begin(),node[i].end(),cmp);
+			_for(j,0,node[i].size()){
+				if(p1.second){
+					ans[node[i][j]]=p1.first;
+					p1.second--;
+				}
+				else{
+					ans[node[i][j]]=p2.first;
+					p2.second--;
+				}
+			}
+		}
+		puts(ans+1);
+	}
+	return 0;
+}
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具