重庆省选解题报告.pdf

《重庆省选解题报告.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、解题报告matrix题目大意给定一个01矩阵的长和宽，要求构造该01矩阵，满足：每个“十字形”图案里有偶数个1。其中，“十字形”图案的定义为：一个元素和与它四个四连通方向的元素所组成的图案。如果一个元素在边或角上，也就是说，它某个方向的四连通元素不存在，记这个方向的联通元素为0。显然该问题一定有解，但是，如果存在不是全部为0的解，那么就不能输出全部为0的那个解。算法讨论首先，根据题意，我们很快就能想到：只要确定了第一行的m个元素，就可以根据第i-1行和i-2行的信息（我们认为第0行所有元素全是0）来确定第i行的信息了。最后，只需要

2、判断以第n行的各个元素为中心的“十字形”图案是否满足条件就可以了。稍微做一下推倒就可以知道，对于给定的矩阵长宽n、m，我们可以通过递推的方法确定第1行的每个数对于第n行每个数是否有影响，用二进制数表示即可。a[i][j]是一个二进制数，其二进制下的第k位表示第一行第k个数对第i行j列的数字是否有影响。由于矩阵只有0和1两种元素，那么，我们有如下递推式：a[1][j]=1<<(j-1)(1<=j<=m)a[i][j]=a[i-1][j]xora[i-1][j-1]xora[i-1][j+1]xora[i-2][j](2<=i<=n,

3、1<=j<=m)通过递推计算出a数组后，我们可以看出，对于所有的i,j(1<=i<=n-1,1<=j<=m)，都有a[i][j]xora[i-1][j]xora[i][j-1]xora[i+1][j]xora[i][j+1]=0现在，我们需要考虑的问题就转化为了：记b[j]=a[n][j]xora[n-1][j]xora[n][j+1]xora[n][j-1]，于是我们得到一个大小为m的b数组，同时，我们可以将这个b数组转换成为一个方程组，将每个b[j]转换成一个方程，得到方程组{(b[1]>>0&1)x[1]+(b[1]>>1&

4、1)x[2]+...+(b[1]>>m-1&1)x[m]=0(b[2]>>0&1)x[1]+(b[2]>>1&1)x[2]+...+(b[2]>>m-1&1)x[m]=0...(b[m]>>0&1)x[1]+(b[m]>>1&1)x[2]+...+(b[m]>>m-1&1)x[m]=0}其中，x[i]表示第1行第i位的数字(只有0或1)。我们要做的，就是如果这个方程组存在一个解，其中存在一个x[i]!=0(1<=i<=m)，那么求出一个这样的解，否则判断方程组只有唯一解：即所有的x[i]都为0.对于异或方程组，有复杂度为O(Nlo

5、gMax)(其中Max为数字最大可能达到的大小)的Gauss消元解法，我们使用这个方法对方程组进行Gauss消元。Gauss消元之后，我们发现，对于每个方程i，只有两种可能的情况：1.方程i的所有系数都为02.存在一个j，方程i的第j个系数为1，而其他方程第j个系数都为0。如果方程i的第j个系数满足上述条件，我们记第j列系数是“特殊的”.于是，我们的构造方案如下：1.对于所有非“特殊的”列j，我们把这一列所对应的x[j]设为1。2.如果第j列的1(注意如果这一列是“特殊的”，那么这一列就仅有1个1)存在于第i行，那么这个1作为第i

6、行的“调节系数”，作为第i行最后确定的x[j]值来确定，根据第i行系数为1的非“特殊的”列的奇偶性来确定就可以了。到此为止，问题完美解决了。bridge给你一张图，有些边只能走2次，有些能走无数次，然后给出a1a2anb1b2bn六个数，你需要从a1走到a2再走回a1总共an次对b1b2bn也同理，问是否可行。嘛，最基础的思路是直接把a1b1当做起点然后a2b2当做终点直接跑一遍网络流看是否可行，嘛，这样的话就能过掉所有样例了，然后就被坑了。这样做的问题在哪里呢？原因是流的时候我有可能是从a1有部分流到了b2去，而b1流到了a2去

7、，这样就导致了虽然满流但并不是符合题意的走法。Sohowtosolveit?嘛，其实解决的办法很简单，先做一遍网络流，不满流就GG了。如果满流的话，交换b1b2，如果还满流，那就是对的了。证明如下：第一次未交换时，我们假设流出来的方案是又不合法的，那么我们设从a1流到b2的流量为x那么有：a1到a2的流量=an-xa1到b2的流量=xb1到a2的流量=xb1到b2的流量=bn-x第二次我们交换b1，b2，那么由于都是无向边，那么首先b2从b1可以流bn-x的流量，a1到a2仍然可以流an-x的流量，也就是说两边都还差x的流量。由于

8、第二次流出来是满流的，那么如果我们最后流出来的方案是a1给b1流了x的流量导致满流，那么我们有：a1到b1和b2都可以流x的流量，那么再交换之后，从a1流到b1的流量我们可以调整为先从b2流到了a1，再从a1流到了b1总共x的流量（关键之处是在于无