[蓝桥杯 2022 省 A] 推导部分和

这篇具有很好参考价值的文章主要介绍了[蓝桥杯 2022 省 A] 推导部分和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[蓝桥杯 2022 省 A] 推导部分和

题目描述

对于一个长度为 N N N 的整数数列 A 1 , A 2 , ⋯ A N A_{1}, A_{2}, \cdots A_{N} A1,A2,AN,小蓝想知道下标 l l l r r r 的部分和 ∑ i = l r A i = A l + A l + 1 + ⋯ + A r \sum\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\cdots+A_{r} i=lrAi=Al+Al+1++Ar 是多少?

然而,小蓝并不知道数列中每个数的值是多少,他只知道它的 M M M 个部分和的值。其中第 i i i 个部分和是下标 l i l_{i} li r i r_{i} ri 的部分和 ∑ j = l i r i = A l i + A l i + 1 + ⋯ + A r i \sum_{j=l_{i}}^{r_{i}}=A_{l_{i}}+A_{l_{i}+1}+\cdots+A_{r_{i}} j=liri=Ali+Ali+1++Ari, 值是 S i S_{i} Si

输入格式

第一行包含 3 个整数 N 、 M N 、 M NM Q Q Q。分别代表数组长度、已知的部分和数量 和询问的部分和数量。

接下来 M M M 行,每行包含 3 3 3 个整数 l i , r i , S i l_{i}, r_{i}, S_{i} li,ri,Si

接下来 Q Q Q 行,每行包含 2 2 2 个整数 l l l r r r,代表一个小蓝想知道的部分和。

输出格式

对于每个询问, 输出一行包含一个整数表示答案。如果答案无法确定, 输出 UNKNOWN

样例 #1

样例输入 #1

5 3 3
1 5 15
4 5 9
2 3 5
1 5
1 3
1 2

样例输出 #1

15
6
UNKNOWN

提示

对于 10 % 10 \% 10% 的评测用例, 1 ≤ N , M , Q ≤ 10 , − 100 ≤ S i ≤ 100 1 \leq N, M, Q \leq 10,-100 \leq S_{i} \leq 100 1N,M,Q10,100Si100

对于 20 % 20 \% 20% 的评测用例, 1 ≤ N , M , Q ≤ 20 , − 1000 ≤ S i ≤ 1000 1 \leq N, M, Q \leq 20,-1000 \leq S_{i} \leq 1000 1N,M,Q20,1000Si1000

对于 30 % 30 \% 30% 的评测用例, 1 ≤ N , M , Q ≤ 50 , − 10000 ≤ S i ≤ 10000 1 \leq N, M, Q \leq 50,-10000 \leq S_{i} \leq 10000 1N,M,Q50,10000Si10000

对于 40 % 40 \% 40% 的评测用例, 1 ≤ N , M , Q ≤ 1000 , − 1 0 6 ≤ S i ≤ 1 0 6 1 \leq N, M, Q \leq 1000,-10^{6} \leq S_{i} \leq 10^{6} 1N,M,Q1000,106Si106

对于 60 % 60 \% 60% 的评测用例, 1 ≤ N , M , Q ≤ 10000 , − 1 0 9 ≤ S i ≤ 1 0 9 1 \leq N, M, Q \leq 10000,-10^{9} \leq S_{i} \leq 10^{9} 1N,M,Q10000,109Si109

对于所有评测用例, 1 ≤ N , M , Q ≤ 1 0 5 , − 1 0 12 ≤ S i ≤ 1 0 12 , 1 ≤ l i ≤ r i ≤ N 1 \leq N, M, Q \leq 10^{5},-10^{12} \leq S_{i} \leq 10^{12}, 1 \leq l_{i} \leq r_{i} \leq N 1N,M,Q105,1012Si1012,1liriN, 1 ≤ l ≤ r ≤ N 1 \leq l \leq r \leq N 1lrN 。数据保证没有矛盾。

蓝桥杯 2022 省赛 A 组 J 题。


分析:

居然是一道图论建模题。。
对于一个部分和的关系,利用前缀和的思想,我们可以理解为是:
s [ r ] − s [ l − 1 ] = v s[r]-s[l-1]=v s[r]s[l1]=v
其实类比差分约束的思想就是让 l − 1 l-1 l1 r r r之间连一条长度为v的边
( l − 1 , r , v ) , ( r , l − 1 , − v ) (l-1,r,v),(r,l-1,-v) (l1,r,v),(r,l1,v)
建完边之后各个部分和之间的关系也就一目了然了
接下来我们只需要利用 D F S DFS DFS或者 B F S BFS BFS遍历这张图,用并查集将具有相同标准的前缀和放在一个块里(一个快里面的任何数都可以作为标准),在一个块里的任何两个数我们都能知道他们之间的部分和文章来源地址https://www.toymoban.com/news/detail-744346.html


Code

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e5+100;
int n,m,q;
int Hom[N],cnt = 0;
bool vi[N];
struct Node{
	int y,Next,v;
}e[2*N];
int Linkk[N] , len;
int s[N];
int fa[N];

void Insert(int x,int y,int v){
	e[++len] = (Node){y,Linkk[x],v};
	Linkk[x] = len;
}

int Getfa(int x){
	return fa[x] == x?x:fa[x] = Getfa(fa[x]);
}

void Dfs(int x,int vv){
	vi[x] = 1;
	s[x] = vv;
	for (int i = Linkk[x]; i; i = e[i].Next){
		int y = e[i].y;
		if (vi[y]) continue;
		fa[Getfa(y)] = Getfa(x);
		Dfs(y,vv+e[i].v);
	}
}

signed main(){
	scanf("%lld %lld %lld",&n,&m,&q);
	for (int i = 1,x,y,v; i <= m; i++)
	  cin>>x>>y>>v,Insert(x-1,y,v),Insert(y,x-1,-v);
	for (int i = 0; i <= n; i++) fa[i] = i;
	for (int i = 0; i <= n; i++)
	  if (!vi[i]) Dfs(i,0);
	for (int i = 1; i <= q; i++){
		int l,r;
		cin>>l>>r;
		if (Getfa(l-1)!=Getfa(r)) {cout<<"UNKNOWN"<<endl;continue;}
		printf("%lld\n",s[r]-s[l-1]);
	}
	return 0;
}

到了这里,关于[蓝桥杯 2022 省 A] 推导部分和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 十三届蓝桥杯JAVA B组国赛部分题解

    大学总共参加了三届蓝桥杯,这应该是我最后一次参加蓝桥杯了,再写一篇题解算是给自己的业余竞赛结个尾。我的题解肯定不是最好的,甚至有许多错误,能给大家提供下思路就行。 思路:模拟下时钟就行,签到题 答案:502-8=494(由于匀速运动,59分59秒到0分0秒实际算一次

    2024年02月08日
    浏览(50)
  • 洛谷2022SCP第一轮J组模拟题(LGR-2022-J1)部分题解

    LGR-2022-J1 T3. 小恺编写了如下函数,希望计算斐波那契数列 f(n) 第 n 项对 10000 取余数的值:

    2024年02月09日
    浏览(36)
  • 2022数学建模“五一杯”B题 题解+论文

    摘要 本文主要研究温度等因素对矿石加工质量控制问题。提高矿石加工质量,对节约不可再生资源和能源,推动节能减排,助力“双碳”’目标的实现,具有重要的意义。 针对问题一,我们要实现在给定系统温度和原矿参数的情况下,预测可能性最大的产品的指标。由于在

    2024年02月02日
    浏览(63)
  • 简洁而优美的结构 - 并查集 | 一文吃透 “带权并查集” 不同应用场景 | “手撕” 蓝桥杯A组J题 - 推导部分和

    💛前情提要💛 本章节是 每日一算法 的 并查集带权并查集 的相关知识~ 接下来我们即将进入一个全新的空间,对代码有一个全新的视角~ 以下的内容一定会让你对 数据结构与算法 有一个颠覆性的认识哦!!! ❗以下内容以 C++/java 的方式实现,对于 数据结构与算法 来说最

    2023年04月08日
    浏览(40)
  • 2022 第十四届蓝桥杯模拟赛第二期题目题解(比赛时使用方法)

    目录 第一题:最小的2022 第二题:经过天数 第三题:特殊的十六进制数 第四题:矩阵的最小路径 第五题:质数拆分 第六题:拷贝时间 第七题:单词去重 第八题:最短回文串 第九题:多少个X? 第十题:最小交换 问题描述 请找到一个大于 2022 的最小数,这个数转换成二进

    2023年04月11日
    浏览(71)
  • 2022 第十三届蓝桥杯大赛软件赛决赛, 国赛,C/C++ 大学B组题解

    2022 第十三届蓝桥杯大赛软件赛决赛, 国赛,C/C++ 大学B组题解 补题链接:地址 两个填空题说实话感觉非常花时间。 第1题 —— 2022 (5分) 题意:将2022拆成10个数相加,有多少方案。 思路:划分dp经典题,数字i划分成j个数。 答案:379187662194355221 第2题 —— 钟表 (5分) 题意

    2024年02月04日
    浏览(49)
  • 2022 第十三届蓝桥杯大赛软件赛省赛(第二场),C/C++ 大学B组题解

    2022 第十三届蓝桥杯大赛软件赛省赛(第二场),C/C++ 大学B组题解 补题链接:地址 第1题 —— 练习 (5分) 题意:过了样例交上去0分,问可能是ABC的哪一种 显然都是,答案:ABC 第2题 —— 三角回文数 (5分) 题意:求第一个大于某2e8的数的回文数,且满足他可以等于1+2+…

    2023年04月09日
    浏览(57)
  • 【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)

    目录 写在前面: 题目:92. 递归实现指数型枚举 - AcWing题库 读题: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 距离蓝桥杯已经不足一个月了, 根据江湖上的传言, 蓝桥杯最喜欢考的是深度优先搜索和

    2024年02月03日
    浏览(56)
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(4)

    目录 写在前面: 题目:P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤

    2023年04月08日
    浏览(46)
  • 【AcWing刷题】蓝桥杯专题突破-深度优先搜索-dfs(8)

    目录 写在前面: 题目:1114. 棋盘问题 - AcWing题库 题目描述: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤为重要, 所以,为了学好深度优先搜

    2023年04月09日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包