AC. 梦想

基础目录下的文章

[APIO 2015] Palembang Bridges

题意简述 城市中有一条河,河两岸A,B分别有10 ^ 9 + 1个建筑。 我们沿某方向把两岸的建筑分别编号为0到10 ^ 9。相邻建筑距离为1,两岸编号相同的建筑相对,距离为1。 现在有n条路径,第i条路径从P_i岸建筑S_i到Q_i岸建筑T_i。 由于需要过河,我们需要在河流上建桥。具体地,你每……
17/04/16 | 暂无评论 | 389阅读 阅读详情

[ZJOI 2013] 抛硬币

题意简述 有一枚硬币,抛出正面的概率是\frac{a} {b},反面的概率就是1 - \frac{a} {b}。 现在给定一个硬币序列S(正面/反面)。现在开始连续抛硬币,当某一枚硬币抛完后,若S作为一段连续子序列出现在了抛出的硬币序列中,则停止。 求到停止的期望步数。输出一个最简分数。 1 \……
17/03/01 | 暂无评论 | 582阅读 阅读详情

[ZJOI 2014] 消棋子

题意简述 有一个r \times c的棋盘和n种颜色的棋子,每种颜色各两枚。 棋盘中一个格子可能为空,也可能有恰好一枚棋子。 你可以执行一种消棋子的操作:选定一个空格子和两个平行于坐标轴的方向,如果这个格子在这两个方向上第一个遇到的棋子是同种颜色的棋子,则这两个棋子可以同……
17/03/01 | 暂无评论 | 364阅读 阅读详情

[BZOJ 4311] 向量

题意简述 维护一个向量集合,支持以下操作: 1. 插入一个向量(x,y)。 2. 删除插入的第i个向量。 3. 查询当前集合与(x,y)点积的最大值是多少。如果当前是空集输出0。 1 \le n \le 200000, 1 \le x,y \le 10^6 算法讨论 考虑每一个向量,如果在时间轴上看,存在时间都对应一段区……
17/01/22 | 暂无评论 | 532阅读 阅读详情

[NOI 2016] 网格

题目描述 跳蚤国王和蛐蛐国王在玩一个游戏。 他们在一个n行m列的网格上排兵布阵。其中的c个格子中(0 \le c \le nm),每个格子有一只蛐蛐,其余的格子中,每个格子有一只跳蚤。 我们称占据的格子有公共边的两只跳蚤是相邻的。 我们称两只跳蚤是连通的,当且仅当这两只跳蚤相邻,……
16/08/06 | 暂无评论 | 1,231阅读 阅读详情

[HNOI 2015] 菜肴制作

题目描述 知名美食家小A被邀请至ATM大酒店,为其品评菜肴。 ATM酒店为小A准备了n道菜肴,酒店按照为菜肴预估的质量从高到低给予1到n的顺序编号,预估质量最高的菜肴编号为1。由于菜肴之间口味搭配的问题,某些菜肴必须在另一些菜肴之前制作,具体的,一共有m条形如“i号菜肴必须……
16/06/02 | 暂无评论 | 468阅读 阅读详情

[NOI 2015] 荷马史诗

题目描述 追逐影子的人,自己就是影子。 ——荷马 Allison 最近迷上了文学。她喜欢在一个慵懒的午后,细细地品上一杯卡布奇诺,静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了,Allison 想通过一种编码方式使得它变……
16/05/12 | 暂无评论 | 571阅读 阅读详情

[ZJOI 2014] 璀璨光华

题目描述 金先生有一个女朋友——没名字。她勤劳勇敢、智慧善良。金先生很喜欢她。为此,金先生用a ^ 3块1 \times 1 \times 1的独特的水晶制作了一个边长为a的水晶立方体。他要将这个水晶立方体送给他见过最单纯善良的她。 由于水晶立方体太大,不好运送,金先生还是将它拆开来送……
16/04/10 | 暂无评论 | 876阅读 阅读详情

线性排序小技巧

在回老家的路上,关于排序这个问题突然想到一个有趣的做法。 先来看一道入门题: 给定长度为n的整数数组A,将元素从小到大排序。1 \le n \le 10 ^ 6,0 \le A_i \le 10 ^ 6,时限1s。 非常简单,由于数据范围较小,直接桶排即可。 再来看一道加强版: 给定长度为n的整数数组A,将……
16/02/07 | 暂无评论 | 1,338阅读 阅读详情

[NOI 2014] 随机数生成器

题目描述 小H最近在研究随机算法。随机算法往往需要通过调用随机数生成函数(例如Pascal中的random和C/C++中的rand)来获得随机性。事实上,随机数生成函数也并不是真正的“随机”,其一般都是利用某个算法计算得来的。 比如,下面这个二次多项式递推算法就是一个常用算法: 算法……
16/01/19 | 暂无评论 | 731阅读 阅读详情