首页 > Tree Constructer
开通博客写题解
头像 hnust_yangyanjun
发表于 2021-02-06 11:30:36
题意：有一棵n个节点树，请你构造节点数据使图正好为这棵树（节点之间有边仅这二个节点位与等于 -1）。 思路：我们可以先黑白染色，因为n<=100,所以一定会有一种颜色少于等于50，所以我们就应该从位上考虑，不然为什么n<=100而不是小于100000呢，又因为只有相邻黑白节点才连接，所以 展开全文
去ta的博客 赞 (6) 回复(1) 收起
头像 (́安◞౪◟排‵)
发表于 2021-01-30 10:20:38
正常人谁打正解啊瞎搞了一个小时终于过了~~~~由于是随机算法，不保证在规定时间内一定可以跑出答案（但是实测还是很快的） 建出的图一定是一个树我们随便固定一个点为跟节点先求一遍dfs序然后就开始我们的随机算法dfs跑树，随机赋值跑到的点的点权，保证和其父亲的或为m（m为1<<60 -1 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 熠丶
发表于 2021-01-29 17:27:07
题意 给定一棵n个结点的树，现要你将每个结点u赋上一个权值​，使得若x,y之间有边，则，若x,y之间没有边，则 这里就不用二分图构造的正解了，毕竟在赛场上构造题想不到就是想不到（别骂了，比赛就没想到qwq我来提供一种随机大法的做法（赛后看dalao提交的因为n最大为100，所以很容易随机过 思路 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 shyyhs
发表于 2021-01-30 13:06:41
不会构造... 思路: 我们先将图进行黑白染色,然后将白点的最高位和第id位设置为0,其余为1,保证白点相互之间不连通,然后黑色点将其最高位设置为1,其它和白色相邻的点设置成1.然后因为中间缺了些1,黑色点也是不连通的,然后这样构造就保证了黑色点只与相邻的白色点相连. 代码: #include &l 展开全文
去ta的博客 赞 (1) 回复(4) 收起
头像 回归梦想
发表于 2021-01-24 22:40:22
题目： 题意： 如果点x和y有连边，当且仅当a[x] or a[y] = 2^60^ - 1 （两者是充分必要）现在给你边的关系，问你每个点的值应该是多少？（给出一种情况即可） 题解： 构造题，思路非常巧妙2^60^就是（1<<60）,减去1也就是从第一位到第59位都是1（第六十位是0 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-01-29 21:43:23
题目描述 现在给定描述，如果两个点之间的或运算结果答案是，说明这两个点之间有边。问给你一个n个节点，你如何设置节点值，使得构造出来的图是一棵树，题目给出数的边信息。 ，输出构造的节点值。 Solution 数据范围的n很小，并且答案给的是一个关于的幂次的形式，那么就要往二进制方向靠。这也是一个比较新 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 hunxuewangzi
发表于 2021-01-31 20:54:42
题目大意 给你一颗树(n<=100) 要你给点赋权值，如果x|y= 则代表x和y有边 题目思路 只要没有回路的图都可以看作是一个二分图 把这个想成二分图染色 想成白点和黑点（白点个数<黑点个数） 白点的第59位为0，以及白点的id位为0，给每个白点赋值一个不同的id，其他位白点均为1 黑 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 回归梦想
发表于 2021-01-24 22:54:33
题意： 有n堆石头，每堆石头最多只有三个石头（最少1个），每两堆石头（这两堆各含石头x个和y个）合一起的费用为(x mod 3) * (y mod 3)，现在把所有堆合成一堆，问最小费用题目第一行给出三个数，第i个数表示有i个石头的堆有多少个 题解： 费用是(x mod 3) * (y mod 3) 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”