BZOJ 1054 移动玩具
题意 在4*4的棋盘上，有一个初始的01状态和一个目标的01状态，每次只能将1和相邻的0交换位置，求最小步数达到目标状态。 题解 首先最小方案中每个1移动到目标位置肯定是欧几里得距离。所以我们先预处理所有1走到所有目标位置的欧几里得距离，最后dfs即可。 代码 123456789101112131415161718192021222324252627282930313233343536373839
标签：搜索
BZOJ 1053 反素数
题意 用g(x)表示x的约数个数，定义：若x满足g(x)>g(i){i|0< i< x}，则x被称为反素数。求不超过n的最大反素数。 数据范围 $$1\leq n\leq2000000000$$ 题解 首先明白：一个数约数个数=所有素因子的指数+1的乘积 。然后可以通过计算得:一个2000000000以内的数字不会有超过12个素因子，并且小素因子多一定比大素因子多要优。那么预处理
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