题解：P13048 [GCJ 2020 Qualification] Vestigium

_WCW_ · 2025-07-03 22:35:17 · 题解

题目传送门

题目分析

这道题其实就是求一个 N \times N 的矩阵的主对角线的元素之和，同时求出矩阵中有多少个含有重复元素的行和列。

解题思路

求主对角线元素之和比较好求，重点在于如何计算有多少个含有重复元素的行和列。我们可以利用 set 容器自动去重的性质，将每一行或每一列的元素存入容器中，如果容器的长度比 N 小，说明有元素被去重了（举个例子，例如 N 是 5，而某一行中有 3 个元素是重复的，存入 set 中，重复的元素只会被存入一次，所以这个容器的长度会比 N 小），这时计数变量加一，最后输出即可。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,t,m[110][110];//m用于存储数据
int main()
{
    scanf("%d",&t);//输入t
    for(int cnt=1;cnt<=t;cnt++)//循环t次
    {
        int k=0,r=0,c=0;//这些变量均为题中意思，初始化为0
        scanf("%d",&n);//输入n
        memset(m,0,sizeof(m));//保险起见将m数组全部设为0
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&m[i][j]);//输入矩阵
        for(int i=1,j=1;i<=n && j<=n;i++,j++) k+=m[i][j];//计算主对角线元素之和，主对角线上的元素行和列是一样的
        for(int i=1;i<=n;i++)//循环每一行，计算有重复元素的行
        {
            set<int> a;//set容器
            for(int j=1;j<=n;j++)//循环每一列
            {
                a.insert(m[i][j]);//将每个元素放入set中
            }
            if(a.size()<n) r++;//如果有重复元素，计算重复行的计数变量加一
        }
        for(int i=1;i<=n;i++)//循环每一列，计算有重复元素的列
        {
            set<int> a;//set容器
            for(int j=1;j<=n;j++)//循环每一行
            {
                a.insert(m[j][i]);//将每个元素放入set中
            }
            if(a.size()<n) c++;//如果有重复元素，计算重复列的计数变量加一
        }
        printf("Case #%d: %d %d %d\n",cnt,k,r,c);//按照题目格式输出
    }

    return 0;
}