POJ解题报告 - 随笔分类 - 小優YoU - 博客园
ACMer与Coder的交流分享地
随笔分类 - POJ解题报告
北大POJ解题报告，全是我亲手所写，仅供与所有ACMer交流分享，未经允许请勿擅自用于个人盈利用途（包括网络虚拟积分、虚拟币、实际货币交易等在内的一切商业行为）
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6799170大致题意：有一面墙，被等分为1QW份，一份的宽度为一个单位宽度。现在往墙上贴N张海报，每张海报的宽度是任意的，但是必定是单位宽度的整数倍，且&=1QW。后贴的海报若与先贴的海报有交集，后贴的海报必定会全部或局部覆盖先贴的海报。现在给出每张海报所贴的位置（左端位置和右端位置），问张贴完N张海报后，还能看见多少张海报？（PS：看见一部分也算看到。）解题思路：水题，区间压缩映射（离散化）+ 线段树首先建立模型：给定一条数轴，长度为1QW，然后在数轴上的某些区
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6784658大致题意：火星人侵略地球，他们意图登陆破坏某个地区的兵器工厂。据探子回报，火星人登陆的地区为n*m大小的地域，而且每一个火星人的着陆点坐标已知。火星人很强悍，只要有一个火星人着陆后能够幸存，他必定能毁坏这片区域的全部兵工厂。为了防止这种情况发生，必须保证在火星人着陆的一瞬间把他们全部同时杀死。现在防卫队有一个激光枪，开一枪就能把 在同一行（或同一列）着陆的火星人全部杀死。但是这种激光枪的使用是有代价的，把这种激光枪安装到不同行的行首、或者不同列的列首，费用都
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6764104大致题意：有N只奶牛，其中奶牛A认为奶牛B备受注目，而奶牛B也可能认为奶牛C备受注目。奶牛们的这种“认为”是单向可传递的，就是说若奶牛A认为奶牛B备受注目，但奶牛B不一定会认为奶牛A备受注目。而当A认为B备受注目，且B认为C备受注目时，A一定也认为C备受注目。 现在给出M对这样的“认为...备受注目”的关系对，问有多少只奶牛被除其本身以外的所有奶牛关注。解题思路：极大强连通分量+缩点。发现自从用Tarjan算法做了POJ2942之后，这些利用Tarjan算法
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6762432大致题意： 为了保护放牧环境，避免牲畜过度啃咬同一个地方的草皮，牧场主决定利用不断迁移牲畜进行喂养的方法去保护牧草。然而牲畜在迁移过程中也会啃食路上的牧草，所以如果每次迁移都用同一条道路，那么该条道路同样会被啃咬过度而遭受破坏。 现在牧场主拥有F个农场，已知这些农场至少有一条路径连接起来（不一定是直接相连），但从某些农场去另外一些农场，至少有一条路可通行。为了保护道路上的牧草，农场主希望再建造若干条道路，使得每次迁移牲畜时，至少有2种迁移途径，避免重复走上次
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6756821大致题意：亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求：1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置；2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。 现在给定准备去开会的骑士数n，再给出m对憎恨对（表示某2个骑士之间使互相憎恨
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6752662大致题意：给定一个连通网络，网络的结点数&=1000，求出这个网络的所有割点编号，并求出若删去其中一个割点k后，对应的，原网络会被分割为多少个连通分量？解题思路：首先要明白什么是割点，什么是连通分量。离散数学的知识。1、【割点】在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。当割点集合的顶点个数只有1个时，该顶点就是割点。2、【连通分量】当删除某个割点后，原图会
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6746954大致题意： 首先说明，下面所述的“大致题意”并不是题目的原意，但是按照题目原意去做是不可能AC的，因为测试数据库与题目原意出入非常大。另外顺便建议，刚玩POJ的同学没事不要做这题，因为如果没有测试数据库你会疯掉的，有测试数据库也很容易疯掉的。 有两种类型的字符串，分别为Contraction和Acronym，它们都有其扩展形式Expand。现在给出C个Contraction和A个Acronym的扩展形式，格式如下：&contraction or a
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6742534大致题意： 有N个供应商，M个店主，K种物品。每个供应商对每种物品的的供应量已知，每个店主对每种物品的需求量的已知，从不同的供应商运送不同的货物到不同的店主手上需要不同的花费，又已知从供应商Mj送第kind种货物的单位数量到店主Ni手上所需的单位花费。问：供应是否满足需求？如果满足，最小运费是多少？解题思路：费用流问题。（1）输入格式在说解题思路之前，首先说说输入格式，因为本题的输入格式和解题时所构造的图的方向不一致，必须要提及注意。以样例1为例：（2）题目
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6732762大致题意：给定一个N*M的地图，地图上有若干个man和house，且man与house的数量一致。man每移动一格需花费$1（即单位费用=单位距离），一间house只能入住一个man。现在要求所有的man都入住house，求最小费用。解题思路：费用流问题。构图： 把man作为一个顶点集合U，house作为另一个顶点集合V，把U中所有点到V中所有点连线，费用cost[u][v]为abs(△x)+abs(△y)，反向弧费用cost[v][u]= -cost[u]
摘要: 载请注明出处：優YoU http://blog.csdn.net/lyy/article/details/6727035大致题意：墙上有一面黑板，现划分为多个矩形，每个矩形都要涂上一种预设颜色C。由于涂色时，颜料会向下流，为了避免处于下方的矩形的颜色与上方流下来的颜料发生混合，要求在对矩形i着色时，处于矩形i上方直接相邻位置的全部矩形都必须已填涂颜色。在填涂颜色a时，若预设颜色为a的矩形均已着色，或暂时不符合着色要求，则更换新刷子，填涂颜色b。注意：1、 当对矩形i涂色后，发现矩形i下方的矩形j的预设颜色与矩形i一致，且矩形j上方的全部矩形均已涂色，那么j符合填涂条件，可以用
摘要: 转载请注明出处：優YoU http://blog.csdn.net/lyy/article/details/6698787大致题意：给出2个整数n（n&10^100）和k（k&10000），求满足以下条件的整数m1、m与n位数相同2、m能被k整除3、满足以上两点时，m和n在相同位置的地方，数字不同的个数最少4、满足以上三点时，m值最小解题思路：这题解法很多，有人用DP，有人用记忆化搜索，有人搜索+强剪枝。POJ分类把这题归入“记忆化搜索”，但是我不推荐，原因在于直接写出记忆化搜索算法去解题不容易，不先用DP做出来，记忆化搜索很难实现。我用的是DFS+强剪枝。我做这
摘要: 转载请注明出处：優YoU http://blog.csdn.net/lyy/article/details/6692382大致题意：给定一个图，图中每条路都有 路长Length 和 过路费Toll 两个参数，一条路连接两个城市，任意两个城市之间有且仅有一条路。现在只有 K 块钱，要求从起点City1出发，到达终点CityN的最短路，也就是说在 K 花费内的最短路。解题思路：这个题其实有很多种解法的，只不过是题目描述用的模型是最短路的模型，其实方法多种多样，Discuss里有同学用dijkstra+A*，也有人用BFS+优先队列，也有人用直接用STL的priotrity_que
摘要: 本文部分链接可能已失效测试数据仅供参考学习之用希望各位同学不要用来刷题====================================１、USACO2006年November题目和测试数据的网址/NOV062007年open赛题目和测试数据的网址/OPEN07以此类推２、日本ACM比赛http://www.acm-japan.org/http://icpc2010.honiden.nii.ac.jp/en/past-contests３、官方网站02年网址http://icpc.baylor.edu/past
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6689310大致题意：有n座城市和m（1&=n，m&=10）条路。现在要从城市1到城市n。有些路是要收费的，从a城市到b城市，如果之前到过c城市，那么只要付P的钱，如果没有去过就付R的钱。求的是最少要花多少钱。注意：路径是有向的。解题思路：DFS。这题当有了思路后，做起来是没有难度的，但是思维推算能力要求很高。这题难点在于“城市与城市之间可能存在多条路径”：1、 输入数据时可能会出现多条 从城市a到城市b的路径信息，但是费用有所差别；2、 对于 从城市a到城
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6683250大致题意：有一块边长为BoxSize的正方形的大蛋糕，现在给出n块不同尺寸的正方形的小蛋糕的边长，问是否能把大蛋糕按恰好切割为这n块小蛋糕，要求每块小蛋糕必须为整块。解题思路：有技巧的DFS可以把大蛋糕想象为一个蛋糕盒子，然后往里面装小蛋糕。装蛋糕时遵循以下原则：自下而上，自左至右；即先装好盒子底部，再继续往上层装，且装每一层时都靠左边放蛋糕；大蛋糕优先装，因为小蛋糕灵活度比较高。只要把问题变换为上述问题，我想对深搜比较熟悉的同学也会马上得到思路了，这个只是
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6676781大致题意：某公司要建立一套通信系统，该通信系统需要n种设备，而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产，而每个厂家生产的同种设备都会存在两个方面的差别：带宽bandwidths 和 价格prices。现在每种设备都各需要1个，考虑到性价比问题，要求所挑选出来的n件设备，要使得B/P最大。其中B为这n件设备的带宽的最小值，P为这n件设备的总价。解题思路：首先需要明确，要使得B/P最大，自然是要令B尽可能大，P尽可能小。由于B和P是两个相互
摘要: 转载请注明出处：優YoU http://blog.csdn.net/lyy/article/details/6674366大致题意：一个工厂制造的产品形状都是长方体盒子，它们的高度都是 h，长和宽都相等，一共有六个型号，分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体箱子包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的箱子数量BoxNum。解题思路：由于盒子和箱子的高均为h，因此只需考虑底面积的空间。6*6的盒子，每个盒子独占一个箱子。5*5的盒子，每个盒子放入一个箱子，该箱子的剩余空间允许放
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6673675大致题意：题意不难懂，对于任意的数字串n，都可以压缩存储为c1 d1 c2 d2 .... ck dk 形式的数字串而存在一些特别的数字串，其压缩前后的样子是一模一样的定义这种数字串为self-inventorying当我们把n看成原串，A为n压缩1次后的数字串，B为n压缩2次后的数字串（即A压缩1次后的数字串）....以此类推K为n压缩k次后的数字串（即K-1压缩k-1次后的数字串）则可以延伸出数字串n的3种属性：1、 n压缩1次就马上出现self-inv
摘要: 转载请注明出处：優YoUhttp://blog.csdn.net/lyy/article/details/6671105大致题意：在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n 个人作为陪审团的候选人，然后再从这n 个人中选m 人组成陪审团。选m 人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0 到20。为了公平起见，法官选出陪审团的原则是：选出的m 个人，必须满足辩方总分D和控方总分P的差的绝对值|D-P|最小。如果有多种选择方案的 |D-P| 值相同，那么选辩控双方总分之和D+P最大的方案即可。输
摘要: 转载请注明出处：優YoU http://blog.csdn.net/lyy/article/details/6661449大致题意：有分别价值为1,2,3,4,5,6的6种物品，输入6个数字，表示相应价值的物品的数量，问一下能不能将物品分成两份，是两份的总价值相等，其中一个物品不能切开，只能分给其中的某一方，当输入六个0是（即没有物品了），这程序结束，总物品的总个数不超过20000输出：每个测试用例占三行： 第一行： Collection #k: k为第几组测试用例 第二行：是否能分（具体形式见用例） 第三行：空白（必须注意，否则PE）解题思路：有两种解决方法：第一种是几乎百
摘要: 转载请注明出处：優YoU http://blog.csdn.net/lyy/article/details/6661421大致题意：有一打（12枚）硬币，其中有且仅有1枚假币，11枚真币用A~L作为各个硬币的代号假币可能比真币略轻，也可能略重现在利用天枰，根据Input输入的3次称量，找出假币，并输出假币是轻还是重。解题思路：模拟法要考虑的情况较繁琐，可利用简单的逻辑推理进行解题。注意Input一行代表一次称量，每行有三个字符串，分别为Left right status代表该次称量时，天枰左盘放的硬币、天枰右盘放的硬币、天枰右盘的状态共三种状态：Up：右盘上升，说明右盘可能有
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：l 通过给定的六种操作将一个六位数变为另一个六位数，求需要的最少操作数。l 六种操作：l 左移和右移：将光标位置左移一位或右移一位，在第一位时无法左移，最后一位时无法右移。l 左交换和右交换：将光标位置的数字与第一位或最后一位交换l 增大或减小：将光标位置的数字增大或减小1解题思路：BFS+状态压缩初步想法l 很难找到有效的贪心算法l 没有明显的局部最优特性，无法动态规划l 考虑搜索直观的想法l 直接进行搜索，从初态开始，知道找到末态的最优解为止。l 无论空间，
摘要: 转载请注明出处：優YoU http://user.//blog/题目大意：给出M个表达式，判断这些信息是否可靠。解题思路：差分约束+Bellman-Ford（建议用优化的Bellman-Ford）设dist[i]为超级源点到i点的距离，则建立&=的差分系统：由于P A B X 指“确定A到B的距离（边权）为X”从P A B X得到的差分系统为dist[A] - dist[B] &= X && dist[A] - dist[B] &= X 等价于dist[B] &= dist[A] - X &a
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：给出数轴上的n个区间[ai，bi]，每个区间都是连续的int区间。现在要在数轴上任意取一堆元素，构成一个元素集合V要求每个区间[ai，bi]和元素集合V的交集至少有ci不同的元素求集合V最小的元素个数。解题思路：POJ1716的升级版，只是边权不是固定，而是变化的而已其实只要把POJ1716的 范围 和“固定边权2”改为ci 就能直接AC了注意本题只能用差分约束+Relax解决，不能像POJ1716那样用贪心。POJ1716：http://user.qzone.
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：给出数轴上的n个区间，每个区间都是连续的int区间。现在要在数轴上任意取一堆元素，构成一个元素集合V要求每个区间和元素集合V的交集至少有两个不同的元素求集合V最小的元素个数。解题思路：一、贪心算法先对所有区间按末端点排序取第i个区间的最后两个元素Selem和Eelem若第i+1个区间包含了这两个元素，则跳到下一个区间所取的元素个数+0若第i+1个区间只包含了这两个元素中的一个（由于有序，所以必定是包含Eelem），则取第i+1个区间的最后一个元素，所取的元素个数
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：某种卫星使用一种叫做“run length encoding”的方式来储存大尺寸图片，有一种简单的 edge detection 算法 是将 图像中的每一个点的值与他周围的八个点相减，然后记录下绝对值最大的，上面的右图是左图经过这种算法转换之后的结果。现在你的任务就是实现这个算法，输入的图片是以 run length encoding 的形式表示的，同时也要求转换后的图片也以 run length encoding 的形式表示。解题思路：非常令人纠结的模拟题，
摘要: 转载请注明出处：優YoU http://user.//blog/­­大致题意：­一种类似围棋的游戏，有黑白两种颜色的棋子。­规定黑棋为先手，白棋为后手。­放下棋子A后，若A的8个马步方位（即中国象棋的“马”或国际象棋的“骑士”的“日”字走法）至少存在1个同色的棋子，且当连接A与这些棋子时，其连线不切割已经有的线，则连接。­黑棋的目标是连出一条从X轴的0列到N列的路；­白棋的目标是连出一条从Y轴的0行到N行的路。­就是说某一方要赢棋，当且仅当其把自己的两个
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：在一个固定大小为10x15的矩形区域A内被RGB三种颜色的小球填满现在按如下步骤操作：1、 删除区域A内最大的一片区域M（任意颜色都可以，只要其占有区域最大）2、 删除M后，自然会出现空的位置，在M区域上方的小球自然下落；当删除M后出现空列时，右边的列往左填充。注意是以“列”为单位填充，非空列只能整列往空列移动。移动后，各个小球之间的相对顺序 与 移动前一样。3、 当区域A剩余小球数为0，或A内的最大区域为1时，游戏结束。否则返回1。输出每一步的得分，最后输出
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：给出一篇规范的文章，求其 句子数、单词数 和 音节数把这3个值代入题目给出的公式，输出其结果，保留2位小数。PS：“规范”即文章没有错误的标点符号，字母在适当的位置有大小写。解题思路：我做了整整5天的BT题,，就是被标点符号害的！！！别听信网上谗言，我个人总结出这题的标点符号只有6个！！！注：下面的分隔符不包括 括号（），所有分隔符均为 英式标点符号标记单词分隔符： 逗号（,） 和 空格（ ）句子分隔符：句号（.） 问号（?） 冒号（:） 分号（;） 感叹号（!
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给出一段Pascial程序，计算其时间复杂度（能计算的项则计算，不能计算则化到最简的关于n的表达式O(n)，并把各项根据n的指数从高到低排列），输出时，系数为0的项不输出，系数为1的项不输出系数，指数为1的项不输出指数。一段程序只有唯一一个BEGIN，代表程序的开始。与其对应的为最后的END，代表程序的结束。一段程序最多只有10层循环嵌套，循环的入口为LOOP，一个LOOP对应一个END，代表该层循环的结束。一段程序中OP的个数不限。LOOP是循环的入口，其后
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意:科普文一篇，文章80%都是无用信息，因为都是常识，但是又不得不看，因为有20%是常人不知道的历史常识。定义：Goog month ： 该月第一个工作日为星期一的月份Luckly month： 该月最后一个工作日为星期五的月份问： 给定一个Gregorian Calendar格里高公历的 时间闭区间（就是包括端点的年月了） 【开始年、月】~【结束年、月】 在这个时间区间内，有多少个Goog month，有多少个Luckly month文章要点：Gregorian
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给定一个字符串，从任意位置把它切为两半，得到两条子串定义 子串1为s1，子串2为s2，子串1的反串为s3，子串2的反串为s4现在从s1 s2 s3 s4中任意取出两个串组合，问有多少种不同的组合方法规定：（1） 串Si不能和其 反串 组合（2） Si+Sj 与 Sj+Si 是两种组合方式（但未必是不同的组合方式）解题思路：利用hash表查重穷举全部组合的情况，每枚举一个就记录一次，假如后面枚举的组合已经存在记录，说明组合重复，计数器不变，否则计数器+1本题不能
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：定义D-pairs表示取字符串s中相距为D的两个字母所构成的字母对，该字母对中两个字母的位置顺序与他们在主串s中的位置顺序一致定义D-unique表示，若从字符串s中取出所有相距为D的字母对D-pairs，且这些D-pairs都是独一无二的，那么成字符串s是一个D-unique串D的取值范围为0~s.len()-2假如字符串s对于所有的D都有D-unique成立，则字符串s是令人惊讶的 = =现在输入一些字符串，问他们能不能令人惊讶= =解题思路：令人惊讶的中级
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给定多边形城堡的n个顶点，绕城堡外面建一个围墙，围住所有点，并且墙与所有点的距离至少为L，求这个墙最小的长度。解题思路：推导公式（1）：城堡围墙长度最小值 = 城堡顶点坐标构成的散点集的凸包总边长 + 半径为L的圆周长由于数据规模较大，必须用GrahamScan Algorithm构造凸包（详细的算法可以参考我的POJ2187，这里就不再啰嗦了），然后顺序枚举凸包相邻的两点并计算其距离，得到凸包的总边长，最后加上圆周长2πL根据圆形的性质,其实就相当于多加了一
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给定平面上的一些散点集，求最远两点距离的平方值。解题思路：别想着暴力枚举任意亮点距离找最大，行不通，想想三点共线吧！平面上的散点集的最远的两点距离必然在这个散点集的凸包的某两个顶点上出现。那么先求凸包，再枚举顶点距离就OK了。别看是3000ms就想用简单的卷包裹，这题数据规模极大，卷包裹铁超（我一开始就是这么做的。。。） 万般无奈不得不用GrahamScan Algorithm。。。。O(nlogn)用来做这题还是相当可观的。GrahamScan理解是不困难的
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：一只蚂蚁,只会向左转,现在给出平面上很多个点,求解一种走法,能使得蚂蚁能经过的点最多,每个顶点该蚂蚁只能经过一次,且所行走的路线不能发生交叉.解题思路：凸包的入门水题，是凸包的一个变形网上看到很多人copy别人的，说什么“极坐标排序”，那是Graham Scan Algoruthm的做法！虽然Graham只有O(nlogn) ，但是这题完全没必要用它，因为题目的规模很小，我用卷包裹算法照样0 ms 一次AC 。确实理论上卷包裹的O(n^2)不如Graham快，
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：按照顺时针或逆时针方向输入一个n边形的顶点坐标集，先判断这个n边形是否为凸包。再给定一个圆形（圆心坐标和半径），判断这个圆是否完全在n变形内部。解题思路：题意已经很直白了。。就是那个思路。。。注意输入完顶点集后，要封闭多边形，方便后面枚举边。封闭方法：定义点集数组Vectex[1~n]记录n个顶点，再令Vectex[0]=Vectex[n]，Vectex[n+1]=Vectex[1]1、判断凸包： 由于点集已经按某个时针方向有序，因此可以先定义一个方向系数di
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：一个1X1的正方形，每条边上有n个不同的点（不包括顶点），并给出它们的坐标。现在把对边相对应的点相连，将正方形分割成(n+1)*(n+1)个小四边形。问最大的四边形的面积是多少。解题思路：计算几何求面积的题，算半条水题吧。。基本思路：构造所有的线段，然后枚举每对水平－竖直线段，求交点，然后计算四边形面积，求最大值。应用知识：叉积（规范相交）多边形分解三角形基于计算几何的面积公式（注意正负）我先建立一个数学模型说明问题：以n=3为例画图 （当然实际上内部的线不一定
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：有一宽度为1的折线管道,上面顶点为(xi,yi),所对应的下面顶点为(xi,yi-1),假设管道都是不透明的,不反射的,光线从左边入口处的(x1,y1),(x1,y1-1)之间射入,向四面八方传播,求解光线最远能传播到哪里(取x坐标)或者是否能穿透整个管道.解题思路:刘汝佳《算法艺术与信息学艺术》第三章 计算几何初步 的例2 P359(别人叫它黑书，小菜们看不懂什么意思，我稍微解释了，确实这书表面内里一般黑。。。)一模一样的题把那本书3.1节读透了，就能理解这题
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：就是给出三维坐标系上的一些球的球心坐标和其半径，搭建通路，使得他们能够相互连通。如果两个球有重叠的部分则算为已连通，无需再搭桥。求搭建通路的最小费用（费用就是边权，就是两个球面之间的距离）。解题思路：不要被三维吓到了，其实就是图论的最小生成树问题球心坐标和半径是用来求 两点之间的边权 的，求出边权后，把球看做点，用邻接矩阵存储这个无向图，再求最小生成树，非常简单的水题。把球A和球B看做无向图图的两个结点，那么边权 = AB球面距离 = A球心到B球心的距离 –
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：ACM比赛中，共M道题，T个队，pij表示第i队解出第j题的概率问 每队至少解出一题且冠军队至少解出N道题的概率。解题思路：真费解为什么这题被划分到了Hash。。。明明是 概率+DP ，概率不好真的拿不下这题T .T，建议数学不好的同学直接放弃算了。。。这题难点不在编程，在于问题的转化和理解= =只要能用笔算出答案，离AC也就不远了。。。要求：每队至少解出一题 且 冠军队至少解出N道题的概率由于冠军队可以不止一队，即允许存在并列冠军则原来的所求的概率可以转化为：
摘要: 转载请注明出处：優YoU http://user.//blog/题目大意：把一个完全图分成两部分，使得连接这两部分边的权和最大。解题思路：图论的无向完全图的最大割问题 （做网络最大流的时候同学们应该看过最小割，所以别问我什么是最大割了。。。不懂的百度去。。。）可以用 随机化算法 Random Algorithm 去做一开始我没读懂题，以为是求最大权。。。傻呼呼的用最了最小生成树的算法去做= =一直RERERE。。。还以为是数组开得不够大。。。悲剧啊。。。虽然是图论，但不懂得为什么人家要把这题归类到 搜索题 去，用搜索我完全没思路去做
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：就是公平地分披萨pie我生日，买了n个pie，找来f个朋友，那么总人数共f+1人每个pie都是高为1的圆柱体，输入这n个pie的每一个尺寸（半径），如果要公平地把pie分给每一个人（就是所有人得到的pie尺寸一致，但是形状可以不同），而且每个人得到的那份pie必须是从同一个pie上得到的后面那句很重要，就是说如果有3个pie, 尺寸分别为1,2,3，如果要给每人尺寸为2的pie，那么最多分给2个人，而不是3个人因为第一个pie尺寸为1，小于2，扔掉第二个pie
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：一根两端固定在两面墙上的杆 受热弯曲后变弯曲求前后两个状态的杆的中点位置的距离解题思路：几何和二分的混合体如图，蓝色为杆弯曲前，长度为L红色为杆弯曲后，长度为sh是所求依题意知S=(1+n*C)*L又从图中得到三条关系式;（1） 角度→弧度公式 θr = 1/2*s（2） 三角函数公式 sinθ= 1/2*L/r（3） 勾股定理 r^2 – ( r – h)^2 = (1/2*L)^2把四条关系式化简可以得到逆向思维解二元方程组：要求（1）式的h，唯有先求r但
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：一条河长度为 L，河的起点(Start)和终点(End)分别有2块石头，S到E的距离就是L。河中有n块石头，每块石头到S都有唯一的距离问现在要移除m块石头（S和E除外），每次移除的是与当前最短距离相关联的石头，要求移除m块石头后，使得那时的最短距离尽可能大，输出那个最短距离。解题思路：经典的二分，理解题意就不怎么难了 （其实编程不难，要理解就非常难。。。。）详细的解释看我的程序，实在看不懂就参考一下我POJ3273的做法，看上去不同，几时思路是差不多的，数学题
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给出农夫在n天中每天的花费，要求把这n天分作m组，每组的天数必然是连续的，要求分得各组的花费之和应该尽可能地小，最后输出各组花费之和中的最大值解题思路：经典的二分穷举详细的思路我写在程序注释中，这样会更容易懂看完我的程序还是无法切入题目的同学，建议先用 朴素的穷举 去左这题，虽然很大机会会超时，但是只是为了辅助理解。本题的二分纯粹是一个优化穷举的工具。 1 //Memory Time 2 //612K 297MS 3 4 #include&iostrea
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：这题在POJ上有译文（原文右上角）解题思路：中国剩余定理，本题难点不在编程，而是分析题目并转化为数学公式要引入本题解法，先来看一个故事“韩信点兵”：传说西汉大将韩信，由于比较年轻，开始他的部下对他不很佩服。有一次阅兵时，韩信要求士兵分三路纵队，结果末尾多2人，改成五路纵队，结果末尾多3人，再改成七路纵队，结果又余下2人，后来下级军官向他报告共有士兵2395人，韩信立即笑笑说不对（因2395除以3余数是1，不是2），由于已经知道士兵总人数在之间，
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：求A^B的所有约数（即因子）之和，并对其取模 9901再输出。解题思路：要求有较强 数学思维 的题应用定理主要有三个：要求有较强 数学思维 的题应用定理主要有三个：（1） 整数的唯一分解定理： 任意正整数都有且只有一种方式写出其素因子的乘积表达式。 A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn) 其中pi均为素数（2） 约数和公式：对于已经分解的整数A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)有A的
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：一个H-number是所有的模四余一的数。如果一个H-number是H-primes 当且仅当它的因数只有1和它本身（除1外）。一个H-number是H-semi-prime当且仅当它只由两个H-primes的乘积表示。H-number剩下其他的数均为H-composite。给你一个数h,问1到h有多少个H-semi-prime数。解题思路：感觉跟同余模扯不上关系。。。筛法打表，再直接输出。。。水题。。。 1 //Memory Time 2 //4172K 6
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给定一个大数K，K是两个大素数的乘积的值。再给定一个int内的数L问这两个大素数中最小的一个是否小于L，如果小于则输出这个素数。解题思路：首先对题目的插图表示无语。。。高精度求模+同余模定理1、 Char格式读入K。把K转成千进制Kt，同时变为int型。把数字往大进制转换能够加快运算效率。若用十进制则耗费很多时间，会TLE。千进制的性质与十进制相似。例如，把K=转成千进制，就变成了：Kt=[ 1][234][567][890]。为了方便处理
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：在b进制下，求p%m其中p为b进制大数1000位以内，m为b进制数9位以内解题思路：以字符串形式保存p，m利用进制转换公式先把m逐位转换为10进制，由于m只有9位，因此直接转换用int保存即可。再利用进制转换公式把p逐位转换为10进制，为了避免处理大数，转换过程中，若出现比m大的时候，则对m取模，继续转换。根据同余模公式知，这是允许的。此时得到的p值就是 （10进制p）%（10进制m）当p==0时，直接输出，否则把p逐位转换回去n进制再输出。n进制的p必须用数
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给定一个矩形网格的长m和高n，其中m和n都是unsigned int32类型，一格代表一个单位，就是一步，求从左下角到右上角有多少种走法，每步只能向上或者向右走解题思路：非常水的中学数学题，用组合做先简单建立一个数学模型：只要给定了长m和高n，那么要从左下角走到右上角，不管怎么走，一定要往右走m次，往上走n次例如给定 m=5,n=4那么可以 上上上上上右右右右又可以 上右上右上右上右上等等。。。关键是“上”和“右”的先后问题，就是组合问题了那么数学模型就是从n
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：有一串数字串，其规律为1 12 123
112······k输入位置n，计算这一串数字第n位是什么数字，注意是数字，不是数！例如的第10位是1，而不是10，第11位是0，也不是10。总之多位的数在序列中要被拆分为几位数
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：（与POJ1850基本一致）输出某个str字符串在字典中的位置，由于字典是从a=1开始的，因此str的位置值就是 在str前面所有字符串的个数 +1规定输入的字符串必须是升序排列。不降序列是非法字符串要求用循环输入，输入若干组字符串，若输入非法字符串则输出0，但不结束程序，这是和POJ1850最猥琐的区别，很多同学只注意到规定str的长度不同，以为把str数组长度改一下直接复制就能AC拿下一题了，殊不知老是WA却找不到原因，大概就是这里出问题了本题Str最长为5
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：（与POJ1496基本一致）输出某个str字符串在字典中的位置，由于字典是从a=1开始的，因此str的位置值就是 在str前面所有字符串的个数 +1规定输入的字符串必须是升序排列。不降序列是非法字符串不要求用循环输入去输入若干组字符串，但若输入非法字符串则输出0，且结束程序，这是和POJ1496最猥琐的区别，很多同学只注意到规定str的长度不同，以为把str数组长度改一下直接复制就能AC再多刷一题了，殊不知老是WA却找不到原因，大概就是这里出问题了本题Str最长
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：输入两个十进制正整数a和b，求闭区间 [a ,b] 内有多少个Round number所谓的Round Number就是把一个十进制数转换为一个无符号二进制数，若该二进制数中0的个数大于等于1的个数，则它就是一个Round Number注意，转换所得的二进制数，最高位必然是1，最高位的前面不允许有0规定输入范围： 1&= a &b&=2E用组合做很猥琐的题，我首先说说猥琐的地方，再说说解题思路，有四点很猥琐：（1）规定输入范围： 1&=
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：有k个坏人k个好人坐成一圈，前k个为好人（编号1~k），后k个为坏人(编号k+1~2k)现在有一个报数m，从编号为1的人开始报数，报到m的人就要自动死去。问当m为什么值时，可以使得在出现好人死亡之前，k个坏人先全部死掉？PS:当前一轮第m个人死去后，下一轮的编号为1的人 为 前一轮编号为m+1的人 前一轮恰好是最后一个人死掉，则下一轮循环回到开头那个人报“1”解题思路:经典的约瑟夫水题由于k值比较少（1~13），暴力枚举m就可以了递推公式为：ans[i]; /
摘要: 转载请注明出处：優YoUhttp://user.//blog/设原序列S的逆序列为S' ，则这道题目的关键在于，最少需要补充的字母数 = 原序列S的长度 — S和S'的最长公共子串长度这个公式我不证明，不难证剩下的就小意思了，最基础的LCS题。注意本题空间开销非常大，需要适当的处理手法先看看几种不同的申请空间方法的区别：1. 静态数组 开销大小为的int是铁定超的.据说用short int的话不会MLE，有兴趣的同学可以试试2. 动态数组 单纯的申请动态数组是不能解决这个问题的，动态数组只能增加空间
摘要: 转载请注明出处：優YoUhttp://user.//blog/LCS的变形而已 注意LCS的子串可以是离散的，不必连续，用动态规划设dp[i][j]为取s1第i个字符，s2第j个字符时的最大分值则决定dp为最优的情况有三种（score[][]为s1[i]和s2[j]两符号的分数）：1、 s1取第i个字母，s2取“ - ”： dp[i-1][j]+score[ s1[i-1] ]['-'];2、 s1取“ - ”，s2取第j个字母：dp[i][j-1]+score['-'][ s2[j-1] ];3、
摘要: 转载请注明出处：優YoUhttp://user.//blog/和POJ3176一模一样，不懂做这题的去看看我对3176的解释这是地址http://blog.csdn.net/lyy/article/details/6648150不骗人，确实是一模一样的代码O(∩_∩)O哈哈~ 1 //Memory Time 2 //232K 0MS 3 4 #include&iostream& 5 6 7 int max(int a,int b) 8 { 9 return a&
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：输入一个n层的三角形，第i层有i个数，求从第1层到第n层的所有路线中，权值之和最大的路线。规定：第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。解题方法：用二维数组way[][]靠左存储三角形内的数据，那么连线规则变更为way[i][j] → Way[i+1][j]或 Way[i][j] → Way[i+1][j+1]注意：way[][]初始化为输入时的三角形数值，此时way[i][j]表示该点位置上的权值，没输入的位置初始化为0。解题思路：
摘要: 转载请注明出处：優YoU http://user.//blog/提示：动态规划，求LIS最大不下降子序列O(n^2)和O(n*logn)算法都能完美AC不懂的就去看看LIS的概念就会做了我把两种算法都贴出来： 1 //Memory Time 2 //228K 16MS 3 4 //O(n^2)算法 5 #include&iostream& 6 7 8 int main(int i,int j) 9 {1011 while(cin&&n)12 {13 in
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给出几类珍珠，以及它们的单价，要求用最少的钱就可以买到相同数量的，相同（或更高）质量的珍珠。【规定买任一类的珍珠n个(价格为p)，都要支付(n+10)*p的钱，即额外支付10*p】例如样例Input的第二个例子：31 101 11100 12需要买第一类1个，第二类1个，第三类100个按常规支付为 (1+10)*10 + (1+10)*11 + (100+10)*12 = 1551元（一共买了102个珍珠）但是如果全部都按照第三类珍珠的价格支付，同样是买102
摘要: 转载请注明出处：優YoUhttp://user.//blog/解题思路：是POJ2533的扩展题。题意不难，令到原队列的最少士兵出列后，使得新队列任意一个士兵都能看到左边或者右边的无穷远处。就是使新队列呈三角形分布就对了。但这里有一个陷阱，看了一些别人的解题报告说“任一士兵旁边不能存在等高的士兵”，然后又举了一个例子说注意35 5 5 的情况，我没看他们的程序，不知道他们是不是把这些例子特殊处理了，但完全没必要，因为“允许处于三角形顶部的两个士兵等高”，图形化就是如下图：其实蓝色士兵的身高和红色士兵的身高是完全没有关系的。要求最少出
摘要: 转载请注明出处：優YoU http://user.//blog/解题思路动态规划题意就是给出一个主串，和一本字典，问最少在主串删除多少字母，可以使其匹配到字典的单词序列。PS:是匹配单词序列，而不是一个单词不多说，看程序主要是知道状态方程的含义dp[i]表示从message中第i个字符开始，到第L个字符（结尾处）这段区间所删除的字符数，初始化为dp[L]=0由于我的程序是从message尾部向头部检索匹配，所以是下面的状态方程：从程序可以看出，第i个位置到L所删除的字符数，总是先取最坏情况，只有可以匹配单词时才进入第二条方程进行状态
摘要: 转载请注明出处：優YoU http://user.//blog/提示：动态规划，多重背包题目大意：有各种不同面值的货币，每种面值的货币有不同的数量，请找出利用这些货币可以凑成的最接近且小于等于给定的数字cash的金额。初始思路：多重背包问题，第i种面额d[i]有 n[i]+1种选择方案可以转化为01背包问题处理转化的大概思路就是把 每种面值乘以其不同的个数，把得到的不同金额作为一件新的独一无二的货币，但是这样存在两个问题，一是 d[i]*ki 可能等于 d[j]*kj ，其中ki ∈n[i]，kj∈n[j]，二是这样做一定TLE超时
摘要: 转载请注明出处：優YoU http://user.//blog/提示：动态规划，01背包初看此题第一个冲动就是穷举。。。。不过再细想肯定行不通= =O(20^20)等着超时吧。。。我也是看了前辈的意见才联想到01背包，用动态规划来解题目大意：有一个天平，天平左右两边各有若干个钩子，总共有C个钩子，有G个钩码，求将钩码全部挂到钩子上使天平平衡的方法的总数。其中可以把天枰看做一个以x轴0点作为平衡点的横轴输入：2 4 //C 钩子数 与 G钩码数-2 3 //负数：左边的钩子距离天平中央的距离；正数：右边的钩子距离天平中央的距离c[k]
摘要: 转载请注明出处：優YoUhttp://user.//blog/题目翻译：当一个广播电台在一个非常大的地区，广播站会用中继器来转播信号以使得每一个接收器都能接收到一个强烈的信号。然而，每个中继器必须慎重选择使用，使相邻的中继器不互相干扰。如果相邻的中继器使用不同的频道，那么就不会相互干扰。由于无线电频道是一有限的，一个给定的网络所需的中继频道数目应减至最低。编写一个程序，读取一个中继网络，然后求出需要的最低的不同频道数。建模：一个有N个节点的无向图，要求对每个节点进行染色，使得相邻两个节点颜色都不同，问最少需要多少种颜色？那么题目就变
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：九宫格问题，也有人叫数独问题把一个9行9列的网格，再细分为9个3*3的子网格，要求每行、每列、每个子网格内都只能使用一次1~9中的一个数字，即每行、每列、每个子网格内都不允许出现相同的数字。0是待填位置，其他均为已填入的数字。要求填完九宫格并输出（如果有多种结果，则只需输出其中一种）如果给定的九宫格无法按要求填出来，则输出原来所输入的未填的九宫格解题思路：DFS试探，失败则回溯用三个数组进行标记每行、每列、每个子网格已用的数字，用于剪枝bool row[10]
摘要: 转载请注明出处：優YoUhttp://user.//blog/题目翻译:公司现在要发明一种新的碎纸机，要求新的碎纸机能够把纸条上的数字切成最接近而不超过target值。比如，target的值是50，而纸条上的数字是12346，应该把数字切成四部分，分别是1、2、34、6。因为这样所得到的和43 (= 1 + 2 + 34 + 6) 是所有可能中最接近而不超过50的。（比如1, 23, 4, 和6 就不可以,因为它们的和不如43接近50，而12, 34, 6也不可以，因为它们的和超过50了。碎纸还有以下三个要求：1、如果target的
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：2011 POJ暑假集训题Problem E，POJ上有中文版解题思路：DFS+剪枝POJ2362的强化版，重点在于剪枝令InitLen为所求的最短原始棒长，maxlen为给定的棒子堆中最长的棒子，sumlen为这堆棒子的长度之和，那么InitLen必定在范围[maxlen，sumlen]中根据棒子的灵活度（棒子越长，灵活度越低） DFS前先对所有棒子降序排序剪枝：1、 由于所有原始棒子等长，那么必有sumlen%Initlen==0；2、 若能在[maxlen
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给定一堆不定长度的小棒子，问他们能否构成一个正方形。解题思路：POJ1011的热身题，DFS+剪枝本题大致做法就是对所有小棒子长度求和sum，sum就是正方形的周长，sum/4就是边长side。问题就转变为：这堆小棒子能否刚好组合成为4根长度均为side的大棒子不难了解，小棒子的长度越长，其灵活性越差。例如长度为5的一根棒子的组合方式要比5根长度为1的棒子的组合方式少，这就是灵活性的体现。由此，我们首先要对这堆小棒子降序排序，从最长的棒子开始进行DFS剪枝，有
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：题意比较难懂。大致如下：第一行数字是邮票的面值，每一个数字就是一个不同的种类，哪怕面值相同。以0结束。第二行数字是顾客所需要的邮票总面值。每个数字就是一个顾客的需求，以0结束。每两行是一组case。以EOF结束输入。顾客是集邮爱好者，所以你必须尽可能的给他不同种类的邮票。但是一位顾客最多只能拿4张邮票。显然，我们拥有的邮票就是第一行中的数据。解题思路：DFS寻找所有的解，再逐一比较寻找最优解，剪枝是关键。关于tie。满足顾客需求的解就是可行解。邮票种类最多的可
摘要: 转载请注明出处：優YoU http://user.//blog/题目大意： 给出一三维空间的地牢,要求求出由字符'S'到字符'E'的最短路径移动方向可以是上，下，左，右，前，后，六个方向每移动一次就耗费一分钟，要求输出最快的走出时间。不同L层的地图，相同RC坐标处是连通的解题思路：我越看这题就越觉得是 XX地下城 = =水题一道，求最短路问题，直接BFS得了开三维数组，每次搜索方向由二维的4个方向增加到6个，但是方法还是那个方法没难度注意若果三维数组恰好开到极限的30*30*30是会RE的，别替人家电
摘要: 转载请注明出处：優YoU http://user.//blog/题目大意：给出了两个瓶子的容量A,B, 以及一个目标水量C，对A、B可以有如下操作:FILL(i) fill the pot i (1 ≤ i ≤ 2)DROP(i) empty thPOUR(i,j) pour after this operation either the pot j is full (and there may be some water
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给定两个四位素数a b，要求把a变换到b变换的过程要保证 每次变换出来的数都是一个 四位素数，而且当前这步的变换所得的素数 与 前一步得到的素数 只能有一个位不同，而且每步得到的素数都不能重复。求从a到b最少需要的变换次数。无法变换则输出Impossible解题思路:超级水题，40入口的BFS + 素数判定不过剪枝之后就没有40入口了，入口数远小于40无论是判定素数还是搜索素数，首先排除偶数，这样就剪掉一半枝叶了判断素数用根号法判断，如果一个数X不能被 [2,
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给出一个整数n，(1 &= n &= 200)。求出任意一个它的倍数m，要求m必须只由十进制的'0'或'1'组成。解题思路：首先暴力枚举肯定是不可能的 1000ms 想不超时都难，而且枚举还要解决大数问题。。要不是人家把这题放到搜索，怎么也想不到用BFS。。。解题方法： BFS+同余模定理不说废话。首先说说朴素的不剪枝搜索方法：我以n=6为例首先十进制数，开头第一个数字（最高位）一定不能为0，即最高位必为1设6的 ”
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给定两个整数n和k通过 n+1或n-1 或n*2 这3种操作，使得n==k输出最少的操作次数解题思路：说实话，要不是人家把这题归类到BFS，我怎么也想不到用广搜的= = 自卑ing。。。水题水题，三入口的BFS注意的地方有二：1、 由于用于广搜的 队列数组 和 标记数组 相当大，如果定义这两个数组时把它们扔到局部去，编译是可以的，但肯定执行不了，提交就等RE吧= =大数组必须开为 全局 。。。常识常识。。。2、 剪枝。直接广搜一样等着RE吧= = 不剪枝的同学
摘要: 大致题意：中文题。。我没什么好说的解题思路：DFS，没想法就很难很难，有想法就很容易的题棋盘规则与否不是难点，无论规则不规则都可以用标记去解决难点在于 棋盘的行数（列数）n 与 待摆放的棋子总数k 的关系为k&=nK==n时还是比较好办的K&n时就让人有点迷糊不知怎样处理了网上普遍做法都是 逐行深搜，效率不错，我也稍微借鉴了，具体看程序，不多说了，搜索的题抽象性太强，文字很难说清楚 1 //Memory Time 2 //184K 32MS 3 4 #include&iostream& 5 6 7 bool chess[9][9
摘要: 转载请注明出处：優YoU http://user.//blog/题目大意:给定一个迷宫，S是起点，E是终点，#是墙不可走，.可以走先输出左转优先时，从S到E的步数再输出右转优先时，从S到E的步数最后输出S到E的最短步数W为宽，列数H为高，行数解题思路：DFS和BFS的综合题水题，难度不大，但是写代码时要注意几方面：1、 左转、右转优先搜索时必须标记当前位置时的方向，我定义的方向是 最初的方向由起点S确定，而下一步的方向则由前一步的走向决定例如 左边优先搜索：当前位置的方向指向 1（向左），(这同时说明前一步是在第“3”的位置走过来的
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意:给出一个国际棋盘的大小，判断马能否不重复的走过所有格，并记录下其中按字典序排列的第一种路径。经典的“骑士游历”问题，DFS水题一道解题思路：难度不大，但要注意的地方有3点：1、 题目要求以&lexicographically&方式输出，也就是字典序...要以字典序输出路径，那么搜索的方向（我的程序是path()函数）就要以特殊的顺序排列了...这样只要每次从dfs(A,1)开始搜索，第一个成功遍历的路径一定是以字典序排列...下图是搜索的次
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给定一些木棒，木棒两端都涂上颜色，求是否能将木棒首尾相接，连成一条直线，要求不同木棒相接的一边必须是相同颜色的。解题思路：可以用图论中欧拉路的知识来解这道题，首先可以把木棒两端看成节点，把木棒看成边，这样相同的颜色就是同一个节点问题便转化为：给定一个图，是否存在“一笔画”经过涂中每一点，以及经过每一边一次。这样就是求图中是否存在欧拉路Euler-Path。回顾经典的“七桥问题”，相信很多同学马上就明白了什么是 欧拉路 了，这里不多作解释。由图论知识可以知道，无
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：有一个农夫要把一个木板钜成几块给定长度的小木板，每次锯都要收取一定费用，这个费用就是当前锯的这个木版的长度给定各个要求的小木板的长度，及小木板的个数n，求最小费用提示：以35 8 5为例：先从无限长的木板上锯下长度为 21 的木板，花费 21再从长度为21的木板上锯下长度为5的木板，花费5再从长度为16的木板上锯下 长度为8的木板，花费8总花费 = 21+5+8 =34解题思路：利用Huffman思想，要使总费用最小，那么每次只选取最小长度的两块木板相加，再把
摘要: 转载请注明出处：優YoUhttp://user.//blog/POJ2002的山寨题，把数据规模从2002的 n=1000修改为n=2000就能AC了注意这种题一定不能图方便用STL的map标记，map效率不高，必定超时的.解题思路参看POJ2002：http://blog.csdn.net/lyy/article/details/ //Memory Time 2 //336K 313MS 3 4 #include&iostream& 5 6
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：有一堆平面散点集，任取四个点，求能组成正方形的不同组合方式有多少。相同的四个点，不同顺序构成的正方形视为同一正方形。解题思路：做本题数学功底要很强= =直接四个点四个点地枚举肯定超时的，不可取。普遍的做法是：先枚举两个点，通过数学公式得到另外2个点，使得这四个点能够成正方形。然后检查散点集中是否存在计算出来的那两个点，若存在，说明有一个正方形。但这种做法会使同一个正方形按照不同的顺序被枚举了四次，因此最后的结果要除以4.已知： (x1,y1) (x2,y2)则
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：给出一个5元3次方程，输入其5个系数，求它的解的个数其中系数 ai∈[-50,50] 自变量xi∈[-50,0）∪（0,50]注意： 若x1 =a, x2=b ,x3=c ,x4=d,x5=e时，与 x1=b, x2=a ,x3=c ,x4 =d, x5=e 代入方程后都得到值0，那么他们视为不同的解。解题思路：直观的思路：暴力枚举，O(n^5)题目Time Limit=5000ms，1ms大约可以执行1000条语句，那么5000ms最多执行500W次每个变量
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：解题思路：经典题，不转化问题很难做，先根据官方的方法转化问题，把“求最远的两行间各个特征出现次数相等”转化为“求最远的相同两行”，再用Hash查找。这是官方解题报告——Consider the partial sum sequence of each of the k features built by taking the sum of all the values up to position i. The problem is equivalent to
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：在n （n&100000)个雪花中判断是否存在两片完全相同的雪花，每片雪花有6个角,每个角的长度限制为1000000两片雪花相等的条件：雪花6个角的长度按顺序相等（这个顺序即可以是顺时针的也可以是逆时针的）解题思路：Hash吧！连加求余法 求key 值，链地址法解决冲突设雪花6片叶子的长度为len1~len6key=( len1+len2+len3+len4+len5+len6)%prime =( len1%prime +len2%prime +len3
摘要: 转载请注明出处：優YoUhttp://user.//blog/大致题意：中文题，我就不废话了，不过据说某些RP低的同学会看到本题是英文题。。。解题思路：有两种处理方法：一、Hash+qsort法在输入时把字符号码转换为7位数字，用int保存，然后开两个8位数组vist和time，分别记录该号码是否出现过；若出现过，出现的次数是多少。把出现过2次或以上的号码先逐一存放到待输出数组sort_out输入完毕后，对数组sort_out快排，逐一输出这些号码及其出现次数即可。二、qsort法在输入时先把字符号码全部转换为7位数字，然后全部存入
摘要: 转载请注明出处：優YoU http://user.//blog/题目大意：给出长度为n的序列，每次只能交换相邻的两个元素，问至少要交换几次才使得该序列为递增序列。解题思路：一看就是冒泡，交换一次记录一次就可以了但是n的范围达到50W，冒泡O(n^2)的复杂度铁定超时（即使有7000ms，其实这是一个陷阱）直接用快排又不符合题目的要求（相邻元素交换），快排是建立在二分的基础上的，操作次数肯定比在所要求的规则下的交换次数要更少那么该怎么处理？其实这题题目已经给出提示了：Ultra-QuickSort特殊的快排，能和快排Quicksort
摘要: 转载请注明出处：優YoU http://user.//blog/水题一道给定n个数，输出中间值（注意不是求平均）可以用sort，干脆快捷，但是注意排序起止位置也可以用quicksort，(最好用随机快排，尝试一下srand和rand) 勤力的同学可以写一下\(^o^)/~没什么要注意的题，不过真要注意的话，就不要用冒泡、插入、选择排序之类的O(n^2)算法，1W个数铁定超再送一些数据给大家 78 02 11 379 478 11 43
222 800 43 45 69
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：输入m个长度为n的DNA序列，把他们按照逆序数从小到大稳定排序输出。PS:“稳定排序”就是当序列中出现A1==A2时，排序前后A1与A2的相对位置不发生改变。解题思路：没难度，先求各个字符串的逆序数，再按逆序数对字符串快排，用qsort()函数。虽然快排不是稳定的排序，但是只要在定义排序规则函数cmp做适当处理，a==b时返回0，即不处理a和b，就不会改变他们之间的相对位置了。 1 //Memory Time 2 //252K 16MS 3 4 #includ
摘要: 转载请注明出处：優YoU http://blog.csdn.net/lyy/article/details/6642573最近AC题：2528更新时间： 已AC题数：146初级题已在全部完成部分解题报告添加新内容，除了原有的“大致题意”和“解题思路”外，新增“Source修正”，因为原Source较模糊，这是为了帮助某些狂WA的同学找到测试数据库，但是我不希望大家利用测试数据打表刷题PS：部分题目的评论中也有给出了测试数据，未必完全，仅供参考这个POJ分类版本是被我修改过的，现在还在根据我做的题在逐步修改中有部分题目的分类不合理，所以根
摘要: 转载请注明出处：優YoU http://user.//blog/在s2中找s1的子串而已，本来还想用LCS的，后来想想，这样空间消耗太大，用滚动数组又麻烦。。。毕竟列数最多高达10W = = 所以还是算了，直接模拟更快= =结论：水题一道，放开怀抱去模拟吧\(^o^)/~注意下标范围 int是够不到10W的，我用了long 没了 1 //Memory Time 2 //364K 0MS 3 4 #include&iostream& 5 #include&string& 6 using namespace st
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：就是求k个长度为60的字符串的最长连续公共子串，2&=k&=10规定：1、 最长公共串长度小于3不输出2、 若出现等长的最长的子串，则输出字典序最小的串解题思路：纠结了几个月放着没做的题目。。一直以为要用KMP或者后缀数组来做。。。然后我就拼命学后缀。。。今天偶然发现直接 暴力 能够达到0ms的效果= =所以。。。暴力吧。。。不愧为初级的题。。。暴力思想很简单：开二维DNA[][]保存所有DNA序列1、 以DNA[0]为母版，顺次截取60个长度le
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：输入一部字典，输入若干单词1、 若某个单词能在字典中找到，则输出corret2、 若某个单词能通过 变换 或 删除 或 添加一个字符后，在字典中找得到，则输出这些单词，输出顺序根据 输入的那部字典的字典序3、 若某个单词无论操作与否都无法在字典中找得到，则输出空解题思路：没难度的字符串处理，1次AC暴力吧！模拟吧！基本思路就是逐个比较 待查单词 与 字典单词 的长度，当且仅当两者长度之差的绝对值&=1时才进行检查操作。Source修正：http://ne
摘要: 转载请注明出处：優YoU http://user.//blog/提示：最大流问题 折磨了我3天的题。。。网上的前辈都推荐拆点做，但是我没有用拆点（感觉拆点很麻烦） 这道题我用了三种方法去做，但是结果却差强人意。。。。 【BFS+标号法+不拆点】 成功AC 【BFS+压入重标法+不拆点】(WA，不知道错哪里了，找不到反例) 【BFS+压入重标法+模拟拆点】(WA，不知道错哪里了，找不到反例) AC的程序我贴下面，后两个WA的代码我贴在AC代码下面，希望有达人帮我查出哪里出错了。。。无限感激题意：老实说，我完全看不懂题目在说什么= =。
摘要: 转载请注明出处：優YoU http://user.//blog/提示：BFS找增广链 + 压入重标法解题思路：多源多汇最大流问题题目给出很多都是废话，特别是符号s(u)，d(u)，Con还有那条公式都别管，混淆视听难点在于构图电站p(u)均为源点，用户c(u)均为汇点，中转站当普通点处理第一个误区是例图， 结点 和 边 都有x/y（流量和容量），这个很容易使人产生矛盾（因为学习最大流问题是，只有 边 才有流量和容量。 但是不难发现，题目所给的例图中有多个源点，多个汇点，多个普通点，只有源点和汇点才标有 x/y，普通点没有标x/y，而
摘要: 转载请注明出处：優YoU http://user.//blog/提示：别被图片的圈圈误导了，看清楚题目，'*'是城市，'o'是空地，椭圆的天线覆盖范围要覆盖的是城市'*',而不是覆盖空地题目大意：一个矩形中，有N个城市’*’，现在这n个城市都要覆盖无线，若放置一个基站，那么它至多可以覆盖相邻的两个城市。问至少放置多少个基站才能使得所有的城市都覆盖无线？解题思路：思前想后，依稀可以认为是一道求二分图的最小路径覆盖问题（注意不是最小点覆盖）那么接下来需要确认的是，究竟是求 有向二分图的最小
摘要: 转载请注明出处：優YoU http://user.//blog/解题思路：把方阵看做一个特殊的二分图（以行列分别作为两个顶点集V1、V2，其中| V1|=| V2|）然后把每行x或者每列y看成一个点，而障碍物(x,y)可以看做连接x和y的边。按照这种思路构图后。问题就转化成为选择最少的一些点(x或y)，使得从这些点与所有的边相邻，其实这就是最小点覆盖问题。再利用二分图最大匹配的König定理：最小点覆盖数 = 最大匹配数（PS：最小点覆盖：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖图的所有的边
摘要: 转载请注明出处：優YoU http://user.//blog/提示：拓扑排序这道题有隐含这一信息，每输入一对关系，如果判定有结果，则可以忽略后面输入数据，即使后面输入数据能改变结果，也不用管。所以应该每输入一个关系就去更新当前的图，然后进行一趟拓扑排序。一旦产生结果，再对后面的数据处理下，就可以输出结果。 所有可能的情况罗列:（独家经验原创，重中之重！可以说没有这些，这题就无法AC！）一、当输入的字母全部都在前n个大写字母范围内时：（1） 最终的图 可以排序： 在输入结束前如果能得到最终的图（就是用这n个字母作为顶点，一个都不能少
摘要: 转载请注明出处：優YoU http://user.//blog/提示：BFS+Prim大致题意：在一个y行 x列的迷宫中，有可行走的通路空格’ ‘，不可行走的墙’#’，还有两种英文字母A和S，现在从S出发，要求用最短的路径L连接所有字母，输出这条路径L的总长度。一格的长度为1，而且移动的方法只有上、下、左、右，所以在无任何墙的情况下（但“墙#”是必须考虑的，这里只是为了说明）任意两个字母之间的距离就是直接把 横坐标之差 加上 纵坐标之差 注意的是，可行的路为 字母 和 空格 不可行的路为 # 和 矩阵范围之外根据题意的“分离”规则，
摘要: 转载请注明出处：優YoU http://user.//blog/提示：又是一题求最小生成树的总权值，继续Prim.... 1 //Memory Time 2 //300K 32MS 3 4 #include&iostream& 5 6 7 const int inf=100001; //无限大 8 9 //农场数量10 int dist[101][101];11 12 int prim(void)13 {14 int s=1;15 int m=1;16 bool u
摘要: 转载请注明出处：優YoU http://user.//blog/提示：题意很简单，就是求最小生成树的最大边。继续Prim吧O(∩_∩)O 1 //Memory Time 2 //656K 766MS 3 //思路、解法都和POJ1789基本一致，只是多了一个判定条件 4 5 #include&iostream& 6 7 8 const int inf=65540; //无限大 9 int dist[501][501];10 //村落数量11 12 int prim(
摘要: 转载请注明出处：優YoU http://user.//blog/题意大概是这样的：用一个7位的string代表一个编号，两个编号之间的distance代表这两个编号之间不同字母的个数。一个编号只能由另一个编号“衍生”出来，代价是这两个编号之间相应的distance，现在要找出一个“衍生”方案，使得总代价最小，也就是distance之和最小。例如有如下4个编号：aaaaaaabaaaaaaabaaaaaaabaaaa显然的，第二，第三和第四编号分别从第一编号衍生出来的代价最小，因为第二，第三和第四编号分别与第一编号只有一个字母是不同的
摘要: 转载请注明出处：優YoU http://user.//blog/提示：本题需要建立容器，建立字符串到int的映射（一一对应）关系，把然后字符串作为数组下标，模拟数组题意：求自身到自身的最大转换率。 最简单的方法就是floryd算法变形，求最大路径后，求最大环，看它是否满足条件。 每一个结点都必须有到自身的环(不甚清楚原因)。注意：该double的地方一定不能为int，切记!!! 1 //Memory Time 2 //276K 79MS 3 4 #include &iostream& 5 #include&map&
摘要: 转载请注明出处：優YoU http://user.//blog/提示：最短路问题，Floyd算法，相比于Bellman和Dijkstra，我认为是最接近人类自然思维的算法，O(∩_∩)O哈哈~说真的，我第一次做Floyd的题目时，我没有看过Floyd算法，我自己把Floyd推导出来了。。。至于数据的存储，就用邻接矩阵，只要对矩阵上的时间进行修改就行了，相对比较方便。 问题重述 描述 众所周知，证券经纪业依靠的就是过度的传言。您需要想出股票经纪人中传播假情报的方法，让您的雇主在股票市场的占据优势。为了获得最大的效果，你必须蔓延最快的方
摘要: 转载请注明出处：優YoU http://user.//blog/提示：唉。。不说了，又是Floyd...注意精度就是了题目大意:给出两只青蛙的坐标A、B，和其他的n-2个坐标，任一两个坐标点间都是双向连通的。显然从A到B存在至少一条的通路，每一条通路的元素都是这条通路中前后两个点的距离，这些距离中又有一个最大距离。现在要求求出所有通路的最大距离，并把这些最大距离作比较，把最小的一个最大距离作为青蛙的最小跳远距离。Floyd算法用Floyd算法求出两两最短路，再求出从每个点开始的最长路，最后从这n个最长路中求出最小的那个即为所求。 1
摘要: 转载请注明出处：優YoU http://user.//blog/提示：难得的中文题。。虽然语言相通但是不好解决。。。都说便宜没好货，这是真的= =最短路问题，dijkstra算法的运用。。。很多同学对dijkstra有一种与生俱来的恐惧，首当其冲就是它的名字。。说实在我现在也不知道怎么念它O(∩_∩)O哈哈~其实dijkstra很简单的，最难也就它的名字，不懂得同学去翻书，这里我不解释dijkstra，我只说一个我认为能够很好理解dijkstra精髓的关键点： 新源点合并到旧源点时，新源点到旧源点的边权的移交（也可理解为松弛）弄清了
摘要: 转载请注明出处：優YoU http://user.//blog/提示：利用虫洞的时光旅行，很有趣的一道题。涉及到图论的知识，关键是构造图，用Bellman-Ford算法找出负权环Bellman-Ford算法核心在于松弛，具体可以百度，这里就不重复前人的智慧了O(∩_∩)O哈哈~需要注意的就是输入说明Input这部分，很多人读不懂这段题意：正权（双向）边部分：Line 1 of each farm: Three space-separated integers respectively: N, M, and W Lines 2~M+1
摘要: 转载请注明出处：優YoUhttp://user.//blog/变种的大数斐波那契数列水题，直接加就可以了，循环使用4个大数数组a,b,c,ans存放最新的和值，循环25次后的ans就是A99的值 1 //Memory Time 2 //216K 32MS 3 4 #include&iostream& 5 #include&string& 6 7 8 const int size=1000; //大数位数 9 10 void add(char* aa,char* bb,
摘要: 转载请注明出处：優YoUhttp://user.//blog/非常恶心的大数相加= =首先输入就够恶心了。。。哪有人逐位还要间断输入两个数的。。。。注意：如果用char[]保存加数和被加数，要用getchar()输入， 如果用int[]保存加数和被加数，要用scanf)输入。用cin会超时，cin是重载函数，没有指定格式，输入时比较浪费时间100W的空间不能局部静态申请，单可以全局静态申请，也可以局部动态申请(用new)最恶心得是，我把结果开头的0（如果有的话）删去，竟然WA，真没见过这样的加法！Output file should
摘要: 转载请注明出处：優YoU http://user.//blog/大数相乘，水题一道，直接模拟笔算竖式得了，没技巧没算法，秒杀 1 //Memory Time 2 //216K 16MS 3 4 #include&iostream& 5 #include&string& 6 7 8 const int size=1000; //大数位数 9 10 void mult(char* A,char* B,char* ans)11 {12 int a[size+1]={0};1
摘要: 转载请注明出处：優YoU http://user.//blog/提示：就是多个大数相加的问题= = 1 //Memory Time 2 //184K 0MS 3 4 #include&iostream& 5 #include&cstring& 6 7 8 const int large=1000; 9 char sum_temp[large];10 char digit_temp[large];11 12 int plus(int j,int carry_bit)13
摘要: 转载请注明出处：優YoU http://user.//blog/浮点大数求幂，水题一道，把“大数乘浮点数”按指数循环就OK了，注意结果的整数部分若为0，则不保留整数部分。小数部分若为0，则不保留小数部分和小数点。 1 //Memory Time 2 //1232K 0MS 3 4 #include&iostream& 5 #include&string& 6 7 8 const int size=1000; //大数位数 9 10 void mult(char* A,
摘要: 转载请注明出处：優YoU http://user.//blog/为了简化说明，以三位数举例，因为153、135、315、351、513、531的立方和都是一样的，均等于 1^3+3^3+5^3 = 153而我们可以通过逐位检查 立方和153，发现1出现1次，3出现1次，5出现1次，而0~9中的其他数字均出现0次，出现的次数之和为3，刚好等于153的长度。由此我们可以得到 利用枚举0~9各个数字出现的次数，得到水仙花数。得到21位水仙花数的具体方法为：通过10层循环，枚举0~9这10个数字出现的次数（每个数字都可能出现0~21次），当
摘要: 转载请注明出处：優YoU http://user.//blog/题目大意：已知两堆牌s1和s2的初始状态， 其牌数均为c，按给定规则能将他们相互交叉组合成一堆牌s12，再将s12的最底下的c块牌归为s1，最顶的c块牌归为s2，依此循环下去。现在输入s1和s2的初始状态 以及 预想的最终状态s12问s1 s2经过多少次洗牌之后，最终能达到状态s12，若永远不可能相同，则输出&-1&。解题思路：很浅白的模拟题= = 不懂为什么别人要把它归类到广搜。。。所以我又重新分类了。。。直接模拟就可以了，关键在于状态记录，然后判
摘要: 转载请注明出处：優YoU http://user.//blog/提示：很烦很简单的国际象棋棋盘模拟，输出比较麻烦而已。。。是POJ2996的相反情况，认真的同学会发现2993的题目和2996的题目是相反的。。。。POJ2996-Help Me with the GamePOJ2993-Emag eht htiw Em Pleh 1 //Memory Time 2 //212K 0MS 3 4 5 #include&iostream& 6 #include&string& 7 using namespace s
摘要: 转载请注明出处：優YoU http://user.//blog/提示：很烦很简单的国际象棋棋盘模拟，输入比较麻烦而已输出时：1、不论黑白，KQRBN P均是依次输出，强制大写，但不输出“P”，只输出其坐标2、对白棋的位置，小行优先大行输出（行的数字越小则优先）同行则按列的顺序(a~h)3、对黑棋的位置，大行优先小行输出（行的数字越大则优先）同行则按列的顺序(a~h)4、从2、3点可以看出，黑棋总是先被输入，白棋总是后输入，即黑棋总在棋盘上方，白棋总在棋盘下方，所以输入完成后，对于黑色棋子只需要按类型次序输出，同类型棋子的顺序就是输入
摘要: 转载请注明出处：優YoU http://user.//blog/提示:不多说了，又是模拟题，读懂题意直接模拟就可以了，没有算法，没有技术含量，直接贴代码 1 //Memory Time 2 //256K 0MS 3 4 5 #include&iostream& 6 7 8 int main(void) 9 {10 int row,col,11 char grid[12][12]; //在规定大小的grid外部至少再定义一圈&门槛&以判断Robot是
摘要: 转载请注明出处：優YoU http://user.//blog/提示：简单的模拟而已。。。程序很长不是因为算法（根本就没算法= =）而是因为很多情况要考虑，要有耐心需要小心的是，当坐标系变换后，注意方向的改变规律注意事项：1、坐标系要改变为二维矩阵的形式，N、W、S、E的方向变化必须注意：改变坐标系后，N为南，S为北，WE不变，L转右，R转左，F不变；2、对于求余数处理是否注意出现负数的情况；3、robot移动过程中，crashes robot和crashes wall 同时判断，crashes robot放在前面。附加测试数据：S
摘要: 转载请注明出处：優YoU http://user.//blog/模拟的题型，基本难度不大，关键读懂题意：对于给出的原括号串，存在两种数字密码串：1.p序列：当出现匹配括号对时，从该括号对的右括号开始往左数，直到最前面的左括号数，就是pi的值。2.w序列：当出现匹配括号对时，包含在该括号对中的所有右括号数（包括该括号对）,就是wi的值。题目的要求：对给出的p数字串，求出对应的s串。串长限制均为20提示：在处理括号序列时可以使用一个小技巧，把括号序列转化为01序列，左0右1，处理时比较方便 1 //Memory Time 2 //256
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：有中文版= = 我不多说解题思路：模拟题，细心点就好了，没难度。Habb历一年365天Tzolkin历一年260天先计算Habb历从第0天到输入日期的总天数sumdaySumday/day就是Tzolkin历的年份Tzolkin历的天数Name每20一循环，先建立Tzolkin历天数Name与1~20的映射，因此Sumday %20+1就是Tzolkin历的天数NameTzolkin历的天数ID每13一循环，且从1开始，则Sumday %13+1就是Tzolk
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：八皇后的扩展：N皇后问题PS: 我用了传统DFS回溯 和 构造法 两种方法去解决解题思路：先说说传统回溯的DFS思路：按行逐行填放皇后，标记已填放的列，两斜边的标记则利用 斜率 进行标记，当 准备填放的点 与 任一已填放的点 之间的斜率为1或-1时，那么该位置不允许填放虽说是八皇后的扩展，但这么一扩展就难很多了。。。题目要求n值范围在 8到300之内，Time还限制在1000ms ，传统的DFS回溯肯定是用不了，用传统的方法求解，n值超过30就爆了那么这题只能
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：输入由p、q、r、s、t、K、A、N、C、E共10个字母组成的逻辑表达式，其中p、q、r、s、t的值为1（true）或0（false），即逻辑变量；K、A、N、C、E为逻辑运算符，K --& and: x && yA --& or: x || yN --& not : !xC --& implies : (!x)||yE --&equals : x==y问这个逻辑表达式是否为永真式。PS:输入格式保证是合法的解题思
摘要: 转载请注明出处：優YoU http://user.//blog/题意比较难懂，其实只要读懂题意，就很简单了。大意是一个公司在12个月中，或固定盈余s，或固定亏损d.但记不得哪些月盈余，哪些月亏损，只能记得连续5个月的代数和总是亏损(&0为亏损)，而一年中只有8个连续的5个月，分别为1~5，2~6，…，8~12问全年是否可能盈利？若可能，输出可能最大盈利金额，否则输出“Deficit&.根据经验，贪心选择往往都在极端处（临界点）选择。（其实这题不用贪心，单纯枚举也可以AC，因为不同情况实在太少呐。。。。不难证明，每连续
摘要: 转载请注明出处：優YoU http://user.//blog/提示：一般思路：二分+高精度算法但是本题还有一个更加巧妙的办法去处理：首先需要明确：double类型虽然能表示10^(-307) ~ 10^308, （远大于题意的1&=p&10101这个范围）,但只能精确前16位，因此必须慎用！那么为了避免double对输入的数在运算过程中进行精确，那么我们必须让double的运算第一步就得到一个int（即小数点尾数全为0），这个不难理解。然后根据题意，是求指数k，一般人自然想到利用 对数log，即k=lognp。但是不要
摘要: 转载请注明出处：優YoU http://user.//blog/提示：简单的贪心正确的算法是：要考虑把雷达站放到哪个位置使得包含雷达的区间最多！ 写算法的时候要注意，按海岛的横坐标排序（纵坐标是跟随横坐标，但不能对排序构成任何影响）后，第一个雷达建立在区间的右端，然后依次判断每个区间的左端点，如果在最新建立的雷达右面，那么肯定需要一个雷达，而且也建在区间右端。如果左端点在雷达左面，这个时候要考虑区间的右端在雷达的左面还是右面，如果是右面，那雷达位置就不变，如果在左面，那现在的雷达是覆盖不了的，所以要把雷达放在该区间的右端点！因为这样
摘要: 转载请注明出处：優YoU http://user.//blog/提示：这题和POJ1753翻转棋的思想是一致的，需要注意的是要求输出翻转过程，因此不能用BFS，必须用DFS（找到目标后，还要过程回溯）与POJ1753相比，这题还要注意翻棋的方法，若不注意会大大浪费时间导致超时，因为是整行整列翻转，在边界处会出现很多多余操作。代码中详细说明同样本题有两种方法，Enum和Bit ，下面分别贴出这两种代码 1 /*代码一：DFS+Enum*/ 2 3 4 5 //Memory Time 6 //240K 641MS 7 8 //本题由于要
摘要: 转载请注明出处：優YoU http://user.//blog/提示：翻转棋，可以建模为多叉树本题难点有两个，一个就是不要以全黑（或全白）作为目标进行搜索，而是要把全黑（或全白）作为“根”，去搜索树叶，看看是否有 输入的棋盘状态。另一个难点需要一点数学功底，就是要知道 树 的最大高度，这是“状态不存在”的判断标准提示：其实每格棋子最多只可以翻转一次（实际是奇数次，但这没意义），只要其中一格重复翻了2次(不论是连续翻动还是不连翻动)，那么它以及周边的棋子和没翻动时的状态是一致的，由此就可以确定这个棋盘最多只能走16步，最多只能有翻出2
摘要: 转载请注明出处：優YoU http://user.//blog/提示：不用提示了= = 超级水。。。。别弄错权值就是了。。 1 //Memory Time 2 //224K 16MS 3 4 #include&iostream& 5 #include&cstring& 6 7 8 int value[91]; 9 10 void value_alphabet(void)11 {12 int i,j;13 for(i='A',j=1;i&=&#39
摘要: 转载请注明出处：優YoU http://user.//blog/提示：二叉树遍历而已。。。给出前序和中序，求后序解题思路1、前序遍历的第一个字母必是 根2、在中序遍历的字母串中找出 根字母，那么根字母左右两边的字符串就分别是它的左、右子树3、利用递归复原二叉树（把子树看作新的二叉树）4、后序遍历特征：后序遍历字母串 自右至左 依次为：最外层（总树，设为第0层）右子树的根，内1层右子树的根，内2层右子树的根….内n层右子树的根，内n层左子树的根，内n-1层左子树的根……内1层左子树的根，最外层（总树，第0层）左子树的根。把总树的左子树
摘要: 转载请注明出处：優YoU http://user.//blog/题目大意狄利克雷基于等差数列的算法原理设一个等差数列，首元素为a，公差为b现在要求输入a,b,n ，要求找出属于该等差数列中的第n个素数并输出 1 //Memory Time 2 //260K 141MS 3 4 #include&iostream& 5 6 7 bool judge_prime(int temp) 8 { 9 int k,flag=1;10 int num=2;11 if(temp==2)12 re
摘要: 转载请注明出处：優YoU http://user.//blog/提示：利用房间号分割走廊，每条“子走廊”都设置一个计数器，每经过一次+1，完了最后对计数器快排，最大的次数X10就是答案初看此题有点像贪心的感觉，因为可能会想到把输入的搬运区间的交点（临界点）进行统计，这是很笨很没效率的方法，而且要考虑一堆可能情况，我按这个思路用栈做过这题，列出了所有可能的例子，结果一致但无限WA。。。。所以呼吁大众：不要误入歧途了。。。 1 //Memory Time 2 //232K 0MS 3 4 #include&iostream&
摘要: 转载请注明出处：優YoU http://user.//blog/提示：100W真是大的BT。。。。我用了优化还是勉强AC掉，认识的一位达人，16ms AC这题，Orz....解题思路：如果还是按常规方法求一百万内的所有素数(就是除法求模)，时间复杂度是大到难以置信的。因此必须转换思路进行优化，用加法代替除法，用空间换取时间！计算算加法绝对要比除法快得多，而且一百万个地址，也就是差不多1MB的内存，相信现在99%的电脑还是可以很轻松地拿出来的！判断素数的优化：1、 素数除2外都是偶数，先减半2、 递归法：如果一个数不能被比它小的所有素
摘要: 转载请注明出处：優YoU http://user.//blog/提示：本题用一般的素数求法就可以做出来了，虽然可以AC，不过时间复杂度很大，所以我用了优化，优化的过程可以参看下一道水题POJ2262，两道水题基本上是同气连枝 1 //Memory Time 2 //232K 16MS 3 4 5 #include&iostream& 6 7 8 int prim[1230]={2,3}; 9 int count=0;10 11 void prime(void) //素数组打表12
摘要: 转载请注明出处：優YoU http://user.//blog/PS：本题稍微说一下题意（当时有点发牢骚的感觉，O(∩_∩)O哈哈~）一种我认为是比较符合现实的解题思路，但是总是Wrong Answer咋看之下确实是被题目忽悠了，一般思路都是先对置换解密，再对乱序解密，但是题目所给出的乱序码只有10个，&2, 1, 5, 4, 3, 7, 6, 10, 9, 8&，输入要求却是不大于100的字符串，这里就显示出了矛盾所在：没有10之后的乱序码根本无法解密！！初看之下这道题目确实是无理取闹，但是从矛盾中同时也给予了我们提示
摘要: 刻苦的训练我打算最后稍微提一下。主要说后者：什么是有效地训练？我想说下我的理解。很多ACMer入门的时候，都被告知：要多做题，做个500多道就变牛了。其实，这既不是充分条件、也不会是必要条件。我觉得一般情况下，对于我们普通学校的大学生，各方面能力的差距不会太大，在这种情况下，训练和学习的方法尤为重要。其实，500题仅仅是一个标志，而且仅仅表示你做ACM-ICPC有一定的时间，我们训练的目的是什么？我觉得有四点1、提高编程能力2、学习算法，（读书，读论文，包括做一些题目验证）3、准备好面临将到来的挑战（熟悉题型，调整心态）4、启发思维。这里四个目的，从训练的角度上，重要性逐次递减；为什么呢？因为
摘要: 转载请注明出处：優YoU http://user.//blog/提示：纯粹的数学公式，连推导公式都可以省了= = 1 //Memory Time 2 //240K 0MS 3 4 #include&iostream& 5 #include&math.h& 6 #include&string& 7 #include&iomanip& 8 9 int main(void)10 {1112 double t,d,h;13 in
摘要: 转载请注明出处：優YoU http://user.//blog/大致题意：根据给定的算法，可以计算一个整数的循环数现在给定一个区间，计算这个区间的所有数的循环数，把最大的循环数输出PS:输出的是整数A的循环数，而不是输出整数A解题思路：好吧，我承认是在找题时，因为输错题号而碰到的水题，顺手A的，没难度，暴力即可。注意的只有一点：输入的两个区间端点不一定是从小到大输入的，因此要先对这两个数排一下序。 1 //Memory Time 2 //256K 0MS 3 4 #include&iostream& 5 using na
摘要: 转载请注明出处：優YoU http://user.//blog/问题描述：Fred Mapper 正在考虑在路易斯安那州购买一些土地来建他自己的房子。在研究土地的过程中，他发现，路易斯安那州的土地每年都会被密西西比河侵蚀掉 50 平方里。因为 Fred 希望在这个房子里度过余生，所以他需要知道他的那些土地是否会被侵蚀掉。在做了更多的调查之后，Fred 发现这些土地是以半圆的形状被侵蚀的。这个半圆所对应的正圆的圆心在坐标原点 (0, 0), 坐标轴 x 轴将这个圆切成两半。在 x 轴下方的区域是河流。在第一年刚开始的时候，这个半圆的面
摘要: 转载请注明出处：優YoU http://user.//blog/额。。还真怀念。。这都遇上了。。2011年5月ACM珠海赛的试机题= =别问我怎么做，求平均数而已，水过水过。。。毫无悬念，当时题目都没看，一看到Sample Input和Sample Output就直接A了= = 1 //Memory Time 2 //256K 0MS 3 4 #include&iostream& 5 #include&iomanip& 6 7 8 int main(void) 9 {
摘要: 转载请注明出处：優YoUhttp://user.//blog/打发时间顺手A的水题= = 没啥好说的。。。算是增强一下做难题前的信心O(∩_∩)O 1 //Memory Time 2 //260K 0MS 3 4 #include&iostream& 5 6 7 int main(void) 8 { 9 const int size=301; //最大长度5.20要用276张卡片10 double length[size]={0.0}; //i张卡片的延伸长度为length[i]
随笔 - 150