首页 > 代码库 > 51 nod 1495 中国好区间
51 nod 1495 中国好区间
1495 中国好区间
基准时间限制：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 300Output示例
7
/*51 nod 1495 中国好区间problem:给你一个公式递推出a[i],问有多少个区间它们的第k大数≥Tsolve:枚举每个点作为它的右端点r,找到最靠右的点l使[l,r]间≥T的数有k个. 那个这个r能贡献的区间个数就是l.hhh-2016/10/01-20:55:47*/#pragma comment(linker,"/STACK:124000000,124000000")#include <algorithm>#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <vector>#include <map>#include <queue>#include <functional>#include <math.h>#define lson i<<1#define rson i<<1|1#define ll long long#define clr(a,b) memset(a,b,sizeof(a))#define key_val ch[ch[root][1]][0]using namespace std;const int maxn = 1e7 + 1000;const int inf = 0x3f3f3f3f;const ll mod = 1000000007;const double eps = 1e-7;template<class T> void read(T&num){ char CH; bool F=false; for(CH=getchar(); CH<‘0‘||CH>‘9‘; F= CH==‘-‘,CH=getchar()); for(num=0; CH>=‘0‘&&CH<=‘9‘; num=num*10+CH-‘0‘,CH=getchar()); F && (num=-num);}int stk[70], tp;template<class T> inline void print(T p){ if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + ‘0‘); putchar(‘\n‘);}int n,k;ll T,a,b,c,p;int ta[maxn];int pos[maxn];int main(){ read(n),read(k),read(T); read(a),read(b),read(c),read(p); ta[0] = 0; memset(pos,0,sizeof(pos)); for(int i = 1; i <= n; i++) { ta[i] = ta[i-1]; ll t = (a * b + c ) % p; if(t >= T) ta[i] ++ ; if(!pos[ta[i]] && ta[i]) pos[ta[i]] = i; a = t; } int tpos = k; while(ta[tpos] < k) tpos ++ ; ll ans = 0; for(int i = tpos;i <= n;i++) { int p = pos[ta[i] - k + 1]; ans += p; } printf("%I64d\n",ans);}
51 nod 1495 中国好区间
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。