AC. 梦想

算法框架目录下的文章

Codeforces 炖题计划

做一波Codeforces的题目涨涨姿势。 744B Hongcow's Game 有一个n \times n的矩阵,A_{i,i} = 0。 现在你有不超过20次的询问机会,询问一个[1, n]的下标集合S,对所有i,返回M_i = \min_{j \in S} {A_{i, j}}。 现在你需要求出对于所有i,求出Q_i = \min_{j \neq i} {A_{i, j}}……
17/02/13 | 暂无评论 | 1,386阅读 阅读详情

AtCoder Grand Contest 选做

昨日晚上一场AGC,令我一度怀疑我是不是根本没有智商。感觉智商被按在地上摩擦…… 于是我来学习一波姿势,看看他究竟是怎么把我智商按在地上摩擦的。 9C Division into Two 给定n个整数a_i。把它们划分到两个集合S_0, S_1,满足S_0集合中任意两个整数差的绝对值不小于A,S_1集合……
17/01/22 | 要查看留言请输入您的密码。 | 1,942阅读 阅读详情

[BZOJ 2784] 时间流逝

题意简述 有n种能量圈,第i种能量是a_i。开始你没有能量圈。对于每一天,你有p的概率失去一个能量最小的能量圈,有1-p的概率可以等概率得到一个能量不大于你现有最小能量圈的能量圈。如果你现在没有能量圈,则不存在概率失去能量圈。 求第一次能量总和超过T的期望天数。 1 \le n……
17/01/22 | 暂无评论 | 1,302阅读 阅读详情

[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 | 暂无评论 | 1,520阅读 阅读详情

[WC 2013] 平面图

题意简述 给定n个点m条边的连通平面图,边有权值。 现在有q个询问。求连接平面上两点的一条曲线,不能经过无穷大区域,且曲线经过边的最大权值尽量小,询问最小值。 保证询问的点不在平面图的点和边上,且询问点的坐标是0.5的奇数倍,平面图点的坐标是0.5的偶数倍。 5 \le n, m ……
16/12/21 | 暂无评论 | 1,664阅读 阅读详情

[NOI 2016] 区间

题目描述 在数轴上有n个闭区间[l_1,r_1],[l_2,r_2],...,[l_n,r_n]。现在要从中选出m个区间,使得这m个区间共同包含至少一个位置。换句话说,就是使得存在一个x,使得对于每一个被选中的区间[l_i,r_i],都有l_i \le x \le r_i。 对于一个合法的选取方案,它的花费为被选中的最长……
16/08/07 | 暂无评论 | 1,250阅读 阅读详情

[NOI 2016] 网格

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

[NOI 2016] 优秀的拆分

题目描述 如果一个字符串可以被拆分为AABB的形式,其中A和B是任意非空字符串,则我们称该字符串的这种拆分是优秀的。 例如,对于字符串aabaabaa,如果令A=aab,B=a,我们就找到了这个字符串拆分成AABB的一种方式。 一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分……
16/08/06 | 暂无评论 | 2,068阅读 阅读详情

[HDU 5306] Gorgeous Sequence

题意简述 维护长度为n的序列a,有m组操作。 1.0 x y t:对于x \le i \le y,令a_i = \min(a_i,t)。 2.1 x y:对于x \le i \le y,求a_i的最大值。 3.2 x y:对于x \le i \le y,求a_i的总和。 1 \le n,m \le 10 ^ 6, 1 \le x \le y \le n, 0 \le a_i,t \lt 2 ^ {31} 题目解析 ……
16/06/03 | 暂无评论 | 3,085阅读 阅读详情

[BZOJ 2956] 模积和

题目描述 求\sum_{i=1}^{n} \sum_{j=1}^{m} {(n \mod i)(m \mod j)[i \neq j]} 输入格式 两个整数n,m。 1 \le n,m \le 10 ^ 9 输出格式 一个整数表示答案\mod 19940417的值。 题目解析 我们先不考虑i = j的情况。由分配律原式可转化为(\sum_{i=1}^{n} {n \mod i})(\sum_{i=1}^{m……
16/06/02 | 暂无评论 | 1,375阅读 阅读详情