阳江做网站seo,邢台市路桥建设总公司网站,南川网站建设,电子商务网店毕业设计[蓝桥杯 2022 省 A] 推导部分和
题目描述
对于一个长度为 N N N 的整数数列 A 1 , A 2 , ⋯ A N A_{1}, A_{2}, \cdots A_{N} A1,A2,⋯AN#xff0c;小蓝想知道下标 l l l 到 r r r 的部分和 ∑ i l r A i A l A l 1 ⋯ A r \sum\limits_{il}^{r}A_iA_{l}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_{il}^{r}A_iA_{l}A_{l1}\cdotsA_{r} il∑rAiAlAl1⋯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_{jl_{i}}^{r_{i}}A_{l_{i}}A_{l_{i}1}\cdotsA_{r_{i}} ∑jliriAliAli1⋯Ari, 值是 S i S_{i} Si 。
输入格式
第一行包含 3 个整数 N 、 M N 、 M N、M 和 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 1≤N,M,Q≤10,−100≤Si≤100 。
对于 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 1≤N,M,Q≤20,−1000≤Si≤1000 。
对于 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 1≤N,M,Q≤50,−10000≤Si≤10000 。
对于 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} 1≤N,M,Q≤1000,−106≤Si≤106 。
对于 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} 1≤N,M,Q≤10000,−109≤Si≤109 。
对于所有评测用例, 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 1≤N,M,Q≤105,−1012≤Si≤1012,1≤li≤ri≤N, 1 ≤ l ≤ r ≤ N 1 \leq l \leq r \leq N 1≤l≤r≤N 。数据保证没有矛盾。
蓝桥杯 2022 省赛 A 组 J 题。 分析
居然是一道图论建模题。。 对于一个部分和的关系利用前缀和的思想我们可以理解为是 s [ r ] − s [ l − 1 ] v s[r]-s[l-1]v s[r]−s[l−1]v 其实类比差分约束的思想就是让 l − 1 l-1 l−1到 r r r之间连一条长度为v的边 ( l − 1 , r , v ) , ( r , l − 1 , − v ) (l-1,r,v),(r,l-1,-v) (l−1,r,v),(r,l−1,−v) 建完边之后各个部分和之间的关系也就一目了然了 接下来我们只需要利用 D F S DFS DFS或者 B F S BFS BFS遍历这张图用并查集将具有相同标准的前缀和放在一个块里一个快里面的任何数都可以作为标准在一个块里的任何两个数我们都能知道他们之间的部分和 Code
#includebits/stdc.h
using namespace std;#define int long longconst int N 2e5100;
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,vve[i].v);}
}signed main(){scanf(%lld %lld %lld,n,m,q);for (int i 1,x,y,v; i m; i)cinxyv,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;cinlr;if (Getfa(l-1)!Getfa(r)) {coutUNKNOWNendl;continue;}printf(%lld\n,s[r]-s[l-1]);}return 0;
}
