1 条题解
-
0
超级吧巧妙的解法(当然不是本蒟蒻想出来的)
思路
注意到,如果两个弦相交,必然他们的两端是交错分布的(有点废话),那如何判断呢?
如果说从号点开始,维护一个栈,每次访问一个点,如果说他是一条弦编号小的点,就入栈,如果说他是编号大的点,就先看目前栈顶的点是不是他的另一半,若不是,则输出,若是,则弹出栈顶。
为什么可以这样子呢?一个点,要想在访问之后的点时依旧可以在栈中,必然不能访问过他的另一半,不然他就出栈了。那既然在访问一个点的时候栈顶是另一个点,就说明他的另一半还未访问过,就可以说这两条弦相交。
AC代码
#include<bits/stdc++.h> using namespace std; const int N=4e5+10; int pos[N],n; int main() { scanf("%d",&n); n*=2; for(int i=1,x,y;i<=n/2;i++) { scanf("%d%d",&x,&y); if(x>y)swap(x,y); pos[x]=i; pos[y]=-i; } stack<int>Q; for(int i=1;i<=n;i++) { if(pos[i]>0)Q.push(pos[i]); else { if(Q.top()!=-pos[i]) { puts("Yes"); return 0; } Q.pop(); } } puts("No"); return 0; }
- 1
信息
- ID
- 8245
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 9
- 标签
- 递交数
- 32
- 已通过
- 4
- 上传者