题解 P3090 【[USACO13NOV]Empty Stalls G】

小柯

2020-07-27 09:16:22

Solution

题意:有 $n$ 头牛,每头牛有一个喜欢的位置 $like_i$ ,在为每头牛分配了 $like_i$ 以后第一个未被占用的位置(包括该位置),若不存在,则选择第一个未被占用的位置以后,第一个被剩下的位置。 分析: 若当前位置前有 $x$ 个位置未被占用,那么分两种情况: >1.当前位置未被占用:则占用该位置。 >2.当前位置已被占用:则占用第 $x+1$ 个未被占用的位置,若不存在第 $x+1$ 个,则占用第一个未被占用的位置。 对于第一种情况,直接由数组维护每个位置的占用情况即可。 对于第二种情况,如果把所有位置看做一个序列,已被占用的为 $0$,未被占用的为 $1$,则问题可以转化: >求 $x$ -> 求该序列的前缀和 $sum_x$。 >求第 $x+1$ 个未被占用的位置 -> 求第一个前缀和 $sum_i$ 为 $x+1$ 的位置 $i$。 很显然,这些操作就是单点修改,区间查询,查询排名,可以用权值树状数组、权值线段树、平衡树等数据结构维护。(可以用树状数组的话,当然不可能用其他的啊qwq,但是注意树状数组下标不支持 $0$,需要下标手动加一) 综上,时间复杂度为 $O(n$ $logn)$,~~勉强能卡过~~。 $code:$ ```cpp #include<iostream> #include<cstdio> #define maxn 3000005 #define lowbit(x) (x&-x) using namespace std; int n,k,cnt; int t[maxn]; int lg[maxn]; int used[maxn]; int like[maxn]; long long x,y,a,b; inline void add(int pos,int val){ for(;pos<=n;pos+=lowbit(pos))t[pos]+=val; } inline int sum(int pos){ int ans=0; for(;pos;pos-=lowbit(pos))ans+=t[pos]; return ans; } inline int qry(int rank){ int ans=0,pos=0,nxt_pos; for(int step=lg[n];~step;step--){ nxt_pos=pos+(1<<step); if(nxt_pos<=n&&ans+t[nxt_pos]<rank)ans+=t[pos=nxt_pos]; } return pos+1; } int main(){ scanf("%d%d",&n,&k); for(int line=1;line<=k;line++){ scanf("%lld%lld%lld%lld",&x,&y,&a,&b); for(int i=1;i<=y;i++){ for(int j=1;j<=x;j++){ like[++cnt]=(a*i+b)%n; } } } //for(int i=1;i<=cnt;i++)printf("%d ",like[i]);printf("/n"); ++n; for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1; for(int i=1;i<=n;i++)add(i,1); for(int i=1;i<=cnt;i++){ ++like[i]; if(!used[like[i]])x=like[i]; else if((x=qry(sum(like[i])+1))==n)x=qry(1); //printf("%d ",x); used[x]=1,add(x,-1); } //printf("\n"); printf("%d",qry(1)-1); return 0; } ```