个人如何开网站,住房和城乡建设部网站现行规范,海口企业模板建站,建单页网站题目传送门
分析
看到这道题我一开始是有点懵的#xff0c;但是看了看数据范围#xff0c;发现有几个点有 n 为质数 的特殊性质#xff0c;结论先行#xff0c;大胆猜测是不是可以贪心#xff0c;所以先打了一个最傻的代码上去试试.
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 % i0) 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 % i0) 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 分调了一个多小时.
当然码力强也是不用考虑这个问题的.
