AC. 梦想

标签 BZOJ 下的文章

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

[NOI 2016] 循环之美

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

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

[BZOJ 4771] 七彩树

题意简述 给定一棵n个点的有根树,编号依次为1到n,其中1号点是根节点。 每个节点都被染上了某一种颜色,其中第i个节点的颜色为c_i。如果c_i=c_j,那么我们认为点i和点j拥有相同的颜色。定义depth_i为i节点与根节点的距离,为了方便起见,你可以认为树上相邻的两个点之间的距离……
17/03/11 | 暂无评论 | 671阅读 阅读详情

[ZJOI 2012] 波浪

题意简述 定义一个n元排列P的权值v(P)如下v(P) = \sum_{i=1} ^ {n-1} {|P_i - P_{i+1}|} 求等概率随机一个n元排列求出的权值\ge m的概率。输出保留q位小数。 n \le 100, m \le 2 ^ {31} - 1, q \le 30 算法讨论 感觉如果不卡常数不卡空间不卡精度的话就是一道十分优美的题了! ……
17/03/02 | 暂无评论 | 609阅读 阅读详情

[ZJOI 2013] 丽洁体

题意简述 给定一个串s。 现在你需要删去尽量少的字符,让其可以和模板串a*b*c匹配。 其中a,b,c是三个串,*可以匹配0个或多个字符。 1 \le |s|, |a|, |b|, |c| \le 50000,保证每个字符出现不超过500次。 算法讨论 难得的清真题。 考虑一个暴力。设f(i,j)为考虑到s的第i个字符,……
17/03/01 | 暂无评论 | 432阅读 阅读详情

[ZJOI 2013] 抛硬币

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

[ZJOI 2013] 话旧

题意简述 有一个长度为n+1的序列A_0, A_1, ..., A_n,满足下列条件。 1. A_0 = A_n = 0。 2. 对于0 \le i \le n - 1,|A_i - A_{i+1}| = 1。 3. 对于所有极小值点k,有A_k = 0。 我们还规定了A的m个位置的值。 求满足条件的序列个数 和 序列最大值的最大值。第一问的答案对19940……
17/03/01 | 暂无评论 | 491阅读 阅读详情

[ZJOI 2014] 消棋子

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

[ZJOI 2014] 星系调查

题意简述 给定n点m边的简单无向连通图。每个点对应一个二维平面上的坐标。 有q个询问,每次给定u,v,求u,v所有简单路径中,路径权值的最小值。 路径权值定义为,在所有直线中,到路径上所有点对应的坐标的欧几里得距离的平方和的最小值。 1 \le n, q \le 10 ^ 5, m \le n,权值\……
17/03/01 | 暂无评论 | 458阅读 阅读详情