HDU 5995 Kblack loves flag ---BestCoder Round #90

题目链接

用两个布尔数组分别维护每个行/列是否被插过旗帜，最后枚举每一行、列统计答案即可。空间复杂度O(n+m)，时间复杂度O(n+m+k)。

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

int t,ansx[],ansy[],ax,ay;

const int _K=,_B=,_P=;

int _X;

inline int get_rand(int _l,int _r){

    _X=((long long)_K*_X+_B)%_P;

    return _X%(_r-_l+)+_l;

}

int n,m,k,seed;

int x[],y[];

void Init(){

    scanf("%d%d%d%d",&n,&m,&k,&seed);

    _X=seed;

    for (int i=;i<=k;++i)

        x[i]=get_rand(,n),

        y[i]=get_rand(,m);

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        Init();

        memset(ansx,,sizeof(ansx));

        memset(ansy,,sizeof(ansy));

        ax=;ay=;

        for(int i=;i<=k;i++)

        {

            ansx[x[i]]=;

            ansy[y[i]]=;

        }

        for(int i=;i<=n;i++)

        if(!ansx[i]) ax++;

        for(int i=;i<=m;i++)

        if(!ansy[i]) ay++;

        printf("%d %d\n",ax,ay);

    }

    return ;

}