今天上午一道内部模拟赛的题目,如果被出题人看到了觉得侵权请联系我删除。
题目如下图
这道题是捆绑测试,我的程序只通过了 Subtask1,得了 5 分的好成绩,我没有想明白是为什么,而且他也没有 std 可以供我打对拍,甚至到现在连题解都没有。所以求助一下,谢谢大家。
都是答案错误,而那个 OJ 只要有一个测试点不通过后面的测试点都不测了,那个答案错误的测试点提示的信息都是应该是 0,而我输出的不是 0。
代码如下
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[13][13], b[13][13];
int temp[13][13];
int n;
int duichen(int aa[13][13],int bb[13][13]) //对称
{
int cnt=0, mmin=2e9+5;
for(int i = 1; i <= n; i ++) //不变
for(int j = 1; j <= i; j ++)
if (aa[i][j] != bb[i][j]) cnt++;
mmin = min(cnt, mmin), cnt = 0;
for (int i = 1; i <= n; i ++) //对称
for (int j = 1; j <= i; j ++)
temp[i][j] = aa[i][i + 1 - j];
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= i; j ++){
aa[i][j] = temp[i][j];
if (aa[i][j] != bb[i][j]) cnt++;
}
}
mmin = min(cnt, mmin);
return mmin;
}
int xuanzhuan(int aa[13][13],int bb[13][13]) //旋转
{
memset(temp, 0, sizeof(temp));
int cnt = 0, mmin = 2e9 + 5;
for(int i = n; i >= 1; i --) //顺120
{
for(int j = 1; j <= i; j ++)
{
temp[i][j] = aa[n + 1 - j][i + 1 - j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
aa[i][j] = temp[i][j];
if(aa[i][j] != bb[i][j]) cnt++;
}
}
mmin = min(cnt, mmin), cnt = 0;
memset(temp, 0, sizeof(temp));
for (int i = n; i >= 1; i--) //顺240
{
for(int j = 1; j <= i; j++)
{
temp[i][j] = aa[i + j - (2 * i - n)][n + 1 - i];
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= i; j ++){
aa[i][j] = temp[i][j];
if(aa[i][j] != bb[i][j]) cnt++;
}
}
mmin = min(mmin, cnt);
return mmin;
}
int both(int aa[13][13],int bb[13][13]) //旋转+对称
{
memset(temp, 0, sizeof(temp));
int cnt = 0, mmin = 2e9 + 5;
for(int i = n; i >= 1; i--) //顺120+对称
{
for(int j = 1; j <= i; j ++)
{
temp[i][j] = aa[n + 1 - j][i + 1 - j];
}
}
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i; j ++)
temp[i][j] = aa[i][i + 1 - j];
for (int i = 1; i <= n; i++){
for (int j = 1; j <= i; j++){
aa[i][j] = temp[i][j];
if (aa[i][j] != bb[i][j]) cnt++;
}
}
mmin = min(cnt, mmin), cnt = 0;
memset(temp, 0, sizeof(temp));
for(int i = n; i >= 1; i --) //顺240 + 对称
{
for(int j = 1; j <= i; j ++)
{
temp[i][j] = aa[i + j - (2 * i - n)][n + 1 - i];
}
}
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i; j ++)
temp[i][j] = aa[i][i + 1 - j];
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= i; j ++){
aa[i][j] = temp[i][j];
if (aa[i][j] != bb[i][j]) cnt++;
}
}
mmin = min(mmin, cnt);
return mmin;
}
signed main()
{
freopen("triangle.in", "r", stdin);
freopen("triangle.out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i; j ++)
cin >> a[i][j];
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i; j ++)
cin >> b[i][j];
int ans = 2e9 + 10;
ans = min(ans, duichen(a,b));
ans = min(ans, xuanzhuan(a,b));
ans = min(ans, both(a,b));
cout << ans <<endl;
return 0;
}
代码已经做了轻微调整,更适宜阅读了(\doge)
在 duichen()
函数里面,temp[i][j] = aa[i][i + 1 - j]
是一个坐标变换的东西,因为这个三角形左右对称,所以横坐标不变,纵坐标变为 i+1−j,这是我推出来的,包括 xuanzhuan()
函数和 both()
函数,都是同理,我是找规律得到的,有可能是这儿出问题了,但我也不知道正确的是什么。