【题解】[GenshinOI Round 3 ]P9817 lmxcslD

题目传送门

分析

看到这道题我一开始是有点懵的，但是看了看数据范围，发现有几个点有 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;
}

坑点

这里的质数要手动枚举，不然就会和大佬 LINTONG1 一样一直 50 分调了一个多小时.

当然码力强也是不用考虑这个问题的.