【NOIP1998】【Luogu1008】三连击(枚举)

举报
小哈里 发表于 2022/05/11 00:48:41 2022/05/11
【摘要】 problem 将1,2,3 … … 9 这九个数分成3组,分别组成3个三位数。且使这 3 个三位数构成1:2:3的比例。求出所有满足的方案 solution1 9重循环枚举九个数。 不剪枝复杂度...

problem

  • 将1,2,3 … … 9 这九个数分成3组,分别组成3个三位数。
  • 且使这 3 个三位数构成1:2:3的比例。
  • 求出所有满足的方案

solution1

9重循环枚举九个数。
不剪枝复杂度(9^9)
剪枝后复杂度O(9!)

#include<iostream>
using namespace std;
int main(){
    for(int a = 1; a <= 9; a++)
        for(int b = 1; b <= 9; b++)
            if(a != b)
                for(int c = 1; c <= 9; c++)
                    if((a!=c) && (b!=c))
                        for(int d = 1; d <= 9; d++)
                            if((a!=d) && (b!=d) && (c!=d))
                                for(int e = 1; e <= 9; e++)
                                    if((a!=e)&&(b!=e)&&(c!=e)&&(d!=e))
                                        for(int f = 1; f <= 9; f++)
                                            if((a!=f)&&(b!=f)&&(c!=f)&&(d!=f)&&(e!=f))
                                                for(int g = 1; g <= 9; g++)
                                                    if((a!=g)&&(b!=g)&&(c!=g)&&(d!=g)&&(e!=g)&&(f!=g))
                                                        for(int h = 1; h <= 9; h++)
                                                            if((a!=h)&&(b!=h)&&(c!=h)&&(d!=h)&&(e!=h)&&(f!=h)&&(g!=h))
                                                                for(int i = 1; i <= 9; i++)
                                                                    if((a!=i)&&(b!=i)&&(c!=i)&&(d!=i)&&(e!=i)&&(f!=i)&&(g!=i)&&(h!=i))
                                                                    {
                                                                        int x = a*100+b*10+c, y = d*100+e*10+f, z = g*100+h*10+i;
                                                                        if(x*2==y && x*3==z)cout<<x<<' '<<y<<' '<<z<<'\n';
                                                                    }
    return 0;
}
  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

solution2

  • 枚举第一个数(范围在123到987之间),就可以计算出第二个和第三个数。
  • 判断三个数的各个位数是否唯一出现(比如满足各位相加为45且相乘为362880,正确性有待证明,桶排或者mapset之类也都可以)。
    复杂度O(900*3);
#include<iostream>
using namespace std;
int main(){
    for(int i = 123; i <= 987; i++){
        int j = 2*i, k = 3*i;
        int s1 = i%10+i/10%10+i/100+j%10+j/10%10+j/100+k%10+k/10%10+k/100;
        int s2 = (i%10)*(i/10%10)*(i/100)*(j%10)*(j/10%10)*(j/100)*(k%10)*(k/10%10)*(k/100);
        if(s1 == 45 && s2 == 362880)cout<<i<<" "<<j<<" "<<k<<"\n";
    }
    return 0;
}
  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。

原文链接:gwj1314.blog.csdn.net/article/details/80601488

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。