自己做的网站显示不出来,网站怎么做长尾词,免费的wordpress主机,保密管理咨询公司题意#xff1a;给定nnn和ddd#xff0c;构造或判断无法构造一棵二叉树使得所有点的深度#xff08;定义为到根距离#xff09;之和为ddd。 n,d≤5000n,d\leq 5000n,d≤5000
显然可以算出有解的ddd的下界和上界#xff0c;分别是完全二叉树和链的情况。下面会证明在这个范…题意给定nnn和ddd构造或判断无法构造一棵二叉树使得所有点的深度定义为到根距离之和为ddd。
n,d≤5000n,d\leq 5000n,d≤5000
显然可以算出有解的ddd的下界和上界分别是完全二叉树和链的情况。下面会证明在这个范围内一定有解。
考虑增量先构造出一条链每次选一个叶结点接到深度小111的位置。
具体实现可以按编号暴力枚举叶结点然后暴力枚举新位置的父亲即深度小222且儿子数222。如果找不到因为它的祖先都遍历过感性理解这个叶结点上面都放满了以后不可能再用打上标记下次增量的时候不访问。
一棵二叉树是完全二叉树当且仅当所有倒数第三深的点都已经有两个儿子。所以不是完全二叉树时可以按上面的方法增量。
复杂度看似是O(n(n2−d))O(n(n^2-d))O(n(n2−d))但实际上ddd小于下界时可以直接输出NO
显然下界是O(nlogn)O(n\log n)O(nlogn)的也就是说只需要考虑nlogndn\log ndnlognd
变换得ndlognn\frac{d}{\log n}nlognd
那么复杂度不劣于O((dlogn)3)O((\frac{d}{\log n})^3)O((lognd)3)
当d5000d5000d5000,nnn最小只能到根号级别
加上算法复杂度不满可以通过
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 5005
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
int fa[MAXN],cnt[MAXN],sum[MAXN],dep[MAXN],bad[MAXN];
int main()
{sum[1]1;for (int i2;iMAXN;i) sum[i]isum[i/2]sum[i-i/2-1];for (int i1;iMAXN;i) sum[i]-i;for (int Tread();T;T--){int n,d;nread(),dread();int curn*(n-1)/2;if (dsum[n]||dcur) {puts(NO);continue;}fa[1]0;for (int i2;in;i) fa[i]i-1;for (int i1;in;i) cnt[i]1;cnt[n]0;for (int i1;in;i) bad[i]0,dep[i]i-1;while (curd){int u;for (u1;un;u)if (!cnt[u]!bad[u])break;bad[u]1;for (int p1;pn;p)if (cnt[p]2dep[u]-dep[p]2){--cnt[fa[u]],fa[u]p;dep[u]dep[p]1,cnt[p];bad[u]0,--cur;break;}}puts(YES);for (int i2;in;i) printf(%d%c,fa[i], \n[in]);}return 0;
}
