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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

USACO奶牛异或题解  

2014-02-27 19:44:30|  分类: usaco |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
在奋斗了将近两个星期,终于把USACO4-6版刷光,前3版以前就A了,相当有成就感,当刷完最后一版。
最后一题让我印象十分,所以放在前面讲。
6.1.3:奶牛异或:今天和GYZ携手刷到了第6版,这是最后一题,一开始我们都很无语,不会做。耀峰随口说的字母树给了我们一丝启示,但还是没有办法,最多也只想到了前缀和,但还是需要N^2的枚举起点和终点,而n的范围直接萎了。耐不住了,点了题解。。才看了一行,我们发现了一个重要的定理:若A XOR B=C,则A,B,C,任意两个XOR都可以都到另一个。我们立刻有了思路,我开始试着写思考了。
写着写着:便发现了可以利用前缀和+这个定理。于是我开始试着证明,(GYZ在旁边看着):
首先,设B[I]是读入的附加值,用A[I]存前缀和,则(A[1]=B[1]),A[I]=A[I-1] XOR B[I](N>=i>=2)。
而我们假设要求B[3]*B[4]*B[5],
因为A[2] XOR B[3]=A[3],则可以根据定理得到:B[3]=A[2] XOR A[3];
同理A[3] XOR B[4]=A[4],得B[4]=A[3] XOR A[4];
                                                 B[5]=A[4] XOR A[5];
则原来要求的可以转换为:A[2] XOR A[3] XOR A[3] XOR A[4] XOR  A[4] XOR A[5]=A[2] XOR A[5];
那么原来的N^2枚举即可转换为N*log2N,甚至更低。因为我们可以用N的时间枚举起点,再运用字母树查找最大的(最优的一定是从高位到低位不同的终点),只需找这么一个,所以可以用字母树处理前缀,若S[I]=1,则找字母树0的方向,反之也如此。而找到的A[Z]和A[I]所形成的便是B[I+1]到B[Z]的这段XOR值,取最大即可。不过算法是想出来了,写写还是超麻烦要处理顺序输出,我交了3次才A..下面是代码:
#include<cstdio>
using namespace std;
int k,n,j,zz,z,t,i,v,ans,ans2,ans3,a[100001],b[100001];
int left[1000000],right[1000000],lu[1000000];int s[200];
void sear(int w,int c)
 {
 if (c>21) return;
 if (s[c]==1) 
                    {
         if (left[w]!=0){//1所对是0,XOR才能最大,依次从高到低
                    z=lu[left[w]];
                    sear(left[w],c+1);
                           }
                    else {
                         z=lu[right[w]];
                         sear(right[w],c+1);
                         }//若不存在匹配的,只能再往1走下去;
                    }
     else {
          if (right[w]!=0)
                          {
                          z=lu[right[w]];
                          sear(right[w],c+1);
                          }
               else {
                    z=lu[left[w]];
                    sear(left[w],c+1);
                    }
          }
 }
void build(int w,int c)
 {
  if (c>21) return;
  if (!s[c]){
         if (!left[w]){ 
          zz++;left[w]=zz;lu[zz]=i;//路径记录等会是那个Z
          build(zz,c+1);
                      }
            else  build(left[w],c+1);//左边所对应的为0,右边为1;
            }
   else  {
         if (!right[w]){
        zz++;right[w]=zz;lu[zz]=i;
         build(zz,c+1);
                       }
        else build(right[w],c+1);
        }
 }
int main()
{
 freopen("cowxor.in","r",stdin);
 freopen("cowxor.out","w",stdout);
 scanf("%d",&n);
 for (i=1;i<=n;i++)
  scanf("%d",&b[i]);
a[1]=b[1];
for (i=2;i<=n;i++)
  a[i]=a[i-1]^b[i];//前缀和处理
for (i=1;i<=n;i++)
 {
 t=22; v=a[i];
 while (v>0){
 k=v%2;t--;s[t]=k;
 v=v>>1;
            }//将A[I]转成2进制
 for (j=1;j<=t-1;j++)
        s[j]=0;
 build(0,1);//构造字母树
 }
ans=-1;

for (i=n;i>=1;i--)//倒着、顺着其实无所谓
  {
    t=22; v=a[i];z=0;
 while (v>0){
 k=v%2;t--;s[t]=k;
 v=v>>1;
            }
 for (j=1;j<=t-1;j++)
        s[j]=0;
 if (ans<=b[i]) {
ans=b[i];ans2=i;ans3=i;
}//一个为顶点,一定是《=
   sear(0,1);//找能和A[I]匹配的最优解Z
 if (z<i+1) continue;//起点终点不相反
 int u=a[i]^a[z];
 if (u>ans)
                 {
                 ans=u;
                 ans2=i+1;ans3=z;continue;
                 }//分别按照题目排序
 if ((u==ans)&&(ans3>z))
                   {
                   ans=u;
                   ans2=i+1;ans3=z;continue;
                   }
if ((u==ans)&&(ans3==z)&&(ans3-ans2>z-(i+1)))
                   {
                     ans=u;
                      ans2=i+1;ans3=z;continue;
                   }
  }
printf("%d %d %d\n",ans,ans2,ans3);
return 0;
}


  评论这张
 
阅读(76144)| 评论(14)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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