资源预览内容
第1页 / 共49页
第2页 / 共49页
第3页 / 共49页
第4页 / 共49页
第5页 / 共49页
第6页 / 共49页
第7页 / 共49页
第8页 / 共49页
第9页 / 共49页
第10页 / 共49页
亲,该文档总共49页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
XOR方程组清华大学 莫涛 mythlyqq.com hwdhwd.name前言约定lXOR的计算方式lN,M=k使得Aj,i为1则交换第j行与第k行用第k行对之后的行进行消元k = k + 1l否则第个变量是自由变量,k不变l时间复杂度O(NM2)解的判断l无解l存在方程系数全为0,常数项不为0l唯一解l无自由变量l多解:l出现了S个自由变量,这些变量可任意取值从而确 定其余变量的值l2S组解例子lN = 4 K = 7lN个数为 5 6 3 4lX1 + X3 = 1lX2 + X3 = 1lX1 + X2 + X4 = 1l欢迎上台解方程位运算优化l一个int64/long long储存60个bitl取出X的第i位:X and 2i-1l两行做异或:A xor B例五l在例四的基础上,给定M个限制,每个限制是 那N个数的一个子集,要求该子集中的数恰有 奇数个或偶数个被选择。解法l给每个限制添加一个方程l用例四的方法解决例六l从N个数中选出任意个数,使XOR和最大。lO(N*603)? O(N*602)? (N/60)*602)?O(N*60)?l最简洁的算法?解法一l从高到低确定K的每一位,设当前考虑第i位l若Ki = 1可行则确定l否则Ki = 0l判断可行l对前i位列方程,使用例四的方法l时间复杂度O(N*603)解法二l确定第i位时,前面的方程已经消好元了l只需用前i-1个方程对第i个方程进行消元l例:前方程组中添加X1 + X2 + X3 + X4 = 0l时间复杂度O(N*602)l使用位运算可以优化为O(N/60)*602)解法三l从前到后考虑每一个数,若它可被之前的数凑 出则可以直接将其扔掉l维护已有的独立数的上三角矩阵,相当于将A 旋转90度后进行高斯消元l直接确定最终答案,O(N*60)例七l从N个数中选出任意个数,求能得到的XOR和 的种数。解法l利用例六的解法三l设有T个独立数,答案为2Tl为什么不会有重复?l其它解法?l建议学习线性代数相关知识例八l从N个数中选出任意个数,使它们的XOR和与 K的XOR和最大。解法l例六解法三,直接确定答案概览二(十分钟)lN个点M条边的边带权的无向图,把点分成两个集合,使处于两集合 之间的边的XOR和最大。(提示:1,2,5,10,20,50,100。7种币值可凑 出所有面值)lN个点M条边的边带权的无向图,求一个回路使XOR和最大。l用第5题的思路。l方程的解与回路一一对应吗?证明之。l时间复杂度?l用第9题的思路。l最少需要多少种“币值”?证明之。l如何构造这样一组“币值”。l上一题的makedata怎么写?lN个点M条边的边带权的无向图,求一条1号点到N号点的路径,使 XOR和最大。例九(XOR最大割)lN个点M条边的边带权的无向图,把点分成两 个集合,使处于两集合之间的边的XOR和最大 。l提示:1,2,5,10,20,50,100。7种币值可凑出所 有面值。解法l设hi为i的邻边的XOR和l一个割S,T = hi(i在S中) = hi(i在T中) l转化为例六例十(XOR最大环)lN个点M条边的边带权的无向图,求一个回 路使XOR和最大。l用第5题的思路。l方程的解与回路一一对应吗?证明之。l时间复杂度?l用第9题的思路。l最少需要多少种“币值”?证明之。l如何构造这样一组“币值”。解法一lXi表示第i条边是否在路径中l点的邻边中恰有偶数条被取lN个方程,M个变量方程的解与回路的对应性l回路均满足方程l方程的解可能是若干不连通的回路l走过来再走回去,XOR和不变时间复杂度l转化为例五+例六l只能使用解法二lO(M/60)N(N+60)解法二l两个回路的和仍是回路l和 指 异或和/对称差l连通性问题l结论:一个无向连通图G中有且仅有M-N+1个 独立回路。数学归纳法lM=N-1时,树,结论成立l设M=K时结论成立,当M=K+1时,任取G中一 条边e,G-e中有K-N+1个独立回路,且l任取一个包含e的回路C,显然独立于之前的回路l任意两个包含e的回路C1与C2,C12=C1+C2是G-e的 回路,C2不独立l故能且仅能增加一个包含e的独立回路l从而G中恰有(K+1)-N+1个独立回路,证毕构造法l任取原图一棵生成树Tl对于每条不在T中的边e,取T+e的回路时间复杂度l利用构造法,求出M-N+1个独立回路的XOR和l转化为例六lO(M+N)*60)l建议学习图论相关知识例十一l例十的makedata怎么写?解法l生成一个独立数集l随机生成一棵树的边权l对于每条非树边,确定其值使得该边对应的环 的XOR和可由独立数集生成例十二(XOR最长路)lN个点M条边的边带权的无向图,求一条1号点 到N号点的路径,使XOR和最大。解法l任意两条路径的和为一个环l任取一条1-N的路,找一个环与其XOR和最大l转化为例八例十三l扩展思考:从N个数中选出不超过K个,使 XOR和最大。例十四l扩展思考:在第10题基础上,限制求得的回路 是简单回路。例十五l扩展思考:带权二分图,求一个完美匹配,使 XOR和最大。Matrixl一个N*N的01矩阵,每个十字中有偶数个1l已经填好了M个数,求填完该矩阵的方案数lM=N=1000解法l确定第一行后,可以递推确定剩下的格子,且 该方案合法当且仅当这样递推得出的第N+1行 全是0l第一行的N个格子作为未知数l递推求出第N+1行与第1行的关系,N个方程l已填数的信息,M个方程l该方程组的解数即为答案,O(N3/60)POI2005dwal一个无向图,将N个点分成两个点集,使得尽 量多的点满足:l邻居中有偶数个点和自己在同一集合l允许分出空集lN=1000解法l设点i的邻居为Si,Si中有偶数个点与i同集合l若di为奇,Si中两集合均包含偶数个点l若di为偶,Si+i中两集合均包含奇数个点lXi表示第i个数所属的集合(0或1)lN个未知数,N个方程l猜想:该方程组一定有解,即答案为N证明l见Matrix67的Blog谢谢
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号