題目傳送門

分析

看到這道題我一開始是有點懵的，但是看了看數(shù)據(jù)范圍，發(fā)現(xiàn)有幾個點有 n 為質(zhì)數(shù) 的特殊性質(zhì)，結(jié)論先行，大膽猜測是不是可以貪心，所以先打了一個最傻的代碼上去試試.

void solve(){cin >> n >> k;cout << max(n*(k-1)*(k-1),(n-k)*(n-k)) << endl;
}

喜提30分.

想到之前隨機跳題跳到的P3539 [POI2012] ROZ-Fibonacci Representation，這道題是直接找離的最近的斐波那契數(shù).

結(jié)合 n 為質(zhì)數(shù) 的這檔部分分，果斷嘗試貪心.

然后就有了這個.

bool get(int x){for(int i = 2;i*i <= x; i++){if(x % i==0) return 0;} return 1;
}
int n,k;void solve(){cin >> n >> k;int ans = 0;int nn = n;while(n){for(int i = n; i >= 1; i--){if(get(i)){ans += (i-k)*(i-k);n -= i;break;}}}cout << max(ans,(k-1)*(k-1)*nn) << endl;
}

但是發(fā)現(xiàn)交上去之后還是只有 40 分.

注意到第一個點都沒過，所以開始手搓數(shù)據(jù)，發(fā)現(xiàn)一些數(shù)據(jù)是最靠近的質(zhì)數(shù)加上一堆1才是正確答案.

所以在代碼里再加一句就好了.

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
bool get(int x){for(int i = 2;i*i <= x; i++){if(x % i==0) return 0;} return 1;
}
int n,k;void solve(){cin >> n >> k;int ans = 0;int res = (k-1)*(k-1)*n;while(n){for(int i = n; i >= 1; i--){if(get(i)){ans += (i-k)*(i-k);n -= i;res = max(res,ans+(k-1)*(k-1)*n);break;}}}cout << res << endl;
}
signed main(){int t;cin >> t;while(t--) solve();return 0;
}

坑點

這里的質(zhì)數(shù)要手動枚舉，不然就會和大佬 LINTONG1 一樣一直 50 分調(diào)了一個多小時.

當然碼力強也是不用考慮這個問題的.