题解 P1008 【三连击】
本题正解是暴力枚举
先引用我们老师的一句话：(无恶意)
不会吧不会吧，不会还有人不会写三连击吧！
废话不多说，开始解题：
- 理解题目和做题思路
P1008 三连击 题目链接：https://www.luogu.com.cn/problem/P1008
题目意思：把
解题思路：枚举
如果你看到这里恍然大悟，请先试着做一做，不会再继续看下去。
- 投机取巧
众所周知，三连击在洛谷还有一个升级版，就是把
#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 的问题。其它细节我会写进注释里，下面给出
#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作用也一样，可以利用这个方法缩短代码。
- 优化
什么？可以优化？是的，因为
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;
}不过这个代码有个小问题，面对
其实原来的时间复杂度最大是