北屯网站建设,做英文网站要多少钱,网站建设源代码文件,网页qq登录保护功能正题
https://www.luogu.com.cn/problem/CF1481F 题目大意
给出nnn个点的一棵树#xff0c;在每个节点上填a/ba/ba/b#xff0c;要求恰好有mmm个aaa。要求每个节点到根路径上的字符串种类最少#xff0c;输出方案。 1≤m≤n≤1051\leq m\leq n\leq 10^51≤m≤n≤105 解题思…正题
https://www.luogu.com.cn/problem/CF1481F 题目大意
给出nnn个点的一棵树在每个节点上填a/ba/ba/b要求恰好有mmm个aaa。要求每个节点到根路径上的字符串种类最少输出方案。
1≤m≤n≤1051\leq m\leq n\leq 10^51≤m≤n≤105 解题思路
被stoorz拉来做这题被D了/kk
很顺理成章的一个思路是我们可以在同一深度的点填上相同的字母如果能够做到答案到达下界就是最大深度。
但是显然不是所有时候都能到达下界再考虑一个能确定上界的构造方法。我们从上往下填当我们到达一层设有xxx个非叶子节点还剩下m0m_0m0个aaa和m1m_1m1个bbb那么显然有m0m1≥2xm_0m_1\geq 2xm0m1≥2x也就是有max{m0,m1}≥xmax\{m_0,m_1\}\geq xmax{m0,m1}≥x所以这一层的非叶子节点一定能填相同的字母然后叶子节点我们优先按照非叶子节点的字母填。如果够那么这一层的贡献是111如果不够这一层会产生一个不同的贡献为222但是此时有一种字母已经用完所以剩下的层的贡献一定都是111。
这样就发现答案的上界就是最大深度1问题就变为了如何判断答案是否是kkk了。
暴力完全背包显然不可行考虑从和为nnn入手相似与根号分治的思路我们可以考虑根号的复杂度。对于所有层来说节点数不同的值只有根号级别种所以我们可以把这些合并出来变成一个多重背包问题然后用单调队列的O(nm)O(nm)O(nm)做法即可但是由于这题是判断是否能够拼出来所以不需要单调队列甚至不需要枚举余数。
时间复杂度O(nn)O(n\sqrt n)O(nn) code
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N1e510;
struct node{int to,next;
}a[N];
int n,m,k,p,tot,r[N],ls[N],f[500][N];
bool ans[N];vectorintv[N],c[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int dep){kmax(k,dep);v[dep].push_back(x);for(int ils[x];i;ia[i].next){int ya[i].to;dfs(a[i].to,dep1);}return;
}
void solve0(){for(int i1;in;i)ans[i]1;while(pm){int l(m-f[p][m])/r[p];for(int i0;il;i)for(int j0;jv[c[r[p]][i]].size();j)ans[v[c[r[p]][i]][j]]0;mf[p][m];p--;}printf(%d\n,k);for(int i1;in;i)putchar(ans[i]a);return;
}
void solve1(){int u[2]{m,n-m};for(int d1;dk;d){int tmp0,uc0;for(int i0;iv[d].size();i)tmp(ls[v[d][i]]!0);if(tmpu[0])u[0]-tmp;else{uc1;u[1]-tmp;for(int i0;iv[d].size();i)if(ls[v[d][i]]!0)ans[v[d][i]]1;}for(int i0;iv[d].size();i){if(ls[v[d][i]]!0)continue;if(!u[uc])uc^1;u[uc]--;ans[v[d][i]]uc;}}printf(%d\n,k1);for(int i1;in;i)putchar(ans[i]a);return;
}
int main()
{scanf(%d%d,n,m);for(int i2,x;in;i)scanf(%d,x),addl(x,i);dfs(1,1);for(int i1;ik;i)c[v[i].size()].push_back(i);for(int i1;im;i)f[0][i]-1;for(int i1;in;i){if(!c[i].size())continue;r[p]i;for(int j1;jm;j)f[p][j]-1;for(int j1;jm;j){if(f[p-1][j]!-1)f[p][j]j;else if(jif[p][j-i]!-1j-f[p][j-i]i*c[i].size())f[p][j]f[p][j-i];}}if(f[p][m]!-1)solve0();else solve1();return 0;
}
