当前位置：首页 > article >正文

2024蓝桥杯省赛真题-封闭图形个数

article 2025/3/4 5:38:08

在这里插入图片描述
拿到题目，咱们先来分析一手，上来就是封闭图形，那我们直接将这个封闭图形用一个数组记录下来，根据题目要求，我们得到了st数组

int st[10]={1,0,0,0,1,0,1,0,2,1};

这就是0-9数字的封闭的数字

然后下一段，分析一下，它们的封闭图形个数不同，那么封闭图形个数较多的数更大，反之就是值大的数大，如果值相同，就是相等的，就不用排序了

最终输出排序后的结果

现在我们来想，我们这个st数组只记录了一个数字的封闭值，让如果是两位数，三位数呢？
OK 啊，我们直接把他们拆开分别计算不就好了嘛！！

说干就干，开搞，这道题的最大范围是 2e5 一定要看清楚题目的数据范围！！！！要不然不会 ac

是不是先是这样想的呀

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
using ll=long long;
int st[10]={1,0,0,0,1,0,1,0,2,1};
ll arr[N];
int main()
{
	ll n;cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	return 0;
}

那你就错了，劳弟，我们的封闭图形数，并没有和这个数字本身产生关联，那产生关联需要用什么呀？
结构体！！！！

所以我们定义一个结构体，来记录数字和数字的封闭数

struct num{
	int total;
	int val;	
}h[N];

这样定义就好啦，然后顺着上面的思路开始搞

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
using ll=long long;
int st[10]={1,0,0,0,1,0,1,0,2,1};
struct num{
	int total;
	int val;	
}h[N];
int main()
{
	ll n;cin>>n;
	for(ll i=0;i<n;i++)
	{
		cin>>h[i].val;
		ll sum=0;
		ll temp=h[i].val;
		while(temp>0)
		{
			sum+=st[temp%10];
			temp/=10;
		}
		h[i].total=sum;
	}
	for(ll i=0;i<n;i++)
	{
		cout<<h[i].val<<" "<<h[i].total<<" "<<'\n';
	}
	return 0;
}

运行一下康康
在这里插入图片描述
18有2个，29有1个，6有1个，OK t妥了，下面我们来进行这道题的核心！！！

排序！！！直接使用sort库函数就好啦！

根据题目来分析这个cmp函数该怎么写

排序规则：它们的封闭图形个数不同，那么封闭图形个数较多的数更大，反之就是值大的数大，如果值相同，就是相等的，就不用排序了

排序函数：

bool cmp(const num& a, const num& b)
{
    if (a.total == b.total) // 如果封闭数相等，执行里面的语句
    {
        if (a.val == b.val) // 如果值相等，返回 false，表示两个元素相等，不需要交换
        {
            return false;
        }
        else // 如果值不相等，返回 a.val < b.val，表示按值升序排列
        {
            return a.val < b.val;
        }
    }
    else // 如果封闭数不相等，返回 a.total < b.total，表示按封闭数升序排列
    {
        return a.total < b.total;
    }
}

注释说明：
封闭数相等的情况：

如果 a.total 和 b.total 相等，则进一步比较 a.val 和 b.val。

如果 a.val 和 b.val 也相等，则返回 false，表示两个元素相等，不需要交换。

如果 a.val 和 b.val 不相等，则返回 a.val < b.val，表示按 val 升序排列。

封闭数不相等的情况：

如果 a.total 和 b.total 不相等，则直接返回 a.total < b.total，表示按 total 升序排列。

最重要的完成了，最后输出一手就好了！

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
using ll=long long;
int st[10]={1,0,0,0,1,0,1,0,2,1};
struct num{
	int total;
	int val;	
}h[N];
bool cmp(const num& a,const num& b)
{
	if(a.total==b.total)
	{
		if(a.val==b.val)
		{
			return false;
		}
		else {
			return a.val<b.val;
		}
	}
	else
	{
		return a.total<b.total; 
	 } 
}
int main()
{
	ll n;cin>>n;
	for(ll i=0;i<n;i++)
	{
		cin>>h[i].val;
		ll sum=0;
		ll temp=h[i].val;
		while(temp>0)
		{
			sum+=st[temp%10];
			temp/=10;
		}
		h[i].total=sum;
	}
	sort(h,h+n,cmp);
	for(ll i=0;i<n;i++)
	{
		cout<<h[i].val<<" ";
	}
	return 0;
}