提交记录GD-S34460

第一题

   #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;
}