Description

Input

Output

Sample Input

4 4
1 2 1 10
2 4 3 5
1 3 1 5
2 4 2 7

Sample Output

6
2 3 4 5 6 7

Solution

• 這題一眼望去有些難，特別是超級大的“泡泡怪”數量令人無從下手。

• 不過只需稍微思考，就很容易發現其答案一定是連續的一段，因為通過的也是一段。

• 而且進一步思考可以發現左右端點也會與蟲洞限制重合，不然就會有擴展的更優解。

• 于是考慮在 M 個蟲洞中枚舉其左右限制，共 O(M2) ，再 O(N) 掃一遍判斷是否可行。

• 但這樣總時間復雜度就達到了 O(N?M2) ，無法通過本題。

• 所以我們可以先將那 M 個蟲洞按 R （右端點）從小到大排一次序，二分查找即可。

• 這樣的總時間復雜度就是 O(N?MlogM) ，AC本題。

Code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1001,M=N*6; struct data {int x,y; }a[N*3],ans; int n,m,tot; int first[N],next[M],en[M],w1[M],w2[M]; bool pd; bool bz[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void write(int x) {if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0'); } inline bool cmp(data x,data y) {return x.y<y.y; } inline void insert(int x,int y,int l,int r) {next[++tot]=first[x];first[x]=tot;en[tot]=y;w1[tot]=l,w2[tot]=r; } inline void dfs(int x,int l,int r) {if(pd) return;if(x==n){ans.x=l,ans.y=r;pd=true;return;}for(int i=first[x];i;i=next[i])if(!bz[en[i]] && w1[i]<=l && r<=w2[i]){bz[en[i]]=true;dfs(en[i],l,r);} } int main() {n=read(),m=read();for(int i=1;i<=m;i++){int x=read(),y=read(),l=read(),r=read();a[i].x=l,a[i].y=r;insert(x,y,l,r);insert(y,x,l,r);}sort(a+1,a+1+m,cmp);for(int i=ans.x=1;i<=m;i++){int l=1,r=m;while(l<=r){int mid=(l+r)>>1;if(a[i].x<=a[mid].y){if(a[mid].y-a[i].x<ans.y-ans.x){l=mid+1;continue;}if(a[mid].y-a[i].x==ans.y-ans.x && a[i].x>=ans.x){l=mid+1;continue;}memset(bz,false,sizeof(bz));pd=false;dfs(bz[1]=1,a[i].x,a[mid].y);if(pd) l=mid+1; else r=mid-1;}else l=mid+1;}}write(ans.y-ans.x+1),putchar('\n');for(int i=ans.x;i<=ans.y;i++) write(i),putchar(' ');return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5177. 【NOIP2017提高组模拟6.28】TRAVEL的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。