P12348 [蓝桥杯 2025 省 A 第二场] 交互

· · 题解

我们班的首 A，写篇 Tj 纪念一下，这题我认为建虚点应该是过不了的，毕竟时间复杂度是 O((n + m)((r-l+1)m))，也就是 2.9\times10^{10}，居然过了，一点都不卡，所以我也不想优化了。

思路

我们观察一下式子 \min_{l\le x\le r}a_x - \max_{p \le y \le q} a_y\ge ans，想必大家一定是看完了标签吧，差分约束，感觉如果你刚学就不会来做这题，如果你学过，那你就一眼秒了，我们可以发现这是一个板子，区间与区间连边，经典的线段树优化建图，如果你想认真学习线段树优化建图的话就去看别的题解吧，我不会讲，也可以说是我太菜了，不想写。

这里发现如果 \min_{l\le x\le r}a_x - \max_{p \le y \le q} a_y\ge ans，那么 [l ,r] 中的所有数都比 [p ,q] 中的数大 ans 以上，我们可以每次连边建一个虚点 d，设其值为 k，则 \forall l\le x\le r \cap p\le y\le q,k - a_x \le -ans \cap a_y - k\le 0，也就是 add(x ,d ,-ans),add(k ,y ,0)，我们可以直接暴力枚举 x ,y，然后将虚点直接建到原序列后面，跑一遍 SPFA，求最短路，此时的 dist 就是 a 的值，没有什么细节我就直接放代码了，硬要说就是判负环时最大更新数其实是 n + m - 1。

代码

链式前向星实现

链式前向星实现，最慢的点是 1.90ms，代码如下

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0 ,f = 1;
    char ch = getchar();
    while('0' > ch || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch & 15);
        ch = getchar();
    }
    return x * f;
}
const int N = 5e4 + 5;
int n ,m;
bool flag[N];
queue<int>que;
int dist[N] ,cnt[N] ,head[4 * N] ,cntt;
struct edge {
    int to;
    int next;
    int dis;
}edge[4 * N];
inline void add(int x ,int y ,int z) {
    edge[++ cntt].to = y;
    edge[cntt].dis = z;
    edge[cntt].next = head[x];
    head[x] = cntt;
  return ;
}
void Spfa() {
  memset(dist ,0x3f ,sizeof dist);
    memset(flag ,0 ,sizeof flag);
  memset(cnt ,0 ,sizeof cnt);
    for(int i = 1;i <= n + m;++ i)
        add(0 ,i ,0);
    while(!que.empty())que.pop();
    que.push(0);
    dist[0] = 0;
    while(!que.empty()){
        int u = que.front();
        flag[u] = 0;
        que.pop();
   for(int xt = head[u];xt;xt = edge[xt].next) {
      pair<int ,int> i = make_pair(edge[xt].to ,edge[xt].dis);
            if(dist[i.first] > dist[u] + i.second) {
                dist[i.first] = dist[u] + i.second;
        cnt[i.first] = cnt[u] + 1;
        if(cnt[i.first] >= n + m) {
          cout << "No Solution";
          return ;
        }
                if(!flag[i.first]) {
                    flag[i.first] = true;
                    que.push(i.first);
                }
            }
        }
    }
  int answer = LLONG_MAX ,maxx = LLONG_MIN ,minn = LLONG_MAX;
    for(int i = 1;i <= m;++ i) {
    maxx = max(maxx ,dist[i]);
    minn = min(minn ,dist[n + i]);
  }
  cout << maxx - minn;
    return ;
}
signed main() {
  m = read() ,n = read();
  for(int i = 1 ,u ,v ,l ,r ,w;i <= m;++ i) {
    u = read() ,v = read() ,l = read() ,r = read() ,w = read();
    for(int j =  u;j <= v;++ j) add(j ,n + i ,-w);
    for(int j =  l;j <= r;++ j) add(n + i ,j ,0);
  }
  Spfa();
  return 0;
}

邻接表实现

邻接表实现，最慢的点 1.09ms，代码如下。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0 ,f = 1;
    char ch = getchar();
    while('0' > ch || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch & 15);
        ch = getchar();
    }
    return x * f;
}
const int N = 5e4 + 5;
int n ,m;
bool flag[N];
queue<int>que;
int dist[N] ,cnt[N];
vector<pair<int ,int> >vt[2 * N];
void Spfa() {
  memset(dist ,0x3f ,sizeof dist);
    memset(flag ,0 ,sizeof flag);
  memset(cnt ,0 ,sizeof cnt);
    for(int i = 1;i <= n + m;++ i)
        vt[0].push_back(make_pair(i ,0));
    while(!que.empty())que.pop();
    que.push(0);
    dist[0] = 0;
    while(!que.empty()){
        int u = que.front();
        flag[u] = 0;
        que.pop();
        for(auto i: vt[u]) {
            if(dist[i.first] > dist[u] + i.second) {
                dist[i.first] = dist[u] + i.second;
        cnt[i.first] = cnt[u] + 1;
        if(cnt[i.first] >= n + m + 1) {
          cout << "No Solution";
          return ;
        }
                if(!flag[i.first]) {
                    flag[i.first] = true;
                    que.push(i.first);
                }
            }
        }
    }
  int answer = LLONG_MAX ,maxx = LLONG_MIN ,minn = LLONG_MAX;
    for(int i = 1;i <= n;++ i) {
    maxx = max(maxx ,dist[i]);
    minn = min(minn ,dist[i]);
  }
  cout << maxx - minn;
    return ;
}
signed main() {
  m = read() ,n = read();
  for(int i = 1 ,u ,v ,l ,r ,w;i <= m;++ i) {
    u = read() ,v = read() ,l = read() ,r = read() ,w = read();
    for(int j =  u;j <= v;++ j) vt[j].push_back(make_pair(n + i ,-w));
    for(int j =  l;j <= r;++ j) vt[n + i].push_back(make_pair(j ,0));
  }
  Spfa();
  return 0;
}