#C241119D. 简单题

标签（Label）

• 贪心
• 动态规划

网址（Website）

题目详情 - 简单题 - Super

题解 - 简单题 - Super

题目（Problem）

输入数据 1

3 3
1 2 3
1 3
1 2
2 3

输出数据 1

17
5
8

输入数据 2

20 20
-1 0 1 1 -1 1 1 -1 1 -1 -1 1 0 1 -1 0 1 1 1 -1 
7 12
7 16
17 17
3 14
8 12
3 16
6 20
4 12
16 19
7 13
19 20
8 17
16 19
8 20
20 20
10 10
12 13
11 17
12 13
13 19

输出数据 2

11
137
1
2231
5
2229
14101
91
14
11
1000000006
453
14
3523
1000000006
1000000006
1
57
1
110

题解（Solution）

40分（伪贪心）

每次找到能合成的最大值并合成（在负数的情况下，这种算法是伪的 ）

使用链表做到 $O(qn^2)$ 。

50分

方法一：使用记忆化搜索 $\text{dp}$ 。每次暴力把区间分成 $[l,i]$ 和 $[i+1,r]$ 两部分，然后直接暴力求最大值，时间复杂度 $O(qn^2)$ ，但是由于有 $r-l\le 50$ 的限制，因此可以过 $50$ 分。时间复杂度 $O(q\times50^2)$

方法二：考虑贪心。对于负数和正数分类讨论，如果 $a_i<0$ ，那么肯定直接将 $a_i$ 往后加最好，而且尽量要把负数往正数上加，防止出现负数越加越小的情况，那么对于每一个正数，我们肯定从后往前加，并且让正数翻两倍最优，如果从后往前一路加起来加出了一个负数，那我们就直接跳过这个负数，在前面继续找正数加（因为让这个负数乘 $2$ 再往后面合成一定是不优的），最后我们在把所有的数从左往右合成就好了。为了保证贪心正确，这样可能会爆 $\verb!long long!$ ，然而因为 $\vert a_i \vert\le1$ 的限制，我们可以拿到 $50$ 分。时间复杂度 $O(qn)$ 。

70分

发现 $50$ 分的方法二时间复杂度实际上可以过 $70$ 分的点，我们还是从后往前加，找到第一个会加起来爆 $\verb!long long!$ 的地方，我们发现这个数往前面加一定会 $\times 2$ ，那么它的增量一定大于 $10^9$ ，这表示它往前面加就一定不会变成负数，那么我们就可以对这个数取模，暴力往前面加，并且合并后面的数就可以了。时间复杂度 $O(qn)$ 。

注意这个时候还是要先往前面加再合并后面的数，保证贪心的正确性。

100分

出题者题解

代码（Code）

40分（伪贪心）

#include<bits/stdc++.h> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<list>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) {For(i,1,n) cerr<<a[i]<<b;cerr<<'\n';}
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 1012345;
bool ST;double Tim;
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
inline void sub(int &x,int y){if((x-=y)<0)x+=mod;}
inline void mul(int &x,int y){x=x*y%mod;}

list<int> li; 
int a[N];
int n,m;

/*思路
贪心：每次找到能合成的最大值并合成——在负数的情况下，这种算法是伪的 
	使用链表做到 O(qn^2) 
	建立笛卡尔树？ 
不带修：笛卡尔树，莫队，树状数组维护 
*/

void Solve(){
	n=rd(),m=rd();For(i,1,n) a[i]=rd();
	while(m--){
		int l=rd(),r=rd();
		For(i,l,r) li.emplace_front(a[i]);//倒着存的链表 
		while(li.size()>1){
			auto p = max_element(li.begin(),li.end());//注意开头的位置 
			if(next(p)==li.end()) p=prev(p);
			int ins = *p*2 + *next(p);
			li.insert(p,ins);
			li.erase(p,next(p,2));
		}write((*li.begin()%mod+mod)%mod), puts("");
		assert(li.size()==1);
		while(li.size()) li.erase(li.begin());
	}
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("easy.in","r",stdin);
	freopen("easy.out","w",stdout);
	int Tt=1;Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}

50分（方法一）

#include<bits/stdc++.h> 
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) {For(i,1,n) cerr<<a[i]<<b;cerr<<'\n';}
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 101234;
bool ST;double Tim;

int a[N],f[N][64];
int n,m;

int dfs(int l,int r){
	if(l==r) return a[l];
	if(f[l][r-l]) return f[l][r-l];
	int res = -inf;
	For(i,l,r-1) res = max(res, dfs(l,i) + dfs(i+1,r)*2);
	return f[l][r-l]=res;
}

void Solve(){
	n=rd(),m=rd();For(i,1,n) a[i]=rd();
	while(m--){
		int l=rd(),r=rd();
		write((dfs(l,r)%mod+mod)%mod), putchar('\n'); 
	}
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("easy.in","r",stdin);
	freopen("easy.out","w",stdout);
	int Tt=1;Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}

70分

#include<bits/stdc++.h> 
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) {For(i,1,n) cerr<<a[i]<<b;cerr<<'\n';}
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 1012345;
bool ST;double Tim;

int a[N],b[N];
int n,m;

void Solve(){
	n=rd(),m=rd();For(i,1,n) a[i]=rd();
	while(m--){
		int l=rd(),r=rd();For(i,l,r) b[i]=a[i];
		int pos = 0;
		Rof(i,r,l+1){
			if(b[i] > (int)1e18){
				pos = i;
				break;
			}
			if(b[i] > 0) b[i-1] = b[i]*2 + b[i-1],b[i] = 0;
		}
		
		int x = 0;
		if(pos){
			x = b[pos]%mod;
			Rof(i,pos-1,l) x = (b[i]+2*x)%mod;
			For(i,pos+1,r) x = (x+2*b[i])%mod;
		}else{
			x = b[l]%mod;
			For(i,l+1,r) x = (x+2*b[i])%mod;
		}write((x+mod)%mod), putchar('\n');
		
	}
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("easy.in","r",stdin);
	freopen("easy.out","w",stdout);
	int Tt=1;Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}