美团笔试，第一题黑白矩阵（ac），第二题格子染色（45%）

第一题根据矩阵索引（i + j % 2 == 0 和 == 1）分别用哈希表统计每个数字出现的次数，然后记录每个组出现最多的两个数ma[1]和ma[2]（因为两个组不能取一样的数字），之后ma[1] - ma[2]较小的组应该取第二个数，最后用总数减去即可，ac。

c++代码：

int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
unordered_map<int, int> m1, m2;
int sum1 = 0, sum2 = 0;
vector<int> res1, res2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
if ((i + j) % 2 == 0) {
sum1++;
m1[a[i][j]]++;
}
else {
sum2++;
m2[a[i][j]]++;
}
}
}
for (auto it = m1.begin(); it != m1.end(); it++) {
if (res1.empty())
res1.push_back(it->first);
else if (res1.size() == 1) {
res1.push_back(it->first);
if (m1[res1[0]] < m1[res1[1]])
swap(res1[0], res1[1]);
}
else if (it->second > res1[0]) {
res1[1] = res1[0];
res1[0] = it->first;
}
else if (it->second > res1[1]) {
res1[1] = it->first;
}
}
for (auto it = m2.begin(); it != m2.end(); it++) {
if (res2.empty())
res2.push_back(it->first);
else if (res2.size() == 1) {
res2.push_back(it->first);
if (m2[res2[0]] < m2[res2[1]])
swap(res2[0], res2[1]);
}
else if (it->second > res2[0]) {
res2[1] = res2[0];
res2[0] = it->first;
}
else if (it->second > res2[1]) {
res2[1] = it->first;
}
}
if (res1.size() == 1)
res1.push_back(99999);
if (res2.size() == 1)
res2.push_back(99999);
if (res1[0] != res2[0])
cout << sum1 + sum2 - m1[res1[0]] - m2[res2[0]];
else if ((m1[res1[0]] - m1[res1[1]]) < (m2[res2[0]] - m2[res2[1]]))
cout << sum1 + sum2 - m1[res1[1]] - m2[res2[0]];
else
cout << sum1 + sum2 - m1[res1[0]] - m2[res2[1]];
system("pause");
return 0;
}

第二题没想到更好的想法，就是每一条线与之前处理过的线逐个比较，去掉重合部分。去重主要分为水平和竖直交叉（此时sum - 1）以及同一水平线交叉（类似集合交叉）。最终可能有部分写错，来不及改了通过45%

c++代码：

int main() {
int n;
cin >> n;
vector<vector<int>> line(n, vector<int>(4));
int sum = 0;
for (int i = 0; i < n; i++) {
cin >> line[i][0] >> line[i][1] >> line[i][2] >> line[i][3];
if (line[i][0] == line[i][2]) {
int x1 = min(line[i][1], line[i][3]), x2 = max(line[i][1], line[i][3]);
sum += x2 - x1 + 1;
for (int j = 0; j < i; j++) {
if (line[j][0] == line[j][2] && line[j][0] == line[i][0]) {
int y1 = min(line[j][1], line[j][3]), y2 = max(line[j][1], line[j][3]);
if (y1 > x1 && y1 < x2) {
sum -= (min(x2, y2) - y1 + 1);
}
else if (y1 < x1 && y2 > x1) {
sum -= (min(x2, y2) - x1 + 1);
}
}
else {
int y1 = min(line[j][0], line[j][2]), y2 = max(line[j][0], line[j][2]);
if (line[i][0] >= y1 && line[i][0] <= y2 && line[j][1] >= x1 && line[j][1] <= x2)
sum--;
}
}
}
else {
int x1 = min(line[i][0], line[i][2]), x2 = max(line[i][0], line[i][2]);
sum += x2 - x1 + 1;
for (int j = 0; j < i; j++) {
if (line[j][1] == line[j][3] && line[j][1] == line[i][1]) {
int y1 = min(line[j][0], line[j][2]), y2 = max(line[j][0], line[j][2]);
if (y1 > x1 && y1 < x2) {
sum -= (min(x2, y2) - y1 + 1);
}
else if (y1 < x1 && y2 > x1) {
sum -= (min(x2, y2) - x1 + 1);
}
}
else {
int y1 = min(line[j][1], line[j][3]), y2 = max(line[j][1], line[j][3]);
if (line[i][1] >= y1 && line[i][1] <= y2 && line[j][0] >= x1 && line[j][0] <= x2)
sum--;
}
}
}
}
cout << sum << endl;
system("pause");
return 0;
}