結果
問題 | No.5021 Addition Pyramid |
ユーザー |
|
提出日時 | 2025-02-25 21:03:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 147 ms / 2,000 ms |
コード長 | 4,087 bytes |
コンパイル時間 | 1,094 ms |
コンパイル使用メモリ | 97,908 KB |
実行使用メモリ | 6,820 KB |
スコア | 34,939,989 |
最終ジャッジ日時 | 2025-02-25 21:03:49 |
合計ジャッジ時間 | 9,659 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <random> #include <chrono> using namespace std; const int MOD = 100000000; // 模 10^8 // 计算模意义下 a 与 b 的距离(取 |a-b| 和 MOD - |a-b| 中较小值) inline int modDiff(int a, int b) { int diff = abs(a - b); return min(diff, MOD - diff); } // 根据底层数字 bottom,利用加法金字塔的递推关系(从下向上)计算整座金字塔, // 并返回其中最大的误差(与目标金字塔 target 对比) int compute_max_error(const vector<int> &bottom, const vector<vector<int>> &target, int N) { // dp[i][j] 表示金字塔第 i 行(0-index,对应题中第 i+1 层)第 j 个数字 // dp[N-1] 就是底层(第 N 层)的数字 vector<vector<int>> dp(N); dp[N-1] = bottom; // 底层初始化 // 自下而上计算金字塔中每个位置:dp[i][j] = (dp[i+1][j] + dp[i+1][j+1]) mod MOD for (int i = N - 2; i >= 0; i--) { dp[i].resize(i + 1); for (int j = 0; j <= i; j++) { dp[i][j] = ( (long long)dp[i+1][j] + dp[i+1][j+1] ) % MOD; } } // 计算与目标金字塔 target 的最大误差 int maxErr = 0; for (int i = 0; i < N; i++) { for (int j = 0; j <= i; j++) { int err = modDiff(dp[i][j], target[i][j]); maxErr = max(maxErr, err); } } return maxErr; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; // 读入完整的金字塔目标值,共有 N 行,第 i 行 i 个数字 vector<vector<int>> target(N); for (int i = 0; i < N; i++) { target[i].resize(i + 1); for (int j = 0; j <= i; j++) { cin >> target[i][j]; } } // 初始解:取目标金字塔底层(第 N 行)的数字作为底层解 vector<int> bottom = target[N-1]; // 计算当前解的最大误差 int bestError = compute_max_error(bottom, target, N); // 启发式调整(简单的 hill climbing / 模拟退火思路) // 下面的迭代次数可以根据需要调节 const int ITER_MAX = 20000; // 初始步长:设为 MOD/100 double initStep = MOD / 100.0; // 使用随机数生成器 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // 每次随机选择一个底层数字位置,尝试进行随机微调 for (int iter = 0; iter < ITER_MAX; iter++) { // 动态降低步长(可理解为退火过程),保证随着迭代步幅逐渐变小 double curStep = initStep * (1.0 - (double)iter / ITER_MAX); if(curStep < 1) curStep = 1; // 选择底层位置 uniform_int_distribution<int> posDist(0, N - 1); int pos = posDist(rng); // 选择调整值,范围大致为 [-curStep, curStep] uniform_int_distribution<int> deltaDist(- (int)curStep, (int)curStep); int delta = deltaDist(rng); // 保存旧值 int oldVal = bottom[pos]; // 更新该位置(注意保证在 [0, MOD) 内) int newVal = (oldVal + delta) % MOD; if(newVal < 0) newVal += MOD; bottom[pos] = newVal; // 计算调整后的最大误差 int newError = compute_max_error(bottom, target, N); // 如果调整有利,则接受改动;否则恢复原值 if(newError < bestError) { bestError = newError; // 可以在此处输出一些调试信息,例如 iter, bestError 等 // cerr << "Iter " << iter << ": Improved max error to " << bestError << "\n"; // 若达到完美匹配可以提前退出 if(bestError == 0) break; } else { // 恢复回去 bottom[pos] = oldVal; } } // 输出最终的底层数字(题目规定每行输出一个数字,共 N 个) // 注意输出顺序为左到右(即 bottom[0] 到 bottom[N-1]) for (int i = 0; i < N; i++) { cout << bottom[i] << "\n"; } return 0; }