COGS 1453. [USACO NOV]空牛栏

2021年09月15日 阅读数:3
这篇文章主要向大家介绍COGS 1453. [USACO NOV]空牛栏,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

★★   输入文件:empty.in   输出文件:empty.out   简单对比
时间限制:1 s   内存限制:64 MBgit

【题目描述】

 

    FJ建的新牛棚里有N(2<=N<=3,000,000)个栏位,这N个栏位围成了一个巨大的环形,N个栏位编号依次为0~N-1,其中0号栏位与N-1号栏位相邻。ide

    到了晚上,FJ的牛会陆续返回牛棚。在每头牛内心都有一个他们最钟意的栏位,然而,若是某头牛最钟意的栏位已经被别的牛抢先占领了,他会从该栏位开始按顺序依次查看后面的栏位,直到找到第一个未被占领的栏位为止,他将占领这个栏位。若是他查看到了N-1号栏位仍未找到空位,他将从0号栏位开始继续找下去。spa

    给定每头牛所钟意的栏位号,请计算:当全部牛都回栏后,未被占领的牛栏中编号最小的那个。请注意本题的答案跟牛返回牛棚的顺序无关。指针

    为避免大量读入数据的问题,输入数据只有K(1<=K<=10,000)行,每行的格式为:X Y A Bcode

    其中指定了X*Y头牛最钟意的栏位,即每X头牛依次钟意的栏位为f(1)~f(Y),其中f(i)=(A*i+B) mod N;A,B均在0到1,000,000,000之间。内存

         切记标准内存限制为64MB。get

 

【输入格式】

 

第1行:两个空格隔开的整数N,K;it

 第2~K+1行:每行包含四个整数X,Y,A,B,含义如上所述。牛的总数不超过N-1,可能有若干行数据都涉及到相同的栏位。io

 

【输出格式】

一行,即求未被占领的栏位中编号最小者。class

【样例输入】

10 3
3 2 2 4
2 1 0 1
1 1 1 7

输入解释:共有10个栏位,编号为0~9;第2行数据显示有3头牛钟意6((2*1+4)mod 10=6)号栏位,另外3头牛钟意8((2*2+4)mod 10=8)号栏位;第3行数据显示有2头牛钟意1((0*1+1)mod 10=1)号栏位;第4行数据显示有1头牛钟意8((1*1+7)mod 10=8)号栏位(共有4头牛钟意这个栏位)。

【样例输出】

5

输出解释: 除了5号栏位,其它栏位均被占领。          

【提示】

在此键入。

【来源】

USACO 2013 November Contest, Gold

 

模拟 

nextt指针表示i下一个没有牛的牛棚

龟速AC 

#include <cctype>
#include <cstdio>
#include <vector>
#include <ctime>
#define N 5000005

using namespace std;
typedef long long LL;
inline void read(LL &x)
{
    register char ch=getchar();
    for(x=0;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);x=x*10+ch-'0',ch=getchar());
}
bool zl[N];
LL msc(LL a,LL b,LL Mod)
{
    LL ret=0,base=a;
    for(;b;b>>=1,base=(base<<1)%Mod)
     if(b&1) ret=(ret+base)%Mod;
    return ret;
}
LL n,k,x,y,a,b,nextt[N];
int main(int argc,char *argv[])
{
    freopen("empty.in","r",stdin);
    freopen("empty.out","w",stdout);
    read(n);
    read(k);
    for(int i=0;i<n;++i) nextt[i]=i+1;
    nextt[n-1]=0;
    for(LL i=1;i<=k;++i)
    {
        read(x);read(y);read(a);read(b);
        for(LL j=1;j<=y;++j)
        {
            LL f=(msc(a,j,n)+b%n)%n;
            for(LL k=1;k<=x;++k)
            {
                LL v=f,vv=v;
                while(zl[vv]) vv=nextt[vv];
                zl[vv]=true;
                nextt[v]=nextt[vv];
            }
        }
    }
    for(LL i=0;i<n;i=nextt[i]) 
    if(!zl[i]) {printf("%lld\n",i);return 0;}
    return 0;
}

 

咱们都在命运之湖上荡舟划桨,波浪起伏着而咱们没法逃脱孤航。可是假使咱们迷失了方向,波浪将指引咱们穿越另外一天的曙光。