洛谷P1618 三连击（升级版）

青旅半醒 2022-06-01 11:57 133阅读 0赞

## 题目描述 ##

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

//感谢黄小U饮品完善题意

## 输入输出格式 ##

输入格式：

三个数，A B C。

输出格式：

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

## 输入输出样例 ##

输入样例\#1： 复制

1 2 3

输出样例\#1： 复制

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

## 说明 ##

保证A<B<C

AC代码

#include<map>
    #include<stdio.h>
    #include<iterator>
    #include<vector>
    #include<iostream>
    using namespace std;
    int sum;
    bool check(int a,int b,int c)
    {
    	map<int,int> Map;
    	while (a)
    	{
    		int a1 = a % 10;
    		if (!a1) return false;
    		map<int, int>::iterator it = Map.find(a1);
    		if (it != Map.end())
    			return false;
    		else
    			Map.insert(pair<int, int>(a1, a1));
    		a /= 10;
    	}
    	while (b)
    	{
    		int b1 = b % 10;
    		if (!b1) return false;
    		map<int, int>::iterator it = Map.find(b1);
    		if (it != Map.end())
    			return false;
    		else
    			Map.insert(pair<int, int>(b1, b1));
    		b /= 10;
    	}
    	while (c)
    	{
    		int c1 = c % 10;
    		if (!c1) return false;
    		map<int, int>::iterator it = Map.find(c1);
    		if (it != Map.end())
    			return false;
    		else
    			Map.insert(pair<int, int>(c1, c1));
    		c /= 10;
    	}
    return true;
    }
    
    int main()
    {
        int A,B,C;
        cin>>A>>B>>C;
    	for (int ans = 123; ans <=329 ; ans++)
    	{
    		if (ans % 100==0 || ans % 110==0 || ans % 111==0)
    			continue;
    		int ans2 = (ans*B)/A, ans3 = (ans*C)/A;
    		if (check(ans, ans2, ans3))
    		{
    			printf("%d %d %d\n", ans, ans2, ans3);
    			sum++;
    		}
    	}
    	if(!sum)
    	cout<<"No!!!";
    		return 0;
    }

大神的简短版本

[https://www.luogu.org/blog/user6596/solution-p1618][https_www.luogu.org_blog_user6596_solution-p1618]

学到的新知识：next\_permutation是C++全排列的STL函数

另附一篇讲解这个函数的博客:[http://blog.sina.com.cn/s/blog\_9f7ea4390101101u.html][http_blog.sina.com.cn_s_blog_9f7ea4390101101u.html]

#include <cstdio>
    #include <algorithm>                                                  //为调用之后的函数next_permutation
    using namespace std;
    int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int main(void){
        int x, y, z, q, w, e; bool b = 0;
        scanf("%d %d %d", &x, &y, &z);
        do{
            q = a[1] * 100 + a[2] * 10 + a[3];
            w = a[4] * 100 + a[5] * 10 + a[6];
            e = a[7] * 100 + a[8] * 10 + a[9];
            if (q * y * z == w * x * z  &&  w * x * z == e * x * y  &&  q * y * z == e * x * y)
            printf("%d %d %d\n", q, w, e), b = 1;
        }while (next_permutation(a + 1, a + 10));                   //按字典序排下一种可能，继续判断
        if (b == 0) printf("No!!!");                                           //三个!,三个!,三个!，重要的事情说三遍
        return 0;
    }

[https_www.luogu.org_blog_user6596_solution-p1618]: https://www.luogu.org/blog/user6596/solution-p1618
[http_blog.sina.com.cn_s_blog_9f7ea4390101101u.html]: http://blog.sina.com.cn/s/blog_9f7ea4390101101u.html