1 条题解
-
0
题目大意： q 次询问，每次取卡牌序列的 [L,R] 区间来玩接竹竿会剩下多少张牌 接竹竿规则为：每张牌上有一个点数 v ，将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相同的牌，则小核桃会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本身）
思路
我们定义从第 x 张牌开始玩，第一次出现 vy = vx 的情况，也就是将 x~y 之间的牌都取出，为 x 的一次跳跃，那么 x 会跳到 y+1 ，即 f[x][0] = y+1 。如果不存在这样的 y ，那么 f[x][0] = x 。记 f[i][j] 为从 i 出发跳 2^j 次的结果。
第一步，用倍增预处理出 f[i][j] 。
第二步，在回答询问时，如果 f[x][j] <= r+1 且 f[x][j+1] > r+1 ，那么我们可以确定，从 x 出发的跳跃次数在 2^j~2^(j+1) 之间，所以我们从大到小枚举j，第一次出现 f[x][j] <= r+1 时进行跳跃，然后重新从 f[x][j] 开始下一轮跳跃。
第三步，如果第二步中连续跳跃的结果是 x <= r，那么本次游戏中第 x 张牌会被留下，答案加一。因为留下的牌一定点数不同，所以最多只会发生 13 次答案加一。
参考代码
for (int i = 1; i <= q; ++i) //处理询问 { int x = l[i]; //x表示起跳点 int ans=0; while(x <= r[i]) { for (int j = log2n; j >= 0; --j) { if(f[x][j] <= r[i] + 1) x = f[x][j]; } if(x <= r[i]) { ans++; x++; } } cout << ans << endl; }
- 1