洛谷 U85587 视频录制

洛谷传送门

题目背景
在开学典礼上，大佬云集的高一 · 66班要拍摄一个宣传班级风貌的视频。技术大佬chz同学和iamrjjiamrjj提出要用航拍拍班级队形。但是在排队形的时候，高一 · 66班同学站的一团糟......

题目描述
负责组织站队的SeawaySeaway很生气，他灵机一动，想出了一个绝妙的主意：需要站队的场地是一条直线，站队的时候，每队人（人数不等）会站满从xx到yy的区间。SeawaySeaway组织同学们站队，最后留出的空位置如果能被66整除，就是一个”Good Queue“，否则就是一个”Bad Queue“.

现在给你场地的长度和每队人需要站的区间，请你编程确定这个队列是一个”Good Queue“还是一个”Bad Queue“。

输入格式
多组数据。

输入文件的第一行包括一个整数TT，表示数据组数。

每组数据的第一行有两个整数N，M,表示场地的长度和队列的数量。

接下来的MM行，每行两个整数X_i,Y_iX
i
? ,Y
i
? 表示第ii个队伍所在的区间（不保证区间无重合）。

输出格式
对于每组数据，输出只包括一行，为”Good Queue“或者”Bad Queue“。

输入输出样例
输入 #1 复制
7 1
1 1
输出 #1 复制
Good Queue
说明/提示
数据范围：

1\le N \le 10^41≤N≤10
4
，1\le M \le 1001≤M≤100。

题解：

这道题改编自“校园外的树”还是很简单的。思路也是模拟，用标记数组，每次站队直接从左端点到右端点枚举，全部打上标记。最后统计还有哪些没有打标记就可以。

这里的一个考点是多组数据。出多组数据主要是为了防止有人骗分（无论输入什么我就输出Good Queue，一切听天由命）。那么碰到多组数据的题我们应该如何处理呢？

读入\(T\),然后使用while(t--)循环，在循环中进行操作即可。

这样看，多组数据还是很简单。但是，这里还是有一个坑点。

我们所有使用的变量和数组，必须在再次使用之前清成0，要不然会导致很严重的后果。

当然，这题的数据范围给的很良心，因为使用暴力枚举的朴素模拟算法的时间复杂度是\(O(N^2)\)的。如果这题的数据范围是\(10^5\)呢？有兴趣的同学可以课下研究讨论，或者自行到网上查阅相关知识。

代码：(很抱歉这里的标程是线段树版本的)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
const int maxn=1e4+10;
int n,m,tree[maxn<<3];
void build(int pos,int l,int r)
{
    int mid=(l+r)>>1;
    tree[pos]=r-l+1;
    if(l==r)
        return;
    build(lson,l,mid);
    build(rson,mid+1,r);
}
void update(int pos,int l,int r,int x,int y)
{
    int mid=(l+r)>>1;
    if(tree[pos]==0)
        return;
    if(x<=l && r<=y)
    {
        tree[pos]=0;
        return;
    }
    if(y<=mid)
        update(lson,l,mid,x,y);
    else if(x>mid)
        update(rson,mid+1,r,x,y);
    else
    {
        update(lson,l,mid,x,y);
        update(rson,mid+1,r,x,y);
    }
    tree[pos]=tree[lson]+tree[rson];
}
int main()
{
    //freopen("#2.in","r",stdin);
    //freopen("#2.out","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(tree,0,sizeof(tree));
        scanf("%d%d",&n,&m);
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            int x,y;
            if(x>y)
                swap(x,y);
            scanf("%d%d",&x,&y);
            update(1,1,n,x,y);
        }
        if(tree[1]%6==0)
        {
            printf("Good Queue\n");
            continue;
        }
        else
        {
            printf("Bad Queue\n");
            continue;
        }
    }
    return 0;
}

洛谷 U85587 视频录制

原文：https://www.cnblogs.com/fusiwei/p/11430828.html