題目鏈接：http://codeforces.com/contest/686/problem/C
題目大意：
給你兩個十進制的數n和m，選一個范圍在[0,n)的整數a，選一個范圍在[0,m)的整數b，要求a的7進制表示和b的7進制表示中的每一位都不重復。其中，a的7進制位數和n-1的7進制位數相同，b的位數和m-1的位數相同。
比如，當n=2,m=3時，a和b的其進制表示的所有集合是：
a=0, b=1
a=0, b=2
a=1, b=0
a=1, b=2
解法：
這套題目可以用dfs做。
我們開一個數組f[]，f[i]表示數字i有沒有在a和b的七進制表示中出現過。
然后我們遍歷a和b的每一位，如果在判斷這個數的第i位的時候恰好f[i]=false，我們就可以將f[i]設為true，并將這一位的值設成i，然后繼續搜索。
假設我們已經通過搜索得到了a，此時邊有一個確定的a（a不是我們答案里需要的，但是我們搜索的過程中實際上會遍歷得到所有合法的a）以及一個確定的f[]數組。此時按照dfs_m()函數求得b（b也不是答案里需要的），如果b合法，則ans++（ans是最終答案）。
dfs_m()函數如下（用它來得到b）：

void dfs_m(int tmp, int tm) {if (tmp >= m) return;if (tm < 0) {ans ++;return;}for (int i = 0; i < maxn; i ++) {if (f[i] == false) {f[i] = true;dfs_m(tmp + i * g[tm], tm-1);f[i] = false;}} }

我們已經有了dfs_m()了，那么只要我們在找b之前找到每一個a就行了，找a的方法也是dfs，如下的dfs_n()方法：

void dfs_n(int tmp, int tn) {if (tmp >= n) return;if (tn < 0) {dfs_m(0, mm-1);return;}for (int i = 0; i < maxn; i ++) {if (f[i] == false) {f[i] = true;dfs_n(tmp + i * g[tn], tn-1);f[i] = false;}} }

完整代碼：

?

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 7; bool f[maxn]; int g[maxn], n, m, nn, mm; long long ans = 0; void init() {memset(f, false, sizeof(f));g[0] = 1;for (int i = 1; i < maxn; i ++)g[i] = g[i-1] * 7; } int chk(int n) {if (n == 1)return 1;n -= 1;int cnt = 0;while (n) {n /= 7;cnt ++;}return cnt; } void dfs_m(int tmp, int tm) {if (tmp >= m) return;if (tm < 0) {ans ++;return;}for (int i = 0; i < maxn; i ++) {if (f[i] == false) {f[i] = true;dfs_m(tmp + i * g[tm], tm-1);f[i] = false;}} } void dfs_n(int tmp, int tn) {if (tmp >= n) return;if (tn < 0) {dfs_m(0, mm-1);return;}for (int i = 0; i < maxn; i ++) {if (f[i] == false) {f[i] = true;dfs_n(tmp + i * g[tn], tn-1);f[i] = false;}} }int main() {scanf("%d%d", &n, &m);init();if (n > m) swap(n, m);nn = chk(n);mm = chk(m);if (nn + mm > 7) {puts("0");return 0;}dfs_n(0, nn-1);cout << ans << endl;return 0; }

?

轉載于:https://www.cnblogs.com/moonlightpoet/p/5613075.html

總結

以上是生活随笔為你收集整理的Codeforces Round #359 (Div. 2) C. Robbers' watch 搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。