前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU4876ZCC loves cards(多校题)

HDU4876ZCC loves cards(多校题)

作者头像
全栈程序员站长
发布2022-07-07 18:01:22
1710
发布2022-07-07 18:01:22
举报

大家好,又见面了,我是全栈君。

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

代码语言:javascript
复制
    4 3 1
2 3 4 5

Sample Output

代码语言:javascript
复制
    7


    
     
      
      Hint 
      ⊕ means xor 

Author

镇海中学

Source

2014 Multi-University Training Contest 2

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

代码语言:javascript
复制
#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);
    }
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116456.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年1月2,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • ZCC loves cards
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档