企业官网建设流程全解析

C 小月的长廊

树状数组板子题

#include <bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl "\n" typedef long long ll; const int N=600005; int n,p; int a[N]; int l[N],r[N]; int lowbit(int x) { return (x&(-x)); } void update(int x,int v){ while(x <= N-10){ a[x]+=v; x+=lowbit(x); } } int sum(int x){ int res=0; while(x>0){ res+=a[x]; x-=lowbit(x); } return res; } void solve() { cin>>n>>p; vector<int> all; for(int i=1;i<=n;i++){ cin>>l[i]>>r[i]; all.push_back(l[i]); all.push_back(r[i]); all.push_back(r[i]+1); } sort(all.begin(),all.end()); all.erase(unique(all.begin(),all.end()),all.end()); auto get=[&](int x){ return lower_bound(all.begin(),all.end(),x)-all.begin()+1; }; memset(a,0,sizeof a); for(int i=1;i<=n;i++){ int L=get(l[i]); int R=get(r[i]+1); update(L,1); update(R,-1); } int ans=0; for(int i=1;i<=n;i++){ int dl=sum(get(l[i])); int dr=sum(get(r[i])); if(abs(dl-dr)>=p )ans++; } cout<<ans; } int main() { IOS int T=1; while(T--) solve(); return 0; }

E 小月的时差

max型瓶颈最短路：

• 优先队列 Dijkstra：按当前瓶颈值从小到大取点；O((n+m)logn)

• 或者二分答案 + BFS/DFS 判断连通性；O((n+m)logV)

• 或者按点权排序后用并查集。O(m α(n) + n log n)

#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e5+5; int n,m,a,b,ss,tt; int s1[N],s2[N],val[N],dis[N]; vector<int>e[N]; void bfs1(int s){ for(int i=1;i<=n;i++) dis[i]=0; queue<int>q; q.push(s); s1[s]=0; dis[s]=1; while(!q.empty()){ int u=q.front(); q.pop(); for(auto v:e[u]){ if(!dis[v]){ dis[v]=1; s1[v]=s1[u]+1; q.push(v); } } } } void bfs2(int s){ for(int i=1;i<=n;i++) dis[i]=0; queue<int>q; q.push(s); s2[s]=0; dis[s]=1; while(!q.empty()){ int u=q.front(); q.pop(); for(auto v:e[u]){ if(!dis[v]){ dis[v]=1; s2[v]=s2[u]+1; q.push(v); } } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>a>>b>>ss>>tt; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; e[u].push_back(v); e[v].push_back(u); } bfs1(a); bfs2(b); for(int i=1;i<=n;i++){ val[i]=abs(s1[i]-s2[i]); dis[i]=1e9+7; } dis[ss]=val[ss]; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>pq; pq.push({dis[ss],ss}); while(!pq.empty()){ auto [d,u]=pq.top();pq.pop(); if(d!=dis[u])continue; for(int v:e[u]){ int nd=max(dis[u],val[v]); if(nd<dis[v]){ dis[v]=nd; pq.push({dis[v],v}); } } } cout<<dis[tt]; return 0; }

F 小月的订单

前后缀DP合并