首页 > 其他分享 >CF1016D Vasya And The Matrix Solution

CF1016D Vasya And The Matrix Solution

时间:2024-01-13 23:22:07浏览次数:33  
标签:CF1016D Vasya xor Matrix int text 异或 ans suma

题目传送门

做法

因为是异或运算,可以按位考虑。

先预处理出行 ( \(a[i]\) ) 异或和 \(suma\),与列 ( \(b[i]\) ) 的异或和 \(sumb\)。

  • 如果 \(suma \ne sumb\),那就说明无解,因为 \(suma\) 和 \(sumb\) 最后都代表着整个矩阵的异或和,如果两者不相等,那就说明矛盾,无解。

  • 否则就一定存在解。

具体地,设 \(ans[n][m]\) 为最终的答案矩阵,对于 \(n-1,m-1\) 的子矩阵我们可以全部填上 \(0\) ,其余的部分就为:

\(ans[i][m]=a[i]~(i \in [1,n-1]),~ans[n][j]=b[j]~(j\in[1,m-1])\)。

\(ans[n][m]=(suma ~~ \text{xor} ~~ a[n]) ~~ \text{xor} ~~ b[m]\)。

前面这两行的意思都是为满足题意,第一行就是直接填上原来的数(因为它前面的数都是一堆 \(0\) ,也就是这一行或者这一列只受一个因素影响,所以直接填上原数不会对答案造成影响),第二行因为 \(ans[n][m]\) 同时被两个因素 \(a[n]\) 与 \(b[m]\) 影响,所以要单独讨论。

\(suma ~~ \text{xor} ~~ a[n]\) 的结果是整个矩阵前 \(n-1\) 行的异或和,用它在 \(\text{xor} ~~ b[m]\) 的结果是长这个样子:

又因为 \(ans[1,~...~,n-1][1,~...~,m-1]\) 都为 \(0\) ,所以 \(suma ~ \text{xor}~ a[n]\) 就是 \(ans[1][m],ans[2][m],...ans[n-1][m]\) 的异或和。用这个结果在异或 \(b[n]\) 就刚好是 \(ans[n][m]\) 。

现在来考虑此做法的正确性,显然在判断无解的情况我们是没有问题的,有解时的对答案矩阵的构造方案也显然是对的。所以正确性得到了证明。

\(Code\)

#include<bits/stdc++.h>
using namespace std;
const int N=200;
int n,m,a[N],b[N],ans[N][N];
int main()
{
	int suma=0,sumb=0;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),suma^=a[i];
	for(int i=1;i<=m;i++)scanf("%d",&b[i]),sumb^=b[i];
	if(suma!=sumb)
	{
		printf("NO\n");
		return 0;
	}
	printf("YES\n");
	for(int i=1;i<=n-1;i++)
		for(int j=1;j<=m-1;j++)ans[i][j]=0;
	for(int i=1;i<=n-1;i++)ans[i][m]=a[i];
	for(int i=1;i<=m-1;i++)ans[n][i]=b[i];
	ans[n][m]=b[m]^(suma^a[n]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d ",ans[i][j]);
		printf("\n");
	}
	return 0;
}

标签:CF1016D,Vasya,xor,Matrix,int,text,异或,ans,suma
From: https://www.cnblogs.com/CQWYB/p/17963193

相关文章

  • 使用cv2.getOptimalNewCameraMatrix函数,变为圆形是出现什么错误
    cv2.getOptimalNewCameraMatrix函数用于计算一个新的相机矩阵,以进行图像畸变校正。这个函数的目标是通过考虑畸变的影响,生成一个新的相机矩阵,使得校正后的图像更接近理想的情况。cv2.getOptimalNewCameraMatrix(cameraMatrix,distCoeffs,imageSize,alpha,newImgSize)其中......
  • AHB Matrix
    常用的AHBBus结构AHBMatrixAHBBusMatrix,即总线矩阵,其实际上就是一个互连(Interconnect)。用于连接满足该总线协议的外设,包括Master和Slave。基于该模块,我们可以快速的完成“连连看”工作。将设计好的IP封装成AHB协议,然后挂载上去即可。这样就完成了简单的SoC集成工作。将......
  • Hessian Matrix Approximations: A Comparative Study in the Context of Machine Lea
    1.背景介绍在机器学习领域,优化算法是非常重要的。在训练模型时,我们需要最小化损失函数,以实现模型的参数估计。这里的损失函数通常是一个非线性函数,因此我们需要使用一种迭代的方法来找到最小值。这里的优化算法就发挥了作用。Hessian矩阵是二阶导数的矩阵,它可以用来衡量损失函数在......
  • CodeForces 1917E Construct Matrix
    洛谷传送门CF传送门\(2\nmidk\)显然无解。若\(4\midk\),发现给一个全\(2\times2\)子矩形全部异或\(1\)不会对行异或和和列异或和造成影响。那么我们找到\(\frac{k}{4}\)个全\(0\)的\(2\times2\)子矩形填\(1\)即可。否则若\(k=2\)或\(k=n^2-2\)......
  • CF1051C Vasya and Big Integers 题解
    Problem-1051E-CodeforcesVasyaandBigIntegers-洛谷感谢女队提交记录推荐给我的一道题\(Orz\)首先\(O(n^2)\)的\(dp\)是simple的,如果你没看出来你可能是像我一样把题目看错了设\(dp_i\)表示考虑前\(i\)个的方案数,转移枚举长度后比较字典序。虽然看......
  • Codeforces1917E - Construct Matrix
    Codeforces1917E-ConstructMatrix首先考虑因为\(n\)为偶数,所以\(k\)为奇数时不可能满足条件。其次,如果\(4|k\),那么实际上在矩阵中一直放\(2\times2\)的全为\(1\)的矩阵就可以了。随后,如果\(k\equiv2\mod4\),那么可以证明如果\(k\ne2\landk\nen^2-2\),......
  • CF Edu160E Matrix Problem
    场上疯狂想求任意解+改动解至最优。。想不下去的时候一定要再读一遍题跳出来啊。限制每一行每一列的\(1\)的个数,这很匹配啊!!考虑网络流,左侧\(n\)个节点连流量\(a_i\),右侧\(m\)个节点连流量\(b_i\)。对于原矩阵中为\(0\)的项\((i,j)\),若新矩阵中为\(0\)则流量为\(0......
  • CF1913 E Matrix Problem 题解
    LinkCF1913EMatrixProblemQuestion给定一个\(n\timesm\)的01矩阵,你可以把矩阵中的任意一个元素01翻转需要最后的矩阵满足,每行\(1\)的个数有\(A[i]\)个,每列\(1\)的个数有\(B[i]\)个Solution这貌似是一道非常经典的费用流题目我们建立\(n\)个行节点,\(m......
  • covariance matrix in signal processing
    cross-covarianceInthecaseofcomplexrandomvariables,thecovarianceisdefinedslightlydifferentlycomparedtorealrandomvariables.Forcomplexrandomvariables(Z_1)and(Z_2),thecovarianceisdefinedas:\[\text{Cov}(Z_1,Z_2)=E[(Z_1-......
  • Is Attention Better Than Matrix Decomposition?
    IsAttentionBetterThanMatrixDecomposition?*Authors:[[ZhengyangGeng]],[[Meng-HaoGuo]],[[HongxuChen]],[[XiaLi]],[[KeWei]],[[ZhouchenLin]]Locallibrary初读印象comment::作者提出了一系列Hamburger,这些汉堡包使用MD的优化算法来分解输入表示并重......