0w1

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;
}