Codeforces Round 982 (Div. 2) 题解

A. Rectangle Arrangement

要计算黑色区域的周长，可以把图形转化为矩形来计算。

code:

#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

const int N = 200010;

int T;
int n;
int a[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n;
        
        int x = 0, y = 0;
        while (n--)
        {
            int w, h;
            cin >> w >> h;
            x = max(x, w), y = max(y, h);
        }
        
        cout << (x + y) * 2 << endl;
    }
	
	return 0;
}

B. Stalin Sort

只有当序列头部元素是整个序列最大元素的时候，才可以使用斯大林排序。

对于所有 \(i\) 满足 \(1<=i<=n\)，计算 \(a_i\) 当头部时需要删除的元素数量，取 \(min\)。

code:

#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

const int N = 200010;

int T;
int n;
int a[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        int res = n;
        for (int i = 0; i < n; i++)
        {
            int ans = i;
            for (int j = i; j < n; j++)
                if (a[j] > a[i])
                    ans++;
            res = min(res, ans);
        }
        
        cout << res << endl;
    }
	
    return 0;
}

C. Add Zeros

\(a_i=|a|+1-i\ ==>\ |a|=a_i+i-1\)

考虑建图，对于下标 \(i\)， 执行操作后，数组长度更新为 \(|a| + i - 1\)。因此，可以把 \(i\) 与所有能在新数组长度上执行操作的下标进行连边。

最后进行 \(dfs\) 深搜，更新所建图能达到的最长数组长度。

code:

#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

const int N = 300010;

int T;
int n;
int a[N];
vector<int> h[N];
bool st[N];

int dfs(int u)
{
    st[u] = true;
    int res = a[u] + (u - 1) * 2;
    for (int i = 0; i < h[u].size(); i++)
    { 
        if (st[h[u][i]]) continue;
        res = max(res, dfs(h[u][i]));
    }
    return res;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        
        map<int, vector<int>> p;
        for (int i = 1; i <= n; i++) p[a[i] + i - 1].push_back(i);
        for (int i = 1; i <= n; i++) 
        {
            if (a[i] == n - i + 1) h[0].push_back(i);
            h[i] = p[a[i] + (i - 1) * 2];
        }
        
        a[0] = n + 2;
        cout << dfs(0) << endl;
        
        for (int i = 0; i <= n; i++) 
        {
            st[i] = false;
            h[i].clear();
        }
    }
	
    return 0;
}

D1. The Endspeaker (Easy Version)

\(dp\)，设 \(f(i, j)\) 为 \(k\) 最大增加到 \(i\)，清空 \(a\) 中前 \(j\) 个元素所需的最小操作成本。

可以列出状态转移方程 \(f(i,j) = \min \left\{ \begin{aligned} & f(i-1,j) \\ & f(i,l) + m - i \end{aligned} \right.\)

时间复杂度为 \(O(n^2m)\)，考虑优化。

可以发现， \(f(i,l)\) 对于 \(l\) 来说是单调递增的。

因此对于第二个状态转移，只需保证 \(l\) 尽可能小，可以用双指针来维护，时间复杂度 \(O(nm)\)。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define int long long
#define endl '\n'

using namespace std;

const int N = 300010;

int T;
int n, m;
int a[N], b[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= m; i++) cin >> b[i];
        
        int m1 = 0, m2 = 0;
        for (int i = 1; i <= n; i++) 
        {
            m1 = max(m1, a[i]);
            a[i] += a[i - 1];
        }
        for (int i = 1; i <= m; i++) m2 = max(m2, b[i]);
        
        if (m1 > m2)
        {
            cout << -1 << endl;
            continue;
        }
        
        vector<vector<int>> f(m + 10, vector<int>(n + 10));
        for (int i = 1; i <= n; i++) f[0][i] = 1e18; 
        
        for (int i = 1; i <= m; i++)
        {
            for (int l = 0, r = 1; r <= n; r++)
            {
                f[i][r] = f[i - 1][r];
                while (a[r] - a[l] > b[i] && l < r) l++;
                if (l < r) f[i][r] = min(f[i][r], f[i][l] + m - i);
            }
        }
        
        cout << f[m][n] << endl;
    }

    return 0;
}

D2. The Endspeaker (Hard Version)

对于操作方案数，可以用二分来查找可以能够进行状态转移的 \((l,r)\) 区间个数，用前缀和来维护这些区间的总方案数。

时间复杂度 \(O(nmlogn)\)。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define int long long
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 300010, mod = 1e9 + 7;

int T;
int n, m;
int a[N], b[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= m; i++) cin >> b[i];
        
        int m1 = 0, m2 = 0;
        for (int i = 1; i <= n; i++) 
        {
            m1 = max(m1, a[i]);
            a[i] += a[i - 1];
        }
        for (int i = 1; i <= m; i++) m2 = max(m2, b[i]);
        
        if (m1 > m2)
        {
            cout << -1 << endl;
            continue;
        }
        
        vector<vector<PII>> f(m + 10, vector<PII>(n + 10));
        for (int i = 1; i <= n; i++) f[0][i] = {1e18, 1}; 
        for (int i = 1; i <= m; i++) f[i][0].y = 1;
        
        for (int i = 1; i <= m; i++)
        {
            int s[n + 10] = {1};
            for (int l = 0, r = 1; r <= n; r++)
            {
                f[i][r] = f[i - 1][r];
                while (a[r] - a[l] > b[i] && l < r) l++;
                if (l < r)
                {	
                    int ll = l, rr = r - 1;
                    while (ll < rr)
                    {
                        int mid = ll + rr + 1 >> 1;
                        if (f[i][mid].x != f[i][l].x) rr = mid - 1;
                        else ll = mid;
                    }
                    int c = 0;
                    if (!l) c = s[ll] % mod;
                    else c = (s[ll] - s[l - 1]) % mod;
                    if (f[i][r].x > f[i][l].x + m - i)
                    {
                        f[i][r].x = f[i][l].x + m - i;
                        f[i][r].y = c;
                    }
                    else if (f[i][r].x == f[i][l].x + m - i)
                    {
                        f[i][r].y = (f[i][r].y + c) % mod;
                    }
                } 
                s[r] = s[r - 1] + f[i][r].y;
            }
        }
        
        cout << f[m][n].x << ' ' << f[m][n].y << endl;
    }

    return 0;
}