标签：《挑战程序设计竞赛(第2版)》

2014-12-12阅读(4988)评论(1)

POJ 3735 Training little cats 调教猫咪：有n只饥渴的猫咪，现有一组羞耻Play，由k个操作组成，全部选自： 1. g i 给第i只猫咪一颗花生 2. e i 让第i只猫咪吃光它的花生 3. s i j 交换猫咪...

2014-11-24阅读(5408)评论(2)

POJ 3420 Quad Tiling 贴瓷砖：4*N的地板上用2*1的瓷砖铺满，求所有方案数对M求余。 3.4熟练掌握动态规划 矩阵的幂 久违地上了节课，太无聊，只好刷一题。 假设S[n]表示填满n时的方案数，有S[0]=1。定义矩阵 ...

2014-10-26阅读(4741)评论(0)

POJ 3411 Paid Roads 开路：N个城市间有m条单向路，分别从a到b，可以在c处交P路费，也可以直接交R路费。那么问题来了，你的挖掘机怎么开最省钱？ 3.4熟练掌握动态规划 状态压缩DP 乍一看可以Dijkstra，实际上的确...

2014-09-28阅读(5043)评论(0)

POJ 1795 DNA Laboratory DNA拼接：弗兰肯斯坦从尸体里提取了一堆DNA碎片，想拼成字典序最小的整体，于是他找了几个实习生，你就是其中一个。 3.4熟练掌握动态规划 状态压缩DP 首先，如果一个字串包含在另一个母串中，...

2014-09-15阅读(4625)评论(0)

POJ 2836 Rectangular Covering 铺地板：坐标平面上有n各点，用任意大小（非零）的地板砖覆盖它们，求最省的地板砖总面积。 3.4熟练掌握动态规划 状态压缩DP 先预处理数据，将n个点两两组合形成n * (n-1) ...

2014-09-14阅读(5890)评论(0)

POJ 3254 Corn Fields 种玉米：农夫约翰有n*m块地，其中一些地荒掉了。玉米是一种傲娇的植物，种在相邻的地里会导致不孕不育。求所有种法数对100000000求余。 3.4熟练掌握动态规划 状态压缩DP 今天换了CLion，...

2014-08-06阅读(5240)评论(0)

POJ 2441 Arrange the Bulls 公牛队：农夫约翰有N支公牛队，分别独占M个球场中的若干个，求分配方案的个数？ 3.4熟练掌握动态规划 状态压缩DP 白天写代码混饭，晚上写代码寻欢。 基本上是个带记忆的枚举，难点在对集合...

2014-08-03阅读(5002)评论(0)

UVa 11990 Inversion 逆序对：从一个长N的序列中逐渐移除M个数，求每次移除前序列的逆序对的个数？ 3.3活用各种数据结构 线段树和平方分割 如果将第i个数映射到点(i,X_i)的话，那么这个点左上和右下的点的个数之和就是逆...

2014-08-03阅读(4963)评论(3)

POJ 1201 Intervals 乞巧：从一系列区间[a_i,b_i]中至少取出c_i个数构成集合s，求s的最小size？ 3.3活用各种数据结构 线段树和平方分割 呵呵，白天睡了一天，晚上吃完翔后怎么也睡不着，爬起来再A一题吧。 这题...

2014-08-02阅读(5123)评论(0)

POJ 3470 Walls 傻鸟：在二维平面上有N堵水平或垂直的墙，放M只傻鸟，每只傻鸟会撞死在最近的那堵墙上。求最后每堵墙上有多少团血肉模糊的尸体！ 3.3活用各种数据结构 线段树和平方分割 中国人出的题目就是这么和谐，不过难度还是有的...