你有本事真卡random_shuffle()，哥们，你能保证刚刚好1/n!概率卡死啊？？
2 个赞
我卡不掉不是你复杂度正确的理由。
1 个赞
不必卡死，卡住就行，不管怎样最坏复杂度包错的
既然这个解很难卡，就说明他是可用的，这和spfa的逻辑差不多
2 个赞
“可用”和“复杂度正确”又不是本质相同。
那你说一些随机化的题目那他的错误概率是1/998244353，那按照你的来说不就WA了吗
2 个赞
错解不都是因为在赛时的数据“可用”但是“复杂度不正确”所以才要卡吗。
所以有的卡哈希，你有意见？
1 个赞
但是那个可以卡，这个无法卡啊
1 个赞
找出来个类似的
#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
怎么，一起讨论的证明方法，老师教的，怎么就是抄袭了？
2 个赞
首先，我承认codeforces上面有随机化题目，错误率十分小。
但是和这个帖子的情况本质不同。这个是时间复杂度的问题不是正确性的问题。
1 个赞
本质肯定相同啊，WA和TLE不都是错吗。这两题中，WA 和 TLE 的概率都很小
2 个赞
如何证明非常小，出题人没考虑到的方面就非常小吗
这么说其实所有的hash题错误率都是100
任何的hash都是可以卡的，除非你的模数是值域，直接T飞/cf
那你总结一下，就是出题人的问题了？就是老师的问题了？
2 个赞