题解：CF1062C Banh-mi

· · 题解

CF1062C 题目传送门

题目大意

有 n 份食物，编号为 1 到 n，定义第 i 份食物的美味值为 x_i \in{0,1}。现在要逐个吃掉这 n 份食物，在每一步中，吃掉第 i 份食物则能量值将增加 x_i 并且剩下的所有食物的美味程度也会增加 x_i。初始能量值为 0。有 q 个查询，每个查询给定两个整数 l 和 r，目标是查询：如果按某种顺序吃掉编号在区间 [l,r] 上所有食物，获得的最大能量值是多少。所有的查询相互独立，查询的答案对 10^9+7 取模后输出。

解决思路

拿走数字 a 后，其余数字就会加上 a。通过观察可得，运用贪心策略，每次拿当前最大的数字即可。不过此时的时间复杂度为 \Theta(nt \log n) 需要用前缀和将复杂度降低为 \Theta (n+t \log n)。

代码展示

#include<bits/stdc++.h>
#define ll long long
//不开long long见祖宗 
using namespace std;

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
ll n, T, a[N], f[N];
string s;

ll ksm(ll a, ll b)
{
    ll mul = 1;
    while(b)
    {
        if(b % 2 == 1) mul = mul * a % mod;
        b /= 2;
        a = a * a % mod;
    }
    return mul;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> T >> s;
    for(int i = 1; i <= s.size(); i++) 
    {
        if(s[i-1] == '1') f[i] = 1;
        a[i] = a[i-1] + f[i];//前缀和 
    }
    while(T--)
    {
        int l, r;
        cin >> l >> r;
        ll p = a[r] - a[l - 1];
        ll q = r - l - p + 1;
        ll a1 = ksm(2, p) - 1;
        ll a2 = ksm(2, q);
        cout << a1 * a2 % M << "\n";
    }
    return 0;
}