洛谷 P1008 [NOIP1998 普及组] 三连击

【题目链接】

洛谷 P1008 [NOIP1998 普及组] 三连击

【题目考点】

1. 枚举

2. 数字拆分

【解题思路】

三个由1~9组成的3位数字，满足1：2：3。那么第一个数字最小为100，最大不会超过333（因为如果第一个数字大于333，那么第三个数字会大于1000，无法构成3位数）
设一个布尔型vis数组，vis[i]表示数字i是否出现过。1~9这9个数字每个数字只能出现一次。
在100~333范围内枚举第一个数字，检查该数字是否可用，步骤如下：

• 对该数字做数字拆分：
  • 如果发现数字0则说明这个数字不能用。
  • 如果这个数字已经出现过了（vis[i]为真），这个数字也不能用。
  • 如果这个数字没出现过，标记这个数字已出现过。

如果第一个数字符合要求，设第二个数字为第一个数字的2倍，第三个数字为第一个数字的3倍。再分别检查第二、第三数字是否可用。如果都可用，输出一组结果。

【题解代码】

解法1：

#include<bits/stdc++.h> using namespace std; bool vis[15];//vis[i]:数字i是否存在 //如果n的各位数字都没有出现过，设vis，返回true。如果有出现过的数字或有0，返回false bool setVis(int n) {for(int i = n; i > 0; i /= 10)//数字拆分 {if(i%10 == 0 || vis[i%10])//如果有0，或已出现过的数字 return false;elsevis[i%10] = true;//如果i%10没出现过，则标记其出现过 }return true; } int main() {for(int a = 100; a <= 333; ++a){memset(vis, 0, sizeof(vis));//清空vis数组 if(setVis(a) && setVis(2*a) && setVis(3*a))//如果3个数之中都没有相同的数字 cout << a << ' ' << 2*a << ' ' << 3*a << endl; }return 0; }

总结

以上是生活随笔为你收集整理的洛谷 P1008 [NOIP1998 普及组] 三连击的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。