夢に僕らで帆を張って
来るべき日のために夜を超え

标签 线性基 下的文章

November 5, 2019

洛谷P4151/WC2011 最大XOR和路径

题意给出一张无向图,求$1 \rightarrow n$的最大异或和路径数据范围:$n \le 50000,m \le 100000,d_i \le 10^{18}$题解考虑没有环的情况,答案为$dis[n]$若存在环,由于从$1 \rightarrow n$的路径上到环上的路径需要走两遍(去/回),相当于没有计算因此统计图上环的异或和,再与$dis[n]$异或求最大值而多个值异或的最大值可...
November 5, 2019

洛谷P3857/TJOI2008 彩灯

题意每个开关能控制若干个彩灯(亮/暗),求这些彩灯有多少种样式数据范围:$n,m \le 50$题解将每个开关控制的彩灯视为一个$01$串,开关之间进行的相当于异或操作,求最后有多少不同的$01$串容易想到线性基设线性基内元素数为$k$,答案即为$2^k$代码:#include<iostream> #include<cstdio> #include<algori...