题目讲解:【比赛题目讲解】牛客小白月赛90_哔哩哔哩_bilibili
题号 | 标题 | 已通过代码 | 通过率 | 我的状态 |
---|---|---|---|---|
A | 小A的文化节 | 点击查看 | 1555/1726 | 通过 |
B | 小A的游戏 | 点击查看 | 1516/1987 | 通过 |
C | 小A的数字 | 点击查看 | 1166/3968 | 通过 |
D | 小A的线段(easy version) | 点击查看 | 614/1214 | 通过 |
E | 小A的任务 | 点击查看 | 342/888 | 通过 |
F | 小A的线段(hard version) | 点击查看 | 26/176 | 未通过 |
C.小A的数字
思路:分类讨论。可以观察样例发现,0这个数字比较特殊,若数字里没0,只要填个个位数就行(1或2)。若数字里有0,那么0这个位置就填1,想让数字最小,那么1的位置填0,0的位置填1。
#include<bits/stdc++.h>
using namespace std;
int T;
char s[12];
int main(){
cin>>T;
while(T--){
cin>>&s[1];
int n = strlen(s+1),pos = n;
for(int i=1;i<=n;i++){
if(s[i]=='0'){
pos = i;
break;
}
}
if(pos == n){
if(s[n]=='1') cout<<2<<endl;
else cout<<1<<endl;
}else{
for(int i=pos;i<=n;i++){
if(s[i]=='0') cout<<1;
else cout<<0;
}
cout<<endl;
}
}
return 0;
}
D.小A的线段
思路:dfs+差分+前缀和。蓝桥杯里面就有这么一个dfs我没写出来,正好学学。
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,use[12],l[12],r[12],c[100010];
void dfs(int now){
if(now==m+1){
memset(c,0,sizeof c);
for(int i=1;i<=m;i++){
if(use[i]){
c[l[i]]++;
c[r[i]+1]--;
}
}
int f = 1;
for(int i=1;i<=n;i++){
c[i]+=c[i-1];
if(c[i]<2) f = 0;
}
if(!f) return;
ans++;
return;
}
use[now] = 1;
dfs(now+1);
use[now] = 0;
dfs(now+1);
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>l[i]>>r[i];
}
dfs(1);
cout<<ans<<endl;
return 0;
}
E.小A的任务
思路:本质是枚举,使用前缀和计算A任务的时间,使用优先队列(大根堆)存储选B任务的代价,通过枚举找到最小值。看起来很像dp的一道题。我感觉使用dp也能写,不过我不会。其实题目的思路很简单,当k等于2时,就是考虑在前2或3或4...n个任务里完成两个B任务的最短时间。A任务是必须做的,所以使用前缀和计算。B任务可以选做,所以一定是选值比较低的进入优先队列会更优。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q;
int a[100010],b[100010];
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
int k;
while(q--){
cin>>k;
priority_queue<ll> st;
ll ans = 1e18,sum=0,stsum=0;
for(int i=1;i<=n;i++){
sum+=a[i];
st.push(b[i]);stsum += b[i];
if(st.size()>k){
stsum-=st.top();st.pop();
}
if(st.size()==k) ans = min(ans,sum+stsum);
}
cout<<ans<<endl;
}
return 0;
}