注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

nand bzoj 2728(hnoi 2012)  

2013-02-09 16:37:40|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

首先要发现,nand操作不是一般的神奇耶

它能够模拟出 not and or xor这四个基础的位运算!

比如not吧 not a不就等于 a nand a吗?

and 也能模拟 似乎 a and b = not (a nand b),既然这样的话 a and b =(a nand b) nand (a nand b )吧?

or 啊 ,xor 啊,都可以模拟的

换句话说,只要这n个数可以通过各种什么and or xor not之类的鬼东西搞出来就可以搞出来了

我们发现什么东西不能搞出来呢?

如果a1(2)=110,a2(2)=000。那么无论你怎么搞,得到的数的第一二位必然相同,这很显然吧。

也就是说每个数写成一排,这n排k列的01矩阵中,如果有两列完全相同,那么得到的数的这两位也一定相同。

work(l,r)=work(1,r)-work(1,l-1)应该大家第一眼就想到了吧

问题转化为,在1~n中求有多少个k位01数。这k位分成若干集合,同一集合内每一位数必须相同。

一般的文章到此打止了,因为大神不屑于讲如何求了。

可是我不会……我只好继续翻博客……

我终于在某大神博客里找到了方法……

维护s[i]表示i+1到k中有多少组在1~i中未出现的集合

对于第i位,分这么几种情况:

①如果第i位未定:

     一、若原数此位为1,我们ans+=2^s[i]并将此位定为1

     二、若原数此位为0,我们将此位定为0

②如果第i位已定(通过在前面的同一集合的数确定)

    一、若原数此位为0,我们这位为1,直接结束。因为接下来不可能有解了

    二、若原数此位位1,我们这位为0,我们累加2^s[i]并直接结束。因为接下来的解必然被统计过了

由于会漏掉n,所以check一下n

说几点注意事项

2^i如果用1<<i算要写成1LL<<i

n可能大于2^k,所以加个if

有个数据不合法,l=0

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 1010
#define MAXK 70
using namespace std;
typedef long long LL;
int next[MAXK],p[MAXN][MAXK],digit[MAXK],s[MAXK],n,k;
LL L,R;
int get(LL a,int b){  return a>>b&1;  }
void read()
{
    scanf("%d %d %lld %lld",&n,&k,&L,&R);
    for(int i=1;i<=n;i++)
    {
        LL d;
        scanf("%lld",&d);
        for(int j=1;j<=k;j++)
            p[i][j]=get(d,k-j);
    }
    for(int i=1;i<=k;i++)
        for(int j=i-1;j>=1;j--)
        {
            bool mark=true;
            for(int r=1;r<=n&&mark;r++)
                if(p[r][i]!=p[r][j])
                    mark=false;
            if(mark)
            {
                next[i]=j;
                break;
            }
        }
    int num=0,from[MAXK];
    bool use[MAXK];
    for(int i=1;i<=k;i++)
    {
        from[i]=next[i]?from[next[i]]:++num;
        use[from[i]]=true;
    }
    for(int i=1;i<=k;i++)
    {
        if(use[from[i]])  num--;
        use[from[i]]=false,s[i]=num;
    }
}
bool check(LL n)
{
    for(int i=1;i<=k;i++)
        if(next[i]&&get(n,k-i)!=get(n,k-next[i]))
            return false;
    return true;
}
LL work(LL n)
{
    if(n<0)  return 0;
    if(n>(1LL<<k)-1)  n=(1LL<<k)-1;
    LL ans=check(n);
    for(int i=1;i<=k;i++)
    {
        digit[i]=0;
        int x=get(n,k-i);
        if(next[i])  digit[i]=digit[next[i]];
        if(next[i]==0&&x==1)  ans=ans+(1LL<<s[i]),digit[i]=1;
        if(next[i]==0&&x==0)  digit[i]=0;
        if(next[i]&&digit[i]==0&&x==1)  return ans+(1LL<<s[i]);
        if(next[i]&&digit[i]==1&&x==0)  return ans;
    }
    return ans;
}
int main()
{
    read();
    printf("%lld\n",work(R)-work(L-1));
    return 0;
}

 
  评论这张
 
阅读(336)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017