T2挺良心,想法和写法都比较容易实现。
题目链接:
https://www.luogu.com.cn/problem/P7076
题目大意:
存在编号为0~2^k-1种小动物,现在有m条饲养指南,每一条饲养要求为:若动物园里养了某种小动物的编号的二进制上pj位为1,则需要购买编号为qj的饲料。
饲料一共有c种。
现在给出n种动物园已经饲养的动物,请你计算需要购买的饲料,对于买过来的饲料,可能存在某些饲料可以养更多其他的动物(当前动物园还没有),请计算在不多购买饲料的情况下,有多少种新动物可以养。
0<=k<=64,n,m<=10^6,c<=10^8
思路:
先将已有的动物编号进行二进制转化,然后将已有的二进制位标记下来。
对于输入的pj和qj,我们可以把某一位需要哪些饲料全部记录下来。可以采用连边的方式记录。
接着我们枚举0 ~ k的二进制位,然后把需要哪些饲料标记一下。这里由于饲料的种类c<=10^8,但实际上只有10^6个指南,因此我们可以对饲料离散化一下。然后我们开一个10^6的数组就可以实现标记了。
最后我们再枚举一下0~k的二进制位,看看哪些位可以不增加饲料,然后标记为1。
最后我们可以统计出可以1的位数cnt,那么总答案就是(1<<cnt)-n。
总复杂度为O(k*m)
坑点:n=0,k=64的时候,答案为2^64,超过了unsigned longlong 范围,需要特判。
代码:
#include<bits/stdc++.h> using namespace std; inline long long read() { long long x=0,y=1;char c=getchar();//y代表正负(1.-1),最后乘上x就可以了。 while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}//如果c是负号就把y赋为-1 while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*y;//乘起来输出 } int n,m,c,k; int a[100],si[1000040]; int b[1000050]; int tot,head[1000400]; struct edge{ int to,next; }e[1000040]; void add(int a,int b){ tot++; e[tot].to=b; e[tot].next=head[a]; head[a]=tot; } struct node{ int p,q; }pi[1000040]; bool cmp(node a,node b){ return a.q<b.q; } void init(){ tot=0; memset(head,-1,sizeof(head)); } int main() { init(); cin>>n>>m>>c>>k; for(int i=1;i<=n;i++){ long long x; x=read(); int t=0; while(x){ if(x%2)a[t]=1; x/=2; t++; } } for(int i=1;i<=m;i++){ int x,y; x=read();y=read(); //快读加一下,不然会超时 pi[i].p=x;pi[i].q=y; } sort(pi+1,pi+1+m,cmp); for(int i=1;i<=m;i++)b[i]=pi[i].q; for(int i=1;i<=m;i++)pi[i].q=lower_bound(b+1,b+1+m,b[i])-b; //离散化 for(int i=1;i<=m;i++)add(pi[i].p,pi[i].q); //位-饲料连边 for(int i=0;i<k;i++){ int flag=0; if(a[i]){ for(int j=head[i];~j;j=e[j].next){ int y=e[j].to; si[y]=1; //标记必须买的饲料 } } } for(int i=0;i<k;i++){ int flag=0; if(!a[i]){ //枚举可能的位置 for(int j=head[i];~j;j=e[j].next){ int y=e[j].to; if(si[y]==0){ flag=1;break; } } if(flag==0)a[i]=1; } } int cnt=0; for(int i=0;i<k;i++){ if(a[i])cnt++; } if(cnt==64&&n==0)cout<<"18446744073709551616"<<endl; else cout<<(1ll<<cnt)-n<<endl; return 0; }