2020-2021:teams:alchemist:mountvoom:training1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:mountvoom:training1 [2020/05/13 20:09] mountvoom [F. 排列计算] |
2020-2021:teams:alchemist:mountvoom:training1 [2020/05/13 20:25] (当前版本) mountvoom [I. 纸牌] |
||
|---|---|---|---|
| 行 84: | 行 84: | ||
| ===== H. 时空栈 ===== | ===== H. 时空栈 ===== | ||
| + | **题意:** | ||
| + | |||
| + | 有三种操作： | ||
| + | |||
| + | $0, t, v$：在时刻$t$把$v$入栈 | ||
| + | |||
| + | $1, t$在时刻$t$把栈顶元素出栈 | ||
| + | |||
| + | $2, t$询问时刻$t$的栈顶元素 | ||
| + | |||
| + | 保证$t$互不相同，且出栈和询问时栈不空。 | ||
| + | |||
| + | **题解:** | ||
| + | |||
| + | 首先将$t$离散化，维护每个时刻栈内元素的个数。 | ||
| + | |||
| + | 那么对于查询操作，设$t$时刻之前首次栈内元素个数小于现在$t$时刻栈内元素个数的时间为$x$，那么在$x + 1$时刻一定是一个插入操作且是$t$时刻的栈顶。 | ||
| + | |||
| + | 想的时候没有注意到$t$都不同，但是好像也可以做，大致方法和上述一致，需要处理的是在$t$时刻先删除后入栈的情况，这两种应该分开维护，因为先删除是删除的前面入栈的元素，后删除删除的是时刻$t$入栈的元素。 | ||
| ===== I. 纸牌 ===== | ===== I. 纸牌 ===== | ||
| + | **题意:** | ||
| + | |||
| + | 桌上有一叠共$n$张牌，从顶向下标号为$1\sim n$。 | ||
| + | |||
| + | 这一叠牌做$k, k \leq 10^{18}$次操作，其中第$i$次操作会将牌堆顶的牌放在牌堆中的某个位置，从而满足这张牌成为自顶向下第$(i - 1) % (n - 1) + 2$张牌。求$k$次操作以后这叠牌自顶向下的编号情况。 | ||
| + | |||
| + | |||
| + | **题解:** | ||
| + | |||
| + | 假设$k \leq (n - 1)$，那么我们可以这样模拟： | ||
| + | |||
| + | 观察到如果此时顶部纸牌插入到了$x$这张牌的后面，那么下次要插入的纸牌位置就是nxt[nxt[x]]，用链表模拟即可。 | ||
| + | |||
| + | 当$k$很大时，假设$n - 1$操作后第$i$张牌编号为$p[i]$，那么$2(n - 1)$次操作后，第$i$张牌编号为$p[p[i]]$，这一部分可以倍增或者把排列$p$拆成循环来处理。 | ||
| + | |||
| + | 剩下的$k \% (n - 1)$次直接模拟即可。 | ||
| ===== J. 斐波那契和 ===== | ===== J. 斐波那契和 ===== | ||
2020-2021/teams/alchemist/mountvoom/training1.1589371769.txt.gz · 最后更改: 2020/05/13 20:09 由 mountvoom
