第七届蓝桥杯（国赛）——凑平方数-白红宇的个人博客

第七届蓝桥杯（国赛）——凑平方数

发布日期：2021-05-12 21:37:49 浏览次数：10 分类：精选文章

本文共 1181 字，大约阅读时间需要 3 分钟。

问题描述

把 0 ~ 9 这 10 个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。

比如：0，36，5948721

再比如：{1098524736}；{1，25，6390784}；{0，4，289，15376} 等等…

注意，0 可以作为独立的数字，但不能作为多位数字的开始。

分组时，必须用完所有的数字，不能重复，不能遗漏。

如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？

答案提交

注意：需要提交的是一个整数，不要填写多余内容。

答案：300

题解

DFS：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long LL;LL used[10], tmp[10], s[10], k;set
         
           cnt;void dfs(int u){ if(u == 10) { copy(used, used + k, tmp); // 将 used 数组中的内容，复制给 tmp 数组 sort(tmp, tmp + k); string ans = ""; for (int i = 0; i < k; i ++) { char s[20]; sprintf(s, "%lld", tmp[i]); // 将数字转换成字符串 ans += s; ans += '-'; // 每个平方数都以 '-' 隔开 } cnt.insert(ans); // 存储答案，并去重 return; } if(s[u] == 0) // 0 不能作为数字的开头 { used[k ++] = 0; dfs(u + 1); used[-- k] = 0; } else { LL t = 0; for (int i = u; i < 10; i ++) { t = t * 10 + s[i]; LL x = sqrt(t); if(x * x == t) { used[k ++] = t; dfs(i + 1); used[-- k] = 0; } } }}int main(){ for (int i = 0; i < 10; i ++) s[i] = i; do { dfs(0); k = 0; }while(next_permutation(s, s + 10)); cout << cnt.size() << endl; return 0;}

ps：不明白为什么要复制一个 tmp 数组，但是不这样做，答案又不对，网上也没个大神解释一下 😭

上一篇：第六届蓝桥杯（国赛）——密文搜索

下一篇：第六届蓝桥杯（国赛）——完美正方形

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章