[洛谷P2827]蚯蚓

难度:提高+/省选-

题目描述

        本题中,我们将用符号⌊c⌋表示对c向下取整,例如:⌊3.0⌋ = ⌊3.1⌋ = ⌊3.9⌋ = 3。
        蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
        蛐蛐国里现在共有n只蚯蚓(n为正整数)。每只蚯蚓拥有长度,我们设第i只蚯蚓的长度为ai(i=1,2,… ,n),并保证所有的长度都是非负整数(即:可能存在长度为0的蚯蚓)。
        每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数p(是满足0 < p < 1的有理数)决定,设这只蚯蚓长度为x,神刀手会将其切成两只长度分别为⌊px⌋和x - ⌊px⌋的蚯蚓。特殊地,如果这两个数的其中一个等于0,则这个长度为0的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加q(是一个非负整常数)。

阅读全文〉

[TJUOJ]难以置信的竞赛

难度:估计在普及+
        天津大学OJ上的一道题,最早来自The 7th UESTC Programming Contest Preliminary。看rank list发现这道题都做的特别惨烈…一看这题感觉是状压DP,一写果然A了,在这里做一个总结。之后应该还会有类似的情景。
        原题在http://acm.tju.edu.cn/toj/vcontest/showp10518_B.html ,下面是翻译。

阅读全文〉

[洛谷P1514]引水入城

难度:提高+/省选-

题目描述

        在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个N行×M列的矩形,如下图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。

        为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。
        因此,只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。由于第N行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能建有水利设施的城市数目。

阅读全文〉

[洛谷P1312]Mayan游戏

难度:提高+/省选-

题目描述

        Mayan puzzle是最近流行起来的一个游戏。游戏界面是一个7行5列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下:

阅读全文〉

组合方案数问题

        这里介绍组合方案数的求法。
        给定N个正整数和M,用这N个数中的一些数进行求和,使得和为M,问方案数。该问题可以采用动态规划的方法快速求得。

阅读全文〉

字符串哈希

本文改编自https://blog.csdn.net/pengwill97/article/details/80879387


        很多题目涉及字符串问题,但是字符串不如整数那样容易处理,尤其是涉及图时。这时需要构造映射string->int来将字符串转化为int,这就是字符串哈希算法。
阅读全文〉

ST表

        ST表是一种求区间最值的高效数据结构,不支持动态维护,建表时间复杂度O(nlogn),查询复杂度O(1)。在不需要修改原数据的情况下ST表要比线段树更简洁,但在需要修改原数据时只能用线段树。

阅读全文〉