P10010 [集训队互测 2023] Grievous Lady 题解

· · 题解

1. 题目分析

这道题一眼搜索或者动规，因为我看不出来怎么动规，所以准备用搜索解这道题。

2. 题目做法

(1) 直接暴力搜索 (12pts)

我们将 r 当作题目中 a，b 数组的长度，将 c 当作搜索到哪一层了，这样我们便可以写出暴力代码：

__int128 ans;
__int128 x,y;
void dfs(int r,int c)
{
    if(c==r+1)
    {
        __int128 s=x*y;
        if(s>ans)
            ans=s;
        return ;
    }
    x+=a[c].x;
    dfs(r,c+1);
    x-=a[c].x;
    y+=a[c].y;
    dfs(r,c+1);
    y-=a[c].y;
}

此算法时间复杂度为 O(2^n) 让我们再看看数据范围，n\le3000，这不得直接 T 飞？

(2) 整体贪心+局部搜索(100pts)

本蒟蒻也是看了第一篇题解才有的思路，我们发现，因为题目数据范围是随机的，并且值域非常大，所以 a 和 b 的值一般不会太接近，我们只需要取更大的那个数即可。

但是这样做会有缺点，如果有 a 和 b 比较接近的情况出现，便很容易举出反例，这一部分我们就只能用搜索解决。

于是，我们可以先将 a，b 数组以 \frac{a}{b} 为排序标准进行降序排列，然后取正中间的 100 个左右的断点进行枚举，先将断点左边大部分数和右边大部分数加入总数中，再暴力搜索断点附近的一些数更新答案就行了。

求总和的代码大概是这样：

void sum(int k)
{
    x=0,y=0;
    //确定搜索范围
    int l=max(1,k-5),r=min(n,k+5);
    //整体贪心
    for(int i=1;i<l;i++)
        x+=a[i].x;
    for(int i=r+1;i<=n;i++)
        y+=a[i].y;
    //局部搜索
    dfs(r,l);
}

这样就可以将这道题切掉了。