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

P1618三连击（暴力+枚举）

news 2026/4/15 23:27:45

P1618 三连击（升级版）

题目描述

将1,2,…,91, 2,\ldots, 91,2,…,9共999个数分成三组，分别组成三个三位数，且使这三个三位数的比例是A:B:CA:B:CA:B:C，试求出所有满足条件的三个三位数，若无解，输出No!!!。

输入格式

三个数，A,B,CA,B,CA,B,C。

输出格式

若干行，每行333个数字。按照每行第一个数字升序排列。

输入输出样例 #1

输入 #1

1 2 3

输出 #1

192 384 576 219 438 657 273 546 819 327 654 981

说明/提示

保证0≤A<B<C≤9990 \le A<B<C \le 9990≤A<B<C≤999。

upd 2022.8.3\text{upd 2022.8.3}upd 2022.8.3：新增加二组 Hack 数据。

【题解】

核心思想

根据输入的比例 A:B:C，枚举倍数 i 生成三个三位数，判断这三个数是否恰好由数字 1∼9 不重复、不遗漏组成。

具体步骤

输入与特判

读入三个整数 A,B,C。
若其中存在 0，直接判定无解。

枚举倍数生成数字

枚举正整数 i，计算 x=Ai, y=Bi, z=C*i。
若任意数字超过 999，停止枚举。
若任意数字不足 100，跳过当前情况。

数字合法性判断

将 x,y,z 转为字符串并拼接成一个 9 位字符串。
对字符串整体排序。
若排序结果等于 “123456789”，说明恰好使用 1∼9 各一次，为合法答案。

输出结果

按顺序输出所有合法解。
若无任何解，输出 No!!!。

关键技巧

利用字符串拼接 + 排序，简洁判断数字 1∼9 是否全部出现且不重复。
利用比例关系 x:y:z=A:B:C，避免浮点运算，保证精度与效率。

#include<bits/stdc++.h>usingnamespacestd;inta,b,c,flag=0;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>a>>b>>c;if(a==0||b==0||c==0){cout<<"No!!!\n";return0;}for(inti=1;;i++){intx=a*i,y=b*i,z=c*i;if(x>987||y>987||z>987)break;if(x<123||y<123||z<123)continue;string s=to_string(x)+to_string(y)+to_string(z);sort(s.begin(),s.end());if(s=="123456789"){flag=1;cout<<x<<" "<<y<<" "<<z<<endl;}}if(!flag)cout<<"No!!!"<<endl;return0;}