双指针扫一遍

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
int read(){
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}
char sh[15];
void print(int x){
int cnt=0;
while(x) sh[++cnt]=x%10,x/=10;
dwn(i,cnt,1) putchar(sh[i]+48);
putchar(32);
}
const int nmax=1e7+5;
bool a[nmax];
int main(){
int n=read(),k=read(),T=read(),a0=read(),b=read(),c=read(),p=read();
rep(i,1,n) if((a0=((ll)a0*b+c)%p)>=T) a[i]=1;
int l=0,r=0,cnt=0;ll ans=0;
while(1){
if(a[l]) --cnt;++l;
while(cnt<k&&r<=n) cnt+=a[r++];
if(cnt==k) ans+=n-r+2;
else break;
}
printf("%lld\n",ans);
return 0;
}

  

基准时间限制:0.7 秒 空间限制:131072 KB 分值: 80 难度:5级算法题
 收藏
 关注

阿尔法在玩一个游戏,阿尔法给出了一个长度为n的序列,他认为,一段好的区间,它的长度是>=k的,且该区间的第k大的那个数,一定大于等于T。那么问题来了,阿尔法想知道有多少好的区间。

由于阿尔法的序列长度实在是太大了,无法在规定时间内读入。

他想了一个绝妙的方法。

读入a[0],b,c,p,则a[i]=(a[i-1]*b+c)mod p。

样例解释:

a1~a5分别为47,135,247,35,147

对应的7个区间分别为[1,3],[2,3],[1,4],[2,4],[1,5],[2,5],[3,5]

 
对于重复的数字1,2,2 第一大是2,第二大也是2,第三大是1。
Input
读入一行,7个数字,表示n(n<=10000000),k(k<=n),T,a[0],b,c,p。
所有数字均为正整数且小于等于10^9。
Output
输出一行表示好区间的个数。
Input示例
5 2 100 10 124 7 300
Output示例
7

最新文章

  1. 安装pdo.so和pdo_mysql.so还有pcntl.so扩展到php中
  2. d3.js &lt;一&gt;
  3. sql 判断两个时间段是否有交集
  4. HDU 2063 过山车 (最大匹配,匈牙利算法)
  5. mysql 远程连接 1045 Access denied for user &#39;root&#39;@&#39;XX.XX.XX.XX&#39; (using password:YES)
  6. VS013的单元测试去哪里了
  7. 2014.8.3情人节欢乐赛【Benny的农场】
  8. hdu4612(双连通缩点+树的直径)
  9. GO语言从入门到放弃目录
  10. Mybatis面试题
  11. vue2.0 父子组件数据传递prop
  12. golang执行shell命令
  13. NFS CIFS SAMBA 的联系和区别
  14. HTML5+CSS3 表格设计(Table)
  15. Git和Repo管理使用简要介绍
  16. DistroWatch评估XStream桌面153版本
  17. lapis http verb 处理
  18. 第六章 通过Service访问Pod(下)
  19. OC和C语言比较
  20. linux 下多版本gcc 共存问题

热门文章

  1. Unity上使用Linq To XML
  2. mysql去除重复查询的SQL语句基本思路
  3. main函数和启动例程
  4. POJ 2023 Choose Your Own Adventure(树形,dfs,简单题)
  5. Javascript offsetLeft详情
  6. hdu 4155 The Game of 31 博弈论
  7. poj3415 Common Substrings(后缀数组,单调栈 | 后缀自动机)
  8. android-non-ui-ui-thread-communications-part-5-5
  9. Spark源码编译
  10. iOS 网络处理注意点