提交记录GD-S34460
2026-10-03 15:16:24
发布于：广东
18阅读
0回复
0点赞
第一题
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using arr=array<ll,2>;
ll n,k;
void solve(){
cin>>n>>k;
vector<ll>a(n+10);
vector<ll>front(n+10,0);
vector<ll>back(n+10,0);
for(ll i=1;i<=n;i++){
cin>>a[i];
}
//显然，当len<=k时，sum=(a[i]+...+a[i+len-1])
// 当len>k时，sum=a[i]到a[i+len-1]个数中
// 前k个最小数的和
//即选min(len,k)个最小值
{
priority_queue<ll>pq;
//pq:存储最大的一个
for(ll i=1;i<=n;i++){
front[i]=front[i-1];
if(pq.size()<k){
pq.push(a[i]);
front[i]+=a[i];
}else{
if(a[i]<pq.top()){
front[i]-=pq.top();
front[i]+=a[i];
pq.push(a[i]);
pq.pop();
}
}
}
}
//pq:存储最大的一个
//back需逆序遍历
priority_queue<ll>pq;
for(ll i=n;i>=1;i--){
back[i]=back[i+1];
if(pq.size()<k){
pq.push(a[i]);
back[i]+=a[i];
}else{
if(a[i]<pq.top()){
back[i]-=pq.top();
back[i]+=a[i];
pq.pop();
pq.push(a[i]);
}
}
}
for(ll i=1;i<n;i++){
cout << front[i]<<" "<<back[i+1]<<"\n";
}
}
int main(){
freopen("kirst.in","r",stdin);
freopen("kirst.out","w",stdout);
//ll t;cin>>t;while(t--)
solve();
return 0;
}
第二题
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using arr=array<ll,2>;
ll n;
const ll mod=998244353;
void solve(){
cin>>n;
//��Ȼ���Ҳ�֪����ô��
//�����Ӧ�ø�ƽ�����й�
//1 -> 1(1)[1]
//2 -> 1(1.4)[1] =>3��1
//3 -> 1(1.7)[1]
//4 -> 2(2)[1,2] +2?
//5 -> 2(2.~)[1,2]
//6 -> 2(2.~)[1,2] =>5��2
//7 -> 2(2.~)[1,2]
//8 -> 2(2.~)[1,2]
//9 -> 3(3)[1,2,3]
//10-> 3(3.~)[1,2,3] =>(9~16)=>7����
//11-> 3(3.~)[1,2,3]
//......
//���Եó����۷�����k�����2*k+1���غ�
//�����Ϊsqrt(n)
//����ǰ����sqrt(n)-1
ll sum=0;
for(ll i=1;i<ll(sqrt(n));i++){
(sum+=i*(2*i+1))%=mod;
}
ll k=sqrt(n);
for(ll i=ll(sqrt(n))*ll(sqrt(n));i<=n;i++){
(sum+=k)%=mod;
}
cout << sum%mod;
}
int main(){
freopen("secret.in","r",stdin);
freopen("secret.out","w",stdout);
//ll t;cin>>t;while(t--)
solve();
return 0;
}
第三题
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using arr=array<ll,2>;
void solve(){
//ע�,n�dz�С��m�dz���
//����������˫ָ�룿O(n+m)
//���ܿ���û��ô��
//ABB
//BBBBBA
//���������������Ϊ1
//��ʵ��ӦΪ2
//����Ӧ����ͼ���㷨����
//��δ�ͼ��
ll n,m;cin>>n>>m;
string s1,s2;cin>>s1>>s2;
bool x=true;
for(ll i=1;i<s1.size();i++){
if(s1[i]!=s1[i-1]) x=false;
}
if(x){
ll ans=0;
for(ll i=1,j=1;i<=n&&j<=m;i++){
while(j<=m&&s2[j]!=s1[i]) j++;
ans++;
}
cout << ans;
}else{
}
}
int main(){
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
//ll t;cin>>t;while(t--)
solve();
return 0;
}
第四题
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using arr=array<ll,2>;
vector<arr>it;
ll n,m,t;
map<ll,ll>mp;
void solve(){
cin>>n>>m>>t;
it=vector<arr>(n+10);
for(ll i=1;i<=n;i++) cin>>it[i][0]>>it[i][1];
sort(it.begin()+1,it.begin()+n+1,greater<arr>());
for(ll i=1;i<=n;i++){
ll cnt=0,l=1,r=n,w=m;
while(l<=r&&cnt+2<i&&w>0){
while(w-it[r][1]<0) r--;
w-=it[r][1];
while(w-it[l][1]<0) l++;
w-=it[l][1];
l++;r--;
cnt+=2;
}
while(w-it[l][1]<0) l++;
if(l>r) mp[i]=-1;
else mp[i]=it[l][0];
}
while(t--){
ll q;
cin>>q;
cout << mp[q]<<"\n";
}
}
int main(){
freopen("median.in","r",stdin);
freopen("median.out","w",stdout);
//ll t;cin>>t;while(t--)
solve();
return 0;
}
第一题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n,k,a[N];
int main()
{
freopen("kirst.in","r",stdin);
freopen("kirst.out","w",stdout);
cin >> n >> k;
priority_queue<ll,vector<ll>,greater<ll> > left,right;
for (int i = 1;i <= n;i++)
cin >> a[i];
for (int i = 1;i < n;i++)
{
for (int j = 1;j <= i;j++)
{
left.push(a[j]);
}
for (int j = i + 1;j <= n;j++)
{
right.push(a[j]);
}
ll ans1 = 0,ans2 = 0;
for (int j = 1;j <= min(k,i);j++)
{
ans1 += left.top();
left.pop();
}
for (int j = 1;j <= min(k,n - i);j++)
{
ans2 += right.top();
right.pop();
}
while (left.size()) left.pop();
while (right.size()) right.pop();
cout << ans1 << ' ' << ans2 << '\n';
}
return 0;
}
第二题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 998244353;
int main()
{
freopen("secret.in","r",stdin);
freopen("secret.out","w",stdout);
ll n;
cin >> n;
double cnt = 0;
double a = 0;
for (int i = 1;i <= n;i++)
{
int j = 1;
while (j * j <= i)
{
cnt++;
j++;
}
a++;
}
ll ans = cnt / a * n;
cout << (ans % mod);
return 0;
}
第三题
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
int n,m,dp[N][N];
char a[N],b[N];
int main()
{
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= m;i++) cin >> b[i];
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
}
}
cout << dp[n][m];
return 0;
}
第四题
#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
int n,m,t;
struct node
{
int v,w;
bool used = 0;
}a[N];
bool cmp1(node x,node y)
{
return x.w < y.w;
}
bool cmp2(node x,node y)
{
return x.v > y.v;
}
int main()
{
freopen("median.in","r",stdin);
freopen("median.out","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m >> t;
for (int i = 1;i <= n;i++) cin >> a[i].v >> a[i].w;
int q,ans = 0;
sort(a + 1,a + 1 + n,cmp1);
while (t--)
{
int mm = m;
cin >> q;
int i = 1;
if (q == 1)
{
sort(a + 1,a + 1 + n,cmp2);
for (node p : a)
{
if (mm - p.w >= 0) ans = p.v;
else break;
}
cout << ans << '\n';
continue;
}
for (;i <= q / 2;i++)
{
mm -= a[i].w;
a[i].used = 1;
}
sort(a + 1,a + 1 + n,cmp2);
ans = a[i].v;
cout << ans << '\n';
}
return 0;
}
有帮助，赞一个