Loading...
310-02-ACOJ-1873-限制数字 题目描述: 一个长度为n的大数,用$S_1,..S_n$表示,其中$S\_i$表示数的第i位,$S_1$是数的最高位。 现告诉你一些限制条件,每个条件表示为四个数,$l_1,r_1,l_2,r_2$,即两个长度相同的区间,表示子串$S_{l_1} … S_{r_1}$与$S_{l_2} … S_{r_2}$完全相同。 给定限制条件后,问满足以上所有...
310-01-ACOJ-0864 : 奶牛赛跑 题目大意: 有$n$头奶牛,在一个圆形的赛跑场地里赛跑。所有奶牛同时从起点出发,奶牛的速度都是匀速的,其中第$i$头牛的速度为$v_i$,跑道的长度为单位$1$。当跑得最快那头奶牛跑完$k$圈之后,比赛就结束了。 有时候,跑得快的奶牛可以比跑得慢的奶牛多绕赛场几圈,从而在一些时刻超过慢的奶牛。这就是最令观众激动的套圈事件了。请问在整个比赛过程中...
310-01-ACOJ-0488-统计节点 题目大意: 给定一棵有$n$个结点的树,给定树上$m$个点,称作标兵,再给定一个距离范围$k$。求树上有多少点,其本身不是标兵,且到每个标兵的距离都不超过$k$。每条边的长度固定为$1$。 题解: 对于这道题,要统计距离所有标兵的距离都不超过$k$的个数。换言之,就是统计节点,对于每一个满足要求的节点,要有其距离最远的标兵的距离不超过$k$。 有了...
307-15-背包的二进制优化 P2851 [USACO06DEC]最少的硬币The Fewest Coins 题目描述 Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that t...
307-13-14-子集枚举DP P3959 宝藏 题目描述 参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了$n$个深埋在地下的宝藏屋, 也给出了这$n$个宝藏屋之间可供开发的$m$条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是,每个宝藏屋距离地面都很远, 也就是说,从地面打通一条到某个宝藏屋的道路是很困难的,而开发宝藏屋之间的道路 则相对容易很多。 小明的决心感动了...
307-09-10矩阵乘法与快速幂 矩阵乘法 定义矩阵$A$,$B$,其中$A$的大小为$a \times b$,$B$的大小为$b \times c$,对于矩阵$C=AB$中的每一个元素$C(i.j),~i\in [1, a],~j\in [1,c]$,存在以下:
307-07-逐行递推 逐行递推:$dp$在某种情况下按照一行一行的顺序进行递推。 P2704 [NOI2001]炮兵阵地 题目描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图...
307-06-期望$dp$ 概述 做一件事情成功:$p$,失败:$\overline{p} = 1-p$。 和性:$E[x+y] = E[x] + E[y]$ 期望的意义就是对于做一件事情,期望多少次这件事情可以做成功。 P1291 [SHOI2002]百事世界杯之旅 题目描述 “……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字,就可参加...
307-05-直径 直径的性质 任意两条直径必定相交 所有直径必交于一点 找直径 任意一个点出发,找出最远点,从最远点,在找到最远点,连起来就是直径(两次$dfs$)。证明从略(反证法)。 P1099 树网的核 题目描述 设$T=(V,E,W)$是一个无圈且连通的无向图(也称为无根树),每条边到有正整数的权,我们称$T$为树网(treebetwork),其中$V$,$E$分别表示结点与边...