题解：CF2035D Yet Another Real Number Problem

· · 题解

CF2035D Yet Another Real Number Problem

简要题意

给定数组 a，对它的每个前缀分别求解。

你可以任意次执行操作：选择 i < j，若当前 b_i 是偶数，则令 b_i \Leftarrow \frac{b_i}{2}，b_j \Leftarrow b_j\times2。

问经过任意次操作后，该前缀数组的元素和最大是多少。需要对每个前缀输出这个最大和模 10^9 + 7 的结果。

解题思路

观察题目可以发现所有 2 因子都可向右转移。

我们考虑什么形式变化后会更优。

设 a_i = b_i\times{2^{k_i}}，b_i 为奇数。

a_i+a_j<\frac{a_i}{2^{k_i}}+a_j\times{2^{k_i}} \frac{a_i}{2^{k_i}}\times({2^{k_i}}-1)<a_j\times({2^{k_i}}-1) \frac{a_i}{2^{k_i}}<a_j

所以对于每个新加进来的 a_j，若前面一段序列中始终满足 b_i<a_j，那么这段序列的 2 因子就可以贪心地全转移过来。

这段过程可以用单调栈维护，而单调栈维护的信息便是 b_i。每次查找区间时把栈顶 b_i<a_j 弹栈即可。

:::success[AC]

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
const int M = 6e6 + 5;
const int mod = 1e9 + 7;
int n;
int a[N], b[N], stk[N], tp;
ll pw[M], s[N];
ll f[N], cnt[N];
inline bool check(int x, int y)//贪心判断是否要弹栈
{
    if (cnt[x] >= 30) return true;  //当遇到这种情况就不能直接判断了，显然成立
    return b[x] * pw[cnt[x]] >= b[y];
}

inline void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)cnt[i] = 0, s[i] = 0;  //初始化
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
        while (b[i] % 2 == 0)b[i] /= 2, cnt[i]++;
        s[i] = s[i - 1] + b[i];
    }
    tp = 0;
    for (int i = 1; i <= n; i++)
    {
        while (tp && check(i, stk[tp]))//转移2因子+查找区间
        {
            cnt[i] += cnt[stk[tp]];
            cnt[stk[tp]] = 0;
            tp--;
        }
        f[i] = (f[stk[tp]] + (s[i - 1] - s[stk[tp]]) + b[i] * pw[cnt[i]] % mod) % mod;
        //[stk[tp]+1,i-1]均为b用前缀和维护
        stk[++tp] = i;
        cout << f[i] <<  " ";
    }
    cout <<  "\n";
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    pw[0] = 1;
    for (int i = 1; i <= 6000000; i++)pw[i] = pw[i - 1] * 2 % mod;
    //预处理2次方
    while (T--)
    {
        solve();
    }
    return 0;
}

:::