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

拿到题目，咱们先来分析一手，上来就是封闭图形，那我们直接将这个封闭图形用一个数组记录下来，根据题目要求，我们得到了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; }

------谨记-lou硕(呆版)