2018QBXT刷题游记（23）

桃扇骨 2022-01-07 15:43 186阅读 0赞

### 【2018QBXT刷题游记】 ###

#### Day5 TEST8 ####

##### T2 schedule #####

【问题描述】  
共有 n 件事情，编号为 1, 2, …, n，第 i 件事情的难度为 i. 划分为 m 个时刻，并设定了三个正整数 a, b, c。  
定义一个数列\{xi\}，满足：  
x0=0,xi=(a∗xI−1+b)mod&ThinSpace;&ThinSpace;2∗n∗c(1≤i≤m)x\_\{0\} = 0, x\_\{i\} = (a\*x\_\{I−1\}+ b) \\mod 2\*n\*c (1 ≤ i ≤ m)x0=0,xi=(a∗xI−1\+b)mod2∗n∗c(1≤i≤m)  
即从 x\_\{1\} 开始，数列的每项等于上一项的 a 倍加上 b 以后除以 2nc 的余数。  
开始时日程表是空的. 第 i 个时刻前，

1.  若 xi < nc，则将编号为⌊xc⌋+1⌊\\frac\{x\}\{c\}⌋ + 1⌊cx⌋\+1的事件加⼊日程表，若日程表已有该事件则忽略；
2.  若 xi ≥ nc，则将编号为 ⌊xc⌋−n+1⌊\\frac\{x\}\{c\}⌋ - n+ 1⌊cx⌋−n\+1 的事件从日程表删除，若日程表没有该事件则忽略；  
    第 i 个时刻（1 ≤ i ≤ m），所做的事情就是该时刻日程表中的所有事件.  
    对于每个时刻，定义该时刻的g工作量为该时刻做了几件事情，该时刻的疲劳度为该时刻做的所有事情的难度之和.

根据 n, m, a, b, c 计算总工作量和疲劳度.  
n≤5×107，m≤2×106，a≤106，b≤109，c≤5×104n ≤ 5×10^7，m ≤ 2×10^6，a ≤ 10^6，b ≤ 10^9，c ≤ 5×10^4n≤5×107，m≤2×106，a≤106，b≤109，c≤5×104

【分析】一道模拟题，不过这n有点大啊……

于是我欢快地开大了数组。爆零快乐！

其实只需要判断一下当前时刻加入或删除的数就可以啦，用t1和t2表示在计划表里的工作量和疲劳度即可~

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    #define ll long long
    #define MAXN 2000005
    bool vis[50000005];
    ll n,m,a,b,c,t1,t2;
    #define MOD 1000000007
    ll gzl,pld;
    int main(){
    	freopen("schedule.in","r",stdin);
    	freopen("schedule.ans","w",stdout); 
    	scanf("%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c);
    	ll tmp=0;ll qaq=n*c;
    	for(ll i=1;i<=m;i++){
    		tmp=(a*tmp+b)%(qaq*2);
    		if(tmp<qaq){
    			ll noww=(tmp/c)+1;
    			if(!vis[noww]){
    			vis[noww]=1;
    			t1=(t1+1)%MOD;t2=(t2+noww)%MOD;}
    		}
    		else{
    			if((tmp/c-n+1)>0){
    			ll noww=tmp/c-n+1;
    			if(vis[noww]){
    			vis[noww]=0;
    			t1=(t1-1+MOD)%MOD;
    			t2=(t2-noww+MOD)%MOD;}
    		}}
    		gzl=(gzl+t1)%MOD;
    		pld=(pld+t2)%MOD;
    	}
    	printf("%lld %lld\n",gzl,pld);
    	return 0;
    }

转载于:https://www.cnblogs.com/erutsiom/p/9905144.html