首页 > 代码库 > UVA 11423 - Cache Simulator(树状数组)

UVA 11423 - Cache Simulator(树状数组)

UVA 11423 - Cache Simulator

题目链接

题意:题目讲的大概就是几个cash,每次操作可以加入一个或一些数据,如果数据之前有就是hit,命中后的数据就不会消失,如果没有就miss,当容量超过cash容量时,就会把之前最早没命中的一个丢掉,每次START就执行这些命令,计算miss次数并输出

思路:由于最多就2^24的数据,所以可以开一个树状数组,每个位置表示第i个添加进去的数据,并且把每个数据对应的位置记录下来,下次如果添加到一个之前有的数据,就利用树状数组查询上一次到这一次之间一共有多少个数据,如果数据超过cash大小,那么就说明上一次的已经被丢弃,就会多一次miss,然后hit成功后就把上一次的数据位置-1,把这个数据定在当前添加位置+1。注意每次START的时候要重新计算一次

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define lowbit(x) (x&(-x))

const int N = 35;
const int MAXN = (1<<24) + 5;
int n, cach[N], bit[MAXN];

void add(int x, int v) {
    while (x < MAXN) {
	bit[x] += v;
	x += lowbit(x);
    }
}

int get(int x) {
    int ans = 0;
    while (x) {
	ans += bit[x];
	x -= lowbit(x);
    }
    return ans;
}

int get(int l, int r) {
    return get(r) - get(l - 1);
}

char op[10];
int ans[N], vis[MAXN], now;

void init() {
    now = 0;
    memset(bit, 0, sizeof(bit));
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++)
	scanf("%d", &cach[i]);
}

void tra(int num) {
    if (vis[num]) {
	int len = get(vis[num], now);
	for (int i = 0; i < n; i++) {
	    if (cach[i] >= len) break;
	    ans[i]++;
	}
	add(vis[num], -1);
    }
    else {
	for (int i = 0; i < n; i++)
	    ans[i]++;
    }
    add(vis[num] = ++now, 1);
}

void solve() {
    int x, b, y, nn;
    while (scanf("%s", op)) {
	if (op[0] == 'E') break;
	if (op[0] == 'S') {
	    for (int i = 0; i < n; i++)
		printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
	    memset(ans, 0, sizeof(ans));
	}
	if (op[0] == 'A') {
	    scanf("%d", &x);
	    tra(x);
	}
	if (op[0] == 'R') {
	    scanf("%d%d%d", &b, &y, &nn);
	    for (int i = 0; i < nn; i++)
		tra(b + y * i);
	}
    }
}

int main() {
    while (~scanf("%d", &n)) {
	init();
	solve();
    }
    return 0;
}