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$分别表示结点与边...