P1618 三连击(升级版)
题目
将 \(1, 2,\ldots, 9\) 共 \(9\) 个数分成三组,分别组成三个三位数,且使这三个三位数的比例是 \(A:B:C\),试求出所有满足条件的三个三位数,若无解,输出 No!!!
。
输入
三个数,\(A,B,C\)。
输出
若干行,每行 \(3\) 个数字。按照每行第一个数字升序排列。
样例
输入
1 2 3
输出
192 384 576
219 438 657
273 546 819
327 654 981
提示
保证 \(A<B<C\)。
思路
题目要求从所有的三位数集合中统计满足比例“\(A:B:C\)”的数,且 \(1,2,3, \cdots ,9\) 九个数字构成三个数字的 \(9\) 位。可使用三重循环分别枚举三位数,判断这三个数字的比例是否合法。接下来判断三个三位数分离出来的数字是否不重不漏地组成 \(1\) 到 \(9\) 这九个数字。显然,时间复杂度过高,且有不必要的枚举对象。
于是,我们可以只枚举“第一个三位数”,且该三位数的集合很容易得知最小是 \(123\),最大是 \(987\),于是数字集合是从 \(123\) 枚举到 \(987\),进而通过比例计算出其他两个三位数。接着逐一判断三个三位数分离出来的数字是否不重不漏地组成 \(1\) 到 \(9\) 这九个数字。借助打标记的方法判断每一个数字是否存在。如果不满足约束条件,则说明“第一个三位数”设置不合适,于是使用 continue
继续确定下一个“第一个三位数”。如果满足约束条件,则把当前分离出来的数字打上标记。
同时我们会想到,存在三位数集合中没有满足约束条件的情况,于是还应该加一个变量作为问题解的存在性标记进行判断。
代码
#include <bits/stdc++.h>
using namespace std;
bool b[20], flag;
int j, k, sum, A, B, C;
int main()
{
scanf("%d %d %d", &A, &B, &C);
for (int i = 123; i <= 987 * A / C; i ++ )
{
memset(b, 0, sizeof(b));
sum = 0;
b[i % 10] = 1;
b[i / 10 % 10] = 1;
b[i / 100] = 1;
j = i * B / A;
if (b[j % 10] == 1)
continue;
else
b[j % 10] = 1;
if (b[j / 10 % 10] == 1)
continue;
else
b[j / 10 % 10] = 1;
if (b[j / 100] == 1)
continue;
else
b[j / 100] = 1;
k = i * C / A;
if (b[k % 10] == 1)
continue;
else
b[k % 10] = 1;
if (b[k / 10 % 10] == 1)
continue;
else
b[k / 10 % 10] = 1;
if (b[k / 100] == 1)
continue;
else
b[k / 100] = 1;
for (int v = 1; v <= 9; v ++ )
sum += b[v];
if (sum == 9)
{
flag = 1;
printf("%d %d %d\n", i, j, k);
}
}
if (flag == 0)
printf("No!!!");
return 0;
}
标签:123,连击,数字,三位数,枚举,三个,P1618,升级版
From: https://www.cnblogs.com/IronMan-PZX/p/18124934