|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 sfqxx 于 2023-2-24 17:40 编辑
你们顺着藏宝图的方向,走到了一个藏有10w鱼币的宝箱(剧情需要,请勿当真!)
但是!要想打开它,休想那么容易
这时,有两个人走了过来,他们能给你们一些提示……
但!需要作答两道超级难的题目
好了咱们先看题:
第一题:
玘给了寒一棵编号为 1~n 的树,这棵树上每个点都有一个点权,同时有些边有边权,有些边没有边权。可是玘把每一个点的点权删除了(真的6)。寒只知道点权都是整数,而且在 l 和 r 之间(包含端点)。而且,点权和边权有着下面的特殊关系:
对于有边权的边,要求连接的两个点的点权和为边权。
对于没有边权的边,无限制。
玘问寒这棵树有多少种不同的点权填写方式。两种填写方式不同,当且仅当至少存在一个点的点权不同。可是寒不会做这个题。
寒请你解决这个问题。回答正确即可获得第一条线索
输入格式:
本题有多组测试数据。
第一行一个整数 T,代表测试数据组数。
对于每一组测试数据:
第一行三个整数 n,l,r,代表树上点的个数是 n,点权的范围是 [l,r]。
接下来 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种填写方式:
{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贡献(通过判定)
使用语言:暂无
(第二题明天再说吧 )
18:00前回答会有20鱼币额外奖励哦 (已结束)
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鱼币活动开始!
万水千山总是情,给个评分行不行
感觉好像有点思路,试着写了一个
- #include <stdio.h>
- #include <stdint.h>
- #include <stdbool.h>
- const uint64_t mod = 1000000007;
- struct edge{
- int64_t weight;
- uint32_t destination;
- uint32_t next;
- };
- struct edge edges[(unsigned int)4e5];
- uint32_t head[(unsigned int)2e5 + 1];
- uint32_t next_edge;
- uint32_t n;
- int64_t l, r;
- void insert_edge(uint32_t source, uint32_t destination, int64_t weight){
- edges[next_edge].weight = weight;
- edges[next_edge].destination = destination;
- edges[next_edge].next = head[source];
- head[source] = next_edge++;
- }
- void trace(
- uint32_t target,
- int64_t p_weight, int64_t p_low, int64_t p_high,
- int64_t* c_low, int64_t* c_high
- ){
- uint32_t start = head[target];
- int64_t low = p_weight - p_high;
- int64_t high = p_weight - p_low;
- head[target] |= 1 << 31;
- int64_t child_low, child_high;
- for(uint32_t edge = start; edge != 0x7fffffff; edge = edges[edge].next){
- if(head[edges[edge].destination] >> 31 == 1) continue;
- if(edges[edge].weight - low < l || edges[edge].weight - high > r){
- low = 1;
- high = 0;
- break;
- }
- if(edges[edge].weight - r > low) low = edges[edge].weight - r;
- if(edges[edge].weight - l < high) high = edges[edge].weight - l;
- trace(edges[edge].destination, edges[edge].weight, low, high, &child_low, &child_high);
- if(child_low > child_high){
- low = 1;
- high = 0;
- break;
- }
- if(edges[edge].weight - child_high > low) low = edges[edge].weight - child_high;
- if(edges[edge].weight - child_low < high) high = edges[edge].weight - child_low;
- }
- *c_low = low;
- *c_high = high;
- }
- void group_main(){
- uint64_t result = 1;
- scanf("%u%ld%ld", &n, &l, &r);
- int64_t minimum_weight = l + l;
- int64_t maximum_weight = r + r;
- for(uint32_t i = 1; i <= n; i++) head[i] = 0x7fffffff;
- next_edge = 0;
- uint8_t op;
- uint32_t source, destination;
- int64_t weight;
- for(uint32_t i = 1; i < n; i++){
- scanf("%hhu", &op);
- if(op == 0) scanf("%*u%*u");
- else if(op == 1){
- scanf("%u%u%ld", &source, &destination, &weight);
- if(weight > maximum_weight || weight < minimum_weight){
- printf("0\n");
- return;
- }
- insert_edge(source, destination, weight);
- insert_edge(destination, source, weight);
- }
- }
- int64_t left, right;
- for(uint32_t i = 1; i <= n; i++){
- if(head[i] >> 31 == 0){
- trace(i, l + r, l, r, &left, &right);
- if(left > right){
- result = 0;
- break;
- }
- result = ((right - left + 1) * result) % mod;
- if(result == 0) break;
- }
- }
- printf("%lu\n", result);
- }
- int main(){
- uint8_t T;
- scanf("%hhu", &T);
- for(uint8_t i = 0; i < T; i++) group_main();
- return 0;
- }
复制代码
|
评分
-
查看全部评分
|