题目链接

传送门

题目描述

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。

从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

题目链接

传送门

题目背景

还记得 NOIP 2012 提高组 Day1 的国王游戏吗？时光飞逝，光阴荏苒，两年过去了。国王游戏早已过时，如今已被皇后游戏取代，请你来解决类似于国王游戏的另一个问题。

题目描述

皇后有 n 位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为 n 位大臣颁发奖金，其中第 i 位大臣所获得的奖金数目为第i－1 位大臣所获得奖金数目与前 i 位大臣左手上的数的和的较大值再加上第 i 位大臣右手上的数。

形式化地讲：我们设第 i 位大臣左手上的正整数为 ai，右手上的正整数为 bi，则第 i 位大臣获得的奖金数目为 ci可以表达为：

当然，吝啬的皇后并不希望太多的奖金被发给大臣，所以她想请你来重新安排一下队伍的顺序，使得获得奖金最多的大臣，所获奖金数目尽可能的少。
注意：重新安排队伍并不意味着一定要打乱顺序，我们允许不改变任何一位大臣的位置。

题目链接

传送门

题目描述

（喵星人LHX和WD同心协力击退了汪星人的入侵，不幸的是，汪星人撤退之前给它们制造了一片幻象迷宫。）

WD：呜呜，肿么办啊……

LHX：momo…我们一定能走出去的！

WD：嗯，+U+U！

描述 Description

幻象迷宫可以认为是无限大的，不过它由若干个N*M的矩阵重复组成。矩阵中有的地方是道路，用’.’表示；有的地方是墙，用’#’表示。LHX和WD所在的位置用’S’表示。也就是对于迷宫中的一个点(x,y)，如果(x mod n,y mod m)是’.’或者’S’，那么这个地方是道路；如果(x mod n,y mod m)是’#’，那么这个地方是墙。LHX和WD可以向上下左右四个方向移动，当然不能移动到墙上。

请你告诉LHX和WD，它们能否走出幻象迷宫（如果它们能走到距离起点无限远处，就认为能走出去）。如果不能的话，LHX就只好启动城堡的毁灭程序了……当然不到万不得已，他不想这么做。。。

题目链接

传送门

题目描述

英雄又即将踏上拯救公主的道路……
这次的拯救目标是——爱和正义的小云公主。
英雄来到boss的洞穴门口，他一下子就懵了，因为面前不只是一只boss，而是上千只boss。当英雄意识到自己还是等级1的时候，他明白这就是一个不可能完成的任务。
但他不死心，他在想，能不能避开boss去拯救公主呢，嘻嘻。
Boss的洞穴可以看成一个矩形，英雄在左下角（1,1），公主在右上角（row，line）。英雄为了避开boss，当然是离boss距离越远越好了，所以英雄决定找一条路径使到距离boss的最短距离最远。
Ps:英雄走的方向是任意的。
你可以帮帮他吗？
当英雄找到了美丽漂亮的小云公主，立刻就被boss包围了！！！英雄缓闭双眼，举手轻挥，白光一闪后使用了回城卷轴，回到了城堡，但只有小云公主回去了……因为英雄忘了进入回城的法阵了。

题目链接

传送门

题目描述

有$n$名同学要乘坐摆渡车从人大附中前往人民大学，第$i$位同学在第$t_i$ 分钟去 等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、 把车上的同学送到人民大学、再回到人大附中（去接其他同学），这样往返一趟总共花费$m$分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。

凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢？

注意：摆渡车回到人大附中后可以即刻出发。

题目描述

遥远的海中，有着风景秀美的Eolv群岛，岛上的居民们一直以来都在幸福快乐地生活着。可是，地壳运动打破了他们平静的生活——近期，火山觉醒，地震频发。最令居民们绝望的是，他们祖祖辈辈耕耘过的小岛，如今正在沉没。

不能坐以待毙！居民们成立了紧急行动队，测算出了群岛中各个小岛将会沉没的时间。接下来，他们要在小岛之间架设一些桥梁，以满足在特殊时期物资的运输需求。

已经知道，群岛中一共包括N座小岛。居民们以将会沉没的时间为序，从先到后将它们从1到N编号。由于距离和地形的限制，他们只可能在M对小岛间建立桥梁，建立每条桥梁所需代价也不尽相同。一座桥梁连接两个不同的小岛，而其中只要有一座沉没，这条桥梁就将不再被允许通行。

现在，你需要设计一份桥梁的建设方案，保证居民们时时刻刻都可以通过桥梁在任意两个仍未沉没的岛屿间通行，而使建造代价尽可能地小。

题目链接

传送门

题目描述

在小Z的家乡，有机房一条街，街上有很多机房。每个机房里都有一万个人在切题。小Z刚刷完CodeChef，准备出来逛逛。

机房一条街有 n 个机房，第 i 个机房的坐标为 xi ，小Z的家坐标为 0。小Z在街上移动的速度为1，即从 x1 到 x2 所耗费的时间为 |x1 − x2|。 每个机房的学生数量不同，ACM 题目水平也良莠不齐。小Z到达第 i 个机房后，可以花 ti 的时间想题，然后瞬间 AK；当然，也可以过机房而不入。

小Z现在只有 m 个单位时间，之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多少个机房 AK，希望你帮帮他。

题目链接

传送门

题目描述

fox来到了一排葡萄架下,葡萄架上有很多葡萄(n串),它想将一部分葡萄偷走.
每串葡萄都有一个价值,当然,由于有酸有甜,葡萄的价值可能为正,也可能为负.
当然,为了让农夫看不出来,fox规定,每k串葡萄中,它最多选b串,但是由于fox是比较贪心的,每连续k串葡萄中,它会最少选a串
例如n=5 k=3 a=1 b=2时,在第1—第3串葡萄中,fox只能选1或2串,在第2—第4串葡萄中,fox也只能选1或2串.
图1的选法是不合法的,因为2—4中选出了3串葡萄
图2的选法也是不合法的,因为1—3中选出了0串葡萄
而图3的选法是合法的.
现在,fox要选出一些葡萄,而农夫得到剩余的葡萄,由于fox有嫉妒心理,希望让fox得到的价值减去农夫得到的价值的差值最大

题目描述

给定 n 个水晶，第 i 个水晶的高度为 H i 。
现在要求将这些水晶排成一排，要求相邻两个水晶之间的高度差均大于 k，问有多少种排法。

输入格式

第一行两个整数 n,k。
接下来 n 行，每行一个整数，第 i 行的整数表示 $H_i$。

题目描述

不知几千年后，本应死去的遗迹，如今却迎来了客人。

拔起了圣剑的你，为追溯过往，从这里开始了冒险的旅程。进入遗迹后，利用探知术，你得知了遗迹中包括入口处在内共有N个探索点，它们由M条双向通道相连通，通道的长度不尽相同。由于遗迹已在地下尘封多年，通道里都充满着污秽。你需要先净化掉所有的污秽，才能迈出探索的脚步。

从遗迹入口开始，将N个探索点从1到N编号。首先，你可以使用神圣驱魔术，净化以你为中心的一定区域内的所有道路。即，消耗数值为C×X的魔力点（C为常数），选定一个非负整数距离X。对于一条通道，若其两端的探索点与1号探索点间的距离均不大于X，则这条通道将被净化。这里，两探索点i与j间的距离定义为从i到j需经通道的长度之和的最小值。之后，你需要分别净化其余的所有通道，净化一条通道所需消耗魔力点即为这条通道的长度。

请确定净化的方式，使你需要消耗魔力点的数值最小。