【C++板块提升计划】梦想护卫舰 第15期 画树
本帖最后由 sfqxx 于 2023-2-24 17:40 编辑你们顺着藏宝图的方向,走到了一个藏有10w鱼币的宝箱(剧情需要,请勿当真!)
但是!要想打开它,休想那么容易
这时,有两个人走了过来,他们能给你们一些提示……
但!需要作答两道超级难的题目{:10_256:}
好了咱们先看题:
第一题:
玘给了寒一棵编号为 1~n 的树,这棵树上每个点都有一个点权,同时有些边有边权,有些边没有边权。可是玘把每一个点的点权删除了(真的6)。寒只知道点权都是整数,而且在 l 和 r 之间(包含端点)。而且,点权和边权有着下面的特殊关系:
对于有边权的边,要求连接的两个点的点权和为边权。
对于没有边权的边,无限制。
玘问寒这棵树有多少种不同的点权填写方式。两种填写方式不同,当且仅当至少存在一个点的点权不同。可是寒不会做这个题。
寒请你解决这个问题。回答正确即可获得第一条线索{:10_254:}
输入格式:
本题有多组测试数据。
第一行一个整数 T,代表测试数据组数。
对于每一组测试数据:
第一行三个整数 n,l,r,代表树上点的个数是 n,点权的范围是 。
接下来 n-1 行,每行先输入一个整数 op,op=0 表示这条边没有边权,op=1 表示这条边有边权。
如果 op=0,再输入两个整数 u,v,表示这条边连接 u,v两个点。
如果 op=1,再输入三个整数 u,v,w,表示有一条权值为 w 的边连接 u,v 两个点。
输出格式:
对于每个测试点,输出一行一个整数,代表点权填写方式的个数。答案对 10^9+7 取模。
输入与输出样例
输入:
2
6 0 4
1 1 2 2
1 2 3 4
1 3 4 2
0 2 5
1 4 6 3
6 -1 4
1 1 2 4
0 2 3
0 3 4
0 2 5
0 4 6
输出:
5
6480
说明/提示
样例解释
对于样例的第一组测试数据,可以得到下图:
5种填写方式:
{0,2,2,0,0,3}
{0,2,2,0,1,3}
{0,2,2,0,2,3}
{0,2,2,0,3,3}
{0,2,2,0,4,3}
可以证明,不存在别的填写方式。
样例输入中,为了直观,添加了空行。实际数据中不存在多余空行。
数据范围
本题采用捆绑测试。
特殊性质:保证每条边都无边权。
对于 100% 的数据,保证 1≤T≤5,1≤n≤2×10^5
,1≤∑(求和,其实我没见过)n≤10 ^6,-10^9≤l≤r≤10^9
,-10^ 9≤w≤10 ^9
,op∈(这个不明白,谁知道在评论区回答可以获得1贡献){0,1}。
注:1.本题非原创,见戳他(修复中,先别点)
2.本期没有答案
最佳战士:暂无
奖励:10荣誉+6贡献(通过判定)
使用语言:暂无
(第二题明天再说吧{:10_256:} )
18:00前回答会有20鱼币额外奖励哦{:10_256:} (已结束)
18:31+10分钟(考虑到不可抗因素)前回答有10鱼币(已结束)
19:01前8鱼币(已结束)
19:31前5鱼币(已结束)
20:00前3鱼币(结束)
20:31前1鱼币(结束)
注:此活动仅限一人,若一人回答对,剩下的直接作废
https://fishc.com.cn/thread-223717-1-1.html
鱼币福利!
保底2鱼币活动开始!
万水千山总是情,给个评分行不行
emmm......什么叫边权?{:10_277:} 元豪 发表于 2023-1-27 17:02
emmm......什么叫边权?
布吉岛{:10_304:} sfqxx 发表于 2023-1-27 18:15
布吉岛
那你怎么发的题目????? 元豪 发表于 2023-1-27 18:32
那你怎么发的题目?????
看原创…… sfqxx 发表于 2023-1-27 18:33
看原创……
。。你原链接呢??点进去是不存在啊 hziyan 发表于 2023-1-27 20:55
。。你原链接呢??点进去是不存在啊
这……
我调一下 《难度适中》https://fishc.com.cn/static/image/smiley/ARU/aru-1x-1_015.png 谢谢分享原创知识 。。看了看题目,那个20:31前1鱼币(没开始)看得很绝望,毕竟已经九点都结束了{:10_282:}
浅浅分析一下,关键句是
对于有边权的边,要求连接的两个点的点权和为边权。
对于没有边权的边,无限制。
其实不用管点权和边权是个啥(硬要理解可以理解为权重?)
可以简单理解就是一堆包含数点和线,连接线的两点代表的数之和要等于线代表的数
配合那个图就很好理解了,
那么在理解以上条件后,题目就是要求出在这些条件限制下的可能解有几个(取模是为了防止"猜"吧)
至于
op∈(这个不明白,谁知道在评论区回答可以获得1贡献){0,1}
这个∈是包含,高中知识,大概就是op必须是0或者1两个数 tomok 发表于 2023-1-27 21:16
谢谢分享原创知识
原创个灯{:10_266:} 2.本期没有答案
是因为你是瞎选的题,啊呵呵,我说随便选你还真的就随便选啊{:10_266:} zhangjinxuan 发表于 2023-1-27 21:24
原创个灯
我***什么时候说原创了 zhangjinxuan 发表于 2023-1-27 21:31
是因为你是瞎选的题,啊呵呵,我说随便选你还真的就随便选啊
不就那个比赛题吗?
445通过1 sfqxx 发表于 2023-1-27 22:24
不就那个比赛题吗?
445通过1
{:10_245:} hziyan 发表于 2023-1-27 21:16
。。看了看题目,那个20:31前1鱼币(没开始)看得很绝望,毕竟已经九点都结束了
浅浅分析一 ...
题目有点难,
你现在回答保底2鱼币 sfqxx 发表于 2023-1-28 11:26
题目有点难,
你现在回答保底2鱼币
。。何止有点难,逻辑判断部分我目前只有一种暴力穷举,我相信大部分人倒在这个地方了 hziyan 发表于 2023-1-28 12:34
。。何止有点难,逻辑判断部分我目前只有一种暴力穷举,我相信大部分人倒在这个地方了
我去看看现在的情况 hziyan 发表于 2023-1-28 12:34
。。何止有点难,逻辑判断部分我目前只有一种暴力穷举,我相信大部分人倒在这个地方了
{:10_247:}不整了,再整伤身,我今天忙,忙完先(今天可能一整天都忙)再看看吧 sfqxx 发表于 2023-1-27 22:21
我***什么时候说原创了
我去!还真的瞎选啊!
我甚至怀疑这题高达 提高+/省选- {:10_285:}
页:
[1]
2