藍橋杯 2014 決賽 2 六角幻方

2019-11-11 05:16:51

字體：大中小

來源：轉載

供稿：網友

把 1 2 3 … 19 共19個整數排列成六角形狀，如下：要求每個直線上的數字之和必須相等。共有15條直線哦！再給點線索吧！我們預先填好了2個數字，第一行的頭兩個數字是：15 13，參見圖【p1.png】，黃色一行為所求。這里寫圖片描述請你填寫出中間一行的5個數字。數字間用空格分開。

參考答案： 9 6 5 2 16

同樣小學奧數題.首先編號

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

然后DFS就好了. 本來想先算出S,然后生成,后來想想也快不到哪里去,反正也不限時這里有個非常神奇的就是如果再DFS里面直接cout 那么就會 Segment fault(Code Dump)不知為何?所以搞了一個ans存答案

#include <bits/stdc++.h>using namespace std;list<int> li;int a[30] = {15, 13};int s = 0;int cnt = 0;vector<int> ans;void dfs(int k){ if (k == 19) { for (int i = 7; i <= 11; i++) ans.push_back(a[i]); } for (auto it = li.begin(); it != li.end(); it++) { if (k == 2) s = a[0] + a[1] + *it; if (k == 6) if (a[3] + a[4] + a[5] + *it != s) continue; if (k == 7) if (a[0] + a[3] + *it != s) continue; if (k == 11) if (a[2] + a[6] + *it != s || a[7] + a[8] + a[9] + a[10] + *it != s) continue; if (k == 12) if (a[1] + a[4] + a[8] + *it != s) continue; if (k == 15) if (a[12] + a[13] + a[14] + *it != s || a[1] + a[5] + a[10] + *it != s) continue; if (k == 16) if (a[7] + a[12] + *it != s || a[2] + a[5] + a[9] + a[13] + *it != s) continue; if (k == 17) if (a[3] + a[8] + a[13] + *it != s || a[6] + a[10] + a[14] + *it != s) continue; if (k == 18) if (a[16] + a[17] + *it != s || a[0] + a[4] + a[9] + a[14] + *it != s || a[11] + a[15] + *it != s) continue; a[k] = *it; it = li.erase(it); dfs(k + 1); it = li.insert(it, a[k]); }}int main(){ for (int i = 1; i < 20; i++) if (i != 15 && i != 13) li.push_back(i); dfs(2); for (int e : ans) { cout << e << ' '; } cout << endl;}

這里寫圖片描述