题目传送门:http://pan.baidu.com/s/1i52O6xR
这题,试一试,可以发现(我真的是试出来的QAQ),我们可以用一个数,在他前面,且大于他的数的个数来更新答案
这个,证明的话,不难发现,每一次排序,都一定会使一个大于a的数跑到a的右边去。
所以搞个BIT就可以O(nlogn)搞,70分。
当然,这个做法有一点奇技淫巧可以让他A掉:
不难发现“在他前面,且大于他的数的个数”是单增的。
所以,我们倒着来的话,既可以提前break掉
这样的话,O(nlogn)就变成了O((n-ans)logn)因为ans一般很大,所以实际耗时和std差不多。
再来说一说std
再一次观察冒泡排序,不难发现,每一次排序,任意一个元素(现在的位置在最终位置的右边的那一部分),
如果不在最终的位置,那么一定会向前移动一格。(证明同算法一)
于是我们就可以直接用i-arr[i]来更新答案
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define LL long long #define low(x) (x&-(x)) using namespace std; inline int read(){ char c=getchar(); int buf=0,f=1; while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();} return buf*f; } const int MAXN = 30000000+9; int n,vout,arr[MAXN],sum[MAXN],S,B,C,D; int main(){ freopen("aria.in","r",stdin); freopen("aria.out","w",stdout); n=read(); S=read(); B=read(); C=read(); D=read(); for (int i=1;i<=n;i++){ arr[i] = i; S = ((LL)S*(LL)B+(LL)C)%(LL)D; swap(arr[i], arr[(S%i)+1]); } for (int i=n,tmp;i>=vout;i--) vout = max(vout, i-arr[i]); printf("%d\n",vout); }