[数据结构与算法]Codeforces Round #680 (Div. 2 based on Moscow Team Olympiad)

A

题意：给两个长度为n的序列a，b，可以对b进行重新排列，判断是否满足a，b所有对应位置和小于x。

题解：将a从小到大排序，b从大到小排序，判断是否有位置和大于x，这样可以保证最大的和取最小。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k,a[N],b[N];
bool cmp(int a,int b)
{
	return a>b;
}
void solve()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>b[i];
	sort(a,a+n);
	sort(b,b+n,cmp);
	int flag=1;
	for(int i=0;i<n;i++){
		if(a[i]+b[i]>k){
			flag=0;
			break;
		}
	}
	if(flag)cout<<"Yes"<<'\n';
	else cout<<"No"<<'\n';
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

B

题意：猜的

#include <bits/stdc++.h>
using namespace std;
int n,k,a,b,c,d;
void solve()
{
	cin>>a>>b>>c>>d;
	cout<<max(a+b,c+d)<<'\n';
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

C

题意：给两个数p,q，找出最大的x，使得p%x==0，x%q!=0。

题解：若给出的p%q!=0，直接输出p，否则需要求出q的所有质因子，显然q的所有质因子也是p的质因子，我们要让p的质因子不包含q的所有质因子，这样就不会整除q了，只需用枚举q的质因子，p一直除q的质因子，直到符合情况求出最大值输出。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
	ll p,q;
	cin>>p>>q;
	if(p%q)cout<<p<<'\n';
	else{
		vector<ll>vc;
		ll b=q;
		for(ll i=2;i*i<=q;i++){
			while(b%i==0){
				b/=i;
				vc.emplace_back(i);
			}
		}
		if(b>1)vc.emplace_back(b);
		ll maxx=0;
		for(ll v:vc){
			ll a=p;
			while(a%q==0)a/=v;
			maxx=max(maxx,a);
		}
		cout<<maxx<<'\n';
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

D

题意：长度为2n的序列，取n个放在p序列(非递减)，n个放在q序列(非递增)，令，计算所有划分p，q序列的的和。

题解：先对2n个值进行从小到大排序，不难想到不管整个序列如何划分到p,q，前n个数对于这一种划分贡献的都是负数(若是将第n小的放到q，他肯定是放到后面，那么与其对应的p序列下标必定大于它，因为p序列后面放的是大的，假设p前n-1个都是最小的，因为第n小的放到q，那么肯定会多出大于第n个数的数放到p)，这样的话，只需算出后n个数-前n个数的和，然后乘可组合的情况数就可得出结果。

#include <bits/stdc++.h>
#define mod 998244353
#define ll long long
using namespace std;
const int N=3e5+5;
int n,k,a[N];
ll qpow(ll a,ll b)
{
	ll res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
void solve()
{
	cin>>n;
	for(int i=0;i<2*n;i++){
		cin>>a[i];
	}
	sort(a,a+2*n);
	ll ans=0,k1=1,k2=1;
	for(int i=0;i<n;i++){
		ans+=a[i+n]-a[i];
		k1=k1*(i+1)%mod;
		k2=k2*(i+1+n)%mod;
	}
	ll inv=qpow(k1,mod-2);
	cout<<ans%mod*k2%mod*inv%mod<<'\n';
	
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
	solve();
}