专栏文章

题解：CF2075C Two Colors

NNEKO_Daze
CF2075C题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipuel2p
此快照首次捕获于
2025/12/03 18:06
3 个月前
此快照最后确认于
2025/12/03 18:06
3 个月前
查看原文
洛谷CF2075C || CodeForces 2075 C

简要题意

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

思路

对于方格中的断点 k∈[1,n)k\in[1,n)，前有 kk 个格子，后有 n−kn-k 个格子。将数组 aa 排序后，用 lower_bound 很容易找出满足 ai≥ka_i\ge k 或 aj≥n−ka_j\ge n-k 的颜料个数 x,yx,y，根据乘法原理可知总共有 xyxy 种可能，但由于两种颜色应不同，所以还需减去 min⁡(x,y)\min(x,y) 种情况，所以最后答案为 xy−min⁡(x,y)xy-\min(x,y)。时间复杂度 O(t×(n+m)log⁡m)O(t\times(n+m)\log m)。
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...