UVA 10825 Anagram and Multiplication ( 暴搜 next_permutation )
UVa Online Judge
解題關鍵在於只要個位數確定,做完乘法後的個位數也會隨之確定,並且這個數會是做完乘法後的個位數的排列。因此只要枚舉個位數後判斷是否合法即可。比較挫的是,我很少用 std::next_permutation(),沒有意識它只會重新排列成比呼叫時字典序更大的排列,忘了先做排序就除錯很久。。
#include <bits/stdc++.h> using namespace std; const int MAXN = 400 + 2; const int MAXM = 6 + 2; int m, n; int dig[ MAXM ]; bool valid(){ set<int> has; for(int i = 0; i < m; ++i) has.insert( dig[ i ] ); sort( dig + 1, dig + m ); do{ bool ok = true; for(int i = 2; i <= m; ++i){ set<int> vis; int carry = 0, cur = 0; for(int j = 0; j < m; ++j){ cur = carry + dig[ j ] * i; carry = cur / n; cur %= n; if( vis.count( cur ) || !has.count( cur ) ){ ok = false; break; } vis.insert( cur ); } if( carry > 0 ) ok = false; if( !ok ) break; } if( ok ) return true; } while( next_permutation( dig + 1, dig + m ) ); return false; } void solve(){ for(int i = 1; i < n; ++i){ set<int> used; for(int j = 0; j < m; ++j){ int k = ( i * ( j + 1 ) ) % n; if( used.count( k ) ) continue; used.insert( k ); dig[ j ] = k; } if( valid() ){ for(int j = m - 1; j >= 0; --j) printf("%d%c", dig[ j ], j == 0 ? '\n' : ' '); return; } } puts("Not found."); } int main(){ while( scanf("%d%d", &m, &n) == 2 && n + m ){ solve(); } return 0; }