2020-2021:teams:legal_string:jxm2001:contest:cf_699_div._2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:cf_699_div._2 [2021/02/08 17:59] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:cf_699_div._2 [2021/02/12 15:42] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 84: | 行 84: | ||
| 如果答案等于 $d+1$，则逆序暴力并输出方案，时间复杂度 $O(n)$。 | 如果答案等于 $d+1$，则逆序暴力并输出方案，时间复杂度 $O(n)$。 | ||
| + | |||
| + | ps. 据说二进制优化 + $\text{bitset}$ 可以做到 $O\left(\frac {n\sqrt n}w\right)$ | ||
| 否则，答案一定为 $d+2$，下面给出构造。 | 否则，答案一定为 $d+2$，下面给出构造。 | ||
| 行 91: | 行 93: | ||
| 若 $c_i$ 满足 $c_i\le \max(x,y)$，则直接将该层节点用一种字符覆盖即可。 | 若 $c_i$ 满足 $c_i\le \max(x,y)$，则直接将该层节点用一种字符覆盖即可。 | ||
| - | 否则当前层的非叶子节点数一定 $\le \frac {x+y}2$ | + | 否则，考虑当前层的非叶子节点数。剩下的节点数总和为 $x+y$，而非叶子结点数总和一定不大于叶子结点数总和。 |
| + | |||
| + | 于是当前层的非叶子节点数 $\le$ 叶子结点数总和 $\le \frac {x+y}2\le \max(x,y)$。 | ||
| + | |||
| + | 不妨设 $\max(x,y)=x$，于是用全部 $a$ 覆盖当前层所有非叶子节点与部分叶子节点，其他剩余节点全部用 $b$ 覆盖，于是总答案仅 $+1$。 | ||
| + | |||
| + | 总时间复杂度 $O(n\sqrt n)$。 | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <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> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_699_div._2.1612778358.txt.gz · 最后更改: 2021/02/08 17:59 由 jxm2001
