Codeforces Round #680 (Div. 2）A,B,C,D

文章目录

• A. Array Rearrangment
• B. Elimination
• C. Division
• D. Divide and Sum

A. Array Rearrangment

把两个数组从小到大排序，判断一下即可。

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int T;
int n,x;
int a[N],b[N];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&x);
        for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
        for(int i=1;i<=n;++i)
        scanf("%d",&b[i]);
        sort(a+1,a+1+n);
        sort(b+1,b+1+n,greater<int>());
        bool flag=0;
        for(int i=1;i<=n;++i)
        {
            if(a[i]+b[i]>x)
            {
                flag=1;
                puts("No");
                break;
            }
        }
        if(!flag)
        puts("Yes");
    }
    return 0;
}

           

B. Elimination

前一个条件，给了第一百名的下限，后一个条件给出了第一百名的另一个下限，取最大的那个即可。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        printf("%d\n",max(a+b,c+d));
    }
    return 0;
}

           

C. Division

这题要找一个最大x，满足p%x==0&&x%q!=0。首先如果，p%q!=0，那么x就是p。否则，p%q=0,那么，p一定包含q的所有质因数分解的结果。如果要找最大的x，每次最少要使p除以一个其包含的素数，那要怎么样才能使此时p%q!=0呢，只要让p的其中一个q有的质因子降到q有的那个质因子次幂之下，就能满足条件。比如p=12,q=6,p的质因子分解为22*3,q的质因子分解为2*3，我们要么把p的22消到2之下即到20,要么把p的3消到3之下，即30，这样都能使p%q!=0。显然消3能使p更大。所以我们找到q的所有质因子分解，看该质因子p要消几次幂才能到q的该质因子的幂次之下，然后找一个权值最小的，p除以改值就是答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll inf=1e18+5;
bool check(ll x)
{
    for(ll i=2;i*i<=x;++i)
    {
        if(x%i==0)
        return false;
    }
    return true;
}
ll mi;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll p,q;
        scanf("%lld%lld",&p,&q);
        if((p%q)!=0)
        {
            printf("%lld\n",p);
            continue;
        }
        else
        {
             mi=inf;
             ll i;
             for(i=2;i*i<=q;++i)
             {
                 if(q%i==0)
                 {
                     ll tmp=1;
                     while(q%i==0)
                     {
                         q/=i;
                         tmp*=i;
                     }
                     ll tmp3=p;
                     ll cnt=1;
                     while(tmp3%i==0)
                     {
                         cnt*=i;
                         tmp3/=i;
                     }
                     mi=min(mi,(cnt/tmp)*i);
                 }
             }
             if(q>1)
             {
                 ll tmp3=p;
                 ll cnt=1;
                 while(tmp3%q==0)
                 {
                    cnt*=q;
                    tmp3/=q;
                 }
                 mi=min(mi,cnt);
             }
             //cout<<mi<<endl;
             printf("%lld\n",p/mi);
        }
    }
    return 0;
}

           

D. Divide and Sum

一道结论题，我们发现无论怎么划分，产生的花费都是一样的，所以答案就是方案数(C(2n,n))*cost(每次的花费)。简单证明一下，因为，无论怎么划分，都是n*|xi-xj|，x数组排完序后，对于x1无论怎么划分，最后都贡献其负数，那么对于x2能不能贡献正数呢，也是不能的，因为如果x2要共献正数，那么其必须和x1配对，但显然是不可能的。再看上面序列最大的xn，其和前1~n-1配对会贡献正数，但是如果把前1~n-1的拿到下面，下面比xn大的就会到上面来，始终不会出现那种情况。由此往后推出前1~n的xi必贡献负数，后n+1~2n必贡献正数。

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=3e5+5;
int n;
ll a[N];
ll quickpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
        res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=(n<<1);++i)
    scanf("%lld",&a[i]);
    sort(a+1,a+1+(n<<1));
    ll t1=1;
    ll t2=1;
    for(int i=1;i<=n;++i)
    {
        t1*=i;
        t1%=mod;
    }
    for(int i=1;i<=n;++i)
    {
        t2*=(n+i);
        t2%=mod;
    }
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        ans+=a[i+n]-a[i];
        ans%=mod;
    }
    printf("%lld\n",ans*(t2*quickpow(t1,mod-2)%mod)%mod);
    return 0;
}