目录
CSP2021 J2
题目传送
P7071 [CSP-J2020] 优秀的拆分
解析：n<=1e7， 那么 2^30=1e9, 可以利用数组存储权值，在从大到小遍历，减去权值。
如果 n为奇数，那么肯定是没有答案的，直接输出 -1也有 20分。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N], n, base=1, p=0;
int main(){
cin>>n;
while(base<=1e7) a[++p]=base, base<<=1;
if(n&1) cout<<-1;
else{
for(int i=p; i>=1; i--){
if(n>=a[i]) n-=a[i],cout<<a[i]<<" ";
}
}
return 0;
}
P7072 [CSP-J2020] 直播获奖
解析：可以直接模拟一遍，取分数线可以使用排序
- 如果使用 sort，整体复杂度 O(n^2log)，预计得分 50.
- 可以使用插入排序优化，整体复杂度 O(n^2)，预计得分 80.
如果排序后，计算分数，那么 \(i\) 选手的成绩评出之后，选择第 \(p\) 个人的分数划线，则该分数线为 \(a[i-p+1]\)，如下图。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,p,a[N];
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++){
p = max(1, int(i*m/100));
for(int j=i; j>1; j--){
if(a[j]<a[j-1]) swap(a[j],a[j-1]);
else break;
}
cout<<a[i-p+1]<<" ";
}
return 0;
}
- 所以我们需要一个O(nlogn)的解法，主要在分数选择的地方确定一个O(log)级别的算法，可以考虑什么呢？
- 注意题目：每个选手的成绩均为不超过 600 的非负整数，所以分数线的区间是比较小的，那么就可以使用计数排序优化。
整体复杂度在 O(600*n)，完美。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,p,a[N],vis[N];
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++){
p = max(1, int(i*m/100));
int cnt=0,score; vis[a[i]]++;
for(int j=600; cnt<p && j>=0; j--){
if(vis[j]) cnt+=vis[j],score=j;
}
cout<<score<<" ";
}
return 0;
}
P7073 [CSP-J2020] 表达式
解析：
P7074 [CSP-J2020] 方格取数
解析：
标签：include,const,int,CSP2020,J2,解析,CSP,J2020 From： https://www.cnblogs.com/hellohebin/p/16746428.html