1. 2030: [蓝桥杯2022初赛] 推导部分和
传送门:http://oj.ecustacm.cn/problem.php?id=2030
1.1. 题意
对于数列,已知部分区间和,询问若干次区间和。
1.2. Tag
并查集、搜索
1.3. 难度
☆☆☆☆
1.4. 思路
对于已知的区间的和为,用前缀和表示,根据差分约束建图准则,相当于点到点长度为,到长度为。
建好图之后,每次询问一个区间的和,相当于询问的值。
首先要保证和在同一个连通块中,其次每个连通块只需要随便一个点初始化为,然后按照边长扩展即可。这是由于等号,不管怎么走,相对差值是不变的。
代码中和均可以。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
inline T read(T& x) {
x = 0;
T w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x = x * w;
}
const int maxn = 1e5 + 10;
const ll INF = -1e13;
int n, m, q;
struct edge{
int v; ll w;
edge(){}
edge(int v, ll w):v(v), w(w){}
};
vector<edge>Map[maxn];
ll sum[maxn];
bool vis[maxn];
void dfs(int u, ll d){
vis[u] = 1;
sum[u] = d;
///cout<<u<<" "<<d<<endl;
for(auto x : Map[u])
{
int v = x.v; ll w = x.w;
if(vis[v])continue;
dfs(v, d + w);
}
}
queue<pair<int,ll> >Q;
void bfs(int u, ll d){
vis[u] = 1;
sum[u] = d;
Q.push(make_pair(u, d));
while(!Q.empty())
{
auto now = Q.front();
Q.pop();
int u = now.first; ll d = now.second;
for(auto x : Map[u])
{
int v = x.v; ll w = x.w;
if(vis[v])continue;
vis[v] = 1;
sum[v] = d + w;
Q.push(make_pair(v, d + w));
}
}
}
int f[maxn];
int Find(int x){
return x == f[x] ? x : f[x] = Find(f[x]);
}
int main(){
read(n);read(m);read(q);
for(int i = 0; i <= n; i++)f[i] = i;
for(int i = 1; i <= m; i++)
{
int l, r; ll s;
read(l);read(r);read(s);
///cout<<l<<" "<<r<<" "<<s<<endl;
///sum[r] - sum[l - 1] = s
Map[l - 1].push_back(edge(r, s));
Map[r].push_back(edge(l - 1, -s));
f[Find(l - 1)] = Find(r);
}
for(int i = 0; i <= n; i++)if(!vis[i])
bfs(i, 0);
while(q--)
{
int l, r;
read(l), read(r);
--l;
if(Find(l) != Find(r))puts("UNKNOWN");
else printf("%lld\n", sum[r] - sum[l]);
}
return 0;
}