AC. 梦想

算法框架目录下的文章

[CQOI 2017] 小Q的表格

题意简述 有一个表格,表格有无穷多行,无穷多列,行和列都从1开始标号。 表格里面每个格子都填了一个整数,第a行第b列的整数记为f(a,b)。 这个表格要满足一些条件: 1. 对任意的正整数a,b,都要满足f(a,b)=f(b,a); 2. 对任意的正整数a,b,都要满足b \times f(a,a+b)=(a+b) \tim……
17/05/03 | 暂无评论 | 560阅读 阅读详情

[CTSC 2016] 时空旅行

题意简述 有n个时空,第i个时空继承于第f_i个时空,并在此基础上加入或删除了某一个星球。 星球以三维坐标(x_i,y_i,z_i)表示,且每个星球有一个参数c_i。 有q个询问。每次选定一个时空s和一个平面x = x_0。求从该平面出发可到达的花费最小的星球。 到一个星球i的花费为(x_0 - x_……
17/04/24 | 暂无评论 | 504阅读 阅读详情

[APIO 2014] Beads and wires

题意简述 有n个点。现在你可以选择一个点x开始,执行若干操作。 1. 选择一个未被加入的点x和一个已经加入的点y,在x,y之间连一条红边。 2. 选择一个未被加入的点x和两个连有红边的点y, z,删去y, z之间的红边,并在x, y和x, z之间分别连一条蓝边。 现在给你一棵带边权的树,作为……
17/04/16 | 暂无评论 | 635阅读 阅读详情

[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阅读 阅读详情

[APIO 2015] Jakarta Skyscrapers

题意简述 有n个点和m只doge。 第i只doge在x_i位置,跳跃能力为v_i。 设在某时刻,第i只doge在点p,它能够 1. 跳到p - v_i或p + v_i(若存在)。 2. 把携带的消息告诉在这个点的doge。 现在第0只doge有一条消息,求所有doge总共最少跳跃多少步能够将消息传达到第1只doge呢? 1 \l……
17/04/16 | 暂无评论 | 373阅读 阅读详情

[UOJ 52] 元旦激光炮

题意简述 交互题。 交互库有三个数组a,b,c,长度为n_a, n_b, n_c。数组元素均是单调不降的。 你可以指定一个下标p,询问a_p或b_p或c_p。如果不存在返回2 ^ {31} - 1。 求在100次询问内确定三个数组合并后第k小的元素。 0 \le n_a, n_b, n_c \le 10 ^ 5, 1 \le k \le n_a + n_b +……
17/04/14 | 暂无评论 | 176阅读 阅读详情

[UOJ 218] 火车管理

题意简述 有n个栈,编号为1到n。有m个操作,如下三种: 1 l r : 计算第l到第r个栈的栈顶元素之和。 2 l : 第l个栈弹出栈顶元素,如果不存在则不执行。 3 l r x : 第l到第r个栈都把x压栈。 强制在线。 1 \le n, m \le 5 \times 10 ^ 5, 1 \le x \le 10 ^ 3 算法讨论 一开始一直在……
17/04/14 | 暂无评论 | 281阅读 阅读详情

[NOI 2016] 循环之美

题目描述 牛牛是一个热爱算法设计的高中生。在他设计的算法中,常常会使用带小数的数进行计算。牛牛认为,如果在k进制下,一个数的小数部分是纯循环的,那么它就是美的。 现在,牛牛想知道:对于已知的十进制数n和m,在k进制下,有多少个数值上互不相等的纯循环小数,可以用分数……
17/04/14 | 暂无评论 | 770阅读 阅读详情

[BZOJ 2874] 训练士兵

题意简述 有一个n \times m的矩阵A,初始值均为0。 要求先进行k次修改操作,再回答q个询问。 修改操作选定一个子矩阵加上一个数。询问操作要求回答一个子矩形的和。 答案保证不超过2 ^ {64}。询问强制在线。 1 \le n, m \le 10 ^ 8, 1 \le t \le 40000, 1 \le q \le 100000 算法……
17/03/29 | 暂无评论 | 318阅读 阅读详情

[ZJOI 2017] 树状数组

题意简述 有一个人在写树状数组题,模2意义。 题目需要支持单点加,求区间和。 写的时候把所有x的变化方向都写反了。 现在你需要执行两种操作: 1 l r : 在[l, r]中等概率随机一点x执行单点加。 2 l r : 询问在此时调用错误的代码求答案有多大的概率出错。 输出概率时要求对9982……
17/03/25 | 暂无评论 | 686阅读 阅读详情