[已解决]三 连 击 问题

柿子饼同学

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. bool vis[9] = {1};
   
5. 
   
6. bool isavaliable(int num, bool & vis[9]){
   
7.         memset(vis, 1, sizeof(vis));
   
8.         int nx2 = num * 2;
   
9.         int nx3 = num * 3;
   
10.         for(int i = 0; i < 3; i++){
    
11.                 if(vis[nx2%10]) vis[nx2%10] = 0;
    
12.                 else return 0;
    
13.                 if(vis[nx3%10]) vis[nx3%10] = 0;
    
14.                 else return 0;
    
15.                 nx2 /= 10;
    
16.                 nx3 /= 10;
    
17.         }
    
18.         return 1;
    
19. }
    
20. 
    
21. int main(){
    
22.         ios::sync_with_stdio(0);
    
23.         
    
24.         for(int i = 1; i < 4; i++){ // 可以证明最小的百位数字为 1， 2， 3 不然就超了
    
25.                 for(int j = 1; j < 10; j++){
    
26.                         if(i == j) continue;
    
27.                         for(int k = 1; k < 10; k++){
    
28.                                 if(i == k || j == k) continue;
    
29.                                 int num = i * 100 + j * 10 + k;
    
30.                                 if(isavaliable(num, vis)) cout << num << ' ' << num * 2 << ' ' << num * 3 << endl;
    
31.                         }
    
32.                 }
    
33.         }
    
34. 
    
35.         return 0;
    
36. }

复制代码

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-6-5 23:45:44

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

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <map>
   
4. 
   
5. using std::vector;
   
6. vector<int> digit(int num) {
   
7.     vector<int> res;
   
8.     res.push_back(num / 100);
   
9.     res.push_back((num / 10) % 10);
   
10.     res.push_back(num % 10);
    
11.     return res;
    
12. }
    
13. 
    
14. using std::map;
    
15. using std::cout, std::endl;
    
16. void check(int a, int b, int c) {
    
17.     map<int, bool> numbers;
    
18.     for (int n = 1; n < 10; ++n) numbers[n] = true;
    
19.     vector<int> A = digit(a); // 第一个三位数
    
20.     vector<int> B = digit(b); // 第二个三位数
    
21.     vector<int> C = digit(c); // 第三个三位数
    
22.     for (int i = 0; i < 3; ++i) {
    
23.         if (not A[i] or not B[i] or not C[i]) return;
    
24.         numbers[A[i]] = false;
    
25.         numbers[B[i]] = false;
    
26.         numbers[C[i]] = false;
    
27.     }
    
28.     for (auto [key, value] : numbers) {
    
29.         if (value) {
    
30.             return;
    
31.         }
    
32.     }
    
33.     cout << a << " " << b << " " << c << endl;
    
34. }
    
35. 
    
36. int main(void) {
    
37.     for (int num = 123; num < 999 / 3; ++num) {
    
38.         check(num, num * 2, num * 3);
    
39.     }
    
40.     return 0;
    
41. }

复制代码

1. 192 384 576
   
2. 219 438 657
   
3. 273 546 819
   
4. 327 654 981

复制代码

跳转到最佳答案楼层

liuzhengyuan

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

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

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

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

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

1. #include <iostream>
   
2. 
   
3. bool isNumberUsed[9];
   
4. bool ifAvaliable(int num)
   
5. {
   
6.         for (size_t i = 0; i < 9; i++)
   
7.         {
   
8.                 isNumberUsed[i] = false;
   
9.         }
   
10. 
    
11.         int num1 = num;
    
12.         int num2 = num * 2;
    
13.         int num3 = num * 3;
    
14. 
    
15.         if (num3 >= 1000) return false;
    
16. 
    
17.         for (size_t i = 0; i < 3; i++)
    
18.         {
    
19.                 if (!isNumberUsed[num1 % 10 - 1]) isNumberUsed[num1 % 10 - 1] = true;
    
20.                 else return false;
    
21. 
    
22.                 if (!isNumberUsed[num2 % 10 - 1]) isNumberUsed[num2 % 10 - 1] = true;
    
23.                 else return false;
    
24. 
    
25.                 if (!isNumberUsed[num3 % 10 - 1]) isNumberUsed[num3 % 10 - 1] = true;
    
26.                 else return false;
    
27. 
    
28.                 num1 /= 10;  num2 /= 10; num3 /= 10;
    
29.         }
    
30. 
    
31.         return true;
    
32. }
    
33. 
    
34. 
    
35. 
    
36. int main()
    
37. {
    
38.         for (size_t i = 1; i <= 3; i++)
    
39.         {
    
40.                 for (size_t j = 1; j <= 9; j++)
    
41.                 {
    
42.                         if (i == j) continue;
    
43. 
    
44.                         for (size_t k = 1; k <= 9; k++)
    
45.                         {
    
46.                                 if (i == k || k == j) continue;
    
47. 
    
48.                                 int num = i * 100 + j * 10 + k;
    
49. 
    
50.                                 if (ifAvaliable(num)) std::cout << num << ' ' << num * 2 << ' ' << num * 3 << std::endl;
    
51.                         }
    
52.                 }
    
53.         }
    
54. 
    
55.         return 0;
    
56. }

复制代码

liuzhengyuan

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

傻眼貓咪

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

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <map>
   
4. 
   
5. using std::vector;
   
6. vector<int> digit(int num) {
   
7.     vector<int> res;
   
8.     res.push_back(num / 100);
   
9.     res.push_back((num / 10) % 10);
   
10.     res.push_back(num % 10);
    
11.     return res;
    
12. }
    
13. 
    
14. using std::map;
    
15. using std::cout, std::endl;
    
16. void check(int a, int b, int c) {
    
17.     map<int, bool> numbers;
    
18.     for (int n = 1; n < 10; ++n) numbers[n] = true;
    
19.     vector<int> A = digit(a); // 第一个三位数
    
20.     vector<int> B = digit(b); // 第二个三位数
    
21.     vector<int> C = digit(c); // 第三个三位数
    
22.     for (int i = 0; i < 3; ++i) {
    
23.         if (not A[i] or not B[i] or not C[i]) return;
    
24.         numbers[A[i]] = false;
    
25.         numbers[B[i]] = false;
    
26.         numbers[C[i]] = false;
    
27.     }
    
28.     for (auto [key, value] : numbers) {
    
29.         if (value) {
    
30.             return;
    
31.         }
    
32.     }
    
33.     cout << a << " " << b << " " << c << endl;
    
34. }
    
35. 
    
36. int main(void) {
    
37.     for (int num = 123; num < 999 / 3; ++num) {
    
38.         check(num, num * 2, num * 3);
    
39.     }
    
40.     return 0;
    
41. }

复制代码

1. 192 384 576
   
2. 219 438 657
   
3. 273 546 819
   
4. 327 654 981

复制代码

jhq999

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. 
   
5. 
   
6. bool isavaliable(int num){
   
7.         int i,j,k;
   
8.         int vis=1;
   
9.         i=num/100,j=(num/10)%10,k=num%10;
   
10.         vis|=1<<i,vis|=1<<j,vis|=1<<k;
    
11.         num/=3;
    
12.         i=num/100,j=(num/10)%10,k=num%10;
    
13.          vis|=1<<i,vis|=1<<j,vis|=1<<k;
    
14.          num<<=1;
    
15.          i=num/100,j=(num/10)%10,k=num%10;
    
16.          vis|=1<<i,vis|=1<<j,vis|=1<<k;
    
17.         return (vis==1023);
    
18. }
    
19. 
    
20. int main(){
    
21.         ios::sync_with_stdio(0);
    
22.         int count=0,i,j,k,num;
    
23.         for(num=987;num>=369;num--)
    
24.         {
    
25.             if(num%3||0==num%10||0==(num/10)%10)continue;
    
26.             count+=1;
    
27. 
    
28.             if(isavaliable(num))
    
29.             {
    
30.                cout<<(num/3)<<' ';
    
31.                cout<<((num/3)<<1)<<' '<<num<<endl;
    
32.             }
    
33. 
    
34.         }
    
35.         cout<<count<<endl;
    
36. 
    
37. 
    
38. 
    
39.         return 0;
    
40. }

复制代码

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. 
   
5. 
   
6. bool isavaliable(int num){
   
7.         int i,j,k;
   
8.         int vis=1;
   
9.         i=num/100,j=(num/10)%10,k=num%10;
   
10.         vis|=1<<i,vis|=1<<j,vis|=1<<k;
    
11.         num>>=1;
    
12.         i=num/100,j=(num/10)%10,k=num%10;
    
13.          vis|=1<<i,vis|=1<<j,vis|=1<<k;
    
14.          num*=3;
    
15.          i=num/100,j=(num/10)%10,k=num%10;
    
16.          vis|=1<<i,vis|=1<<j,vis|=1<<k;
    
17.         return (vis==1023);
    
18. }
    
19. 
    
20. int main(){
    
21.         ios::sync_with_stdio(0);
    
22.         int count=0,i,j,k,num;
    
23.         for(num=246;num<=658;num++)
    
24.         {
    
25.             if(num%2||0==num%10||0==(num/10)%10)continue;
    
26.             count+=1;
    
27. 
    
28.             if(isavaliable(num))
    
29.             {
    
30.                cout<<(num>>1)<<' ';
    
31.                cout<<num<<' '<<((num>>1)*3)<<endl;
    
32.             }
    
33. 
    
34.         }
    
35.         cout<<count<<endl;
    
36. 
    
37. 
    
38. 
    
39.         return 0;
    
40. }

复制代码

柿子饼同学

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

或者报错有没有可 ...

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

柿子饼同学

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

谢谢