Codeforces Global Round 19 A - E

https://codeforces.com/contest/1637

选择一个长度len，将前len个数和后面的数分别排序，问是不是总能把数组排好

显然只有数组之前已经排好序才行

#include 

using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector a(n);
        for(auto &i : a) cin >> i;
        if(!is_sorted(a.begin(), a.end())) cout << "YESn";
        else cout << "NOn";
    }
    return 0;
}

按照给定的规则，问这个数组的所有子数组划分之后的最大值这题想了好久，想不出来这个最优解是什么，实际上把一个长度为k的数组分成k段总是最优的，没有0的时候这样分分出来是k，使用其他的分法比如说随便分一个，假设说分出来两个区间长度分别为 l , r l, r l,r，这里 l + r = k l+r=k l+r=k，那么这时候答案是 2 + 0 + 0 = 2 ≤ k 2+0+0=2leq k 2+0+0=2≤k最多也就分出来 k k k个；即使有0,对于答案的贡献也是全分出来更大，因为 m e x ( 0 ) = 1 mex(0)=1 mex(0)=1，而把0分到别的组里面最大只有 k k k这题很巧妙，所以说区间 [ l , r ] [l,r] [l,r]对于答案的贡献就是 r − l + 1 + r e s r-l+1+res r−l+1+res，其中 r e s res res表示区间0的个数，这样枚举每一个区间时间复杂度是 O ( n 2 ) O(n^2) O(n2)

#include 

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector a(n);
        for(int i=0;i> a[i];
        long long ans = 0;
        function cal = [&](int l, int r){
            long long res = 0;
            for(int i=l;i<=r;i++){
                if(!a[i]){
                    res += 1;
                }
            }
            return res + r - l + 1;
        };
        for(int i=0;i 
C 
题读错了，同样想了好久，这里面说了
     
      
       
        
         1
        
        
         <
        
        
         j
        
        
         <
        
        
         n
        
       
       
        1lt jlt n
       
      
     1 3 1 1 1 1,这个3可以产生两个偶数，偶数又可以让奇数变成偶数 
#include 

using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector a(n);
        for(auto &i : a) cin >> i;
        function solve = [&](){
            if(n == 3 && (a[1] & 1)){
                cout << -1 << 'n';
                return; 
            }
            ll ans = 0;
            bool ok = false;
            for(int i=1;i 
D 
这样一个问题，给你
     
      
       
        
         a
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        a[i]
       
      
     a[i]和
     
      
       
        
         b
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        b[i]
       
      
     b[i]，现在要最小化
     
      
       
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           i
          
          
           +
          
          
           1
          
         
         
          n
         
        
        
         (
        
        
         
          a
         
         
          i
         
        
        
         +
        
        
         
          a
         
         
          j
         
        
        
         
          )
         
         
          2
         
        
       
       
        sum_{i=1}^{n}sum_{j=i+1}^{n}(a_i+a_j)^2
       
      
     ∑i=1n​∑j=i+1n​(ai​+aj​)2和
     
      
       
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           i
          
          
           +
          
          
           1
          
         
         
          n
         
        
        
         (
        
        
         
          b
         
         
          i
         
        
        
         +
        
        
         
          b
         
         
          j
         
        
        
         
          )
         
         
          2
         
        
       
       
        sum_{i=1}^{n}sum_{j=i+1}^{n}(b_i+b_j)^2
       
      
     ∑i=1n​∑j=i+1n​(bi​+bj​)2的和平方打开，然后加和，得到
     
      
       
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           i
          
          
           +
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
         
          2
         
        
        
         +
        
        
         
          b
         
         
          i
         
         
          2
         
        
        
         +
        
        
         
          a
         
         
          j
         
         
          2
         
        
        
         +
        
        
         
          b
         
         
          j
         
         
          2
         
        
        
         +
        
        
         2
        
        
         (
        
        
         
          a
         
         
          i
         
        
        
         
          a
         
         
          j
         
        
        
         +
        
        
         
          b
         
         
          i
         
        
        
         
          b
         
         
          j
         
        
        
         )
        
       
       
        sum_{i=1}^{n}sum_{j=i+1}^{n}a_i^2+b_i^2+a_j^2+b_j^2+2(a_ia_j+b_ib_j)
       
      
     ∑i=1n​∑j=i+1n​ai2​+bi2​+aj2​+bj2​+2(ai​aj​+bi​bj​)前面
     
      
       
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           i
          
          
           +
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
         
          2
         
        
        
         +
        
        
         
          b
         
         
          i
         
         
          2
         
        
        
         +
        
        
         
          a
         
         
          j
         
         
          2
         
        
        
         +
        
        
         
          b
         
         
          j
         
         
          2
         
        
       
       
        sum_{i=1}^{n}sum_{j=i+1}^{n}a_i^2+b_i^2+a_j^2+b_j^2
       
      
     ∑i=1n​∑j=i+1n​ai2​+bi2​+aj2​+bj2​是一个定值,可以
     
      
       
        
         O
        
        
         (
        
        
         
          n
         
         
          2
         
        
        
         )
        
       
       
        O(n^2)
       
      
     O(n2)得到，
 现在需要处理的问题是最小化
     
      
       
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           i
          
          
           +
          
          
           1
          
         
         
          n
         
        
        
         2
        
        
         (
        
        
         
          a
         
         
          i
         
        
        
         
          a
         
         
          j
         
        
        
         +
        
        
         
          b
         
         
          i
         
        
        
         
          b
         
         
          j
         
        
        
         )
        
       
       
        sum_{i=1}^{n}sum_{j=i+1}^{n}2(a_ia_j+b_ib_j)
       
      
     ∑i=1n​∑j=i+1n​2(ai​aj​+bi​bj​)，因为
     
      
       
        
         
          a
         
         
          i
         
        
        
         
          a
         
         
          j
         
        
       
       
        a_ia_j
       
      
     ai​aj​和
     
      
       
        
         
          b
         
         
          i
         
        
        
         
          b
         
         
          j
         
        
       
       
        b_ib_j
       
      
     bi​bj​等价，所以先只考虑
 
      
       
        
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
         
          
           ∑
          
          
           
            j
           
           
            =
           
           
            i
           
           
            +
           
           
            1
           
          
          
           n
          
         
         
          
           a
          
          
           i
          
         
         
          
           a
          
          
           j
          
         
        
        
         sum_{i=1}^{n}sum_{j=i+1}^{n}a_ia_j
        
       
      i=1∑n​j=i+1∑n​ai​aj​
 我们要知道
      
       
        
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
         
          
           ∑
          
          
           
            j
           
           
            =
           
           
            i
           
           
            +
           
           
            1
           
          
          
           n
          
         
         
          
           a
          
          
           i
          
         
         
          
           a
          
          
           j
          
         
         
          =
         
         
          
           
            
             ∑
            
            
             
              i
             
             
              =
             
             
              1
             
            
            
             n
            
           
           
            
             ∑
            
            
             
              j
             
             
              =
             
             
              1
             
            
            
             n
            
           
           
            
             a
            
            
             i
            
           
           
            
             a
            
            
             j
            
           
           
            −
           
           
            
             ∑
            
            
             
              i
             
             
              =
             
             
              1
             
            
            
             n
            
           
           
            
             a
            
            
             i
            
           
           
            
             a
            
            
             i
            
           
          
          
           2
          
         
         
          =
         
         
         
          
           
            (
           
           
            
             ∑
            
            
             
              i
             
             
              =
             
             
              1
             
            
            
             n
            
           
           
            
             a
            
            
             i
            
           
           
            
             )
            
            
             2
            
           
           
            −
           
           
            
             ∑
            
            
             
              i
             
             
              =
             
             
              1
             
            
            
             n
            
           
           
            
             a
            
            
             i
            
            
             2
            
           
          
          
           2
          
         
        
        
         sum_{i=1}^{n}sum_{j=i+1}^{n}a_ia_j=frac{sum_{i=1}^{n}sum_{j=1}^{n}a_ia_j-sum_{i=1}^{n}a_ia_i}{2}=\frac{(sum_{i=1}^{n}a_i)^2-sum_{i=1}^{n}a_i^2}{2}
        
       
      i=1∑n​j=i+1∑n​ai​aj​=2∑i=1n​∑j=1n​ai​aj​−∑i=1n​ai​ai​​=2(∑i=1n​ai​)2−∑i=1n​ai2​​如何证明呢？可以考虑矩阵乘法，左侧相当于一个
     
      
       
        
         n
        
        
         ×
        
        
         n
        
       
       
        ntimes n
       
      
     n×n矩阵的一个三角区域（去除主对角线），那么如何得到呢？显然应该使用整个矩阵减去主对角线元素除以2,这也就得到了这个公式知道了这个公式以后，我们实际上要最小化的式子为
      
       
        
         
          (
         
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
         
          
           a
          
          
           i
          
         
         
          
           )
          
          
           2
          
         
         
          −
         
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
         
          
           a
          
          
           i
          
          
           2
          
         
         
          +
         
         
          (
         
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
         
          
           b
          
          
           i
          
         
         
          
           )
          
          
           2
          
         
         
          −
         
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
         
          
           b
          
          
           i
          
          
           2
          
         
         
          =
         
         
         
          (
         
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
         
          
           a
          
          
           i
          
         
         
          
           )
          
          
           2
          
         
         
          +
         
         
          (
         
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
         
          
           b
          
          
           i
          
         
         
          
           )
          
          
           2
          
         
         
          −
         
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
         
          
           a
          
          
           i
          
          
           2
          
         
         
          −
         
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
         
          
           b
          
          
           i
          
          
           2
          
         
        
        
         (sum_{i=1}^{n}a_i)^2-sum_{i=1}^{n}a_i^2+(sum_{i=1}^{n}b_i)^2-sum_{i=1}^{n}b_i^2=\(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
        
       
      (i=1∑n​ai​)2−i=1∑n​ai2​+(i=1∑n​bi​)2−i=1∑n​bi2​=(i=1∑n​ai​)2+(i=1∑n​bi​)2−i=1∑n​ai2​−i=1∑n​bi2​那么其实后面也是一个定值，只需要最小化前面，换句话说，现在有这样一个问题，给你两个数组，可以互换
     
      
       
        
         a
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        a[i]
       
      
     a[i]和
     
      
       
        
         b
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        b[i]
       
      
     b[i]，求
     
      
       
        
         (
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
        
        
         
          )
         
         
          2
         
        
        
         +
        
        
         (
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          b
         
         
          i
         
        
        
         
          )
         
         
          2
         
        
       
       
        (sum_{i=1}^{n}a_i)^2+(sum_{i=1}^{n}b_i)^2
       
      
     (∑i=1n​ai​)2+(∑i=1n​bi​)2的最小值经典dp，设
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         ]
        
        
         [
        
        
         j
        
        
         ]
        
       
       
        dp[i][j]
       
      
     dp[i][j]为前
     
      
       
        
         i
        
       
       
        i
       
      
     i个数能否凑出
     
      
       
        
         j
        
       
       
        j
       
      
     j，那么问题就转化为01背包了，这样最后得到的就是前
     
      
       
        
         i
        
       
       
        i
       
      
     i个数能否凑出
     
      
       
        
         j
        
       
       
        j
       
      
     j，这是对于
     
      
       
        
         a
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        a[i]
       
      
     a[i]来说的，也就是
     
      
       
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          a
         
         
          i
         
        
       
       
        sum_{i=1}^{n}a_i
       
      
     ∑i=1n​ai​的值，那么根据前缀和
     
      
       
        
         s
        
        
         u
        
        
         m
        
       
       
        sum
       
      
     sum就可以得到
     
      
       
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          n
         
        
        
         
          b
         
         
          i
         
        
       
       
        sum_{i=1}^{n}b_i
       
      
     ∑i=1n​bi​ ，这样也就求出了这个最小值 
#include 

using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector a(n + 1), b(n + 1);
        for(int i=1;i<=n;i++) cin >> a[i];
        for(int i=1;i<=n;i++) cin >> b[i];
        int ans = 0;
        int mx = 0;
        for(int i=1;i<=n;i++){
            ans -= a[i] * a[i];
            ans -= b[i] * b[i];
            mx += a[i];
            mx += b[i];
            for(int j=i+1;j<=n;j++){
                ans += a[i] * a[i];
                ans += a[j] * a[j];
                ans += b[i] * b[i];
                ans += b[j] * b[j];
            }
        }
        vector > dp(n + 1, vector(mx + 1));
        dp[0][0] = 1;
        for(int i=1;i<=n;i++){
            for(int j=a[i];j<=mx;j++){
                dp[i][j] |= dp[i - 1][j - a[i]];
            }
            for(int j=b[i];j<=mx;j++){
                dp[i][j] |= dp[i - 1][j - b[i]];
            }
        }
        int res = INT_MAX;
        for(int i=0;i<=mx;i++){
            if(dp[n][i]){
                res = min(res, i * i + (mx - i) * (mx - i));                
            }
        }
        cout << ans + res << 'n';
    }
    return 0;
}
 
E 
定义
     
      
       
        
         c
        
        
         n
        
        
         
          t
         
         
          x
         
        
       
       
        cnt_x
       
      
     cntx​为
     
      
       
        
         x
        
       
       
        x
       
      
     x出现次数，问
     
      
       
        
         (
        
        
         c
        
        
         n
        
        
         
          t
         
         
          x
         
        
        
         +
        
        
         c
        
        
         n
        
        
         
          t
         
         
          y
         
        
        
         )
        
        
         ×
        
        
         (
        
        
         x
        
        
         +
        
        
         y
        
        
         )
        
       
       
        (cnt_x+cnt_y)times(x+y)
       
      
     (cntx​+cnty​)×(x+y)的最大值，要求
     
      
       
        
         (
        
        
         x
        
        
         ,
        
        
         y
        
        
         )
        
       
       
        (x,y)
       
      
     (x,y)不能是
     
      
       
        
         b
        
        
         a
        
        
         d
        
        
          
        
        
         p
        
        
         a
        
        
         i
        
        
         r
        
       
       
        bad pair
       
      
     bad pair一个数组里面所有数的本质不同的出现次数的复杂度是
     
      
       
        
         O
        
        
         (
        
        
         
          n
         
        
        
         )
        
       
       
        O(sqrt n)
       
      
     O(n
            ​)的，这个可以考虑出现为1,2,3,4…n，加一起带平方，所以我们可以考虑使用出现次数枚举，注意不能是
     
      
       
        
         b
        
        
         a
        
        
         d
        
        
          
        
        
         p
        
        
         a
        
        
         i
        
        
         r
        
       
       
        bad pair
       
      
     bad pair，这样的时间复杂度平均为
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         
          n
         
        
        
         )
        
       
       
        O(nsqrt n)
       
      
     O(nn
            ​) 
#include 

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        set > s;
        set b;
        map mp;
        set a;
        int mx = -1;
        for(int i=0;i> x;
            a.insert(x);
            mp[x] += 1;
        }
        for(auto i : mp){
            mx = max(mx, i.second);
        }
        vector > g(mx + 1);
        for(auto i : mp){
            g[i.second].push_back(i.first);
            b.insert(i.second);
        }
        for(int i=0;i<=mx;i++) sort(g[i].rbegin(), g[i].rend());
        for(int i=0;i> u >> v;
            if(u > v) swap(u, v);
            s.insert({u, v});
        }
        long long ans = 0;
        for(auto i : a){
            for(auto j : b){
                for(auto k : g[j]){
                    if(i == k) continue;
                    if(!s.count({min(i, k), max(i, k)})){
                        ans = max(ans, 1ll * (i + k) * (mp[i] + j));
                        break;
                    }
                }
            }
        }
        cout << ans << 'n';
    }
    return 0;///
}
 
这代码昨天能过，今天就不行了，第77个点是从小到大依次排布的，这种暴力会被卡到
     
      
       
        
         O
        
        
         (
        
        
         
          n
         
         
          2
         
        
        
         )
        
       
       
        O(n^2)
       
      
     O(n2)，换成枚举出现次数，这样时间复杂度能回到
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         )
        
       
       
        O(n)
       
      
     O(n) 
#include 

using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        set a;
        map mp;
        for(int i=1;i<=n;i++){
            int x;
            cin >> x;
            a.insert(x);
            mp[x] += 1;
        }
        set b;//本质不同出现次数
        set > s;
        for(int i=0;i> u >> v;
            if(u > v) swap(u, v);
            s.insert({u, v});
        }
        int mx = 0;
        for(auto i : mp){
            mx = max(mx, i.second);
        }
        vector > vis(n + 1);
        for(auto i : mp){
            vis[i.second].push_back(i.first);
            b.insert(i.second);
        }
        for(int i=1;i<=n;i++){
            reverse(vis[i].begin(), vis[i].end());
        }
        ll ans = 0;
        for(int cnt_x=1;cnt_x<=n;cnt_x++){
            for(auto x : vis[cnt_x]){
                for(int cnt_y=1;cnt_y<=cnt_x;cnt_y++){
                    for(auto y : vis[cnt_y]){
                        if(x != y && !s.count({min(x, y), max(x, y)})){
                            ans = max(ans, 1ll * (cnt_x + cnt_y) * (x + y));
                            break;
                        }
                    }
                }
            }
        }
        cout << ans << 'n';
    }
    return 0;
}