洛谷 P1618 三连击（升级版）【DFS/next_permutation()/技巧性枚举/sprintf】
2024-10-21 14:29:01
【链接】：https://www.luogu.org/problemnew/show/P1618
题目描述
将1，2，…，9共9个数分成三组，分别组成三个三位数，且使这三个三位数的比例是A:B:C，试求出所有满足条件的三个三位数，若无解，输出“No!!!”。
//感谢黄小U饮品完善题意
输入输出格式
输入格式：
三个数，A B C。
输出格式：
若干行，每行3个数字。按照每行第一个数字升序排列。
输入输出样例
说明
保证A<B<C
【分析】：
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int a,b,c,num,i1,i2,i3,flag=;
cin>>i1>>i2>>i3;
for(num=;num<=;num++){
a=i1*num;b=i2*num;c=i3*num;
if((a/+a/%+a%+b/+b/%+b%+c/+c/%+c%==)&&((a/)*(a/%)*(a%)*(b/)*(b/%)*(b%)*(c/)*(c/%)*(c%)==)){
cout<<a<<" "<<b<<" "<<c<<endl;
flag=;
}
}
if(flag==){
cout<<"No!!!";
}
return ; }
普通枚举
1.
枚举每一个可能的数，将三个倍数保存在数组中，再排序，最后通过和标准的“123456789”比较，如果相同，则满足条件。这样用一个常量数组，可以简化计算，不需要过多的思考。所以说常量数组大法真的好~因为之前做过三连击的简单版，就有了思维定式，枚举总是从123开始，所以最后一个（数据是123 456 789）总是错。最后一个过不去的同学可以试试从1开始枚举，就会过去了。
#include <bits/stdc++.h> using namespace std; char stdanard[]=""; int a,b,c; int main()
{
int flag=;
cin>>a>>b>>c;
for(int i=;i<=;i++)
{
char buf[];//开大防止溢出
sprintf(buf,"%d%d%d",a*i,b*i,c*i);
sort(buf,buf+);
if(strcmp(stdanard,buf)==)
{
flag=;
printf("%d %d %d\n",a*i,b*i,c*i);
}
}
if(flag) puts("No!!!");
return ;
}
sprintf
2.我和大部分人思路基本一样，不一样的地方在于对三个数组成的9个数的拆分上，我用的是sstream头文件，将三个数放到一个字符串中去，这样就不用%或者/去费力拆分了,写起来更优雅，然后将字符串每个数加起来 乘起来，即可验证是否为不同的9个数。
/*
对三个数组成的9个数的拆分上，用的是sstream头文件，
将三个数放到一个字符串中去，
这样就不用%或者/去费力拆分了,写起来更优雅，
然后将字符串每个数加起来 乘起来，即可验证是否为不同的9个数。
*/
#include <bits/stdc++.h> using namespace std; stringstream ss;
string str;
int cnt=;
int a,b,c; int main()
{
cin>>a>>b>>c; for(int i=;i<=;i++)
{
int j=i*b/a;
int k=i*c/a;
int sum=;
int pro=;
ss<<i<<j<<k;
ss>>str;
ss.clear(); for(int j=;j<;j++)
{
sum+=str[j]-'';
pro*=str[j]-'';
} if(sum== && pro==)
{
cout<<i<<" "<<j<<" "<<k<<" "<<endl;
cnt++;
} }
if(!cnt) puts("No!!!");
return ;
}
stringstream
3.
/*
其实判断是否相等不需要if（a==b&&b==c...）这样乱七八糟的打一大坨，一个数组就能完成。如下：
*/
#include <bits/stdc++.h> using namespace std; int d[];//数组d判断位数是否相等。
int main()
{
float x,y,z;
int a,b,c,t=,j=;//j判断是否有解
cin>>x>>y>>z;//即A、B、C
for(a=;a<=;a++)//枚举最小的那个数
{
b=y*a/x;
c=z*a/x;
d[a/]++;
d[(a%)/]++;
d[a%]++; d[b/]++;
d[(b%)/]++;
d[b%]++; d[c/]++;
d[(c%)/]++;
d[c%]++;
for(int bb=;bb<=;bb++)
{
if(d[bb]==) t=;//由于总共只有九个数字，若有一个数没有出现，就说明有数字重复了。
d[bb]=;//归零
}
if(t==) {cout<<a<<" "<<b<<" "<<c<<endl;j=;}//若有解，输出a、b、c
t=;
}
if(!j) cout<<"No!!!";
return ;
}
数组技巧性枚举
# include <stdio.h>
# define MUL(x) (x%)*(x/%)*(x/) //一个三位数x所包含的3个数的乘积为MUL(x)
# define ADD(x) (x%)+(x/%)+(x/) //一个三位数x所包含的3个数的总和为ADD(x)
const product=********; //数字1—9的乘积为product
const int sum=++++++++; //数字1—9的总和为sum
int main()
{
int A,B,C,a=,Yes=; //变量Yes用于检测是否有解
scanf("%d %d %d",&A,&B,&C); //输入3个三位数的比例A:B:C(A<B<C且为最简比)
while(++a*A<); //保证这3个数中最小的数是三位数
for(;a*C<;a++) //保证这3个数中最大的数是三位数
if(product==MUL(a*A)*MUL(a*B)*MUL(a*C) //倘若它们所包含的9个数的乘积恰好为product
&& sum==ADD(a*A)+ADD(a*B)+ADD(a*C)) //并且总和恰好为sum时，说明没有重复数字和0
Yes=printf("%i %i %i\n",a*A,a*B,a*C); //输出这3个由1—9组成的三位数，并给Yes赋值
if(!Yes) //若无解
puts("No!!!"); //则输出“No!!!”
return ;
}
技巧性枚举
4.
#include<iostream>
using namespace std;
int x[]={},a,b,c; //x[1]~x[9]为当前位置的数字 先把三个三位数合成一个9(10)位数的大数组
bool used[]={},ans=false;
//used数组表示该数字的使用情况 避免重复 ans判断是否有答案
int cons(int m){ //将数组拆分成三个三位数
int sum=;
for(int i=*m-;i<=*m;i++){
sum*=;
sum+=x[i];
}
return sum;
}
void solve(int n){
if(n==&&cons()*b==cons()*a&&cons()*c==cons()*a){ //当n=10时x数组数字存满 开始判断
cout<<cons()<<" "<<cons()<<" "<<cons()<<endl;
ans=true;
return;
}
for(int i=;i<=;i++){
if(!used[i]){
x[n]=i; //存数字
used[i]=; //该数字被使用
solve(n+); //下一位继续调用
used[i]=; //恢复
}
}
return;
}
int main(){
cin>>a>>b>>c;
solve(); //开始搜索
if(!ans) cout<<"No!!!"; //ans!=true即输出"No!!!"
return ;
}
DFS
5.STL中的next_permutation函数提供下一个排列功能，是用生成法实现的，所以速度要比搜索快多了。
#include<bits/stdc++.h>
using namespace std;
int a[]={,,,,,,,,,};
int main()
{
int A,B,C,h=;
cin>>A>>B>>C;
int t=A*B*C;
A=t/A;
B=t/B;
C=t/C;
do{
if((*a[]+*a[]+a[])*A==(*a[]+*a[]+a[])*B&&(*a[]+*a[]+a[])*A==(*a[]+*a[]+a[])*C)//如果符合比例；
{
cout<<a[]<<a[]<<a[]<<" "<<a[]<<a[]<<a[]<<" "<<a[]<<a[]<<a[]<<endl;//输出
h++;
}
}while(next_permutation(a+,a+));//STL中的下一个排列函数；
if(h==) cout<<"No!!!";//没有解输出NO；
return ;
}
next_permutation()
#include<iostream>
#include<algorithm>
using namespace std;
int a[] = { , , , , , , , , };
bool isSame(int v[], int a[]) {
for (int i = ; i != ; i++)
if (v[i] != a[i])
return false;
return true;
}
int main()
{
int A, B, C;
int visit[] = { };
int pos;
bool flag = false;
cin >> A >> B >> C;
do {
int x = a[] * + a[] * + a[];
int y = a[] * + a[] * + a[];
int z = a[] * + a[] * + a[];
int a[] = { x, y, z };
sort(a, a + );
if (!isSame(visit, a)) {
if ((double)y / x == (double)B / A && (double)z / x == (double)C / A && (double)z / y == (double)C / B) {
cout << a[] << " " << a[] << " " << a[] << endl;
flag = true;
}
}
} while (next_permutation(a, a + ));
if (flag == false)
cout << "No!!!" << endl;
return ;
}
5.2
最新文章
- ubuntu下载工具uget和aria2
- Nancy之基于Nancy.Hosting.Aspnet的小Demo
- shell脚步传参
- HTML5实现下载文件且指定下载文件名
- 爬虫Larbin解析(一)——Larbin配置与使用
- javascript date部分
- Apache & WebDav 配置（二）
- [置顶] WPF数据修改demo
- Maven学习专题--Maven入门及安装
- [DeeplearningAI笔记]ML strategy_2_2训练和开发/测试数据集不匹配问题
- CentOS上PHP完全卸载
- 解密JavaScript闭包
- 【机器学习】Google机器学习工程的43条最佳实践
- tarjan强连通算法
- 唯美PS转手绘之SAI篇_百度经验
- YII2十三大特性
- jsplumb流程器使用2
- 2017-2018-1 20155331 课下测试（ch10）
- 学以致用:Python爬取廖大Python教程制作pdf
- 面试-存储过程与Insert的性能比较