当前位置：首页 > news >正文

建站资源网站建设方案申请报告

news 2025/9/16 1:17:39

建站资源,网站建设方案申请报告,嗨学网官网,东坑镇网站建设公司题目传送门分析看到这道题我一开始是有点懵的，但是看了看数据范围，发现有几个点有 n 为质数的特殊性质，结论先行，大胆猜测是不是可以贪心，所以先打了一个最傻的代码上去试试. void solve(){cin >> n >&…

题目传送门

分析

看到这道题我一开始是有点懵的，但是看了看数据范围，发现有几个点有 n 为质数 的特殊性质，结论先行，大胆猜测是不是可以贪心，所以先打了一个最傻的代码上去试试.

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

喜提30分.

想到之前随机跳题跳到的P3539 [POI2012] ROZ-Fibonacci Representation，这道题是直接找离的最近的斐波那契数.

结合 n 为质数 的这档部分分，果断尝试贪心.

然后就有了这个.

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;
}

但是发现交上去之后还是只有 40 分.

注意到第一个点都没过，所以开始手搓数据，发现一些数据是最靠近的质数加上一堆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;
}