-
[APIO2015]雅加达的摩天楼
题目描述 印尼首都雅加达市有 NN 座摩天楼,它们排列成一条直线,我们从左到右依次将它们编号为 00 到 N − 1 。除了这 NN 座摩天楼外,雅加达市没有其他摩天楼。有 MM 只叫做 “doge” 的神秘生物在雅加达市居住,它们的编号依次是 0 到 M − 1 。编号为 i 的 doge 最初居住于编号为 B[i]的摩天楼。每只 doge 都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为 i 的 doge 的跳跃能力为 P[i]在一次跳跃中,位于摩天楼 bb 而跳跃能力为 pp...…
-
[NOIP2012]开车旅行
题目描述 小 A 和小 B 决定利用假期外出旅行,他们将想去的城市从 1 到 N 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 i 的海拔高度为Hi,城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值,即d[i,j] = abs(Hi− Hj)。 旅行过程中,小 A 和小 B 轮流开车,第一天小 A 开车,之后每天轮换一次。他们计划选择一个城市 S 作为起点,一直向东行驶,并且最多行驶 X 公里就结束旅行。小 A 和...…
-
[NOI2015]品酒大会
题目描述 一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战 两个环节,分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项,吸引了众多品酒师参加。在大会的晚餐上,调酒师 Rainbow 调制了 n 杯鸡尾酒。这 n 杯鸡尾酒排成一行,其中第 n 杯酒 (1 ≤ i ≤ n) 被贴上了一个标签si,每个标签都是 26 个小写 英文字母之一。设 str(l, r)表示第 l 杯酒到第 r 杯酒的 r − l + 1 个标签顺次连接构成的字符串。若 str(p, po) = ...…
-
[CQOI2012]交换棋子
题目描述 有一个n行m列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第i行第j列的格子只能参与mi,j次交换。输入输出格式输入格式: 第一行包含两个整数n,m(1<=n, m<=20)。以下n行为初始状态,每行为一个包含m个字符的01串,其中0表示黑色棋子,1表示白色棋子。以下n行为目标状态,格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串,表示每个格子参与交换的次数上限。输出格式:输出仅一行,为最小交换总...…
-
[ZJOI2011]贪吃的老鼠
题目描述 奶酪店里最近出现了m只老鼠!它们的目标就是把生产出来的所有奶酪都吃掉。奶酪店中一天会生产n块奶酪,其中第i块的大小为pi,会在第ri秒被生产出来,并且必须在第di秒之前将它吃掉。第j只老鼠吃奶酪的速度为sj,因此如果它单独吃完第i快奶酪所需的时间为pi/sj。老鼠们吃奶酪的习惯很独特,具体来说: (1) 在任一时刻,一只老鼠最多可以吃一块奶酪; (2) 在任一时刻,一块奶酪最多被一只老鼠吃。 由于奶酪的保质期常常很短,为了将它们全部吃掉,老鼠们需要使用一种神奇的魔法来延长奶酪的...…
-
遥远的国度
题目描述 zcwwzdjn在追杀十分sb的zhx,而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时,守护神RapiD阻拦了zcwwzdjn的去路,他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。问题是这样的:遥远的国度有n个城市,这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都,我们可以把这个首都看做整棵树的根,但遥远的国度比较奇怪,首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值,有些时候RapiD会使得某两...…
-
[NOI2011]阿狸的打字机
题目背景 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。题目描述 打字机上只有28个按键,分别印有26个小写英文字母和’B’、’P’两个字母。经阿狸研究发现,这个打字机是这样工作的:输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。 按一下印有’B’的按键,打字机凹槽中最后一个字母会消失。 按一下印有’P’的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。 例如,阿狸输入aPaPBbP,纸上被打印的字符如下: ...…
-
[国家集训队]种树
刚看到这题第一反应是DP。。然而瞅了一眼数据范围(emm,200000)发现是一个贪心。。思路非常神奇。。就是以在每个坑种树的收益建一个大根堆然后用链表存它的前驱后继(n的后继为1,1的前驱为n)每次取最大的收益。那么问题来了————有可能在这个点种树比在它两边各种一棵树收益小。但一定是两边各种一棵,因为我们建的是大根堆,先出来的一定大。所以我们可以选这个坑种树,也可以选两边的坑各种一棵,所以我们给我们的贪心一个反悔的机会就是选在这个坑种树以后将它两边的坑合并为一个价值为(w[l]+w[r...…
-
[HEOI2016|TJOI2016]排序
题目描述 在2016年,佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题,需要你来帮助他。这个难题是这样子的:给出一个1到n的全排列,现在对这个全排列序列进行m次局部排序,排序分为两种:1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。输入输出格式输入格式: 输入数据的第一行为两个整数n和m。n表示序列的长度,m表示局部排序的次数。1 <= n, m <...…
-
Hello World!
由于xMinh和Gay神的帮助,我~成功~搞了一个blog然而我太菜并且还很懒导致blog里的题目大家可能早就已经A过辣不过我还是尽量在我的blog里放一些我最近看题解A掉的好题…