我正在嘗試解決一項競爭性編程任務，但我找不到有效的解決方案來解決最后 5 個測驗用例。
您會收到 t (t >= 1 && t <= 5) 查詢，每個查詢由 n 個數字 num (num >= 1 && num <= 1000000) 組成。代表每個查詢的序列沒有排序，其中可以有重復的數字。所有 ns 的總和小于 1000000。讓我們將單個查詢中所有數字的 GCD 稱為 x。任務是找出為了使 x 最大化而必須進行的最小移除次數。時間限制為 0.7 秒。
考慮到這個 (8, 2, 6, 4, 10, 12) 是給我的詢問。GCD (8, 2, 6, 4, 10, 12) = 2 但如果我移除 2、6 和 10 GCD (8, 4, 12) = 4。我將初始 GCD x 從 2 增加到 4，移除 3 次即 2 , 6 和 10。這個問題的答案是 3。
到目前為止，我提出的最好的想法如下：
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <limits>
#include <algorithm>
#include <iterator>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
int i, n, tmp, j, num, div, max, min, rem;
std::vector<int> ans;
for (i = 0; i != t; i) {
std::cin >> n;
tmp = 0;
std::map<int, int> buckets;
for (j = 0; j != n; j) {
std::cin >> num;
tmp = std::gcd(tmp, num);
for (div = 1; div * div <= num; div) {
if (num % div == 0) {
buckets[div];
if (div * div != num) {
buckets[num / div];
}
}
}
}
max = tmp;
min = std::numeric_limits<int>::max();
for (auto const& elem : buckets) {
if (elem.second != n && elem.first > max) {
rem = n - elem.second;
if (rem < min) {
max = elem.first;
min = rem;
}
}
}
ans.emplace_back(min);
}
std::copy(ans.cbegin(), std::prev(ans.cend()),
std::ostream_iterator<int>(std::cout, "\n"));
std::cout << ans.back() << '\n';
return 0;
}
我正在計算 x (tmp) 并將每個數字 (num) 拆分為其除數 (div)。我不斷更新存盤桶，這是一個 std::map<div，該 div 可以劃分的特定查詢 t 中的數字計數>。我遍歷存盤桶并找出哪個是大于 max (x) 的除數 (elem.first)，同時導致最小數量的移除。
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <limits>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
int i, n, tmp_gcd, tmp_max, j, num,
ans, k, tmp_sum, l, tmp_min;
for (i = 0; i != t; i) {
std::cin >> n;
std::vector<int> inq_db;
inq_db.reserve(n);
tmp_max = tmp_gcd = 0;
for (j = 0; j != n; j) {
std::cin >> num;
inq_db.emplace_back(num);
tmp_gcd = std::gcd(tmp_gcd, num);
tmp_max = std::max(tmp_max, num);
}
std::vector<int> buckets(tmp_max 1);
for (auto const& elem : inq_db) {
buckets[elem];
}
ans = std::numeric_limits<int>::max();
for (k = tmp_gcd 1; k <= tmp_max; k) {
tmp_sum = 0;
for (l = k; l <= tmp_max; l = k) {
tmp_sum = buckets[l];
}
tmp_min = n - tmp_sum;
if (tmp_min != n && tmp_min < ans) {
ans = tmp_min;
}
}
std::cout << ans << '\n';
}
return 0;
}
I’m calculating x (tmp_gcd) and finding out maximum value of num (tmp_max) in the inquiry t that I’m working with. I initialize buckets with max 1 zeroes (counters). I do this in order to avoid initializing buckets with 1000000 counters each time. Instead of splitting the number into its divisors I’m using the counters in buckets to count the numbers that are equal to their index. 5th element in buckets is counting how many numbers with the value 5 I have in the inquiry, 100th element – value 100 and so on. I loop through buckets starting from index x 1 and find out how many numbers with GCD = k I have in buckets. The idea here is that numbers k, 2k, 3k, 4k, 5k and so on have GCD = k. I find out which is the number (ans) that leads to minimum number of removals.
The problem with both my ideas is that they are given with time limit exceeded on the last 5 test cases. I need some help to optimize them or If this is not possible to be given a new one. Thanks in advance for your time.
@Damien I reworked your logic this way:
#include <iostream>
#include <map>
#include <vector>
#include <numeric>
#include <cmath>
#include <algorithm>
std::vector<int> split(int num) {
std::vector<int> ret;
if ((num & 1) == 0) {
ret.emplace_back(2);
do {
num >>= 1;
} while ((num & 1) == 0);
}
int div, div_lim;
for (div = 3, div_lim = static_cast<int>(std::sqrt(num)); div <= div_lim; div = 2) {
if (num % div == 0) {
ret.emplace_back(div);
do {
num /= div;
} while (num % div == 0);
div_lim = static_cast<int>(std::sqrt(num));
}
}
if (num != 1) {
ret.emplace_back(num);
}
return ret;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
int i, n, x, j, num, ans;
std::map<int, int>::const_iterator it;
for (i = 0; i != t; i) {
std::cin >> n;
std::vector<int> seq;
seq.reserve(n);
x = 0;
for (j = 0; j != n; j) {
std::cin >> num;
seq.emplace_back(num);
x = std::gcd(x, num);
}
if (x != 1) {
for (auto& elem : seq) {
elem /= x;
}
}
std::map<int, int> lookup;
for (auto const& elem : seq) {
auto ret = split(elem);
for (auto const& div : ret) {
lookup[div];
}
}
it = std::max_element(lookup.cbegin(), lookup.cend(),
[](std::pair<const int, int> const& lhs, std::pair<const int, int> const& rhs) {
return lhs.second < rhs.second;
});
ans = n - it->second;
std::cout << ans << '\n';
}
return 0;
}
but sadly I hit TLE on the last 5 test cases.
@TonyK It is in Bulgarian because the task is given on a Bulgarian competitive programming competition.
If I have this (4 6 8 10 12 14) test GCD is 2. Now let's split each number into its divisors:
4 (1, 2, 4)
6 (1, 2, 3, 6)
8 (1, 2, 4, 8)
10 (1, 2, 5, 10)
12 (1, 2, 3, 4, 6, 12)
14 (1, 2, 7, 14)
The candidates for GCD > 2 are the following ones:
14->I have to remove all the numbers but 14->5 removals
12->I have to remove all the numbers but 12->5 removals
10->I have to remove all the numbers but 10->5 removals
8->I have to remove all the numbers but 8->5 removals
7->I have to remove all the numbers but 14->5 removals
6->I have to remove 4, 8, 10 and 14->4 removals
5->I have to remove all the numbers but 10->5 removals
4->I have to remove 6, 10 and 14->3 removals
3->I have to remove 4, 8, 10 and 14->4 removals
The answer is 3 removals and they can be achieved at GCD = 4.
uj5u.com熱心網友回復：
這是一個相當快速的解決方案。
第一步包括計算全域 gcd 并將所有數字除以它。
全域 GCD 現在等于 1。現在的問題是找到最小的移除次數，使得這個 GC 不再等于 1。
為此，我們對每個數字進行素數分解，并找到其中最常見的素數。
結果是陣列大小減去這個素數出現的次數。
復雜性由素數分解決定：O(n sqrt(m))，其中m是最大資料值。
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <limits>
#include <map>
#include <cmath>
// For test
void print (const std::vector<int> &v) {
for (auto &x: v) {
std::cout << x << " ";
}
std::cout << std::endl;
}
// Get the prime factors of a number (multiplicity is not important here)
std::vector<int> get_primes (int n) {
int n_sav = n;
if (n <= 1) return {};
std::vector<int> primes;
if (n % 2 == 0) {
primes.push_back(2);
n /= 2;
while (n%2 == 0) {n /= 2;}
}
int max_prime = sqrt(n);
int p = 3;
while (p <= max_prime) {
if (n % p == 0) {
primes.push_back(p);
n/= p;
while (n%p == 0) {n /= p;}
max_prime = sqrt(n);
}
p = 2;
}
if (n != 1) {
primes.push_back(n);
}
//std::cout << n_sav << ": ";
//print (primes);
return primes;
}
int min_removals (std::vector<int>& numbers) {
int n = numbers.size();
if (n == 1) return -1;
int current_gcd = numbers[0];
for (int i = 1; i < n; i) current_gcd = std::gcd (current_gcd, numbers[i]);
std::cout << "current GCD = " << current_gcd << "\n";
if (current_gcd != 1) {
for (int i = 0; i < n; i) numbers[i] /= current_gcd;
}
std::map<int, int> list_primes;
for (auto x: numbers) {
auto primes = get_primes(x);
for (int i: primes) {
list_primes[i] ;
}
}
int most_frequent = 0;
for (const auto& p: list_primes) {
if (p.second > most_frequent) {
most_frequent = p.second;
}
}
return n - most_frequent;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
int n;
std::cin >> n;
std::vector<int> numbers (n);
for (int i = 0; i < n; i) {
std::cin >> numbers[i];
}
auto ans = min_removals (numbers);
std::cout << ans << "\n";
}
return 0;
}
使用以下變體，通過在主函式中加入素數分解，速度略有提高。這避免了一些無用的資料副本。看來收益不可小覷。
int min_removals_new (std::vector<int>& numbers) {
int n = numbers.size();
if (n == 1) return -1;
int current_gcd = numbers[0];
for (int i = 1; (i < n) && (current_gcd > 1); i) current_gcd = std::gcd (current_gcd, numbers[i]);
if (current_gcd != 1) {
for (int i = 0; i < n; i) numbers[i] /= current_gcd;
}
std::map<int, int> list_primes;
for (auto x: numbers) {
if (x == 1) continue;
if (x % 2 == 0) {
list_primes[2] ;
x /= 2;
while (x%2 == 0) {x /= 2;}
}
int max_prime = sqrt(x);
int p = 3;
while (p <= max_prime) {
if (x % p == 0) {
list_primes[p] ;
x/= p;
while (x%p == 0) {x /= p;}
max_prime = sqrt(x);
}
p = 2;
}
if (x != 1) {
list_primes[x] ;
}
}
int most_frequent = 0;
for (const auto& p: list_primes) {
if (p.second > most_frequent) {
most_frequent = p.second;
}
}
return n - most_frequent;
}
uj5u.com熱心網友回復：
我終于找到了足夠快（550-600 ms）的解決方案！
#include <iostream>
#include <vector>
#include <utility>
#include <numeric>
#include <algorithm>
#include <memory>
#include <bitset>
#include <unordered_map>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
int i, n, j, num, lim = 0, max, div, cpy, ans;
std::vector<int> ns, gcds(t);
std::vector<std::vector<int>> db(t);
std::vector<int>::const_iterator it;
std::pair<decltype(it), decltype(it)> ret;
for (i = 0; i != t; i) {
std::cin >> n;
ns.emplace_back(n);
db[i].reserve(n);
for (j = 0; j != n; j) {
std::cin >> num;
db[i].emplace_back(num);
gcds[i] = std::gcd(gcds[i], num);
lim = std::max(lim, num);
}
if (gcds[i] != 1) {
for (auto& elem : db[i]) {
elem /= gcds[i];
}
}
std::sort(db[i].begin(), db[i].end());
}
auto primes = std::make_unique<std::bitset<10000000 1>>();
primes->set();
primes->set(0, false);
primes->set(1, false);
for (i = 2; i * i <= lim; i) {
if (primes->test(i)) {
for (j = i * i; j <= lim; j = i) {
primes->set(j, false);
}
}
}
for (i = 0; i != t; i) {
std::unordered_map<int, int> lookup;
max = 0;
for (it = db[i].cbegin(); it != db[i].cend(); it = ret.second) {
ret = std::equal_range(it, db[i].cend(), *it);
if (primes->test(*it)) {
lookup[*it] = ret.second - ret.first;
if (lookup[*it] > max) {
max = lookup[*it];
}
continue;
}
for (div = 2, cpy = *it; div * div <= cpy; div) {
if (cpy % div == 0) {
lookup[div] = ret.second - ret.first;
if (lookup[div] > max) {
max = lookup[div];
}
do {
cpy /= div;
} while (cpy % div == 0);
}
}
if (cpy != 1) {
lookup[cpy] = ret.second - ret.first;
if (lookup[cpy] > max) {
max = lookup[cpy];
}
}
}
ans = ns[i] - max;
std::cout << ans << '\n';
}
return 0;
}
我閱讀了所有 t 個查詢并將它們的 nums 存盤在一個由 t 個向量組成的大向量中，每個向量由 n 個元素組成。在讀取和存盤 db[i] 中的 nums 時，我將每個 n 存盤在向量 ns 中，計算特定查詢 gcds[i] 的 gcd 并找出最大 num lim。當我完成閱讀階段時，我將 db[i] 中的所有 nums 劃分為 gcds[i] 以便將 gcds[i] 從最終計算中排除。我對 db[i] 進行排序是為了避免對其中的重復數字進行質數分解。基于 lim 我找出范圍內的所有素數 [2; lim] 使用我通過 unique_ptr 素數存盤在堆中的位集。我使用 unordered_map 查找處理每個查詢 db[i]。使用 for 回圈和 equal_range 演算法，我跳到 db[i] 中的 nums 上，只對重復的第一個進行素數分解。例如，如果我有 7 7 7 7 7 7 7 13 17 19 ... ret.first 將指向第一個 7，而 ret.second 將指向 13。因為 7 已經是一個素數（我使用 bitset primes 進行檢查) 我不會將它分解為素數，我將遞增它的計數器 ret.second - ret.first 次，并將該計數器與表示 db[i] 中最頻繁 num 的計數的 max 進行比較。如果需要，我通過分配更新最大值。如果 *it 不是素數，我將使用下一個帶有 div 和 cpy 的 for 回圈對其進行素數分解。如果我遇到像 6 這樣的數字，它不能使用第一個 for 回圈完全分解，我將在它之后使用 If 子句，因為第一次迭代會發現 2 作為 6 的主要因素之一，然后我們將失敗3 它必須增加它的計數器。這就是 if 子句的目的。當我找出 db[i] 中最常見的 num 時，我只需從 ns[i] 中減去它的計數，從而找出為了改進 gcds[i] 而必須進行的最小洗掉次數最多。我輸出ans，就是這樣。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/420165.html
標籤：
上一篇：使用遞回回溯。為什么代碼有效