回归梦想

题解

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2)

/ 注册

全部文章 / 题解（共5篇）

P3265 [JLOI2015]装备购买

题目描述：给N个整数向量，每个向量带权值，求权值和最小的线性基题解：按权值v从小->大排序，依次插入线性基。整数线性基的思想类似，只是此时“消去”不能直接xor完成，需要类似高斯消元一样for一遍代码： #include<bits/stdc++.h> #define eps...

线性基 *** 高斯消元

2021-02-18

0 632

[TJOI2008]彩灯

题目： Peter 女朋友的生日快到了，他亲自设计了一组彩灯，想给女朋友一个惊喜。已知一组彩灯是由一排 N个独立的灯泡构成的，并且有 MM 个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有 2^N^个样式。由于技术上的问题，Peter 设计的每个开关控制的彩灯没...

线性基 ***

2021-02-18

0 536

【acwing210 异或运算】

【acwing210 异或运算】题意：给定你由N个整数构成的整数序列，你可以从中选取一些（甚至一个）进行异或（XOR）运算，问所有能得到的不同的结果中第k小的结果是多少。题解：把所有数插入线性基，把k二进制分解然后把1对应的位置xor起来；注意这样是从第0小=0开始数，需要特判0是否能够被x...

** 线性基

2021-02-18

0 627

P4301 [CQOI2013] 新Nim游戏

P4301 [CQOI2013] 新Nim游戏题目：在传统的Nim游戏基础上加一步，在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和 Nim 游戏一样。题解：...

** 线性基

2021-02-18

0 614

P4570 [BJWC2011]元素

题目描述：每个矿石有序号和魔力值，每个矿石最多使用一次，且多个矿石序号不能异或为0的前提下，问最多可以得到多少魔力值题解：异或运算的最终结果只和用于运算的数的各位上1的数量有关，与各数字运算的顺序无关所以直接先使用魔力值最大的石头就行按照魔力值从大到小排列，insert成功的就记录魔力值，失败...

线性基

2021-02-18

0 589