2026年10月3日(day3题解）
2026-10-03 17:07:07
发布于：广东
29阅读
0回复
0点赞
第一题
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
ll front_mi[N],back_mi[N];
void solve(){
int n,k;cin>>n>>k;
priority_queue<int>que;
for(int i=1;i<=n;i++)cin>>a[i];
ll sum=0;//维护队列中的结果
//前缀x个最小值 i,x//i递增或者递减动态x个最大值或者最小值
for(int i=1;i<=n;i++){
que.push(a[i]);sum+=a[i];
//优先队列的容量始终要维持在k的范围内
if(que.size()>k){
sum-=que.top();que.pop();
}
front_mi[i]=sum;
}
while(que.size())que.pop();//清空队列
sum=0;
for(int i=n;i>=1;i--){
if(que.size()>k){
sum-=que.top();que.pop();
}
back_mi[i]=sum;
que.push(a[i]);sum+=a[i];
}
for(int i=1;i<n;i++){
cout<<front_mi[i]<<' '<<back_mi[i]<<endl;
}
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第二题
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N],mod=998244353;
void solve(){
ll n;
cin>>n;
ll ans=0;
for(ll i=1;i*i<=n;i++){
ll L=(i*i),R=(i+1)*(i+1);
R=min(R,n+1);
ans=(ans+i*(R-L))%mod;
}
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第三题
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll dp[N];//dp[i]表示长度为i的最长匹配的最下位置
vector<ll>vec[30];//vec[i]存储字符i的所有出现下标 字符串b
//当前枚举字符x
// dp[1]=2; 4
// dp[2]=4;
// dp[3]=10
// dp[4]=20;
void solve(){
int n,m;
cin>>n>>m;
string a,b;cin>>a>>b;
a=' '+a;
b=' '+b;
for(int i=1;i<=n;i++)dp[i]=1e18;
for(int i=1;i<=m;i++){
vec[b[i]-'A'].push_back(i);//只存储对应字符的下标。
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=i-1;j>=0;j--){//枚举当前已有j个匹配好了的字符
if(dp[j]==1e18)continue;//没有对应结果，不能在此基础上增加
int c=a[i]-'A';
int inx=upper_bound(vec[c].begin(),vec[c].end(),dp[j])-vec[c].begin();
if(inx==vec[c].size())continue;//没找到
dp[j+1]=min(dp[j+1],vec[c][inx]);//更新找到的下标.
ans=max(ans,j+1);
}
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第四题
//给定n个数字
// //求数字的全排列
// 每个排列输出n个0/1
// 第i位置为1则表示第i个数字被选
// 否则第i个数字没有被选
// 2
// 10->只选第一个
// 01->只选第二个
// 11->两个全选。
// n
// 3
// 100=4
// 010=2
// 001=1
// 110=6
// 101=5
// 011=3
// 111=7
//状压->状态压缩
//拆分状压
//A=40->2^40
//总共有n<=40个学生
//总共有x<=60项技能//long long 多少位?64
//每个学生都会掌握一些技能
//A:3 4 6 7
//B:3 4 8
//
//00110110/A
//00110001/B //异或：同为0，异为1
//让学生自由组队，但是会有一个特殊的情况
//如果队伍里面有两个人会同一项技能的时候
//
//这两个人会失去这个技能。
//问总共有多少个不同的组队方案
//使得该队伍掌握所有技能
//
//20，20
//2^20 2^20
//1 2 5
//动态前缀k个最小值的和
//树状数组,前缀
//树状数组1：求前i个数字出现的次数
//树状数组2：求前i个数字的和
// 1 2 3 4 293487 293487 293487 293487
// 1 2 3 4 8
//1
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
#define pii pair<int,int>
ll a[N];
vector<pii>vec;
ll cal_front(int i,int x){
priority_queue<int>que;
while(i>=0){
que.push(vec[i].second);
if(que.size()>x)que.pop();
i--;
}
if(que.size()!=x)return 1e18;
ll sum=0;
while(que.size())sum+=que.top(),que.pop();
return sum;
}
ll cal_back(int i,int x){
priority_queue<int>que;
while(i<vec.size()){
que.push(vec[i].second);
if(que.size()>x)que.pop();
i++;
}
if(que.size()!=x)return 1e18;
ll sum=0;
while(que.size())sum+=que.top(),que.pop();
return sum;
}
int ans[N];
void solve(){
int n,m,t;
cin>>n>>m>>t;
for(int i=1;i<=n;i++){
int a,b;cin>>a>>b;
vec.push_back({a,b});
}
for(int i=0;i<=n;i++)ans[i]=-1;
sort(vec.begin(),vec.end());
int len=0;//对应左右两边的个数
for(int i=vec.size()-1;i>=0;i--){
if(cal_front(i-1,len)+cal_back(i+1,len)+vec[i].second<=m){
ans[len]=vec[i].first;
len++;
}
}
while(t--){
int x;cin>>x;
cout<<ans[x/2]<<endl;
}
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
这里空空如也
有帮助，赞一个