posted on 2020-11-12 17:25:10 | under 题解 | source
2023 编者注：请尊重历史。
本题正解是暴力枚举
先引用我们老师的一句话：(无恶意)
不会吧不会吧，不会还有人不会写三连击吧！
废话不多说，开始解题：
- 理解题目和做题思路
P1008 三连击 题目链接：https://www.luogu.com.cn/problem/P1008
题目意思：把\(1,2,3,4,5,6,7,8,9\)(注意没有\(0\))，拆分成\(3\)组，每组\(3\)个数字，组成\(3\)个三位数，让这\(3\)个三位数的比成\(1:2:3\)的关系，并把符合这些条件的(\(4\)组)数字输出，注意行尾换行。
解题思路：枚举\((100,333)\)之间的所有整数，算出另外\(2\)个数，检查它们是否重复。如果不重复，输出这\(3\)个数，并换行。
如果你看到这里恍然大悟，请先试着做一做，不会再继续看下去。
- 投机取巧
众所周知，三连击在洛谷还有一个升级版，就是把\(1:2:3\)改成了\(A:B:C\)。好巧不巧，升级版的输出样例，刚好就是这道题的答案。所以，我们的代码，可以简化成这样：
#include<iostream>
int main(){
std::cout<<"192 384 576\n219 438 657\n273 546 819\n327 654 981";
}
PHP 的好处这时候就体现出来了:
192 384 576
219 438 657
273 546 819
327 654 981
真不错，这个输出样例真不错。
- 暴力枚举
相信这是你们第一时间想到的办法。九重 for 循环，或者三重 for 循环，一个一个数慢慢枚举，最后绝对能出答案。就是时间有点长，会 TLE，得在本机运行之后交答案。
//代码不写了，太长了，写了你们也不会用。
- 真正的AC方法
主要思想还是枚举，只不过是枚举一个数，算出另外两个数，检查重复，输出结果。这种算法能从根源上解决 TLE 的问题。其它细节我会写进注释里，下面给出\(AC\) \(Code\)：
#include<cstdio>//唯一一个头文件
using namespace std;
bool chongfu(int a,int b,int c);//好习惯
bool panduan[10];//要算重复，用这个数组做桶
int sum,A=1,B=2,C=3,dw1,a,b,c,flag=1,i,j;//少写一点int
//dw1指单位"1"，我自己发明的说法。比如说2:3:5=6:X:Y,算出单位"1"是6/2=3，用单位"1"推出X=3*3=9、Y=5*3=15，就大概是这么一个东西。
int main(){
//scanf("%d%d%d",&A,&B,&C);//你敢直接交到升级版吗？
//开始枚举第一个数
for(i=100;i<=333;i++){//循环上下限应该都能想出来吧
if(i%A) continue;//i%A = i%A!=0，
//上面这个语句在普通版没用，但在升级版能减少很多计算
//具体作用：单位"1"算出来是不是整数，不是就下一个
dw1=i/A,a=dw1*A,b=dw1*B,c=dw1*C;//好看，整齐
//普通版可以改成：int a=i,b=i*2,c=i*3;
if(chongfu(a,b,c)){
printf("%d %d %d\n",a,b,c);//输出
flag=0;//flag倒下
}
}
if(flag) printf("No!!!");//flag没倒，输出NO!!!
return 0;//好习惯从你我做起
}
bool chongfu(int a,int b,int c){
for(j=0;j<10;j++) panduan[j]==0;//重置数组
sum=0;//计算数字个数用的变量
//数位相离+桶排序思想
while(a){//a = a!=0
panduan[a%10]=1;//a%10就是a的最后一位
a/=10;//去掉最后一位
sum++;//统计数字个数
}
while(b){
panduan[b%10]=1;
b/=10;
sum++;
}
while(c){
panduan[c%10]=1;
c/=10;
sum++;
}
if(sum>9) return 0;//数字不是9个，直接退出
if(panduan[0]) return 0;//找到了0，退出
for(j=1;j<10;j++){
if(!panduan[j]) return 0;//有一个数字没有发现，是因为别的数字重复了
//!panduan[j] = panduan[j]==0
}
return 1;//经过这么多判断活了下来，就是没重复了
}
经过测试，这份代码普通版和升级版(去掉scanf前面的//)都能过，升级版并没有需要约分的数据。
小知识：a==0与!a作用一样，a!=0与a作用也一样，可以利用这个方法缩短代码。
- 优化
什么？可以优化？是的，因为\((1,9)\)这\(9\)个数字的和与积是固定的，所以算重复的部分，可以变成这样：
bool chongfu(int a,int b,int c){
int he=0,j=1;
while(a){
he+=a%10;
ji*=a%10;
a/=10;
}
while(b){
he+=b%10;
ji*=b%10;
b/=10;
}
while(c){
he+=c%10;
ji*=c%10;
c/=10;
}
return he==45&&ji==362880;
}
不过这个代码有个小问题，面对\(124445799\)时会出现意想不到的错误。即\(1 + 2 + 4 + 4 + 4 + 5 + 7 + 9 + 9 = 45\)和\(1 \times 2 \times 4 \times 4 \times 4 \times 5 \times 7 \times 9 \times 9= 362880\)。不过，除非输入给的是\(124:445:799\)这种变态数据，不然你很难遇见这组数，所以请放心。
其实原来的时间复杂度最大是\(O(10+9+9)\)(重置+数位相离+判断)，优化后也只不过变成了\(O(9+9)\)(算和+算积)，对于1秒执行数亿条的计算机来说，差不了多少，不做这个优化也行。