这期的题目整体比较简单,相比之前的都简单
第一题-塔子哥送粉丝周边
简单排序
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+100;
struct str{
int num;
int s;
}st[N];
bool cmp(str a,str b){
if(a.s!=b.s){
return a.s>b.s;
}else{
return a.num<b.num;
}
}
signed main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
st[i].num=i;
st[i].s=x+2*y;
}
sort(st+1,st+1+n,cmp);
vector<int> p;
for(int i=1;i<=k;i++){
p.push_back(st[i].num);
}
sort(p.begin(),p.end());
for(auto pi:p) cout<<pi<<" ";
return 0;
}
第二题-塔子哥的优秀题解
优先队列维护下,写代码必须专注,脑袋别混乱,刚开始的时候输入写错了
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+100;
struct str{
int a,b;
}st[N];
bool cmp(str aa,str bb){
return aa.b>bb.b;
}
priority_queue<int,vector<int> ,greater<int>> q;
int n,k;
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>st[i].a;
}
for(int i=1;i<=n;i++){
cin>>st[i].b;
}
// for(int i=1;i<=n;i++) cout<<st[i].a<<" "<<st[i].b<<endl;
sort(st+1,st+1+n,cmp);
// for(int i=1;i<=n;i++) cout<<st[i].a<<" "<<st[i].b<<endl;
int sum=0,ans=0;
for(int i=1;i<=k;i++){
sum+=st[i].a;
q.push(st[i].a);
}
ans=sum*st[k].b;
// cout<<ans<<" "<<sum<<" "<<st[k].b<<endl;
for(int i=k+1;i<=n;i++){
ans=max(ans,(st[i].a+sum-q.top())*st[i].b);
if(q.top()<st[i].a){
sum-=q.top();
q.pop();
sum+=st[i].a;
q.push(st[i].a);
}
}
cout<<ans;
return 0;
}
第三题-塔子哥的题解点赞方案
简单DP一下
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e3+100;
const int mod = 1e9+7;
int dp[N][N],sum[N];
int n,m;
char str[N];
/*
dp[i,j]=dp[i-1,j]
*/
signed main(){
memset(dp,0,sizeof(dp));
cin>>n>>m>>(str+1);
// for(int i=1;i<=n;i++) cout<<str[i]<<" ";cout<<endl;
// dp[i,j]:表示当前已经处理到第i位,且以j为结尾的方案数
for(int i=1;i<=m;i++){
dp[1][i]=1;
sum[i]=sum[i-1]+1;
}
for(int i=2;i<=n;i++){
if(str[i-1]=='='){
for(int j=1;j<=m;j++) dp[i][j]=dp[i-1][j];
}else if(str[i-1]=='<'){
for(int j=1;j<=m;j++) dp[i][j]=sum[j-1];
}else if(str[i-1]=='>'){
for(int j=1;j<=m;j++) dp[i][j]=(sum[m]-sum[j]+mod)%mod;
}
for(int j=1;j<=m;j++) sum[j]=(sum[j-1]+dp[i][j])%mod;
}
int ans=0;
for(int i=1;i<=m;i++) ans=(ans+dp[n][i])%mod;
cout<<ans;
return 0;
}
标签:2024.4,小红书,long,st,int,str,康复训练,const,dp
From: https://www.cnblogs.com/pengge666/p/18165748