2019.2.12

长沙集训 $ Day 2 $

今天的题目真正有了省选难度，要不是第一题是个暴力我就要爆零了…

~~这才是大佬们的世界吧…~~

T1 十字形

在今天的模拟赛中，这题算非常简单了，最起码是随机数据。

如此将线段分开存储，将 $ a $ 按照 $ len $ 从大到小排序。将 $ b $ 按照 $ p $ 从小到大， $ len $ 从大到小排序。之后枚举 $ a $ ，用二分查找与 $ b $ 的交点，计算答案，在 $ len < 2 \cdot ans+1 $ 时退出。便可解决此题。

其实还有更优的解法，可以对 $ ans $ 二分答案，将各线段两端减去 $ ans $ 的长度后，按 $ x $ 坐标枚举竖直线段，用扫描线+线段树进行维护，判断是否有交点。

(1)如果二进制中第 $ i $ 位一共有奇数个 $ 1 $ ,那么这一位一定会给答案增加 $ 2^{i} $ 的贡献，因为奇数个 $ 1 $ 分成两堆，一定有一堆为奇数个，一堆为偶数个。如果二进制中第 $ i $ 位有偶数个 $ 1 $ ,那么我肯定尽量使得两堆都分得奇数个 $ 1 $ ,那么这一位就会对答案贡献 $ 2 \times 2^{i} $ ,而且肯定是尽量满足高位。这样的话就可以得到 $ 60 $ 个异或方程。

例如： $ a_{1,1} \cdot x_1 \oplus a_{2,1} \cdot x_2 \oplus … \oplus a_{n,1} \cdot x_n = f_1 $

$ a_{i,j} $ 表示第 $ i $ 个数的第 $ j $ 位是否为 $ 1 $ , $ \oplus $ 表示异或，若这一位一共有奇数个 $ 1 $ ,那么
$ f $ 值为 $ 0 $ ，否则为 $ 1 $

(2)先考虑和最大，从高位到低位，如果这一位异或和为 $ 1 $ ，和一定是 $ 1 $ ，不用管。否则的话异或和可能是 $ 2 $ 或者 $ 0 $ ，如果可以是 $ 2 $ 的话一定要求是 $ 2 $ 。再考虑 $ x_1 $ 最小。跟上面类似，如果异或和是 $ 1 $ 的话，尽量让 $ x_1 $ 取 $ 0 $ 。关键是如何维护这些限制条件。可以用 $ x_i $ 表示第 $ i $ 个数是否选择，那么每个条件都是形如 $ XOR^{n-1}{i=0} a{i,j} \cdot x_i =y_j $ 。这样用高斯消元维护一下就可以了，对于每个新方程，如果产生新的主元就加进来。

线性基

线性基是一种贪心的算法。

用 $ p[i] $ 记录 $ 1 $ 最高位为第i位的数：

$ p[i]=0 $ ，直接记录
$ p[i]<>0 $ ,将$ x \ \ xor \ \ p[i] $ ，再继续处理

for t:=62 downto 0 do
  if x shr t<>0 then begin
    if p[t]=0 then begin p[t]:=x;break; end
      else x:=x xor p[t];
  end;

计算答案：

尽量使高位上的 $ 1 $ 更多，这样答案更大
从高位开始，如果 $ ans \ \ xor \ \ p[i] $ 更大，则更新 $ ans $

for i:=62 downto 0 do
  if ans xor p[i]>ans then ans:=ans xor p[i];

长沙集训Day2

2019.2.12

长沙集训 $ Day 2 $

T1 十字形

T2 集合

官方题解

线性基