标签 - BZOJ

? 解题记录 ? ? BZOJ ? ? 斜率优化 ? ? 带权二分 ? ? 动态规划 ?    2018-11-04 16:21:53    721    0    0
【题目描述】 小H最近迷上了一个分隔序列的游戏。在这个游戏里,小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列,小H需要重复k次以下的步骤: 1.小H首先选择一个长度超过1的序列(一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列); 2.选择一个位置,并通过这个位置将这个序列分割成连续的两个非空的新序列。 每次进行上述步骤之后,小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式,使得k轮之后,小H的总得分最大。 【输入】 输入第一行包含两个整数n,k(k+1≤n)。 第二行包含n
? 解题记录 ? ? BZOJ ? ? 费用流 ? ? 网络流 ?    2018-10-01 10:03:10    495    0    0
很套路的一道题,做过无限之环来看这道题还是十分好想的因为我比较菜,考试的时候就没能想出来。按照套路,把格子黑白染色,然后考虑图的特点,到一个地方一定拐弯。并且,对于一条回路来说,正向和反向的贡献都是一样的。接下来,我们指定黑、白格子的流向,考虑一个白格子的流出一定是某个黑格子的流入。那么就好办了,我们规定黑格子横进竖出,白格子横出竖进。这样我们把问题抽象成一张图,对于每一个格子可以选择从进向自己连边,自己向出连边,相当于每种进的方案都可以选择两种出去的方案。但是题目还有一个隐含条件,一个点只能经过一条流量,也就是出入度都是1,想到限制出入度便想到了最小路劲覆盖的模型。于是,初步的构图便完成了。
? 解题记录 ? ? BZOJ ? ? 动态规划 ? ? 组合数 ?    2018-09-25 08:31:27    808    0    0
Description在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建n(n-1)/2条单向道路,对于任意两个不同的点i和 j,在它们之间有且仅有一条单向道路,方向要么是i到j,要么是j到i。换句话说,这是一个n个点的竞赛图。Byte asar居住在1号城市,他希望从1号城市出发,沿着单向道路不重复地访问一些城市,使得访问的城市数尽可能多。 请写一个程序,帮助Byteasar计算有多少种道路修建方式,使得从1号点出发的最长简单路径经过点数恰好为k,由 于答案可能很大,请对P取模输出 Input第一行包含两个正整数n,P,表示点数和模数。 2≤P≤1e9,N<=200
? 解题记录 ? ? BZOJ ? ? Kosaraju ? ? 状态压缩 ? ? 莫队 ?    2018-09-25 08:12:04    869    0    0
Description在Byteland 一共有n 座城市,编号依次为1 到n,这些城市之间通过m 条单向公路连接。对于两座不同的城市a 和 b,如果a 能通过这些单向道路直接或间接到达b,且b 也能如此到达a,那么它们就会被认为是一对友好城市。Byt eland 的交通系统十分特殊,第i 天只有编号在[li, ri] 的单向公路允许通行,请写一个程序,计算每天友好城 市的对数。 注意:(a, b) 与(b, a) 没有区别。   Input第一行包含三个正整数n, m, q,分别表示城市的个数、单向公路的条数以及询问的天数。 接下来m 行,每行两个正整数ui, vi,表示一条从城
? 解题记录 ? ? BZOJ ? ? 并查集 ? ? 线段树 ? ? Kruscal ?    2018-09-25 08:06:17    338    0    0
Description在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建m条双向道路,其中修建第i条道路的费用为ci。B yteasar作为Byteland公路建设项目的总工程师,他决定选定一个区间[l,r],仅使用编号在该区间内的道路。他希 望选择一些道路去修建,使得连通块的个数尽量少,同时,他不喜欢修建多余的道路,因此每个连通块都可以看成 一棵树的结构。为了选出最佳的区间, Byteasar会不断选择 q个区间,请写一个程序,帮助 Byteasar计算每个区 间内修建公路的最小总费用。  Input第一行包含三个正整数n; m; q,表示城市数、道路数和询问数
? 解题记录 ? ? BZOJ ? ? 动态规划 ? ? 组合数 ?    2018-09-25 08:00:44    552    0    0
Description在 Byteland一共开着 n家商店,编号依次为 1到 n,其中编号为1到 m的商店有日消费量上限,第 i家商店的日消 费量上限为wi。Byteasar每次购物的过程是这样的:依次经过每家商店,然后购买非负整数价格的商品,并在结账 的时候在账本上写上在这家商店消费了多少钱。当然,他在这家商店也可以什么都不买,然后在账本上写上一个0 。这一天, Byteasar日常完成了一次购物,但是他不慎遗失了他的账本。他只记得自己这一天一共消费了多少钱 ,请写一个程序,帮助 Byteasar计算有多少种可能的账单。    Input第一行包含三个正整数 
? 解题记录 ? ? BZOJ ? ? FFT|NTT ?    2018-09-20 14:56:12    905    0    0
DescriptionByteasar 组建了一支舰队!他们现在正在海洋上航行着。海洋可以抽象成一张n×m 的网格图,其中有些位置是“ .”,表示这一格是海水,可以通过;有些位置是“#”,表示这一格是礁石,不可以通过;有些位置是“o”,表 示这一格目前有一艘舰,且舰离开这一格之后,这一格将变为“.”。这些“o” 表示Byteasar 的舰队,他们每天 可以往上下左右中的一个方向移动一格,但不能有任何一艘舰驶出地图。特别地,Byteasar 对阵形有所研究,所 以他不希望在航行的过程中改变阵形,即任何时刻任何两艘舰的相对位置都不能发生变化。Byteasar 的舰队可以 航行无限长的时间,每当一艘
? 解题记录 ? ? BZOJ ? ? FFT|NTT ? ? 构造 ?    2018-09-19 08:03:56    641    0    0
【题目描述】兔子们在玩两个串的游戏。给定两个字符串S和T,兔子们想知道T在S中出现了几次,分别在哪些位置出现。注意T中可能有“?”字符,这个字符可以匹配任何字符。 【输入】两行两个字符串,分别代表S和T 【输出】第一行一个正整数k,表示T在S中出现了几次 接下来k行正整数,分别代表T每次在S中出现的开始位置。按照从小到大的顺序输出,S下标从0开始。 【输入样例】bbabaababaaaaabaaaaaaaabaaabbbabaaabbabaabbbbabbbbbbabbaabbbababababbbbbbaaabaaabbbbbaabbbaabbbbabab a?aba?abba 【输出样例】
? 解题记录 ? ? 矩阵树定理 ? ? 高斯消元 ? ? 期望概率 ? ? BZOJ ?    2018-09-13 22:42:02    416    0    0
Description  T国有N个城市,用若干双向道路连接。一对城市之间至多存在一条道路。    在一次洪水之后,一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况,但直到现在几乎没有消息传回。    辛运的是,此前T国政府调查过每条道路的强度,现在他们希望只利用这些信息估计灾情。具体地,给定每条道路在洪水后仍能通行的概率,请计算仍能通行的道路恰有N-1条,且能联通所有城市的概率。 Input  输入的第一行包含整数N。  接下来N行,每行N个实数,第i+l行,列的数G[i][j]表示城市i与j
【题目描述】给定一棵n个点的有根树,编号依次为1到n,其中1号点是根节点。每个节点都被染上了某一种颜色,其中第i个节点的颜色为c[i]。如果c[i]=c[j],那么我们认为点i和点j拥有相同的颜色。定义depth[i]为i节点与根节点的距离,为了方便起见,你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面,你将面临m个问题。 每个问题包含两个整数x和d,表示询问x子树里且depth不超过depth[x]+d的所有点中出现了多少种本质不同的颜色。请写一个程序,快速回答这些询问。 【输入】第一行包含一个正整数T(1<=T<=500),表示测试数据的组数。 每组数据中,第