2 条题解
-
0
求最小值,即求最长路。设 s[i]为区间[0,i]被选中的数的个数,区间[a b]至少选2个数可以转化为:s[ b ] -s[a-1]>=2 -> s[a-1]+2 <= s[ b ] -> G[a-1].push_back({b, 2}), s[i]-s[i-1]<=1 -> s[i] -1 <=s[i-1] -> G[i].push_back({i-1, -1}), s[i]-s[i-1]>=0 -> s[i-1] <=s[i] -> G[i-1].push_back({i, 0}),
#include <bits/stdc++.h> using namespace std; const int N=1e4+10; vector<pair<int,int>> G[N]; int st,ed,d[N],dd[N];bool v[N]; int spfa() { memset(d,0,sizeof(d)); memset(dd,0,sizeof(dd)); memset(v,0,sizeof(v)); deque<int> Q; for(int i=st;i<=ed;i++) Q.push_front(i),v[i]=1; d[st]=0; while(!Q.empty()) { int x=Q.front();Q.pop_front();v[x]=0; for(auto i:G[x]) { int y=i.first,w=i.second; if(d[y]<d[x]+w) { d[y]=d[x]+w;if(x==y){return -1;}//判断负自环 dd[y]=dd[x]+1;if(dd[y]>(ed-st+1)){return -1;} if(v[y]==0) Q.push_front(y),v[y]=1; } } } return d[ed]-d[st]; } int main() { int n;scanf("%d",&n); ed=0,st=N; for(int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y);x++,y++; G[x-1].push_back({y,2}); ed=max(ed,y); st=min(st,x-1); } for(int i=st+1;i<=ed;i++) { G[i].push_back({i-1,-1}); G[i-1].push_back({i,0}); } printf("%d\n",spfa()); return 0; } -
0
/* 求最小值,即求最长路。 设 s[i]为区间[0,i]被选中的数的个数, 区间[a b]至少选2个数可以转化为:s[ b ] -s[a-1]>=2 -> s[a-1]+2 <= s[ b ] -> G[a-1].push_back({b, 2}), s[i]-s[i-1]<=1 -> s[i] -1 <=s[i-1] -> G[i].push_back({i-1, -1}), s[i]-s[i-1]>=0 -> s[i-1] <=s[i] -> G[i-1].push_back({i, 0}), */ #include<bits/stdc++.h> using namespace std; const int N=1e4+10; vector< pair<int,int> >G[N]; int st,ed,d[N],dd[N];bool v[N]; int spfa() { memset(d,0,sizeof(d)); memset(dd,0,sizeof(dd)); memset(v,0,sizeof(v)); deque<int>Q; for(int i=st;i<=ed;i++)Q.push_front(i),v[i]=1; d[st]=0; while(!Q.empty()) { int x=Q.front();Q.pop_front();v[x]=0; for(auto i:G[x]) { int y=i.first,w=i.second; if(d[y]<d[x]+w) { d[y]=d[x]+w;if(x==y){return -1;}//判断负自环 dd[y]=dd[x]+1;if(dd[y]>(ed-st+1)){return -1;} if(v[y]==0) Q.push_front(y),v[y]=1; } } } return d[ed]-d[st]; } int main() { int n;scanf("%d",&n); ed=0,st=N; for(int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y);x++,y++; G[x-1].push_back({y,2}); ed=max(ed,y); st=min(st,x-1); } for(int i=st+1;i<=ed;i++) { G[i].push_back({i-1,-1}); G[i-1].push_back({i,0}); } printf("%d\n",spfa()); return 0; }
- 1
信息
- ID
- 703
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 38
- 已通过
- 10
- 上传者