讨论
ABC306 CDE 题解 -fangyanli
ABC306 CDE 题解 -fangyanli
fangyanli
2023-08-17 8:36:32
2023-08-17 8:37:00
2
C题
题意：一共个数，要找出每个数第二次出现的位置，并从小到大排序后输出原数
思路：边读入统计每个数出现次数，等于两次就输出
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c[300001];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=3*n;i++){
int a;
cin>>a;
c[a]++;
if(c[a]==2){
cout<<a<<" ";
}
}
}
D题
题意：一共有个菜，每个菜有两个属性,，意思为:
- X = 0 表示第道菜有解毒功效
- X = 1 表示第道菜有毒
- Y 表示第道菜的美味值
高桥君一开始十分舒服，在吃了有毒的菜后会中毒; 中毒时，如果再吃有毒的菜就会原地升天，吃有解毒功效就会重回十分舒服的状态；高桥君对于每道菜可以选择吃或不吃;
求他在不升天的情况下所吃食物的美味值的和的最大值
思路：开个二维dp,,表示前i道菜在j状态下的美味值的和的最大值
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,dp[300001][2];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
if(x==0){ dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]+y,dp[i-1][0]+y)); dp[i][1]=dp[i-1][1]; }
else{ dp[i][1]=max(dp[i-1][1],dp[i-1][0]+y); dp[i][0]=dp[i-1][0]; }
}
cout<<max(dp[n][0],dp[n][1]);
}
E题
题意：长度为的数组最开始所有项均为0,一共有次操作每次操作把 的第 X 个数改为 ，同时输出前大的数之和
思路：和对顶堆有点像但我还是用了map统计个数，数组维护分界线
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,q,a[500010],ans,cnt;
map<int,int> m;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>k>>q;
m[0]=n;
map<int,int>::iterator it=m.begin();
while(q--){
int x,y,last;
cin>>x>>y;
last=a[x];
a[x]=y;
if(last==y){
cout<<ans+(it->first)*(k-cnt)<<"\n";
}
else {
m[last]--;
m[y]++;
if(last<=it->first&&y>it->first){
cnt++;
ans+=y;
}
else if(last>it->first&&y<=it->first){
cnt--;
ans-=last;
}
else if(last>it->first&&y>it->first){
ans+=(y-last);
}
if(!m[last]){
if(it->first==last){
if(it!=m.begin()){
it--;
}
else {
it++;
cnt-=it->second;
ans-=(it->first)*(it->second);
}
}
m.erase(last);
}
while(cnt>=k){
it++;
cnt-=it->second;
ans-=(it->second)*(it->first);
}
while(cnt+it->second<k){
cnt+=it->second;
ans+=(it->second)*(it->first);
it--;
}
cout<<ans+(it->first)*(k-cnt)<<"\n";
}
}
}
{{ vote && vote.total.up }}
