BZOJ-2115-Xor-WC2011

叙述性说明

BZOJ-2115-Xor-WC2011


分析

  • 我把文库里的粘了过来.
  • 仅仅知道点1到点N的一条路径和图中若干个环。就能通过异或,表示成全部路径。那么。须要多少环才干保证必然能表示成全部路径呢?事实上。并不须要非常多, 由于一些环能够通过其它的环异或得到,仅仅需保证环是相互 独立的。两两之间存在着不同的边(乘数)。

    构建一棵生成树,统计非树边与生成树形成的环就可以,最多仅仅有M-N+1个环。可用dfs实现,时间复杂度为O(M)。

  • 结合上述性质。能够设计贪心说法:将x表示成二进制数,从高位到低位枚举,当前位能取1则取1。

    1. 从高位到低位枚举当前位。
    2. 在a数组中选取一个当前位为1的数a[i],假如不存在a[i],则转1);
    3. 假如x的当前位为0,则x=x xor a[i];
    4. 将a数组中全部当前位为1的数a[j]与a[i]异或,a[j]=a[j] xor a[i], 转1)。
  • 终于x保证必然是最大的,时间复杂度为O (NB)。(N为a数组的大小,B为二进制位数)

  • 看了上面的解析就去打了, 结果好几次都 WA. 然后跟HZWER的代码对照, 发现他在步骤2中选过的元素在后面再进行步骤2时不去考虑了.
  • 资料里怎么没说…
  • 改了这个地方就对了

  • 1直接左移62位是会报错的. 但一次一次来就没事…

  • 这个题究竟和高斯消元和线性基的关系在哪?

    • 贪心的那四步事实上就是标准的用高斯消元解异或方程组的步骤. 我后来更新了代码片.
    • 解得的那些解就是线性基. 用它们直接异或就能够表示出全部原来a数组能够异或出的结果.

代码

https://code.csdn.net/snippets/619907


$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('

    ').addClass('pre-numbering').hide();
    $(this).addClass('has-numbering').parent().append($numbering);
    for (i = 1; i ').text(i));
    };
    $numbering.fadeIn(1700);
    });
    });

    版权声明:本文博主原创文章,博客,未经同意不得转载。

    上一篇:python学习笔记(六)- 函数、文件json与python字典互操作


    下一篇:web页面防盗链功能使用--request.getHeader("Referer")