本人还没有上紫，打不了 $\text{Div.1}$ 。抱歉

A Array Rearrangment

分析

贪心的考虑 $A,B$ 的匹配。把 $A$ 由小到大排序， $B$ 由大到小排序。那么合法方案当 $\max\{A_i +B_i \} \le x$ 就可以了。时间复杂度为 $O(Tn\log n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long log
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
int n,x;
const int N = 1e6 + 100;
int a[N],b[N];
int main() {
    int T = read();
    while(T--) {
        n=read();x=read();int f=0;
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++)b[i]=read();
        sort(a+1,a+1+n);sort(b+1,b+1+n);
        for(int i=1;i<=n;i++){
            if(a[i]+b[n-i+1]>x){
                puts("No");f=1;break;
            }
        }
        if(!f)puts("Yes");    
    }
}

B Elimination

分析

阅读题，不做分析，考虑 $200$ 人参赛就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 1e6 + 100;
int main() {
    int T = read();
    while(T--) {
        int a = read(),b = read(),c = read(),d = read();
        printf("%d\n",max(a + b,c + d));
    }
}

C Division

分析

我们可以质因数分解 $A,B$ 。那么 $A=p_1^{a_1}p_2^{a_2}..p_k^{a_k}$ ，同理 $B=p_1^{a_1}p_2^{a_2}..p_k^{a_k}$ 。那么要找到最大的 $C$ 。那么令 $D = \frac{A}{C}$ 。我们就是要找到最小的 $C$ 。由于 $C \not = k B$ ，所以 $B,A$ 只要在 $B$ 中出现的一个质数 $P$ 在 $A$ 中的指数小于在 $B$ 中就可以了。时间复杂度为 $O(T\sqrt{B})$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
    ll x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 1e6 + 100;
ll ksm(ll a,ll b){
    ll x = 1;
    for(;b;b >>= 1,a = a * a){
        if(b & 1) x = x * a;
    }
    return x;
}
int main() {
    int T = read();
    while(T--) {
        ll x;
        ll a = read(),b = read();
        x = a;
        if(a % b != 0) {
            printf("%lld\n",a);
        }  
        else {
            ll ans = 1e18;
            for(ll i = 2;i * i <= b;i++) {
                if(b % i == 0) {
                    ll sum = 0;
                    while(b % i == 0) sum++,b /= i;
                    ll cc = 0;
                    while(a % i == 0) a /= i,cc++;
                    ans = min(ans,ksm(i,cc - sum + 1));
                }    
            }
            if(b != 1) {
                ll cc = 0;
                while(a % b == 0) a /= b,cc++;
                ans = min(ans,ksm(b , cc));                    
            }
            printf("%lld\n",x / ans);
        }
    }
}

D Divide and Sum

分析

考虑 $\sum{|p_i - q_i|}$ 。我们考虑到一个序列是由小到大，另一个由大到小。所以将 $2n$ 个数排完序，前 $n$ 的贡献一定是 $-a_i$ 后面的是 $a_i$ 。所以最后的答案就是 $ans={2n \choose n} (\sum_{1\le i\le n}a_i - \sum_{n+1\le j\le 2n}a_j)$ 。时间复杂度为 $O(n\log n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 1e6 + 100,mod = 998244353;
ll a[N],sum[N],fac[N],ifac[N];
ll ksm(ll a,ll b) {
    ll x = 1;for(;b;b>>=1,a=a*1ll*a%mod){
        if(b&1) x = x*1ll*a%mod;
    }return x;  
}
ll C(int a,int b) {
    return fac[a] * 1ll * ifac[b] % mod * 1ll * ifac[a - b] % mod;
}
int main() {
    int n = read();n *= 2;
    for(ll i = 1;i <= n;i++) a[i] = read();
    sort(a + 1,a + 1 + n);int ans = 0;
    for(ll i = 1;i <= n;i++) sum[i] = (1ll * sum[i - 1] + a[i]) % mod;
    fac[0] = 1;
    for(int i = 1;i <= n;i++) fac[i] = 1ll * i * fac[i - 1] % mod;
    ifac[n] = ksm(fac[n],mod - 2);
    for(int i = n - 1;i >= 0;i--) ifac[i] = (i + 1) * 1ll * ifac[i + 1] % mod;
//    cout << C(2,1) << endl;
    ll CC = (sum[n] - sum[n/2] * 2ll % mod + mod) % mod;
    ans = CC * C(n,n/2) % mod;
    cout << ans << endl;
}

E Team-Building

分析

判断二分图，考虑有多少个奇环，代码来自一位大佬。用可撤销并查集。个人认为比 $D$ 简单。这里添加一些说明，至于为什么并查集可以维护是否为二分图，可以参加百度的扩展域并查集做法。

第一步，算出可以用的颜色集合。
第二步，算不同颜色是否构成二分图。
第三步，把互不影响的两个集合的答案算出来，也就是 ${n \choose 2}$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+3,M=1e6+3,O=2e6+3;
int c[N],a[N],b[N],id[O],tp;
bool f[N];
struct P{
    int f,sz;
}d[M],st[O];
int gf(int x){return d[x].f==x?x:gf(d[x].f);}
void mg(int x,int y){
    int u=gf(x),v=gf(y);
    if(d[u].sz>d[v].sz)swap(u,v);
    st[++tp]=d[u],id[tp]=u,st[++tp]=d[v],id[tp]=v;
    d[v].sz+=d[u].sz,d[u].f=v;
}
map<pair<int,int>,int>mp;
vector<int>vc[N];
int main(){
    int n,m,k,i,j,l,u,v,w,uu,vv,tt,uuu,vvv;
    long long ans=0;
    scanf("%d%d%d",&n,&m,&k);
    for(i = 1;i <= n;++i) scanf("%d",c+i);
    for(i = 1;i <= n*2;++i) d[i].f=i,d[i].sz=1;
    for(i = 1;i <= m;++i) scanf("%d%d",a+i,b+i);
    for(i = 1;i <= m;++i) if(c[a[i]]==c[b[i]]) {
        u = gf(a[i]),v = gf(b[i]);
        if(u==v)f[c[a[i]]]=1;
        else mg(a[i],b[i]+n),mg(b[i],a[i]+n);
    }
    for(i=1,j=0;i<=m;++i)if(c[a[i]]!=c[b[i]]&&!f[c[a[i]]]&&!f[c[b[i]]]){
        u=c[a[i]],v=c[b[i]];
        if(u>v)swap(u,v);
        l=mp[{u,v}];
        if(!l)l=mp[{u,v}]=++j;
        vc[l].push_back(i);
    }
    for(auto o:mp){
        u=o.first.first,v=o.first.second,w=o.second,tt=tp;
        for(int o2:vc[w]){
            uu=a[o2],vv=b[o2],uuu=gf(uu),vvv=gf(vv);
            if(uuu==vvv){
                --ans;
                break;
            }
            mg(uu,vv+n),mg(uu+n,vv);
        }
        while(tp!=tt)d[id[tp]]=st[tp],--tp;
    }
    for(i=1,j=0;i<=k;++i)if(!f[i])++j;
    ans+=j*1ll*(j-1)/2;
    printf("%lld",ans);
    return 0;
}

Codeforces Round #680 Div. 2 题解

A Array Rearrangment

分析

代码

B Elimination

分析

代码

C Division

分析

代码

D Divide and Sum

分析

代码

E Team-Building

分析

代码