Codeforces Global Round 19 A B C D

A. Sorting Parts

思路： 如果有后面的数小于前面统计的最大的数，那么一定是$YES$，因为以此为分界点两边$sort$，一定不会形成升序序列。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=1e4+10;
int a[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int ma=0;
        int n;
        cin>>n;
        bool ok=false;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]<ma){
                ok=true;
            }
            ma=max(ma,a[i]);
        }
        if(ok)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

B. MEX and Array

• Tip：阅读理解、greedy

  思路： 你说这道题简单嘛，我说题目真难读懂，你说难嘛，读懂之后发现就那样，所以觉得就是个阅读理解题。本质意思就是从$1$开始枚举区间长度，最长为$n$。然后每次枚举里面计算最大的$cost$。那么最大的$cost$就是将区间内所有的数全部单独分块，如果碰到$0$就多加上$1$。Proof：如果不单独分块，那么每合并一个单独块总共献一定会少1，那么仅当合成的块是不间断的情况下才能和全部单独分块获得的贡献相等。例如(MEX(0，1，2，3，4，…n)=1+n+1)==MEX(0)+MEX(1)+....+MEX(n)=n+1+MEX(0)=n+1+1），所以MEX(a1，a2，a3，…an)<=MEX(a1)+MEX(a2)+…+MEX(an) 所以将所有长度区间的所有情况且所有元素全部单独分块，最后统计一下总贡献即可。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=110;
int a[N];
void solve(){
    int n;
    cin>>n;
    int res=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int len=1;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            for(int j=i;j<=i+len-1;j++){
                if(a[j]==0)res++;
            }   
            res+=len;
        }
    }
    cout<<res<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C. Andrew and Stones

• Tip:greedy

  思路： 感觉$C<B$，感觉比较明显，$NO$无非就两种情况。1：全是1。2:n的长度为3，且中间那个数是奇数。 其余的情况都可以$YES$，首先我们得把奇数全部消掉，每次消奇数操作会少一个偶数，同时也会多一个偶数(奇数$+1$变偶数)。所以我们先统计奇数个数，得花奇数个次数去消奇数，剩余的就是将所有的偶数全部放到首尾，两个两个放。总次数就是偶数个数+奇数个数。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=1e5+10;
int a[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    bool ok=false;
    for(int i=2;i<=n-1;i++){
        if(a[i]==1)continue;
        else ok=true;
    }
    if(!ok){
        cout<<"-1"<<endl;
        return ;
    }
    if(n==3){
        if(a[2]%2){
            cout<<"-1"<<endl;
            return ;
        }
        else{
            cout<<a[2]/2<<endl;
            return ;
        }
    }
    int cnt1,cnt2;
    cnt1=cnt2=0;
    for(int i=2;i<=n-1;i++){
        cnt2+=a[i]/2;
        if(a[i]%2)cnt1++;
    }
    cout<<cnt1+cnt2<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

D. Yet Another Minimization Problem

• Tip：math 、dp

思路： 首先推公式，将题目总贡献的公式进行化简，看看真正对题目有影响的变量是啥。

Let $s = \sum_{i=1}^{n} a_i$.

$cost = (n - 1) \cdot \sum_{i=1}^{n} a_i^2 + \sum_{i=1}^n (a_i \cdot (s - a_i)) = (n - 1) \cdot \sum_{i=1}^{n} a_i^2 + s^2 - \sum_{i=1}^{n} a_i^2 = (n - 2) \cdot \sum_{i=1}^{n} a_i^2 + (\sum_{i=1}^n a_i)^2$.

Then the total cost of two arrays equals to $(n - 2) \cdot \sum_{i=1}^{n} (a_i^2 + b_i^2) + (\sum_{i=1}^n a_i)^2 + (\sum_{i=1}^n b_i)^2$. The first term is a constant $\Rightarrow$ we need to minimize $(\sum_{i=1}^n a_i)^2 + (\sum_{i=1}^n b_i)^2$.

接下去就是尽量让$(\sum_{i=1}^n a_i)^2 + (\sum_{i=1}^n b_i)^2$最小即可。我们可以将$b[i]$和$a[i]$中最小的数存到$a[i]$中，因为这个等式很明显，前者和后者尽可能接近，那么总的贡献值会最小。 我们可以枚举$a$数组中所有可能获得的值。可以通过01背包的枚举来实现，也可以用$BitSet$直接存下所有的可能进行遍历取一个最小的值。因此本题我用两种方法来实现。

• 参考代码1(01背包)：

 #include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=110;
int a[N];
int b[N];
int c[N];
int f[N][N*N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        int smin=0,smax=0;
        int sumc=0;
        int ans=0;
        for(int i=1;i<=n;i++){
            if(a[i]>b[i])swap(a[i],b[i]);
            smin+=a[i];
            smax+=b[i];
            sumc+=(b[i]-a[i]);
            c[i]=(b[i]-a[i])*2;//因为要找到a和b的总和尽可能接近，所以如果相差10，只需要分配5，可以转化为体积*2
            ans+=(n-2)*(a[i]*a[i]+b[i]*b[i]);
        }
        memset(f,0,sizeof f);
        for(int i=1;i<=n;i++){
            for(int j=sumc;j>=0;j--){//sumc<=n*n，所以是O(n^3)
                f[i][j]=f[i-1][j];
                if(j>=c[i]){//当前物品可以选择
                    f[i][j]=max(f[i][j],f[i-1][j-c[i]]+c[i]/2);
                }
            }
        }//最后的f[n][sumc]就是最接近a和b差一半的值。
        ans+=(smin+f[n][sumc])*(smin+f[n][sumc])+(smax-f[n][sumc])*(smax-f[n][sumc]);
        cout<<ans<<endl;
    }
    return 0;
}

• 参考代码2(BitSet):

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=110;
int a[N];
int b[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        int smin=0,smax=0;
        int sumc=0;
        int ans=0;
        for(int i=1;i<=n;i++){
            if(a[i]>b[i])swap(a[i],b[i]);
            smin+=a[i];
            smax+=b[i];
            sumc+=(b[i]-a[i]);
            ans+=(n-2)*(a[i]*a[i]+b[i]*b[i]);
        }
        int res=ans;
        ans+=smin*smin+smax*smax;
        bitset<N*N>dp;
        dp[0]=1;
        for(int i=1;i<=n;i++){//直到最后一个1，前面所有的组合都成立。
            dp|=dp<<(b[i]-a[i]);
        }
        for(int i=1;i<=smax-smin;i++){
            if(dp[i]){//可以转移多少
                ans=min(ans,res+(smin+i)*(smin+i)+(smax-i)*(smax-i));
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}