2014寒假总结(1.26-1.27)

【1.27】

【收获】
认真研究并且理解了高斯消元求解异或方程组的过程与性质,复习了线性相关与基等线性代数基本知识。对拟阵的理解进一步加深。
【SGU275】To xor or not to xor
高斯消元实质维护的是一组代表元,通过这些代表元可以表示出原数列可以表示出的任何一个数。对于每一列的控制可以把它看成主元(pivot column),我们实质是通过它们来进行构造出答案的。
对于异或和最大,可以依次从高位向低位异或主元即可。对于方案,答案即为,其中T为主元数量。还有一些类似选取若干数字与K异或后最大,方法类似,按位确定。
下面是部分核心代码

void Eliminate(long long X0)
{
    for (int i=62; i>=0; i--)
    {
        if (X0>>i&1)
        {
            if (F[i]) X0^=F[i];
            else 
            {
                F[i]=X0;
                for (int j=62; j>=0; j--)
                {
                    if (j!=i && (F[j]>>i&1)) F[j]^=F[i];
                }
                break;
            }
        }
    }
}

【CQOI2013】新Nim游戏
题目大意是求一个在GF(2)下,可重正整数S的一个极大无关组T,使得T的权值和最大。
我们可以通过拟阵证明将S中元素排序后从大到小依次选取解是最优的,现在的问题是如何判断一个数能否加入当前的线性无关组。
这里用到了一些线性代数的性质,就是一个向量组是线性无关组的充要条件是该向量组中任意一个向量不能被其他向量所表示出来。这里的证明是显然的,在此掠过。
我们的解法如下,通过一个类似高斯消元的方法,维护一个基,因为高斯消元的实质是对矩阵做初等行变换,这是不会改变向量组的线性相关性与能够线性生成出的向量空间的。将一个数放进矩阵进行高斯消元,如果这个数能被矩阵中的主元线性表示,那一定就不能与之前的数构成线性无关向量组。

【WC2011】最大Xor路径
注意到任意一条从1到N的路径都可以由从1到N的任意一条基本路径与若干独立环异或而得到。而我们是可以走到任意一个独立环的(因为两次异或会导致只有环上的值流了下来),所以这题转为SGU275。注意DFS找环时只需要Dis[u] xor Dis[v] xor W(u,v)。
【Beijing2011】元素
此题与CQOI2013那题雷同。
【Beijing2011】梦想封印
这题应该是之前几道题的综合版了吧。思考后,可以发现我们可以把从Kernel到任意一点的操作看做一条连接根的路径与若干独立环的异或和。考虑没有删边操作的问题,链和环是独立的,我们还是可以维护一个上三角矩阵,把环的一组基动态维护,现在问题是如何处理链的判重问题,画图分析,可得只要在同一阶段中如果两个数在高斯消元后表示一样,那么这两个链代表元等价。所以可以用一个平衡树维护判重。
细节问题的考虑是需要耐心的,比如合并两个块时需要更新组内元素到代表元的异或距离,将1号块与其它块合并时需要加入新的元素动态消元,消元后更新链代表元。

JAN. 26th

【收获】
复习了Nim游戏与SG函数等有关组合游戏的博弈论知识,加深了对SG函数的理解。
【Beijing2009】取石子游戏
基本的SG函数的应用。F[i]表示取1堆石子数为i的SG值,最后异或可得答案。
【HNOI2010】取石子游戏
题目难度较大。
如果可取元素是降序排列,那么显然我们排序后依次取值一定是最优策略。通过贪心思想,我们发现可以对如下两种情况进行化简以达到降序排列的目的:
1. 如果存在栈底元素大于栈顶元素,那么除非万不得已,先手一定不会选择,那么我们可以把这种情况放在最后考虑。删去它们也无妨。
2. 如果在双端队列中的元素出现B>A,B>C,那么我们用A+C-B来替换它们三个,实质是等价的。
实现方面我们用链表维护即可。

【ZJOI2009】染色游戏
题目构思巧妙。将棋盘中每一个反面向上的硬币看做一个子游戏,除这个点之外的其余硬币均为向上。我们可以推出F(x,y)的值为。对于只有一行或只有一列的,我们发现上面式子并不适用。在这种情况下,游戏已经转化成一维的翻硬币了,F(x)=x&-x,亦就是我们在Fenwick树中常用的Lowbit。剩下的工作就是异或求解了。