ZCC loves cards

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2362 Accepted Submission(s): 590

   
   

    
    4 3 1
2 3 4 5
   
   

   
   

    
    7


    
    
 
     
 
      Hint 
     
 ⊕ means xor 
    
    
     
   
   

题意：给n个数。从中选出k个数，这k个数能够随意排列，一旦定了顺序就不能改变，在这个确定的顺序。选出m（m<=k）个数异或得到的值x,在这个顺序得到的全部x的值中找出一个最大值R，这些数中使得存在一个连续的范围L~R。

#include<stdio.h>
#include<string.h>
int n,k,L,ans[25];
int a[13],aa[13],R,flag[150];
int vist[10];
void find(int tk)
{
    if(tk==k-1)
    {
        memset(flag,0,sizeof(flag));
        for(int i=0;i<k-1;i++)
        a[i+k]=a[i];
        int maxa=0;
        for(int i=0;i<k;i++)//枚举一个确定序列的连续片断的异或值
        {
            int x=a[i]; flag[x]=1; if(maxa<x)maxa=x;
            for(int j=i+1;j-i+1<=k;j++)
            {
                x^=a[j]; flag[x]=1;if(maxa<x)maxa=x;
            }
        }
        int r=0;
        for(int i=L;i<=maxa;i++)//找出这个最大值R,使得这些数存在L~R范围的数都存在。
        if(flag[i]==0)break;
        else r=i;
        if(r>R)R=r;
        return ;
    }
    tk++;
    for(int i=0;i<k;i++)
    if(vist[i]==0)
    {
        a[tk]=aa[i]; vist[i]=1; find(tk); vist[i]=0;
    }
}
bool panduan()//放宽条件（随意顺序）推断
{
    memset(flag,0,sizeof(flag));
    int maxa=0;
    for(int i=1;i<(1<<k);i++)
    {
        int x=0;
        for(int j=0;(1<<j)<=i;j++)
        if((1<<j)&i)x^=aa[j];
        flag[x]=1;
        if(maxa<x)maxa=x;
    }
    int r=0;
    for(int i=L;i<=maxa;i++)
    if(flag[i]==0)break;
    else r=i;
    return r>R;
}
void CNM(int tk,int i)
{
    if(tk==k-1)
    {
        if(panduan())
        find(-1);
        return ;
    }
    tk++;
    for(int j=i+1;j<n;j++)
    {
        aa[tk]=ans[j]; CNM(tk,j);
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&k,&L)>0)
    {
        R=0; memset(vist,0,sizeof(vist));
        for(int i=0;i<n;i++)
        scanf("%d",&ans[i]);
        CNM(-1,-1);
        printf("%d\n",R);
    }
}