NOI
「NOI2006」最大获利-网络流-最大权闭合子图
· ✏️ 1108 words · ☕ 3 mins read

新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜,需要做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。

在前期市场调查和站址勘测之后,公司得到了一共 $N$ 个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需要投入的成本也是不一样的,所幸在前期调查之后这些都是已知数据:建立第 $i$ 个通讯中转站需要的成本为 $P_i$ 。

另外公司调查得出了所有期望中的用户群,一共 $M$ 个。关于第 i 个用户群的信息概括为 $A_i$ , $B_i$ 和 $C_i$ :这些用户会使用中转站 $A_i$ 和中转站 $B_i$ 进行通讯,公司可以获益 $C_i$​ 。

THU 集团的 CS&T 公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 – 投入成本之和)


「NOI2005」聪聪与可可-期望dp
· ✏️ 874 words · ☕ 2 mins read

给定一个 $n$ 个点, $m$ 条边的无向图。聪聪开始的时候在 S,可可在节点 T 处。以后的每个时间单位,可可都会选择去相邻的景点(可能有多个)中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。假设有 $P$ 个景点与景点 M 相邻,它们分别是景点 R、 景点 S,……,景点 Q,在时刻 $i$ 可可处在景点 M,则在 $i+1$ 时刻,可可有 $\frac{1}{1+P}$ 的可能在景点 R,有 $\frac{1}{1+P}$ 的可能在景点 S,……,有 $\frac{1}{1+P}$ 的可能在景点 Q,还有 $\frac{1}{1+P}$ 的可能停在景点 M。

当聪聪在景点 C 时,她会选一个更靠近可可的景点,如果这样的景点有多个,她会选一个标号最小的景点。如果走完第一次移动以后仍然没吃到可可,她还可以在本段时间内再向可可进行一次移动。

在每个时间单位,假设聪聪先走,可可后走。在某一时刻,若聪聪和可可位于同一个景点,则可怜的可可就被吃掉了。

请求出平均情况下,聪聪用几个时间单位就可能吃到可可。


「NOI2007」货币兑换-Splay+斜率优化
· ✏️ 1924 words · ☕ 4 mins read

小 $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$ 天后最多能够获得多少元钱。


「NOI2015」寿司晚宴-状压dp
· ✏️ 1426 words · ☕ 3 mins read

为了庆祝 $NOI$ 的成功开幕,主办方为大家准备了一场寿司晚宴。小 $G$ 和小 $W$ 作为参加 $NOI$ 的选手,也被邀请参加了寿司晚宴。

在晚宴上,主办方为大家提供了 $n−1$ 种不同的寿司,编号 $1,2,3,⋯,n-1$ ,其中第种寿司的美味度为 $i+1$(即寿司的美味度为从 $2$ 到 $n$ )。

现在小 $G$ 和小 $W$ 希望每人选一些寿司种类来品尝,他们规定一种品尝方案为不和谐的当且仅当:小 $G$ 品尝的寿司种类中存在一种美味度为 $x$ 的寿司,小 $W$ 品尝的寿司中存在一种美味度为 $y$ 的寿司,而 $x$ 与 $y$ 不互质。

现在小 $G$ 和小 $W$ 希望统计一共有多少种和谐的品尝寿司的方案(对给定的正整数 $p$ 取模)。注意一个人可以不吃任何寿司。


「NOI2009」诗人小G-动态规划+决策单调性
· ✏️ 994 words · ☕ 2 mins read

小 $\text{G}$ 是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。

一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小 $\text{G}$ 给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小 $\text{G}$ 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下,小 $\text{G}$ 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 $P$ 次方,而一个排版的不协调度为所有行不协调度的总和。

小 $\text{G}$ 最近又作了几首诗,现在请你对这首诗进行排版,使得排版后的诗尽量协调(即不协调度尽量小),并把排版的结果告诉他。


「NOI2012」魔幻棋盘-差分+树套树
· ✏️ 1480 words · ☕ 3 mins read

将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘,它是一个 $N$ 行 $M$ 列的网格棋盘,每个格子中均有一个正整数。棋盘守护者在棋盘的第 $X$ 行第 $Y$ 列(行与列均从 $1$ 开始编号)并且始终不会移动。棋盘守护者会进行两种操作:

  1. 询问:他会以自己所在位置为基础,向四周随机扩展出一块大小不定的矩形区域,向你询问这一区域内所有数的最大公约数是多少。

  2. 修改:他会随意挑选棋盘上的一块矩形区域,将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友,当你连续答对 $19930324$ 次询问后会得到一个惊喜噢!”。小 Q 十分想得到这个惊喜,于是每天都在玩这个玩具。但由于他粗心大意,经常算错数,难以达到这个目标。于是他来向你寻求帮助,希望你帮他写一个程序来回答棋盘守护者的询问,并保证 $100%$ 的正确率。

为了简化问题,你的程序只需要完成棋盘守护者的 $T$ 次操作,并且问题保证任何时刻棋盘上的数字均为不超过 $2^{62} - 1$ 的正整数。


「NOI2010」航空管制-拓扑排序
· ✏️ 756 words · ☕ 2 mins read

假设目前被延误航班共有 $n$ 个,编号为 $1$ 至 $n$ 。机场只有一条起飞跑道,所有的航班需按某个顺序依次起飞(称这个顺序为起飞序列)。定义一个航班的起飞序号为该航班在起飞序列中的位置,即是第几个起飞的航班。

起飞序列还存在两类限制条件:

  • 第一类(最晚起飞时间限制):编号为 $i$ 的航班起飞序号不得超过 $k_i$ ;

  • 第二类(相对起飞顺序限制):存在一些相对起飞顺序限制 $(a, b)$ ,表示航班 $a$ 的起飞时间必须早于航班 $b$ ,即航班 $a$ 的起飞序号必须小于航班 $b$ 的起飞序号。

小 $\text{X}$ 思考的第一个问题是,若给定以上两类限制条件,是否可以计算出一个可行的起飞序列。第二个问题则是,在考虑两类限制条件的情况下,如何求出每个航班在所有可行的起飞序列中的最小起飞序号。


「NOI2015」品酒大会-后缀数组
· ✏️ 1520 words · ☕ 4 mins read

简单版题意:

给定一个长度为 $n$ 的字符串,和一个长度为 $n$ 的数列 ${a_n}$ ,求对于 $r$ 从 $0$ 到 $n-1$ ,所有满足 $1 \leq p < q \leq n$ 且 $lcp(p,q) \geq r$ 的数对个数以及满足上述条件的数对中 $a_p \times a_q$ 的最大值。( $a_i$ 可以为负数)


「NOI2016」优秀的拆分-后缀数组
· ✏️ 1271 words · ☕ 3 mins read

如果一个字符串可以被拆分为 $AABB$ 的形式,其中 $A$ 和 $B$ 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$ ,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意:

  • 出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
  • 在一个拆分中,允许出现 $A = B$。例如 $cccc$ 存在拆分 $A = B = c$。
  • 字符串本身也是它的一个子串。

「NOI2010」能量采集-简单数学
· ✏️ 558 words · ☕ 2 mins read

给定两个整数 $n,m$ ,对于平面上的整点 ${(x,y)|x \in [1,n],y \in [1,m],x,y \in \mathbb Z}$ 。若 $(x,y)$ 与 $(0,0)$ 的连线上有 $k$ 个整点(不包括 $(0,0),(n,m)$ ),则产生的贡献为 $2k+1$ 。求所有满足条件的点的贡献总和。


「NOI2014」魔法森林-LCT
· ✏️ 1188 words · ☕ 3 mins read

给定一个 $n$ 个点 $m$ 条边的无向图,每条边有两个权值 $a_i,b_i$ 。请你找到一条从 $1 \rightarrow n$ 的道路,令道路上所有边的集合为 $S$ ,使 $ans = \max(a_i)+\max(b_j),i,j \in S$ 最小,求出这个最小值 $ans$ 。


「NOI2012」美食节-费用流
· ✏️ 1114 words · ☕ 3 mins read

美食节共有 $n$ 种不同的菜品,每个同学都点了一份在这 $n$ 个菜品中的菜。总共有 $m$ 个厨师来制作这些菜品。厨师们会按照要求的顺序进行制作,并且每次只能制作一人份。第 $j$ 个厨师制作第 $i$ 种菜品的时间记为 $t_{i,j}$ 。每个同学的等待时间为所有厨师开始做菜起,到自己那份菜品完成为止的时间总长度。总等待时间为所有同学的等待时间之和。

已知共有 $n$ 种菜品,第 $i$ 种菜品需要做 $p_i$ 份,共有 $m$ 个厨师。请计算出最小的总等待时间是多少。


「NOI2009」二叉查找树-区间dp
· ✏️ 1045 words · ☕ 3 mins read

给定 $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$ 的最小值。