竞赛讨论区 > 牛客暑假多校第二场J-farm<随机的非随机解法>
头像
波塞冬(寂寞如雪版)
编辑于 2018-07-25 01:38
+ 关注

牛客暑假多校第二场J-farm<随机的非随机解法>

一、题意

White Rabbit has a rectangular farmland of n*m. In each of the grid there is a kind of plant. The plant in the j-th column of the i-th row belongs the a[i][j]-th type.
White Cloud wants to help White Rabbit fertilize plants, but the i-th plant can only adapt to the i-th fertilizer. If the j-th fertilizer is applied to the i-th plant (i!=j), the plant will immediately die.
Now White Cloud plans to apply fertilizers T times. In the i-th plan, White Cloud will use k[i]-th fertilizer to fertilize all the plants in a rectangle [x1[i]...x2[i]][y1[i]...y2[i]].
White rabbits wants to know how many plants would eventually die if they were to be fertilized according to the expected schedule of White Cloud.
简单的说就是,给定一个大型矩形,矩形中每个格子对应一个单独的数字。之后K个命令给,要求大矩阵中某些子矩形的各个元素的赋予统一值,求在命令结束后还保持原有值的个数。其中矩阵的格子总数不超过1e6,但是不指定长宽。

二、解题思路

要求使用一种数据结构进行批量染色操作,且要求后面可以检测是否被"其他颜色污染"。

看了题解很容易想到,使用某种数据结构做批量增加的操作,之后检测增加后的值是否能够整除原来的元素。

考虑如果直接按照1、2、3、4进行赋值就会有:同样是染色2次,有3+3 = 6和2+2+2 = 6,无法有效判断整除。考虑加一个操作:增加染色次数的判定,但是同样也会有3+3 = 6 = 2+4的问题,因此对数组进行重新设计,则直觉告诉我们,1,2,4,7,......an,an+n这个数列可以完美解决这个问题——不存在第2种组合可以使用相同数目的数列元素相加得到数列的某个其他元素。

因此,使用一位数组开足够大的数组之后,动态的按照二维数组的方式进行寻址,即可完成上述操作。<然鹅大佬指出这个数列还是有缺陷,44 = 37+7 = 22 + 22,于是这玩意过题本质上还是随机>


复制代码
#include<bits/stdc++.h> using namespace std; #define ll intmax_t const int MAXN=4000233;

ll mapp[MAXN];
ll farm[MAXN];
ll times[MAXN];
ll color[MAXN]; int maxx_numebr = 1 ; int add_number = 1 ; int m,n,k; void insert_mex(ll *v,int a,int b,ll key)
{
    a+=2;
    b+=2; while(a<n+3)
    { int num = a*(m+3); int pos = b; while(pos<m+3)
        {
            v[num+pos] += key;
            pos+= pos&(-pos);
        }a+=a&(-a);

    }
}
ll find_mex(ll *v,int a,int b)
{
    a+=2;
    b+=2;
    ll cntt = 0; while(a)
    { int num = a*(m+3); int pos = b; while(pos)
        {
            cntt += v[num+pos];
            pos -= pos&(-pos);
        }
        a-=a&(-a);
    } return cntt;
} void insert(ll *v,int a,int b,int c,int d,ll key)
{ // cout<<"coor :"<<a<<" "<<b<<endl; // cout<<"coor :"<<a<<" "<<d<<endl; // cout<<"coor :"<<c<<" "<<b<<endl; // cout<<"coor :"<<c<<" "<<d<<endl;  insert_mex(v,a,b,key);
    insert_mex(v,c,d,key);
    insert_mex(v,a,d,-key);
    insert_mex(v,c,b,-key);
}

ll find(ll *v,int a,int b)
{
    ll cntt = 0;
    cntt += find_mex(v,a,b); return cntt;
} void init()
{
    memset(color,-1,sizeof(color)); for(int i=0;i<n;++i)
    { int pos = i*m; for(int j=0;j<m;++j)
        { // int ppos = pos +j; scanf("%d",&mapp[pos]); if(color[pos] == -1)color[mapp[pos]] = (maxx_numebr += (add_number++));
            pos++;
        }
    } for(int i=0;i<k;++i)
    { int a,b,c,d,kk;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&kk); if(color[kk] == -1)color[kk] = (maxx_numebr += add_number++ );
        ll key = color[kk];
        a--;b--;
        insert(farm,a,b,c,d,key);
        insert(times,a,b,c,d,1);
    } int cntt = n*m; int pos = 0; for(int i=0;i<n;++i)
    { for(int j=0;j<m;++j)
        { // int pos = i*(m+23)+j; ll kk = color[mapp[pos]]; int time_now = find(times,i,j);
            ll res = find(farm,i,j); // cout<<"check: "<<i<<" "<<j<<" times: "<<time_now<<" color "<<mapp[pos]<<endl; if(time_now == 0 || res == time_now*kk)cntt--;
            pos++;
        }
    }
    cout<<cntt<<endl;


} int main()
{
    cin>>n>>m>>k;
    init(); return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐