E题我出了个视频qwq

https://www.bilibili.com/video/BV1G5411Z7NK/

A

题目描述

给了你一个数组，让你选一个位置i，使得数组a[1 ~ i],a[i + 1 ~ n]分别排为升序（非严格），然后问你存不存在一个位置排完使得，整个数组a[1~n]不为一个升序数组(非严格)

解题思路

构造两个数组
maxv[i] : a[1 ~ i]的最大值
minv[i] : a[i ~ n]的最小值
然后选取每个位置i去check，如果maxv[i] > minv[i + 1]那么就是可以构造一个不为升序的数组，因为操作完之后，a[i] > a[i + 1],不是一个升序的数组
时间复杂度: O(n)

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

int a[N],maxv[N],minv[N];

bool solve(){

    int n;

    cin >> n;

    for(int i=1;i<=n;i++)
        cin >> a[i];

    maxv[1] = a[1];

    for(int i=2;i<=n;i++)
        maxv[i] = max(maxv[i - 1],a[i]);

    minv[n] = a[n];

    for(int i=n - 1;i>=1;i--)
        minv[i] = min(minv[i + 1],a[i]);

    for(int i=1;i<n;i++)
    {
        if(maxv[i] > minv[i + 1])
            return true;
    }

    return false;
}

int main(){


    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    int T;

    cin >> T;

    while(T--)
    {
        if(solve()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }



    return 0;
}

B

题目描述

给了个数组a[1~n],要你将他的任意子数组割成任意份，份数记为c,且元素不重不漏，求所有子数组c+∑mex(每个分割)的最大值。
mex为数组中不存在的最小非负整数

解题思路

考虑区间dp，初始化所有区间为1+mex(a[l~r])(即c=1的时候),然后区间dp，对于区间a[l~r],依次枚举中点mid,状态转移方程为f[l][r] = max(f[l][r],f[l][mid] + f[mid + 1][r]);
时间复杂度：O(n^3)

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 110;

int n,a[N];

int f[N][N];

bool st[N];

int solve(){

    cin >> n;

    for(int i=1;i<=n;i++)
        cin >> a[i];

    for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++)
        {
            memset(st,false,sizeof st);

            for(int u=l;u<=r;u++)
            {
                if(a[u] < N)
                st[a[u]] = true;
            }

            int c = 0;
            while(st[c]) c ++ ;
            f[l][r] = c + 1;
        }

    for(int len = 2 ; len <= n ; len ++ )
        for(int l = 1 ; l + len - 1 <= n ; l ++ )
        {
            int r = l + len - 1;
            for(int mid = l ; mid < r ; mid ++ )
            {
                f[l][r] = max(f[l][r],f[l][mid] + f[mid + 1][r]);
            }
        }
    int res = 0;

    for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++)
        {
            res += f[l][r];
        }

    return res;
}

signed main(){


    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    int T;

    cin >> T;

    while(T--)
    {
        cout << solve() << endl;
    }



    return 0;
}

C

题目描述

给了你一个数组a[1~n],然后你可以执行操作,选取i<j<k,使得a[j]给i和k各分1个,即a[j] -= 2,a[i] += 1,a[k] += 1,问你最小操作多少次，使得a[2~n-1]皆为0

解题思路

直接贪心,考虑a[2~n-1],显然a[i]为偶数时怎么样都能分到两边最少需要次数为a[i] / 2,a[i]为奇数时最少需要别人分一个给他，最少需要次数为(a[i] + 1) / 2，显然只要方案有解，那么总是存在一种方案可以达到上述最小次数。所以我们只要把不可行的特判掉就行,即a[2~n-1]全为1或者n=3,a[2]为奇数。
时间复杂度O(n)

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 10;

int n;

int a[N];

int solve(){

    cin >> n;

    for(int i=1;i<=n;i++)
        cin >> a[i];

    if(n == 3 && a[2] % 2 == 1)
        return -1;

    bool flag = true;

    for(int i=2;i<=n-1;i++)
        if(a[i] != 1)
            flag = false;

    if(flag) return -1;

    int res = 0;

    for(int i=2;i<=n-1;i++)
        res += (a[i] + 1) / 2;

    return res;
}

signed main(){


    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    int T;

    cin >> T;

    while(T--)
    {
        cout << solve() << endl;
    }



    return 0;
}

D

题目描述

给了你两个数组a[1~n],b[1~n],你可以swap(a[i],b[i])任意次，然后让你求$ \sum_{i=1}^n \sum_{j=i+1}^n (a_i + a_j)^2 + \sum_{i=1}^n \sum_{j=i+1}^n (b_i + b_j)^2$的最大值

解题思路

dp，对于第i个位置来说,如果不对它进行操作,所有涉及i这个位置对最后答案的贡献记为I = $ \sum_{j≠i}^n (a_i + a_j)^2 + \sum_{j≠i}^n (b_i + b_j)^2$,如果对它进行交换操作记为I’ = $ \sum_{j≠i}^n (b_i + a_j)^2 + \sum_{j≠i}^n (a_i + b_j)^2$，用I’ - I即为交换过后的收益$ 2*(b_i - a_i) * ( \sum_{j≠i}^n (a_j - b_j)) $,根据上述公式我们就知道，增量只和当前点和总和有关，那么状态表示和状态转移就迎刃而解。dp[i][j]表示现在考虑第i个位置，j = $ \sum_{j=1}^n (a_j - b_j) $
时间复杂度:O(n*max{a[i]}*n)

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 110,M = 100 * 100,K=M*2+5;

int n;

int a[N],b[N],f[N][K];

int solve(){

    cin >> n;

    memset(f,0x3f,sizeof f);

    int INF = f[0][0];

    int sum = M;

    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        sum += a[i];
    }

    for(int i=1;i<=n;i++)
    {
        cin >> b[i];
        sum -= b[i];
    }

    f[0][sum] = 0;

    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            f[0][sum] += (a[i] + a[j]) * (a[i] + a[j]);
            f[0][sum] += (b[i] + b[j]) * (b[i] + b[j]);
        }
    int res = f[0][sum];

    for(int i=1;i<=n;i++)
        for(int j=0;j<K;j++)
        {
            if(f[i - 1][j] == INF) continue;

            f[i][j] = min(f[i][j],f[i - 1][j]);

            sum = j - M - (a[i] - b[i]);
            int add = 2 * sum * (b[i] - a[i]);
            int cur = j - 2 * (a[i] - b[i]);
            f[i][cur] = min(f[i][cur],f[i - 1][j] + add);
        }
    for(int i=0;i<K;i++)
        res = min(res,f[n][i]);

    return res;
}

signed main(){

    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    int T;

    cin >> T;

    while(T--)
    {
        cout << solve() << endl;
    }



    return 0;
}

E

题目描述

给定一个数组a[1~n],让你求$ (cnt_x+cnt_y)* (x+y) $的最大值,x为数组中的一个值，$ cnt_x $为数组中这个x的出现次数，且x≠y,此外禁用掉m个对

解题思路

枚举每个x,然后枚举y，找到出现次数为i,i要满足<=$cnt_x$,且对于出现次数为i找到其中可选的最大值(不在禁用范围内),即$ cnt_y $ == i,且y是最大的
这个过程是只需要O(n)的(因为无论如何数字的总和就是n,这里的复杂度总和无非就是∑cnt_x = n)
考虑到禁用的过程，因为禁用在整个遍历的过程最多产生2*M次,另外数据需要离散化处理，所以最后时间复杂度为O(nlogn+m*2)

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 3e5 + 10;

int a[N],cnt[N],v[N],idx;
map<int,int> mp;
int n,m;
vector<int> ban[N];
vector<int> c[N];
bool st[N];

int get(int x)
{
    if(mp.count(x)) return mp[x];
    v[idx] = x;
    mp[x] = idx ++ ;
    return mp[x];
}

ll solve() {

    ll res = 0;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        cnt[get(a[i])] ++ ;
    }

    for(int i=0;i<idx;i++)
    {
        c[cnt[i]].push_back(v[i]);
    }

    for(int i=1;i<=n;i++)
    {
        sort(c[i].begin(),c[i].end());
        reverse(c[i].begin(),c[i].end());
    }

    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ban[get(x)].push_back(get(y));
        ban[get(y)].push_back(get(x));
    }

    for(int i=0;i<idx;i++)
    {
        int x = v[i];
        int cx = cnt[i];

        for(auto e : ban[i])
            st[e] = true;
        st[i] = true;


        for(int j=1;j<=cnt[i];j++)
        {
            int t = -1;
            for(auto e : c[j])
            {
                if(!st[get(e)])
                {
                    t = e;
                    break;
                }
            }
            if(t != -1)
                res = max(res,1ll * (t + x) * (cx + j));
        }

        for(auto e : ban[i])
            st[e] = false;
        st[i] = false;
    }

    for(int i=0;i<idx;i++)
    {
        cnt[i] = 0;
        ban[i].clear();
    }

    for(int i=1;i<=n;i++)
        c[i].clear();

    idx = 0;
    mp.clear();

    return res;
}

int main(){

    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);

    int T;

    scanf("%d",&T);

    while(T -- )
        printf("%lld\n",solve());



    return 0;
}