「SHOI2013」发牌-fhq Treap

在一些扑克游戏里,如德州扑克,发牌是有讲究的。一般称呼专业的发牌手为荷官。荷官在发牌前,先要销牌。所谓销牌,就是把当前在牌库顶的那一张牌移动到牌库底,它用来防止玩家猜牌而影响游戏。

假设一开始,荷官拿出了一副新牌,这副牌有 $N$ 张不同的牌,编号依次为 $1$ 到 $N$ 。由于是新牌,所以牌是按照顺序排好的,从牌库顶开始,依次为 $1, 2, \dots$ 直到$N$ ,$N$ 号牌在牌库底。为了发完所有的牌,荷官会进行$N$ 次发牌操作,在第 $i$ 次发牌之前,他会连续进行 $R_i$ 次销牌操作, $R_i$ 由输入给定。请问最后玩家拿到这副牌的顺序是什么样的?

「NOI2007」货币兑换-Splay+斜率优化

小 $Y$ 最近在一家金券交易所工作。该金券交易所只发行交易两种金券:$A$ 纪念券(以下简称 $A$ 券)和 $B$ 纪念券(以下简称 $B$ 券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 $A$ 券 和 $B$ 券的价值分别为 $A_K$ 和 $B_K$(元/单位金券)。为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法。比例交易法分为两个方面:

(a)卖出金券:顾客提供一个 $[0,100]$ 内的实数 $OP$ 作为卖出比例,其意义为:将 $OP\%$ 的 $A$ 券和 $OP\%$ 的 $B$ 券以当时的价值兑换为人民币;

(b)买入金券:顾客支付 $IP$ 元人民币,交易所将会兑换给用户总价值为 $IP$ 的金券,并且,满足提供给顾客的 $A$ 券和 $B$ 券的比例在第 $K$ 天恰好为 $Rate_K$ ;

注意到,同一天内可以进行多次操作。小 $Y$ 是一个很有经济头脑的员工,通过较长时间的运作和行情测算,他已经知道了未来 $N$ 天内的 $A$ 券和 $B$ 券的价值以及 $Rate$ 。他还希望能够计算出来,如果开始时拥有 $S$ 元钱,那么 $N$ 天后最多能够获得多少元钱。

Splay学习笔记

伸展树(Splay Tree)是一种二叉查找树,它能在$O(log n)$内完成插入、查找和删除操作。它是由丹尼尔·斯立特(Daniel Sleator)和罗伯特·塔扬(Robert Tarjan)在1985年发明的。其也可以维护区间信息,当作类似线段树的数据结构。

「SCOI2013」多项式的运算-Splay

维护一个动态的关于 $x$的无穷多项式 ,这个多项式初始时对于所有 $i$ 有 $a_i = 0$

$$
f(x)=a_0x^0+a_1x^1+a_2x^2…
$$

操作者可以进行四种操作:

  • mul L R V 表示将 $x^L$ 到 $x^R$ 这些项的系数乘上某个定值 $v$ ;

  • add L R V 表示将 $x^L$ 到 $x^R$ 这些项的系数加上某个定值 $v$ ;

  • mulx L R 表示将 $x^L$ 到 $x^R$ 这些项乘上x变量;

  • query V 求 $f(v)$ 的值。

操作集中在前三种,第四种操作不会出现超过 $10$ 次。

「HNOI2009」梦幻布丁-set-启发式合并

$n$ 个布丁摆成一行,每个布丁最开始都有一个颜色 $c_i$ ,进行 $m$ 次操作。

操作格式:

  • 1 c d :将所有的 $c$ 颜色替换为$d$

  • 2 :查询当前布丁序列一共有多少段颜色。例如颜色分别为 $1,2,2,1$ 的四个布丁一共有3段颜色。

「NOI2009」二叉查找树-区间dp

给定$n$个结点的数据值$V_i$,权值$P_i$,访问频度$T_i(T_i \geq 0)$。对于$\forall i,j \in V$且$i \neq j$,有$V_i \neq V_j, P_i \neq P_j$。

现令这n个点组成一颗二叉树,且满足$\forall \, i \in V$,若$p$为$i$的左子节点,$q$为$i$的右子节点,则$V_p < V_i < V_q$且$P_i < P_p,\; P_i < P_q$。可以证明,这样的二叉树是唯一的。点$i$在树中的深度$D_i$定义为它到根的距离加$1$。定义结点$i$的访问代价$E_i = T_i \times D_i$。可以修改每个点的权值为任意实数,其代价均为给定的正整数$K$,但需保证任两点权值仍互不相同。

现求上文所述二叉树中,其 $\sum^n _{i = 1}{E_i} + \sum K$的最小值。

「Luogu3765」总统选举-平衡树-线段树

秋之国共有$n$个人,分别编号为$1,2,…,n$,一开始每个人都投了一票,范围$[1,n]$,表示支持对应编号的人当总统。共有$m$次预选,每次选取编号$[l_i,r_i]$内的选民展开小规模预选,在该区间内获得超过区间大小一半的票的人获胜,如果没有人获胜,则由小$C$钦定一位候选者获得此次预选的胜利(获胜者可以不在该区间内),每次预选的结果需要公布出来,并且每次会有$k_i$个人决定将票改投向该次预选的获胜者。全部预选结束后,公布最后成为总统的候选人,没有候选人的话输出$-1$。

「ZJOI2007」报表统计-平衡树

有一个长度为$n$的整数序列,并且有以下三种操作:

  • $INSERT i k$:在原数列的第$i$个数后面添加一个新数$k$;如果原数列的第$i$个数已经添加了若干数,则添加在这些数的最后

  • $MIN GAP$:查询相邻两个数的之间差值(绝对值)的最小值

  • $MIN SORT GAP$:查询所有数中最接近的两个数的差值(绝对值)

「NOI2005」维护数列-非旋Treap

维护一个数列,给定初始的 $n$ 个数字。

现有六种命令:

  • 在第 $pos$ 个数后插入 $tot$ 个数
  • 翻转从第 $pos$ 个数开始的 $tot$ 个数
  • 删除从第 $pos$ 个数开始的 $tot$ 个数
  • 查询从第 $pos$ 个数开始的 $tot$ 个数的和
  • 设定从第 $pos$ 个数开始的 $tot$ 个数设定为 $c$
  • 查询整个数列中和最大的连续子区间的和

非旋Treap学习笔记

非旋$Treap$,是一种不基于旋转的平衡树。它基于$Treap$的树堆思想,并且能够高效的完成某些对区间的操作,而且灵活性比较高。它也可以进行可持久化的操作。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×