ZOJ5593:Let's Chat（双指针）

传送门

题意

给出x个a区间和y个b区间，询问a和b交区间的子区间长度为m的个数

分析

类似于双指针，具体见代码

trick

代码

#include <bits/stdc++.h>

using namespace std;

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

struct node

{

    int l,r;

}a[101],b[101];

int t,n,m,x,y;

int loca,locb;

int ans;

int main()

{

    for(scanf("%d",&t);t--;)

    {

        scanf("%d %d %d %d",&n,&m,&x,&y);

        for(int i=1;i<=x;++i) scanf("%d %d",&a[i].l,&a[i].r);

        for(int i=1;i<=y;++i) scanf("%d %d",&b[i].l,&b[i].r);

        ans=0;locb=1;

        for(int i=1;i<=x;++i)

        {

            if(locb>y) break;

            if(a[i].r<b[locb].l) continue;

            while(a[i].l>b[locb].r) locb++;

            while(locb<=y&&b[locb].l<=a[i].r)

            {

                int rr=min(b[locb].r,a[i].r),ll=max(b[locb].l,a[i].l);

                if(rr-ll+1>=m) ans+=(rr-ll+2-m);

                if(b[locb].l>=a[i].l&&b[locb].r>=a[i].r) break;

                if(b[locb].l<=a[i].l&&b[locb].r<=a[i].r) {locb++;continue;}

                if(b[locb].l>=a[i].l&&b[locb].r<=a[i].r) {locb++;continue;}

                if(b[locb].l<=a[i].l&&b[locb].r>=a[i].r) break;

                locb++;

            }

        }

        printf("%d\n",ans);

    }

    return 0;

}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>;

using namespace std;

struct  points

{

	int l,r;

};

vector <points> a,b;

int main()

{

	int cases,n,m,x,y,i,j,s;

	points now;

	bool flag;

	int m1,m2;

    scanf("%d",&cases);

    while (cases--)

    {

    	scanf("%d%d%d%d",&n,&m,&x,&y);

    	a.clear(); b.clear();

    	for (i=1;i<=x;i++)

    	{

    		scanf("%d%d",&now.l,&now.r);

    		if (now.r-now.l+1>=m)

    		{

    			a.push_back(now);

    		}

    	}

    	for (i=1;i<=y;i++)

    	{

    		scanf("%d%d",&now.l,&now.r);

    		if (now.r-now.l+1>=m)

    		{

    			b.push_back(now);

    		}

    	}

    	if (a.size()==0 || b.size()==0) printf("0\n");

    	else

    	{

    		m1=0; m2=0; flag=true; s=0;

    		while (m1<a.size() && m2<b.size())

    		{

    			while (flag && a[m1].r<b[m2].l )

    			{

    				m1++;

    				if (m1==a.size()) {flag=false; break;}

    			}

    			while (flag && b[m2].r<a[m1].l )

    			{

    				m2++;

    				if (m2==b.size()) {flag=false; break;}

    			}

    			if (flag)

    			{

    				x=max(a[m1].l,b[m2].l);

    				y=min(a[m1].r,b[m2].r);

    				if (y-x+1>=m) s+=(y-x+1-m+1);

    				if (a[m1].r<b[m2].r) m1++;

    					else if (a[m1].r>b[m2].r) m2++;

    						else {m1++; m2++; }

    			}

    		}

    		printf("%d\n",s);

    	}

    }

    return 0;

}

巴特西

ZOJ5593:Let's Chat（双指针）

传送门

题意

分析

trick

代码

最新文章

热门文章