Hdu4876zcc love cards (multi check questions)

Hello everyone , I meet you again , I'm the king of the whole stack .

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

Problem Description

ZCC loves playing cards. He has n magical cards and each has a number on it. He wants to choose k cards and place them around in any order to form a circle. He can choose any several consecutive cards the number of which is m(1<=m<=k) to play a magic. The magic is simple that ZCC can get a number x=a1⊕a2…⊕am, which ai means the number on the ith card he chooses. He can play the magic infinite times, but once he begin to play the magic, he can’t change anything in the card circle including the order. ZCC has a lucky number L. ZCC want to obtain the number L~R by using one card circle. And if he can get other numbers which aren’t in the range [L,R], it doesn’t matter. Help him to find the maximal R.

Input

The input contains several test cases.The first line in each case contains three integers n, k and L(k≤n≤20,1≤k≤6,1≤L≤100). The next line contains n numbers means the numbers on the n cards. The ith number a[i] satisfies 1≤a[i]≤100. You can assume that all the test case generated randomly.

Output

For each test case, output the maximal number R. And if L can’t be obtained, output 0.

Sample Input

    4 3 1
2 3 4 5

Copy

Sample Output

    7


    
     
      
      Hint 
      ⊕ means xor 

Copy

Author

Zhenhai middle school

Source

2014 Multi-University Training Contest 2

The question ： to n Number . Choose from k Number , this k The number can be arranged randomly , Once the order is set, it cannot be changed , In this definite order . elect m（m<=k） The value obtained by the number XOR x, All in this order x Find a maximum value of R, Among these numbers, there is a continuous range 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++)// Enumerate the XOR values of consecutive segments of a definite sequence 
        {
            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++)// Find this maximum R, Make these numbers exist L~R The number of ranges exists .
        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()// Relax the conditions （ Random order ） infer 
{
    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);
    }
}

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116456.html Link to the original text ：https://javaforall.cn