c - HackerEarth 上的错误答案

Question

问题链接::http://www.hackerearth.com/the-big-bang-challenge/algorithm/subset-and-4/

问题是给你一个数字 Z 和一些 n 整数。您必须找出是否存在 n 个整数的子集并且(按位运算符)Z 给出零，如果存在则打印"is"，否则打印“否”。

我知道一个简单的方法就是对所有输入的 n 个数字和 Z 进行 AND，看看它是否给出零。但是当我第一次看到这个问题时，我无法意识到这一点。我实际上为此感到非常愚蠢。

这是我在阅读问题时首先编写的代码::

#include <stdio.h>

int main()
{
    int t;
    int n;
    long int z;
    int i,j,x;
    long int a[1000];
    int b[30];
    int count,count2;
    int flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%ld %d",&z,&n);
        count=0;
        for(i=0;i<n;i++)
            scanf("%ld",&a[i]);

        for(i=0;i<30;i++)
            b[i]=-1;
        j=0;
        for(i=0;i<25;i++)
        {
            if(z&1==1)
            {
                b[j++]=i;
                count++;
            }
            z=z>>1;
        }

        flag=0;
        count2=0;
        for(i=0;i<n;i++)
        {

            for(j=0;j<count;j++)
            {
                x=a[i];
                if(b[j]!=-1)
                {
                    x=x>>b[j];
                //    printf("New x=%d\nx&1=%d\n",x,x&1);
                    x==x&1;
                    if(x==0)
                    {
                        count2++;
                        b[j]=-1;
                    }
                  //  printf("Count2=%d and Count1=%d\n",count2,count);

                }

            }
            if(count2>=count)
                {
                    flag=1;
                    break;
                }

        }
        if(flag==0)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}

我的代码实际上打算做什么？？

在我的代码中，我检查了整数 Z 的二进制表示并计算数字中出现的 1 的数量，并将 1 的位置记录在单独的数组 b[30] 中。我将所有 n 整数存储在数组 a[1000] 中，并检查所有整数是否有 0 位置我存储在 b[30] 中，如果其中任何一个存储了，那么我将 b[30] 位置标记为已标记，这样我就不会在前面的数字中再次检查该位位置一个[1000]。如果我发现我存储在 b[30] 中的所有位置都是零，那么我打印 yes，否则我打印 No。

我知道与我应该做的相比，这是一个非常困惑和糟糕的算法。但是，请帮助大家。我的代码在提交时给出了错误的答案。

例如:Z=5，则Z的二进制为1001，即第0位和第3位为1。因此，在数组 b[30] 中，我将位为 1 的位置存储在 Z 中。像这里一样，我将 0 存储在 b[0](对于第一个Z 中的有效位)，然后将 3 存储在 b[1](用于下一个有效位)，我这样做 20 位(根据我的需要)，如果任何位为 1，那么我将其位置存储在 b[j++] 中。

然后，我开始将我存储在 a[1000] 中的所有元素一个一个地存储到 x 中，然后从我之前处理过的 b[30] 数组中取 1 个位置，将x右移那么多位置，并检查最右边的位是否为1。例如，我的a[1000]数组有2个元素，3和1。3是0011，我将3存储在x中，取b[0]然后执行 x>>b[0]，在本例中与 0011 相同(因为 b[0] 为 0)。然后我通过执行 x&1 检查最右边的位，它返回 1，因此该位不为零，所以我前进到 b[1]，它是 3，然后我执行 x>>b[ 1]，它给出 0000，然后我检查 x&1，它给我零。所以，现在我知道我在数组中有一个数字的第 3 位为零，所以我将 b[1] 标记为 -1，这样我就不会再次检查它以获得 a[1000] 中的下一个整数。然后我取 1 这是 a[1000] 的第二个元素，然后执行与上面相同的步骤，我发现我在 a[1000] 中没有第 0 位为零的元素.因此，我没有在 Z 为 1 的位置具有零位的元素。因此，AND 永远不会为零，所以我打印 No。

问题陈述::(如HackerEarth)

You are given a number Z and a set S with N elements. Your job is to find a sub set of S such that the AND of the given number and this subset is zero. If this sub set is possible print "Yes" otherwise print "No"

Input First line contains number of test case T. Each test case contains two lines , first line contains two numbers Z and N , where Z is given number and N is size of set S . Second line contains N elements of the subset S.

Output For each test case print Yes if the subset is possible else print No .

Constraints: 1<=T<=100 1<=N<=1000 0<=Ai<=Z<=1000000

示例输入3个10 22 010 31 1 15 31 5 3

示例输出是的是的否

我的代码给出了示例输入的正确答案，但在 HackerEarth 提交中失败。请大家帮忙..提前感谢您的帮助.. :)

Answer 1

你的想法也不错，但是你把它复杂化了一点。你能想一想如何更简化它吗(做的事情比你描述的要少，但保持相同的总体思路)？继续阅读了解方法。

And I store all the n integers in the array a[1000]

您不需要存储它们:您只会使用它们中的每一个一次，所以不要费心存储它们。只需依次阅读和处理每一个。

and check all the integers if any of them have a 0 at the positions that I stored in b[30] and if any of them does then I mark that b[30] position as marked, so that I do not check for that bit position again

无需标记或为不再检查而烦恼。你怎样才能更容易地做到这一点？只需为您在 i 位置的数字中找到的每个零递减每个 b[i]。然后，如果 b 仅包含数字 <= 0，您将打印 yes。

现在，我们已经删除了您想要做的两件事，同时保留了您的想法。这很好，因为如果我们少做一些工作，我们做错事的机会就会减少。

我意识到这并不能回答您的代码有什么问题。我的观点是，通过更多地思考您的想法，您可以编写更好的代码，这最有可能起作用。在这种情况下，您会摆脱很多不必要的包袱，减少犯错的机会。

至于你的代码到底哪里错了，有很多东西，但最重要的是这个:

    for(i=0;i<n;i++)
    {

        for(j=0;j<count;j++)
        {
            x=a[i]; <= you are setting x for each j. 
                       You probably want this a level up, in the other loop?
            if(b[j]!=-1) <= don't need this the way I described it.
            {
                x=x>>b[j]; <= b[j] has no bearing on how much you shift x by. 
                              You probably meant x = x>>j? 
                              But wait, that's wrong too, because we're in a loop, 
                              so we'll shift by too much! Maybe x = x>>1?
            //    printf("New x=%d\nx&1=%d\n",x,x&1);
                x==x&1; <= this doesn't do anything. Why? 
                           What is the difference between == and =?
                           Do you want to use =, or move this in the if below?
                if(x==0)
                {
                    count2++;
                    b[j]=-1;
                }
              //  printf("Count2=%d and Count1=%d\n",count2,count);

            }
        }
        if(count2>=count)
        {
            flag=1;
            break;
        }
    }

我推荐一个编程教程，比如这个:http://www.cprogramming.com/tutorial/c-tutorial.html以及该网站上的其他人，让您在尝试解决比赛问题之前开始。