[已解决]三 连 击 问题

柿子饼同学

题目 https://www.luogu.com.cn/problem/P1008
我的代码如下 ， 思路是先枚举出一个最小的 ， 然后再看第二个第三个是否可行
但是它报错了 ， 检查不出来。。。

#include <bits/stdc++.h>
using namespace std;

bool vis[9] = {1};

bool isavaliable(int num, bool & vis[9]){
        memset(vis, 1, sizeof(vis));
        int nx2 = num * 2;
        int nx3 = num * 3;
        for(int i = 0; i < 3; i++){
                if(vis[nx2%10]) vis[nx2%10] = 0;
                else return 0;
                if(vis[nx3%10]) vis[nx3%10] = 0;
                else return 0;
                nx2 /= 10;
                nx3 /= 10;
        }
        return 1;
}

int main(){
        ios::sync_with_stdio(0);
        
        for(int i = 1; i < 4; i++){ // 可以证明最小的百位数字为 1， 2， 3 不然就超了
                for(int j = 1; j < 10; j++){
                        if(i == j) continue;
                        for(int k = 1; k < 10; k++){
                                if(i == k || j == k) continue;
                                int num = i * 100 + j * 10 + k;
                                if(isavaliable(num, vis)) cout << num << ' ' << num * 2 << ' ' << num * 3 << endl;
                        }
                }
        }

        return 0;
}

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-6-5 23:45:44

我的思路：
题目提示：
（一）1：2：3 的比例分组
（二）三位数

所以答案必然在 100 至 999 之间，而且最大数的比例是最小数的三倍，那么最小数必然小于 999 / 3（因为要分成三等份）
以上提示可以得出，最小数在 123 ~ 999/3 之间（循环次数大大降低至 210 次）
接下来把最小数分成三个三位数，如：最小数、最小数*2，最小数*3
然后再判断是否三个三位数所有数字没有重复即可。

#include <iostream>
#include <vector>
#include <map>

using std::vector;
vector<int> digit(int num) {
    vector<int> res;
    res.push_back(num / 100);
    res.push_back((num / 10) % 10);
    res.push_back(num % 10);
    return res;
}

using std::map;
using std::cout, std::endl;
void check(int a, int b, int c) {
    map<int, bool> numbers;
    for (int n = 1; n < 10; ++n) numbers[n] = true;
    vector<int> A = digit(a); // 第一个三位数
    vector<int> B = digit(b); // 第二个三位数
    vector<int> C = digit(c); // 第三个三位数
    for (int i = 0; i < 3; ++i) {
        if (not A[i] or not B[i] or not C[i]) return;
        numbers[A[i]] = false;
        numbers[B[i]] = false;
        numbers[C[i]] = false;
    }
    for (auto [key, value] : numbers) {
        if (value) {
            return;
        }
    }
    cout << a << " " << b << " " << c << endl;
}

int main(void) {
    for (int num = 123; num < 999 / 3; ++num) {
        check(num, num * 2, num * 3);
    }
    return 0;
}

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

跳转到最佳答案楼层

liuzhengyuan

先给个建议：vis是全局变量，所以不需要作为函数的参数，也可以在函数中访问此变量。

或者报错有没有可能是因为 两个变量重名？

还要加一个 num3 是否为 3 位数的判断

函数中 nx2 % 10 要减 1
而且你没有对num 的查重判断（也就是初始数）

我写了一个代码，洛谷通过了：

#include <iostream>

bool isNumberUsed[9];
bool ifAvaliable(int num)
{
        for (size_t i = 0; i < 9; i++)
        {
                isNumberUsed[i] = false;
        }

        int num1 = num;
        int num2 = num * 2;
        int num3 = num * 3;

        if (num3 >= 1000) return false;

        for (size_t i = 0; i < 3; i++)
        {
                if (!isNumberUsed[num1 % 10 - 1]) isNumberUsed[num1 % 10 - 1] = true;
                else return false;

                if (!isNumberUsed[num2 % 10 - 1]) isNumberUsed[num2 % 10 - 1] = true;
                else return false;

                if (!isNumberUsed[num3 % 10 - 1]) isNumberUsed[num3 % 10 - 1] = true;
                else return false;

                num1 /= 10;  num2 /= 10; num3 /= 10;
        }

        return true;
}



int main()
{
        for (size_t i = 1; i <= 3; i++)
        {
                for (size_t j = 1; j <= 9; j++)
                {
                        if (i == j) continue;

                        for (size_t k = 1; k <= 9; k++)
                        {
                                if (i == k || k == j) continue;

                                int num = i * 100 + j * 10 + k;

                                if (ifAvaliable(num)) std::cout << num << ' ' << num * 2 << ' ' << num * 3 << std::endl;
                        }
                }
        }

        return 0;
}

liuzhengyuan

这应该是我第一次写这么长的回答

傻眼貓咪

我的思路：
题目提示：
（一）1：2：3 的比例分组
（二）三位数

所以答案必然在 100 至 999 之间，而且最大数的比例是最小数的三倍，那么最小数必然小于 999 / 3（因为要分成三等份）
以上提示可以得出，最小数在 123 ~ 999/3 之间（循环次数大大降低至 210 次）
接下来把最小数分成三个三位数，如：最小数、最小数*2，最小数*3
然后再判断是否三个三位数所有数字没有重复即可。

#include <iostream>
#include <vector>
#include <map>

using std::vector;
vector<int> digit(int num) {
    vector<int> res;
    res.push_back(num / 100);
    res.push_back((num / 10) % 10);
    res.push_back(num % 10);
    return res;
}

using std::map;
using std::cout, std::endl;
void check(int a, int b, int c) {
    map<int, bool> numbers;
    for (int n = 1; n < 10; ++n) numbers[n] = true;
    vector<int> A = digit(a); // 第一个三位数
    vector<int> B = digit(b); // 第二个三位数
    vector<int> C = digit(c); // 第三个三位数
    for (int i = 0; i < 3; ++i) {
        if (not A[i] or not B[i] or not C[i]) return;
        numbers[A[i]] = false;
        numbers[B[i]] = false;
        numbers[C[i]] = false;
    }
    for (auto [key, value] : numbers) {
        if (value) {
            return;
        }
    }
    cout << a << " " << b << " " << c << endl;
}

int main(void) {
    for (int num = 123; num < 999 / 3; ++num) {
        check(num, num * 2, num * 3);
    }
    return 0;
}

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

jhq999

#include <bits/stdc++.h>
using namespace std;



bool isavaliable(int num){
        int i,j,k;
        int vis=1;
        i=num/100,j=(num/10)%10,k=num%10;
        vis|=1<<i,vis|=1<<j,vis|=1<<k;
        num/=3;
        i=num/100,j=(num/10)%10,k=num%10;
         vis|=1<<i,vis|=1<<j,vis|=1<<k;
         num<<=1;
         i=num/100,j=(num/10)%10,k=num%10;
         vis|=1<<i,vis|=1<<j,vis|=1<<k;
        return (vis==1023);
}

int main(){
        ios::sync_with_stdio(0);
        int count=0,i,j,k,num;
        for(num=987;num>=369;num--)
        {
            if(num%3||0==num%10||0==(num/10)%10)continue;
            count+=1;

            if(isavaliable(num))
            {
               cout<<(num/3)<<' ';
               cout<<((num/3)<<1)<<' '<<num<<endl;
            }

        }
        cout<<count<<endl;



        return 0;
}

#include <bits/stdc++.h>
using namespace std;



bool isavaliable(int num){
        int i,j,k;
        int vis=1;
        i=num/100,j=(num/10)%10,k=num%10;
        vis|=1<<i,vis|=1<<j,vis|=1<<k;
        num>>=1;
        i=num/100,j=(num/10)%10,k=num%10;
         vis|=1<<i,vis|=1<<j,vis|=1<<k;
         num*=3;
         i=num/100,j=(num/10)%10,k=num%10;
         vis|=1<<i,vis|=1<<j,vis|=1<<k;
        return (vis==1023);
}

int main(){
        ios::sync_with_stdio(0);
        int count=0,i,j,k,num;
        for(num=246;num<=658;num++)
        {
            if(num%2||0==num%10||0==(num/10)%10)continue;
            count+=1;

            if(isavaliable(num))
            {
               cout<<(num>>1)<<' ';
               cout<<num<<' '<<((num>>1)*3)<<endl;
            }

        }
        cout<<count<<endl;



        return 0;
}

柿子饼同学

liuzhengyuan 发表于 2022-6-5 23:25
先给个建议：vis是全局变量，所以不需要作为函数的参数，也可以在函数中访问此变量。

或者报错有没有可 ...

谢谢~
话说 , 函数里改变全局变量只是在函数里改变吧
后面就改不了了

柿子饼同学

jhq999 发表于 2022-6-6 15:09

谢谢