【BZOJ4837】LRU算法 [模拟]

LRU算法

Time Limit: 6 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]

Description

　　小Q同学在学习操作系统中内存管理的一种页面置换算法，LRU(LeastRecentlyUsed)算法。

　　为了帮助小Q同学理解这种算法，你需要在这道题中实现这种算法，接下来简要地介绍这种算法的原理：

　　　　1.初始化时，你有一个最大长度为n的空队列，用于暂时存储一些页面的地址。

　　　　2.当系统需要加载一个不在队列中的页面时，如果队列已满，则弹出队首元素，并将需要加载的页面加到队尾，否则直接将需要加载的页面加到队尾。

　　　　3.当系统需要加载一个在队列中的页面时，将该页面移至队尾。

　　在这道题中，小Q同学需要处理有q个请求，每个请求会给定一个整数x，表示系统需要加载地址为x的页面，而你需要在每个请求完成后给出整个队列中页面的地址之和。

　　为了便于计算，设第i个请求给出的整数为x_i，

　　第i个请求后你给出的答案为y_i，则对于1<i≤q有x_i=(A*x_(i-1)+B)modp，其中x_1,A,B,p是给定的整数，并且你只需要输出sigma(i*y_i),1<=i<=Q对2^64取模的值，而不是每个y_i。

Input

　　第一行包含一个正整数T，表示有T组数据，满足T≤20。

　　接下来依次给出每组测试数据。对于每组测试数据：

　　第一行包含两个正整数n和q，满足。

　　第二行包含四个整数x_1,A,B和p，满足。

Output

　　对于每组测试数据，输出一行一个非负整数，表示这组数据的答案。

Sample Input

　　2
　　5 10
　　0 1 1 5
　　5 10
　　0 1 1 10

Sample Output

　　485
　　1135

HINT

　　1≤n≤10^5, 1≤q≤10^6
　　0≤x_1,A,B<p, 1≤p≤10^6+3

Main idea

　　队列元素个数上限为n。每次加入一个元素x，
　　1.如果x不在队列中：
　　　　1.如果队列没满，把x放在队尾；
　　　　2.如果队列元素满了，把队头删掉，x放在队尾。
　　2.如果x在队列中：
　　　　把x删掉，把x扔到队尾。

　　定义val为当前队列中所有元素和，求Σi*val。

Solution

　　直接用数组模拟即可，我们设定PD[i]表示 i 这个位置是否有元素，pos[i]表示元素 i 所在的位置，然后用一个 q 表示当前队列。

　　那么显然删除队头的话，只要删除当前第一个有元素的位置，加入的话扔在队尾即可。

　　中间用num、val记录元素个数以及元素和即可。

　　（至于对2^64取模，就是unsigned long long自然溢出即可。）

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<vector>

 using namespace std;

 typedef unsigned long long ull;

 const int ONE = 1e5+;

 const int INF = ;

 int T;

 int n,m;

 int x,A,B,p;

 int PD[],pos[];

 int q[];

 int Ans;

 inline int get()

 {

         int res=,Q=;  char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 void Solve()

 {

         n=get();    m=get();

         x=get();    A=get();    B=get();    p=get();

         ull Ans = , val = ;

         int tou=, wei=, num=;

         for(int i=;i<=max(n,m);i++) PD[i] = ;

         for(int i=;i<=p;i++) pos[i] = ;

         for(int i=;i<=m;i++)

         {

             if(!pos[x])

             {

                 if(num == n)

                 {

                     while(!PD[tou]) tou++;

                     pos[q[tou]] = ;    PD[tou] = ;

                     val -= q[tou];  num--;

                 }

                 q[++wei] = x;

                 pos[x] = wei; PD[wei] = ;

                 val+=x; num++;

             }

             else

             {

                 q[++wei] = x;

                 PD[pos[x]] = ; pos[x] = wei; PD[pos[x]] = ;

             }

             x = ((long long)A*x%p + B) % p;

             Ans += i*val;

         }

         cout<<Ans<<endl;

 }

 int main()

 {

         T=get();

         while(T--)

             Solve();

 }

秒客网