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