[C++知识库]补题计划Codeforces Round #680 div2

https://codeforces.com/contest/1445

A 思维

#include<bits/stdc++.h>
using namespace std;
const int maxn=60;
int a[maxn],b[maxn];
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,x;
        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+n+1);
        sort(b+1,b+n+1);
        bool success=true;
        for(int i=1;i<=n;i++)
        {
            if(a[i]+b[n-i+1]>x)
            {
                success=false;
                break;
            }
        }
        if(success)printf("Yes\n");
        else printf("No\n");
    }
}

B思维

最低情况100人a+b，100人d+c

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,d+c));
    }
}

C 欧拉筛后对q分解质因子

考虑特列p本身不能被q整除。

再考虑p能被q整除，意味着p中所有质数因子的指数是大于q中对应质因子的质数的。可以在纸上尝试写下p和q的质因数分解。

所以只需要让p中仍和一个质因子的指数小于q的对应质因子指数就好了。接下来就是简单的枚举质因子。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int prime[maxn],cnt;
bool st[maxn];
void init()
{
    for(int i=2;i<maxn;i++)
    {
        if(!st[i])prime[cnt++]=i;
        for(int j=0;prime[j]*i<maxn;j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }
    }
}
ll get(ll p,int q,int prim)
{
    while(p%q==0)
    p/=prim;
    return p;
}
int main()
{
    int T;
    scanf("%d",&T);
    init();
    while(T--)
    {
        ll p,q;
        cin>>p>>q;
        ll res=0;
        int t=q;
        for(int i=0;i<cnt;i++)
        if(t%prime[i]==0)
        {
            while(t%prime[i]==0)t/=prime[i];
            res=max(res,get(p,q,prime[i]));
            // cout<<prime[i]<<endl;
        }
        if(t>1)res=max(res,get(p,q,t));
        cout<<res<<endl;
    }
}

D 思维，组合数

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
ll a[maxn];
const int p=998244353;
int qmi(int a, int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}
 
int C(int a, int b)
{
    if (a < b) return 0;
 
    int down = 1, up = 1;
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        up = (ll)up * i % p;
        down = (ll)down * j % p;
    }
 
    return (ll)up * qmi(down, p - 2) % p;
}
 
int Lucas(int a, int b)
{
    if (a < p && b < p) return C(a, b);
    return (ll)Lucas(a / p, b / p) * C(a % p, b % p) % p;
}
int main()
{
    int n;
    scanf("%d",&n);
    int nn=n+n;
    for(int i=1;i<=nn;i++)scanf("%lld",&a[i]);
    sort(a+1,a+nn+1);
    ll res=0;
    for(int i=1;i<=n;i++)
    res+=a[i+n]-a[i];
    res=(res+p)%p;
    res=res*Lucas(2*n,n)%p;
    cout<<res<<endl;
}

E? 这题debug了好久，最后看了别人题解才搞出来

贴个题解链接https://www.cnblogs.com/George1123/p/13912680.html

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
#define mp(a,b) make_pair((a),(b))
#define x first
#define y second
const int maxn=5e5+10;
struct node
{
    int p[maxn],dep[maxn];
    int find(int x)
    {
        if(p[x]!=x)
        {
            int nex=find(p[x]);
            dep[x]^=dep[p[x]];
            p[x]=nex;
        }
        return p[x];
    }
}d[2];
map<pii,int> mp;
pii me[maxn];
vector<pii> e[maxn];
int cnt;
int c[maxn];
int n,m,k;
bool st[maxn];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&c[i]);c[i]--;
    }
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        a--,b--;
        if(c[a]>c[b])swap(a,b);
        pii t=mp(c[a],c[b]);
        if(!mp.count(t))
        {
            mp[t]=cnt;
            me[cnt]=t;
            cnt++;
        }
        e[mp[t]].push_back({a,b});
    }
    iota(d[0].p,d[0].p+n,0);
    ll res=k;
    for(int i=0;i<k;i++)
    if(mp.count(mp(i,i)))
    {
        for(pii t:e[mp[mp(i,i)]])
        {
            int x=d[0].find(t.x),y=d[0].find(t.y);
            if(x==y&&d[0].dep[t.x]^d[0].dep[t.y]==0)
            {
                res--;
                st[i]=true;
                break;
            }
            d[0].dep[x]=d[0].dep[t.y]^1^d[0].dep[t.x];
            d[0].p[x]=y;
        }
    }
    res=res*(res-1)/2;
    for(int i=0;i<cnt;i++)
    {
        if(me[i].x==me[i].y)continue;
        if(st[me[i].x]||st[me[i].y])continue;
        for(auto t:e[i])
        {
            int xi=d[0].find(t.x),yi=d[0].find(t.y);
            d[1].dep[xi]=0,d[1].dep[yi]=0;
            d[1].p[xi]=xi,d[1].p[yi]=yi;
        }
        for(auto t:e[i])
        {
            int xi=d[0].find(t.x),yi=d[0].find(t.y);
            int x=d[1].find(xi),y=d[1].find(yi);
            if(x==y&&d[1].dep[xi]^d[1].dep[yi]^d[0].dep[t.x]^d[0].dep[t.y]==0)
            {
                res--;
                break;
            }
            d[1].dep[x]=d[1].dep[xi]^d[1].dep[yi]^d[0].dep[t.x]^d[0].dep[t.y]^1;
            d[1].p[x]=y;
        }
    }
    cout<<res<<endl;
}