CF1872G Replace With Product

刚看到这道题的时候就第一感觉应该是乘积比加和更优。

发现如果序列中所有数的乘积比 \(2\times10^{14}\) 更大，在区间左右端点不为 \(1\) 时，全乘起来一定更优。

若左右端点为 \(1\)，则找到两端的第一个非 \(1\) 位置即为答案。

否则，发现 \(2^{49}>2\times10^{14}\)，则区间内非 \(1\) 的位置一定小于 \(50\) 个，只需枚举区间左右端点取最大值即可，实现时注意不要爆 long long 以及全是 \(1\) 的情况。

本题思想主要在于排除掉乘积比 \(2\times10^{14}\) 更大的情况后暴力的时间复杂度得到了保障。

#define int ll
const int N = 2e5 + 5, MAX = 2e14;
int a[N], n, sum[N], mul[N];
vector <int> v;
void solve()
{
    cin >> n; rer(i, 1, n, a);
    int now = 1;
    R(i, 1, n)
    {
        if (now > MAX / a[i]) 
        {
            int l = 1, r = n;
            while (a[l] == 1) ++l;
            while (a[r] == 1) --r;
            cout << l << ' ' << r << '\n';
            return ;
        }
        now *= a[i];
    }
    mul[0] = 1;
    v.clear();
    R(i, 1, n) 
    {
        mul[i] = mul[i - 1] * a[i], sum[i] = sum[i - 1] + a[i];
        if (a[i] != 1) v.pb(i);
    }
    int l = 1, r = 1, ans = 0;
    for (int i = 0; i < v.size(); ++i)
    {
        for (int j = i; j < v.size(); ++j)
        {
            // cout << v[i] << ' ' << v[j] << endl;
            int tmp = sum[n] - sum[v[j]] + sum[v[i] - 1];
            tmp += mul[v[j]] / mul[v[i] - 1];
            // cout << tmp << endl;
            if (tmp > ans) 
            {
                ans = tmp;
                l = v[i], r = v[j];
            }
        }
    }
    cout << l << ' ' << r << '\n';
}
signed main() 
{
    cout.tie(0);
    int T = 1; 
    read(T);  
    while (T--) solve();
    return 0;
}