站外题求助!!!

题目总版

xingshuyan000 @ 2024-09-15 22:44:26

今天上午一道内部模拟赛的题目,如果被出题人看到了觉得侵权请联系我删除。

题目如下图

这道题是捆绑测试,我的程序只通过了 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() 函数,都是同理,我是找规律得到的,有可能是这儿出问题了,但我也不知道正确的是什么。


by xingshuyan000 @ 2024-09-15 22:46:53


by JoyLosingK @ 2024-09-15 22:58:54

图太小了看不清


by xingshuyan000 @ 2024-09-15 23:01:24

好像图片有点看不清,所以我给大家大概叙述一下题目吧。(上面的几幅图应该能看清吧)

题目描述

有一个用硬币摆成的三角形,第一行有 1 个硬币,第二行有 2 个硬币,第三行有 3 个,以此类推,第 n 行有 n 个硬币,每个硬币上都标有数字 0 或 1,分别表示正面和反面。

(图 1)

你可以旋转该三角形任意次,如下图是三角形 A 通过旋转可以变成的形态。

(图 2)

同时你也可以使三角形左右对称,下图是三角形 A 对称后的形态。

(图 3)

定义两个三角形的差值是两个三角形重叠时不同位置的数目。例如将三角形 A 和 B 重叠,第二行第一个,第三行第一个、第三个都不同,此时差值为 3。若将三角形 A 逆时针旋转 120 度(图 2 右边的三角形)和 B 重叠,那么只会有一个位置不同,差值为 1

给出两个大小为 N 的三角形 A 和 B,你可以任意地旋转和对称 A,求旋转和对称 A 后与 B 最小的差值为多少。

输入格式

第一行一个整数 n,表示两个三角形的大小。

在接下来的 n 行中,第 i 行有 i 个整数,每个整数都是 01,表示三角形 A。

在接下来的 n 行中,第 i 行有 i 个整数,每个整数都是 01,表示三角形 B。

输出格式

输出一行一个整数表示答案。

数据范围

对于 100\% 的测试点,1 \le n \le 10


by xingshuyan000 @ 2024-09-15 23:02:03

@JoyLosingK 我刚才又发了个评论,描述了下题目,你看我发的这个评论吧


by xingshuyan000 @ 2024-09-15 23:10:48

输入输出样例

输入样例 1

2
0
1 1
0
1 1

输出样例 1

0

输入样例 2

4
0
1 0
0 0 1
1 1 0 0
0
0 1
0 0 0
0 1 1 1

输出样例 2

2

输入样例 3

4
0
1 1
1 0 0
1 0 0 0
0
0 0
0 0 1
1 1 1 0

输出样例 3

0

by JoyLosingK @ 2024-09-15 23:11:41

@xingshuyan000

感觉你的代码大体没啥问题,如果错了应该是规律的问题


by xingshuyan000 @ 2024-09-15 23:12:09

@JoyLosingK OK,那我再看看,谢谢你


|