首页 > 代码库 > 【NOIP 模拟赛】区间第K大(kth) 乱搞
【NOIP 模拟赛】区间第K大(kth) 乱搞
biubiu~~~
这道题就是预处理，我们就是枚举每一个数，找到左边比他大的数的个数以及其对应的区间，右边也如此，我们把左边的和右边的相乘就得到了我们的答案，我们发现这是O(n^3)的，但是实际证明他能A，分析证明他的时间复杂度是较小的，这个故事告诉我们，对于一些估计的时间复杂度，如果我们估计得太草率以至于他过于偏离实际我们往往会做出错误的决定，于是我们对于某一些拿不准的时间复杂度应该稍作分析。
正解FFT.............
#include <cstdio>#include <cstring>namespace Pre{ inline void read(int &sum){ register char ch=getchar();bool symbol=0; for(sum=0;ch<‘0‘||ch>‘9‘;ch=getchar())if(ch==‘-‘)symbol=1; for(;ch>=‘0‘&&ch<=‘9‘;sum=(sum<<1)+(sum<<3)+ch-‘0‘,ch=getchar()); if(symbol)sum=-sum; } const int N=2017; int Num_Kth[N][N]; int z[N],y[N],l,r,Q; int n,a[N]; inline void Init(){ for(int mid=1;mid<=n;mid++){ memset(z,0,sizeof(z)); memset(y,0,sizeof(y)); l=r=0;z[0]=y[0]=1; for(int i=mid-1;i>0;--i){ if(a[i]>=a[mid])++l; ++z[l]; } for(int i=mid+1;i<=n;++i){ if(a[i]>a[mid])++r; ++y[r]; } for(int i=0;i<=l;++i) for(int j=0;j<=r;++j) Num_Kth[a[mid]][i+j+1]+=z[i]*y[j]; } }}namespace P=Pre;inline void Init(){ P::read(P::n),P::read(P::Q); for(int i=1;i<=P::n;i++)P::read(P::a[i]); P::Init();}inline void Work(){ register int k,x; while(P::Q--){ P::read(k),P::read(x); printf("%d\n",P::Num_Kth[x][k]); }}int main(){ Init(),Work(); return 0;}
【NOIP 模拟赛】区间第K大(kth) 乱搞
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。