CF 780 E. Matrix and Shifts

本文主要是介绍CF 780 E. Matrix and Shifts，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 Problem - E - Codeforces

 题目恰好和昨天讲过的矩阵相关，所以读完题目就已经有了答案。

题目大意：仅有0和1组成的矩阵，矩阵可以整体性地上下移动或左右移动，移动不花费代价，然后可以通过异或运算，将矩阵转换成对角线元素均为1，而其他值为0的矩阵。每次异或运算代价1，求最小代价
解题思路：由于题目要求对角线为1，而其他为0，所以通过移动让对角线1的数量尽可能多，这样才能使得代价最小。

那么哪些元素可以通过移动，构成对角线元素，可找规律，发现共n条斜线。如下图。

#include <bits/stdc++.h>
using namespace std;
int t,n;
char a[2005][2005];
int  check(int x)
{int cnt=0;for(int i=1; i<=n; i++,x=x%n+1) /**< 这也是双指针 */cnt+=a[i][x]-'0';return cnt;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0);int i,j;cin>>t;while(t--){int sum=0,ans=0;cin>>n;for(i=1; i<=n; i++)for(j=1; j<=n; j++){cin>>a[i][j];sum+=a[i][j]-'0';/**< 统计1的总数 */}for(i=1; i<=n; i++)ans=max(ans,check(i));/**< 检查对角线 */cout<<sum-ans+n-ans<<endl;/**< 对角线0的数量+其他区域1的数量 */}return 0;
}

这篇关于CF 780 E. Matrix and Shifts的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---