V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
sdushn
V2EX  ›  程序员

请教一个算法题-是否存在所有元素异或结果为 0 的子数组

  •  
  •   sdushn · 2018-09-27 22:30:58 +08:00 · 2274 次点击
    这是一个创建于 2008 天前的主题,其中的信息可能已经有所发展或是发生改变。
    • 给定一个 int 型的 M 和 N,其中 M 小于等于 340,N 小于等于 50000 ;
    • 给出一个 int[N]数组,数组中每个数都小于 2 的 M 次方;
    • 问题:是否存在一个子数组,使得子数组中所有元素异或后的结果为 0 ?存在输出 yes,不存在输出 no。要求子数组元素之和大于 0。
    • 例子:M=7,N=5,int[] input = {0, 1, 2, 3, 5};存在子序列{1, 2, 3},1 ^ 2 ^ 3 = 0,所以输出 yes。
      M=7,N=5,int[] input = {0, 1, 3, 5, 9};不存在这样的子序列,输出 no。
    • 我的思路:最初结题的思路是迭代求最小异或值(排除 0 元素),但是发现和数组的顺序是相关的,后面想到,如果都写成二进制,排成 N 行 M 列的矩阵,如果某一列相加的值为 1,证明只有一个元素在该位为 1,是绝对不会出现在最终的子序列中的,这样可以排除掉一部分,如果出现例如{5, 7, 4, 3}这样的数据就不知道该怎么样做比较好了。
    • 拓展:如果问题升级,输出存在几个这样的子序列,又该怎么解呢?
    13 条回复    2018-09-28 00:06:05 +08:00
    sdushn
        1
    sdushn  
    OP
       2018-09-27 22:32:24 +08:00
    想看看大家的思路和想法,无需给出解题代码,我也继续想想
    ejq
        2
    ejq  
       2018-09-27 22:35:03 +08:00   ❤️ 1
    异或前缀和
    sdushn
        3
    sdushn  
    OP
       2018-09-27 22:38:54 +08:00
    暴力解的话,应该要计算 2 的 N 次方吧,每个数都有 2 种可能性,题目给的 N 比较大,M 比较小,应该不能用暴力解
    ejq
        4
    ejq  
       2018-09-27 22:52:42 +08:00
    @sdushn 欸,这里的子数组的意思是 sub sequence 么……
    高斯消元
    ejq
        5
    ejq  
       2018-09-27 22:58:08 +08:00
    二进制异或意义下的高斯消元,原数组看成一个 N*M 的矩阵

    如果矩阵的秩没到 N,那么就是 YES

    =》 所以如果 N > M 直接 YES ?
    sdushn
        6
    sdushn  
    OP
       2018-09-27 22:59:45 +08:00
    @ejq {0, 1, 2, 3, 5}的异或前缀和是{0, 1, 3, 0, 5},但是如果改变顺序{0, 1, 5, 2, 3},异或前缀和就变成了{0, 1, 5, 2, 3},这样该如何判断呢,我的理解如果是异或和为零的连续子段的话用这个方法是可行的,但是这里的字段不一定连续,似乎不太适用
    zsh1995
        7
    zsh1995  
       2018-09-27 22:59:55 +08:00
    今天搜狗的题?
    ejq
        8
    ejq  
       2018-09-27 23:00:12 +08:00
    计数的话,答案就是 2^(N-R) - 1 (N >= R)

    R 是矩阵的秩
    sdushn
        9
    sdushn  
    OP
       2018-09-27 23:06:58 +08:00
    @ejq 如果是{9,8,1}这样的可能就不符合 N>M,但是也是 YES, {0, 1, 3, 5, 9}这个例子其实 M 可以是 4,这样就是 N>M 输出 no 了。 不过我感觉确实应该用矩阵去解啊,矩阵知识忘差不多了,补一下去
    sdushn
        10
    sdushn  
    OP
       2018-09-27 23:17:50 +08:00
    @ejq {0, 1, 3, 5, 9}这个的秩是不是 4 啊,好像应该把 0 元素排除掉,如果秩小于行数,那就 yes,等于就 no 了
    sdushn
        11
    sdushn  
    OP
       2018-09-27 23:22:06 +08:00
    @ejq 想明白了,这个问题确实应该用矩阵来解,多谢多谢
    CDEGAE
        12
    CDEGAE  
       2018-09-27 23:52:58 +08:00   ❤️ 1
    动态规划可解,复杂度 O(N*M),解法可以参见这道题: http://codeforces.com/contest/1053/problem/B,不过 2 的 M 次方超过了 int 的范围,应该要当成字符串去处理。
    sdushn
        13
    sdushn  
    OP
       2018-09-28 00:06:05 +08:00
    @CDEGAE 最开始我也想用动态规划的,没太想明白怎么规划,今天有些晚了,明天研究,多谢啦
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5479 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 08:22 · PVG 16:22 · LAX 01:22 · JFK 04:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.