洛谷历险记2

遇到一个有意思的题目P1008，先贴代码

#include <iostream>
#include <cmath>
#include <iomanip>


using namespace std;

int result[9];
int used[9];

void test() {
 int num1 = result[0] * 100 + result[1] * 10 + result[2];//按位获得值
 int num2 = result[3] * 100 + result[4] * 10 + result[5];
 int num3 = result[6] * 100 + result[7] * 10 + result[8];
 /*cout << num1 << " " << num2 << " " << num3 << endl;*/
 if (num1 * 6 == num2 * 3 && num1*6 == num3 * 2) {//注意不能用三值相等若是a==b==c,则会令右边为逻辑值
  cout << num1 << " " << num2 << " " << num3 << endl;
 }

}

void test1() {
 cout << (1 == 0 == 0);//返回1，标识该过程是右往左，右边得1，再跟1比较得1
}

void dfs(int count) {
 if (count == 9) {//当选中9个值，进入判定区
  test();
  return;
 }
 for (int i = 0; i < 9; i++)
 {
  if (used[i] != 1) {//未被使用
   used[i] = 1;//将其标记
   result[count] = i + 1;//放入结果集
   dfs(count+1);//树延伸向下一个节点。！！：不能用count++,否则无法回溯。
   used[i] = 0;//当该路径不成功则将节点回溯
  }
 }
 return;
}


int main() {
 //另外一套，暴力枚举
 //for (int i = 192; i < 333; i++) {
 // int i2 = i * 2;
 // int i3 = i * 3;
 // //cout << i<<endl;
 // if ((i / 100 + i / 10 % 10 + i % 10 + i2 / 100 + i2 / 10 % 10 + i2 % 10 + i3 / 100 + i3 / 10 % 10 + i3 % 10 == 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9) && ((i / 100) * (i / 10 % 10) * (i % 10) * (i2 / 100) * (i2 / 10 % 10) * (i2 % 10) * (i3 / 100) * (i3 / 10 % 10) * (i3 % 10) == (1) * (2) * (3) * (4) * (5) * (6) * (7) * (8) * (9))) {
 //  cout << i << " " << i2 << " " << i3 << endl;
 // }
 //}
 for (int i = 0; i < 9; i++)//初始化
 {
  result[i] = 0;
  used[i] = 0;
 }
 dfs(0);
 test();
 //test1();
 return 0;
}

该题在小子看来有两种方向：①暴力枚举 ②回溯

首先说枚举，枚举的话，由题目给出的提示，我们可以知道第一个值最小值是192，最大不能打过999/3，逐个遍历，检索是否满足1~9全部出现，运用了题目讨论区一个不错的比较方式，将集合内的值相加相乘值唯一，则为相同集合（未经数学严格证明）。

再来，是回溯，深度优先，得到满足1~9皆出现的序列，再验证是否符合1:2:3，其实与上面的方法方向相反，但在我看来，也是一种枚举。

p1424

可以先将能凑出来的整数排除掉，再运算剩余部分

摘的别人代码，说下思想，大概就是一开始的日子，先-7，-7。。直到余下的日子不足7天在分析，余下的日子会出现哪些情况减少工作日