上海计算机学会2024年12月月赛C++乙组T2删除网格
发布时间
阅读量：
阅读量
删除网格
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n×m 的矩阵 a，对 1≤x≤n,1≤y≤m 的 x,y 定义 w(x,y)为：
换句话说，在每一行和每一列之外的位置上取ai,j与ax,y进行异或运算后再相加得到w(x,y)。这里使用的是按位异或运算符。
求 w(x,y) 的最大 值。
输入格式
第一行两个整数 n,m。
接下来 n 行，第 i 行 m 个整数 ai,1∼m 表示矩阵第 i 行的元素。
输出格式
一行一个整数表示答案。
数据范围
对于 30% 的数据，1≤n,m≤10，0≤ai,j≤1。
对于 60% 的数据，1≤n,m≤105，1≤n×m≤106，0≤ai,j≤1。
对于 100% 的数据，1≤n,m≤105，1≤n×m≤106，0≤ai,j<2^30。
样例数据
输入:
2 3
1 2 3
4 5 6
输出:
13
说明:
选择 (x,y)=(2,1)，则 w(x,y)=(4 xor 2)+(4 xor 3)=6+7=13。
解析：
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector <int> a[100005];//a[i][j]表示矩阵第i行第j列的数字
int r[100005][2][35];//r[i][j][k]表示第i行二进制第k位数字是j的数量
int c[100005][2][35];//c[i][j][k]表示第i列二进制第k位数字是j的数量
int sum[2][35];//sum[i][j]表示矩阵中二进制第j位为i的数字数量
long long ans = 0;//答案
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++) {//循环输入矩阵
for(int j = 0; j < m; j++) {
int x;
cin >> x;
a[i].push_back(x);
for(int k = 0; k < 30; k++) {//循环取第k位（从低位开始）
if (x % 2 == 0) {//统计行，列，整体中0和1的数量
r[i][0][k]++;
c[j][0][k]++;
sum[0][k]++;
} else {
r[i][1][k]++;
c[j][1][k]++;
sum[1][k]++;
}
x /= 2;
}
}
}
for(int i = 0; i < n; i++) {//枚举删除a[i][j]后的结果
for(int j = 0; j < m; j++) {
long long t = 0;
long long w = 1;//位权
int x = a[i][j];
for(int k = 0; k < 30; k++) {//枚举每一位
if (x % 2 == 0) {
t += (sum[1][k] - r[i][1][k] - c[j][1][k]) * w;
} else {
t += (sum[0][k] - r[i][0][k] - c[j][0][k]) * w;
}
x /= 2;
w *= 2;
}
ans = max(ans, t);//取最大值
}
}
cout << ans;
return 0;
}全部评论 (0)
还没有任何评论哟~