題目傳送門

這道題事實上解并不多，所以我們倒過來從$7$開始搜索。主過程中為廣搜，而函數(shù)深搜進行拓展。其實是對于前導$0$刪去的情況也要考慮，否則只有$20pts$。

最后別忘了判斷$7$在不在$[A,B]$。

1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define rep(i, a, b) for (register int i = a; i <= b; ++i) 6 7 int A, B, ans, pw[10], dB = 0; 8 9 queue< pair<int, int> > q; 10 11 void dfs(int v, int s, int dep, int max_dep, int last) { 12 if (dep > dB+1) return; 13 if (dep == max_dep) { 14 if (s <= B && last) { 15 q.push(make_pair(s, dep)); 16 if (s >= A) 17 ans++; 18 } 19 return; 20 } 21 int bit = v % 10; 22 if (bit+last < 10) dfs(v / 10, s + (bit+last) * pw[dep], dep+1, max_dep, bit+last); 23 if (last-bit >= 0 && bit != 0) dfs(v / 10, s + (last-bit) * pw[dep], dep+1, max_dep, last-bit); 24 } 25 26 int main() { 27 scanf("%d%d", &A, &B) 28 if (A <= 7 && 7 <= B) ans++; 29 q.push(make_pair(7, 1)); 30 pw[0] = 1; 31 rep(i, 1, 9) { 32 pw[i] = pw[i-1] * 10; 33 if (B > pw[i]) dB = i; 34 } 35 36 while (!q.empty()) { 37 pair<int, int> h = q.front(); q.pop(); 38 rep(i, 0, 9) 39 dfs(h.first, i, 1, h.second+1, i); 40 if (h.second <= dB) q.push(make_pair(h.first, h.second+1)); 41 } 42 43 printf("%d", ans); 44 return 0; 45 }

這道題如果要打表也可以，就是表會很大。

轉(zhuǎn)載于:https://www.cnblogs.com/ac-evil/p/10339825.html

總結(jié)

以上是生活随笔為你收集整理的[洛谷P1822]魔法指纹的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。