专栏文章

题解：CF1062C Banh-mi

OOIerJiang_1017
CF1062C题解参与者 2已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@miqte67a
此快照首次捕获于
2025/12/04 10:26
3 个月前
此快照最后确认于
2025/12/04 10:26
3 个月前
查看原文

CF1062C 题目传送门

题目大意

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

解决思路

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

代码展示

CPP
#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;
}

评论

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

正在加载评论...