UVa 10891 - Game of Sum

题目地址

描述

长度为 $n(1 \leq n \leq 100)$ 的整数序列,两个玩家 $\text{A}$ 和 $\text{B}$ 轮流取数。 $\text{A}$ 先取,每次每一个玩家只能从序列的一端开始取若干个数,但不能在序列的两端同时取。所有数都被取走后,统计 $\text{A}, \text{B}$ 玩家手上的数字的和作为各自的得分。我们假定 $\text{A}, \text{B}$ 两个人都很聪明且采用对自己最优的策略,求 $\text{A}$ 的得分减去 $\text{B}$ 的得分的结果。

Read More

Share

UVa 10635 - Prince and Princess

题目地址

描述

两个长度为$p + 1$的序列$\text{A}$和$q + 1$的序列$\text{B}$,每个序列中的元素各不相同,且都是$1 \sim n^{2}$之间的整数 $(2 \leq n \leq 250)$。两个序列开始的第一个元素都是$1$,求$A$和$B$的最长公共子序列。

Read More

Share

BZOJ 1579: [Usaco2009 Feb]Revamping Trails 道路升级

题目地址

描述

每天,农夫 John 需要经过一些道路去检查牛棚 $N$ 里面的牛。
农场上有$M(1 \leq M \leq 50,000)$条双向泥土道路,编号为$1 \cdots M$, 道路 $i$ 连接牛棚$P1_{i}$和$P2_{i}$ $(1 \leq P1_{i} \leq N; 1 \leq P2_{i} \leq N)$。
John 需要$T_{i} (1 \leq T_{i} \leq 1,000,000)$ 时间单位用道路 $i$ 从$P1_{i}$走到$P2_{i}$或者从$P2_{i}$ 走到$P1_{i}$ 他想更新一些路经来减少每天花在路上的时间。具体地说,他想更新 $K (1 \leq K \leq 20)$ 条路经,将它们所须时间减为$0$。帮助 FJ 选择哪些路经需要更新使得从 $1$ 到 $N$ 的时间尽量少。

Read More

Share

BZOJ 2763: [JLOI2011]飞行路线

题目地址

描述

Alice 和 Bob 现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在 $n$ 个城市设有业务,设这些城市分别标记为 $0$ 到 $n-1$ ,一共有 $m$ 种航线,每种航线连接两个城市,并且航线有一定的价格。
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多 $k$ 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少?

Read More

Share

[模板]哈夫曼树

定义

哈夫曼树(Huffman Tree)是一种带权路径长度最短的二叉树,也称为最优二叉树。

Read More

Share

「NOI 2015」 荷马史诗

题目地址

描述

追逐影子的人,自己就是影子。 ——荷马

Allison 最近迷上了文学。她喜欢在一个慵懒的午后,细细地品上一杯卡布奇诺,静静地阅读她爱不释手的《荷马史诗》。《荷马史诗》实在是太长了,Allison 想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有 $n$ 种不同的单词,从 $1$ 到 $n$ 进行编号。其中第 $i$ 种单词出现的总次数为 $w_{i}$。Allison 想要用 $k$ 进制串 $s_{i}$ 来替换第 $i$ 种单词,使得其满足如下要求:

  • 对于任意的 $1 \leq i,j \leq n$,$i \neq j$,都有:$s_{i}$ 不是 $s_{j}$ 的前缀。

现在 Allison 想要知道,如何选择 $s_{i}$,才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下,Allison 还想知道最长的 $s_{i}$ 的最短长度是多少?

Read More

Share

「NOIP 2004」 合并果子

题目地址

描述

在一个果园里,多多按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过$n-1$次合并之后,就只剩下一堆了,多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
多多在合并果子时要尽可能地节省体力。假定每个果子重量都为$1$,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。
$1 \leq n \leq 10000$

Read More

Share

BZOJ 1578: [Usaco2009 Feb]Stock Market 股票市场

题目地址

描述

尽管奶牛们天生谨慎,她们仍然在住房抵押信贷市场中受到打击,现在她们开始着手于股市。 Bessie很有先见之明,她不仅知道今天$S (2 \leq S \leq 50)$只股票的价格,还知道接下来一共$D(2 \leq D \leq 10)$天的(包括今天)。
给定一个$D$天的股票价格矩阵$(1 \leq 价格 \leq 1000)$以及初始资金$M(1 \leq M \leq 200,000)$,求一个最优买卖策略使得最大化总获利。
每次必须购买股票价格的整数倍,同时你不需要花光所有的钱(甚至可以不花)。
这里约定你的获利不可能超过$500,000$。

Read More

Share

[模板]传递闭包

很久之前听说过,今天学习一下QAQ

简介

传递闭包,在数学中表示为在集合 $X$ 上的二元关系 $R$ 的传递闭包是包含 $R$ 的 $X$ 上的最小的传递关系。

Read More

Share

BZOJ 1577: [Usaco2009 Feb]庙会捷运Fair Shuttle

题目地址

描述

公交车一共经过$N(1 \leq N \leq 20000)$个站点,从站点$1$一直驶到站点$N$。$K(1\leq K \leq 50000)$群奶牛希望搭乘这辆公交车,第$i$群牛一共$M_{i}(1\leq M_{i} \leq N)$只,他们希望从$S_{i}$到$E_{i}$去。
公交车只能坐$C(1\leq C \leq 100)$只奶牛,而且不走重复路线,请计算这辆车最多能满足多少奶牛听要求。
注意:对于每一群奶牛,可以部分满足,也可以全部满足,也可以全部不满足。

Read More

Share