結果
問題 |
No.3030 Kruskal-Katona
|
ユーザー |
|
提出日時 | 2025-02-21 22:46:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,901 bytes |
コンパイル時間 | 1,084 ms |
コンパイル使用メモリ | 70,944 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-21 22:46:20 |
合計ジャッジ時間 | 2,144 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <climits> // 添加此头文件 using namespace std; typedef long long ll; ll comb(ll n, int k) { if (k == 0 || k == n) return 1; k = min(k, (int)(n - k)); ll res = 1; for (int i = 1; i <= k; ++i) { if (res > LLONG_MAX / (n - k + i)) { return LLONG_MAX; } res *= (n - k + i); res /= i; } return res; } vector<ll> solve(ll N, int i) { vector<ll> res; ll remaining = N; int current_k = i; while (remaining > 0 && current_k >= 1) { ll left = current_k; ll right = current_k + 100; ll best_n = current_k; // 动态扩展右边界 while (true) { ll c = comb(right, current_k); if (c == LLONG_MAX || c > remaining) break; right *= 2; if (right > 1e18) break; } // 二分查找 while (left <= right) { ll mid = (left + right) / 2; ll c = comb(mid, current_k); if (c == LLONG_MAX) { // 溢出处理 right = mid - 1; continue; } if (c <= remaining) { best_n = max(best_n, mid); left = mid + 1; } else { right = mid - 1; } } if (best_n < current_k) { current_k--; continue; } res.push_back(best_n); remaining -= comb(best_n, current_k); current_k--; } return res; } int main() { ll N; int i; cin >> N >> i; auto ans = solve(N, i); for (size_t idx = 0; idx < ans.size(); ++idx) { cout << ans[idx]; if (idx != ans.size() - 1) cout << " "; } cout << endl; return 0; }