BZOJ 1010 玩具装箱
题意 有n件玩具，玩具长度为ci。连续的玩具可以装进同一容器里，玩具之间要留有1个单位的空间。容器制作费为(X-L)^2，其中X表示容器长度，L表示常量。求最小费用。 数据范围 $$n\leq50000\ \ \ ;\ \ \ L,C_i\leq10^7$$ 题解 动规方程 根据题目描述很容易列出动规方程： 其中 $$s[i]=\sum_{k=1}^{i} c[k]；$$ 而X即为s
分类：BZOJ
BZOJ 1003 物流运输
题意 一批货物从1码头运送到m码头，许n天运完。运输过程中要转停好几个码头。某些天某码头无法转停，此时可以改变运输路线。每次改变路线要花费K代价。从i码头运送到j码头要花费C[i,j]的代价。求运输总代价最小。 数据范围 $$n\leq100\ \ \ ;\ \ \ m\leq20$$ 题解 先预处理出cost[i][j]表示从第i天到第j天航行路线不变时的最小代价，其实就是求最短路。因为n特别小
BZOJ 1002 轮状病毒
题意 给定n(N<=100)，编程计算有多少个不同的n轮状病毒。 题解 基尔霍夫矩阵（什么鬼），f[i]=(f[i-1]*3-f[i-2]+2)；f[1]=1,f[2]=5。剩下的就是高精度了。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<cstdio
半平面交（三弹连发）
半平面交基本概念 半平面：由不等式ax+by+c>=0确定。 在一个有界区域里半平面或半平面的交是一个凸多边形区域。 n个半平面的交是一个至多n条边的凸多边形。BZOJ 1007 水平可见直线 题意 平面直角坐标系上，有n条直线，从y为正无穷处往下看。问能看看到哪些直线？数据范围 $$n\leq50000$$题解 当一条直线不是最后半平面交的组成部分，仅当它被与它斜率相同的直线挡住，或被
BZOJ 1054 移动玩具
题意 在4*4的棋盘上，有一个初始的01状态和一个目标的01状态，每次只能将1和相邻的0交换位置，求最小步数达到目标状态。 题解 首先最小方案中每个1移动到目标位置肯定是欧几里得距离。所以我们先预处理所有1走到所有目标位置的欧几里得距离，最后dfs即可。 代码 123456789101112131415161718192021222324252627282930313233343536373839
BZOJ 2748 音量调节
题意 吉他有一个初始音量，吉他手每弹奏一首歌曲，都要将音量改变ci，可加可减，但音量不能小于0，也不能高于max。求最后一首歌曲音量最大值。无解（无法避免音量超出范围）输出-1。 数据范围 $$歌曲数n\leq50\ \ \ ;\ \ \ ci\leq max\ \ \ ;\ \ \ 初始值begin,max\leq1000$$ 题解 数据如此之小……v[i][j]表示第i首歌时音量j是否能达到，
BZOJ 1053 反素数
题意 用g(x)表示x的约数个数，定义：若x满足g(x)>g(i){i|0< i< x}，则x被称为反素数。求不超过n的最大反素数。 数据范围 $$1\leq n\leq2000000000$$ 题解 首先明白：一个数约数个数=所有素因子的指数+1的乘积 。然后可以通过计算得:一个2000000000以内的数字不会有超过12个素因子，并且小素因子多一定比大素因子多要优。那么预处理
BZOJ 1006 神奇的国度
题意 保证大于3人的朋友关系一定会出现弦边（即连接环上不相邻的两个点）。在分组时要求朋友关系的两人不能分在同一组，求最少分几组。 数据范围 $$人数n\leq10000\ \ \ ;\ \ \ 朋友对数m\leq1000000$$ 题解 环上有弦被称为弦图，那这道题就是在弦图上做最小染色（即相邻的点不能染同一种颜色），需要用到完美消除序列的最大势算法(MCS)。最大势算法是排序时每次找势能最大的点
BZOJ 1854 游戏
题意 一个武器有两种属性，属性由一个[1…10000]之间的整数表示。现从属性1 向上依次递增，共n武器，每个武器只能有一次，求最多能到多少属性。 数据范围 $$n\leq1000000$$ 题解 做法一将武器和属性都看成点，并从属性向对应武器连边，这样就构成二分图，跑匈牙利。直到某一属性无法找到路径就跳出。但由于匈牙利算法复杂度是n^3，所以无法得满分。 做法二满分算法是并查集。将武器看成边，
BZOJ 1024 生日快乐
题意 将X*Y的矩形蛋糕平均切成n份，每次只能平行于蛋糕一边切，求蛋糕的长边比短边的最大值最小是多少。 数据范围 $$1\leq X,Y\leq10000\ \ \ ;\ \ \ n\leq10$$ 题解 暴搜，枚举切点，假设平行于长切一刀，使整块蛋糕分成i人份和n-i人份，那么切点一定是 X/n*i，因为每人分得蛋糕面积为(X*Y)/n，i人份要求总面积为(X*Y)/n*i。 代码 123456