提高模考7.30 T4《柱状图》题解

找出来个类似的,快来卡

#include<bits/stdc++.h>
#define ll long long
#define N 200005
using namespace std;
int n,lg[N];
int dp_a[N][25],dp_b[N][25];
ll ans=0;
int query_a(int l,int r){
    int k=lg[r-l+1];
    return min(dp_a[l][k],dp_a[r-(1<<k)+1][k]);
}
int query_b(int l,int r){
    int k=lg[r-l+1];
    return min(dp_b[l][k],dp_b[r-(1<<k)+1][k]);
}
vector<int> v;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
		scanf("%d%d",&dp_a[i][0],&dp_b[i][0]);
		v.push_back(i);
    }
    for(int i=2;i<=n;i++){
        lg[i]=lg[i>>1]+1;
    }
    for(int i=1;i<21;i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			dp_a[j][i]=min(dp_a[j][i-1],dp_a[j+(1<<i-1)][i-1]);
			dp_b[j][i]=min(dp_b[j][i-1],dp_b[j+(1<<i-1)][i-1]);
		}
    }
    random_shuffle(v.begin(),v.end());
    for(auto i:v){
    	for(ll j=i;j<=n;j++){
    		ll x=1ll*query_a(i,j)*query_b(i,j);
    		ans=max(ans,x*(j-i+1));
    		j=(ans/x)+i-1;
		} 
	}
	cout<<ans;
    return 0;
}

@linan024

你无法说明他的错误性, 也无法说明它的正确性, 大概率能行,考场上就可以试一试,

1 个赞

我说

“我要对着这个卡”

表现出来我忍受不了吗。我忍受不了的是他们的态度还有说什么“不TLE就是对的”的逆天言论。

那你还指责楼主人品呢,你看你这个脏话,你觉得你这样很有意思吗

2 个赞

考场上可以试试只是一种策略罢了,但理论上是可以卡的

1 个赞

但是,世界上只有AC,WA,TLE,RE,(其他忽略不计)这四个状态,证明了正确性,又不会RE,你说他不T不就是AC吗

2 个赞

AC 不等价于正确。

2 个赞

态度不妥,是有问题,但是你指出来之后自己开始骂脏话,这确实是没文化的体现。

2 个赞
  • 楼主态度问题,值得我们谴责。
  • 你们强词夺理,这也并不合理。
  • 复杂度不正确,这个我们承认。
  • 此贴到此结束,其余没有意义。
1 个赞

可是,你自己也表明了,非正解,那只能说数据比较水,稍微严一点都可以卡掉,非正解你发什么题解啊

1 个赞

什么【强词夺理】大佬/bx/bx/bx/bx

2 个赞

是楼主先骂,但先后无关,骂了就是不应该。

3 个赞

那是, 1 / n! 就很难被遇上,策略其实最为重要, 拼一拼, 搏一搏, 单车变摩托

3 个赞

但是这个非正解是一种考场上的策略,可以参考啊

2 个赞

你自己计算一下卡掉的概率再说话

2 个赞

这也有点过了

做法都可以发,但是发出来就要考虑经受评价的后果。

1 个赞

@张铭祺 小朋友,这个卡不掉的,除非你出n!个数据才能保证卡掉hh

2 个赞

很小很小

1 个赞

为什么被卡掉的概率是1/n!

2 个赞

TLE的理论概率是 1/n!
n \le 200000

1 个赞