题解：CF2075C Two Colors

NEKO_Daze · 2025-03-22 20:12:29 · 题解

洛谷CF2075C || CodeForces 2075 C

简要题意

对于一个长度 n 空白方格，有 m 种颜色的颜料，第 i 种颜料可以对 a_i 个连续格子染色。选取两种颜色 x,y，并将方格分为两半，左边全涂为颜色 x，右边全涂为颜色 y。求不同的方案数。

思路

对于方格中的断点 k\in[1,n)，前有 k 个格子，后有 n-k 个格子。将数组 a 排序后，用 lower_bound 很容易找出满足 a_i\ge k 或 a_j\ge n-k 的颜料个数 x,y，根据乘法原理可知总共有 xy 种可能，但由于两种颜色应不同，所以还需减去 \min(x,y) 种情况，所以最后答案为 xy-\min(x,y)。时间复杂度 O(t\times(n+m)\log m)。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        int a[200005];
        for (int i = 0; i < m; ++i)
        {
            cin >> a[i];
        }
        sort(a, a+m);
        long long ans = 0;
        for (int k = 1; k < n; ++k)
        {
            long long x = m - (lower_bound(a, a+m, k) - a);
            long long y = m - (lower_bound(a, a+m, n-k) - a);
            ans += x * y - min(x, y);
        }
        cout << ans << endl;
    }
    return 0;
}