Lotplace

本人於該blog的全部文章轉移至[UVA] 12218 An Industrial Spy – KKWBlog (kkwtech.com)該網域下，其後此處不進行更新，一律於新站點更新。

f711. 12218 – An Industrial Spy – 高中生程式解題系統 (zerojudge.tw)
題目重點:
給N個數字從中取K(K<=N)個排列並且算出所有排列樹的質數總和。

解題思路:
基本上不難就是一道DP題，只要會組合、排列、質數檢測就能解出該題，
不過看了一下官方答案，果然還是存在更快的做法的。

驗證質數的方式:
有很多種作法我是選擇Optimized School Method，該作法簡單說明:從(5,7)開始下一個可能質數對為(5+6.5+6+2)，也就是(6n + 5, 6n + 7),n >= 0，因此可以略過大部分的和數。

組合:
使用mask可以取得所有可能的組合解，並且時間複雜度只需2^(n.len())
ex: n = 123, mask = 2^0 = 001,得到3並且001 += 1 => 010
mask = 010,得到2
依此類推可以得出所有的組合

排列:
使用c++內建的next_permutaion即可得到所有排列，使用該方法得注意原字串需先排列

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
//判斷質數 By Optimized School Method
bool isprime (int number) {
    if(number <= 1) {
        return false;
    }
    if(number <= 3) {
        return true;
    }
    if(number % 2 == 0 || number % 3 == 0) {
        return false;
    }
    for(int i = 5; i * i <= number; i += 6) {
        if(number % i == 0 || number % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}
//同時組合及排列並確認是否為質數
int CombPermThenCountPrime (string input) {
    set <int> res;//set存放解可以避免重複
    for(int i = 1; i < (1 << input.size()); i++) {//建立mask i
        string tmp = "";
        for(int j = 0; j < input.size(); j++) {//mask得出組合結果
            if(i & (1 << j)) {
                tmp += input[j];
            }
        }
        do {
            if(isprime(stoi(tmp)) == true) {//驗證質數
                res.insert(stoi(tmp));
            }
        }while(next_permutation(tmp.begin(),tmp.end()));
    }
    return res.size();
}
int main () {
    int n = 0;
    cin >> n;
    string input;
    while(n--) {
        cin >> input;
        sort(input.begin(),input.end());
        cout << CombPermThenCountPrime(input) << endl;
    }
    return 0;
}

時間複雜度:
對於一輸入另N為該輸入長度
sort() * CombPermThenCountPrime()
= N*log₂(N) * { 2^N * ( N + N! * sqrt(N) ) }

---

Filed under: UVA - @ 2021 年 9 月 6 日 下午 3:29

標籤: uva