正经题解｜答题卡

题目大意

给定一个$n \times n$的矩阵，矩阵仅由A,B,C,D组成，代表竖着的答题卡。

随后给定一个$n \times n$的矩阵，矩阵仅由+,-,?所组成,代表用横着的答案去比较竖着的答题卡当中，有哪些格子的答案是正确，错误，与不确定的。

现在，假若你将答题卡横过来，求解最多有几个正确的答案与最少有几个正确的答案。

题意分析

我们可以通过题意得知，竖着的答题卡对应横着的答案，也会有几道题目正确，从而得知正确答案矩阵当中的部分信息，再去进行解题即可。

解题思路

题目最终要求的目的为两个 最多以及最少 ，那么我们就要通过枚举的方式求出不确定答案格子的总数与确定答案格子的总数即可。

首先，我们要明确不确定答案格子的定义:

• 原本位置为?的格子一定为不确定答案
• 竖着答题卡原本错误格子-所对应的字符，与旋转变为横着答题卡对应格子的字符不相同，也有可能是正确答案，也为不确定答案。

随后确定答案格子定义就比较简单了:

• 竖着的答题卡原本正确+格子对应的字符与翻转过后横着的答题卡对应位置字符一致，则为正确答案。

最终，我们只需要将不确定答案总数累加上确定答案总数则为最多，只保留确定答案则为最小。

时间复杂度解析

本题使用循环对矩阵进行枚举，时间复杂度为$O(n^2)$

代码演示

##include<bits/stdc++.h>
using namespace std;
char mp[5005][5005];
char mp2[5005][5005];
char mp3[5005][5005];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n ; i ++ )
    {
        for(int j = 1 ; j <= n ; j ++ )
        {
            cin >> mp[i][j];
            mp2[j][i] = mp[i][j];
        }
    }

   int answer = 0  ;
   int count = 0 ;
   
   for(int i = 1 ; i <= n ; i ++ )
   {
   		for(int j = 1 ; j <= n ; j ++ )
   		{
   			char x;
   			cin >> x;
   			if(x == '+' && mp2[i][j] == mp[i][j])
   			{
   				answer ++ ;
			}else{
				if(x == '?')count ++ ;
				if(x == '-' && mp[i][j]!=mp2[i][j])count ++;
			}
		}
   }
   cout << count + answer << " " << answer << endl;
   return 0;
}