2020牛客NOIP（第二场）D

暴力做法

在网格图上，以(x , y) 代表在y时刻，在第x个位置 那么很显然，你把关闭的闸门在图上表示出来就可以了 复杂度$O(n\ast max(C))$

正解做法

发现暴力做法的瓶颈在于$max(C)$上，考虑怎么搞掉

于是大胆的猜想，跟缝有没有关系

我们可以用跑最短路的思想来处理 对于两个相邻的缝 ，能否到达对方（非常容易判断，不再赘述） 那么直接按照堆优化的disjkra跑一下就可以了 复杂度$O(m\ast logm)$

#include<bits/stdc++.h> #define MAXN 200005 typedef long long ll; using namespace std; int n,m; ll ans,tot,vis[MAXN],f[MAXN]; struct node{ll dx,L,R,val,id;}t[MAXN]; struct node2{ll id,val;}; vector<node>ycl[MAXN]; vector<int>ycl2[MAXN]; bool cmp(node x , node y){return x.L < y.L;} bool cmp2(node x , node y){ if(x.R == y.R){ if(x.L == y.L)return x.dx < y.dx; return x.L < y.L; } return x.R < y.R; } bool operator < (node2 x , node2 y){return x.val > y.val;} priority_queue<node2>q2; int main(){ cin>>n>>m;ll a,b,c;ans = 0x3f3f3f3f3f3f; for(int i = 1 ; i <= m ; i++){ cin>>a>>b>>c; ycl[a].push_back((node){a , b , c , 0 , 0}); } for(int i = 1 ; i <= n ; i++)sort(ycl[i].begin() , ycl[i].end() , cmp); ll last = 0 , zz; for(int i = 1 ; i <= n + 1 ; i++){ zz = ycl[i].size(); if(zz == 0){ tot++ , t[tot].dx = i; t[tot].L = 0 , t[tot].R = 0x3f3f3f3f3f3f; continue; } last = 0; for(int j = 0 ; j < zz ; j++){ tot++ , t[tot].dx = i; t[tot].L = last , t[tot].R = ycl[i][j].L - 1; last = ycl[i][j].R + 1; } tot++ , t[tot].dx = i; t[tot].L = last , t[tot].R = 0x3f3f3f3f3f3f; } memset(f , 0x3f , sizeof(f)); sort(t + 1 , t + 1 + tot , cmp2); t[0].L = 0 , t[0].R = 0x3f3f3f3f3f3f , t[0].dx = 0 , t[0].val = f[0] = 0; tot++ , t[tot].L = 0 , t[tot].R = 0x3f3f3f3f , t[tot].dx = n + 1 , t[tot].val = f[tot] = 0x3f3f3f3f3f3f; for(int i = 0 ; i <= tot ; i++)ycl2[t[i].dx].push_back(i); q2.push((node2){0 , 0}); node2 now;ll zz2,pp; while(!q2.empty()){ now = q2.top();q2.pop(); if(vis[now.id])continue; vis[now.id] = 1; if(t[now.id].dx > 0){ zz2 = ycl2[t[now.id].dx - 1].size(); for(int i = 0 ; i < zz2 ; i++){ pp = ycl2[t[now.id].dx - 1][i]; if(abs(t[now.id].dx - t[pp].dx) != 1)continue; if(t[now.id].L + 1 > t[pp].R)continue; if(t[now.id].R + 1 < t[pp].L)continue; if(now.val + 1 > t[pp].R)continue; zz = max(f[now.id] + 1 , t[pp].L); if(zz >= f[pp])continue; f[pp] = zz; q2.push((node2){pp , f[pp]}); } } if(t[now.id].dx < n + 1){ zz2 = ycl2[t[now.id].dx + 1].size(); for(int i = 0 ; i < zz2 ; i++){ pp = ycl2[t[now.id].dx + 1][i]; if(abs(t[now.id].dx - t[pp].dx) != 1)continue; if(t[now.id].L + 1 > t[pp].R)continue; if(t[now.id].R + 1 < t[pp].L)continue; if(now.val + 1 > t[pp].R)continue; zz = max(f[now.id] + 1 , t[pp].L); if(zz >= f[pp])continue; f[pp] = zz; q2.push((node2){pp , f[pp]}); } } } if(f[tot] >= 0x3f3f3f3f3f)cout<<-1<<endl; else cout<<f[tot]<<endl; }