1 条题解

  • 0
    @ 2026-6-4 17:07:34

    超级吧巧妙的解法(当然不是本蒟蒻想出来的)

    思路

    注意到,如果两个弦相交,必然他们的两端是交错分布的(有点废话),那如何判断呢?

    如果说从11号点开始,维护一个栈,每次访问一个点,如果说他是一条弦编号小的点,就入栈,如果说他是编号大的点,就先看目前栈顶的点是不是他的另一半,若不是,则输出YesYes,若是,则弹出栈顶。

    为什么可以这样子呢?一个点,要想在访问之后的点时依旧可以在栈中,必然不能访问过他的另一半,不然他就出栈了。那既然在访问一个点的时候栈顶是另一个点,就说明他的另一半还未访问过,就可以说这两条弦相交。

    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
    上传者