当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] poj 2464 Brownie Points II 树状数组

    题意: 给Stan个点,玩家Stan先经过某个点画一条竖线,玩家Ollie再经过这条线上的某一点画一条竖线,这样将整个区域分为4个区域,左上和右下里的点是Stan的得分,左下和右上是Ollie的得分,问Stan最多能得多少分和在保证Stan的最高分的情况下Ollie能得的最高分是多少.注意Stan选...

    20
    热度
  • [综合] poj 2513 Colored Sticks 字典树

    题意: 给一堆小棒,每跟小棒上有两种颜色,颜色相同的两端可以连起来,问所有小棒是否可以练成一条线。 分析: 无向图是否存在欧拉路径问题,这题主要是与输入做斗争,输入的字符串用map水的话会超时,只能老老实实写字典树。 代码: //poj2513 //sepNINE #include<iost...

    8
    热度
  • [综合] poj 2607 Fire Station dijkstra算法求到点集的最短路

    题意: 给一个有n个路口的城市,路口之间由路相连,某些路口上建有消防站,现在要在没有建消防站的路口建一个消防站,使没建消防站的路口到建有消防站的路口最短路径的最大值最小。 分析; 枚举没建消防站的点建消防站,然后求所有点到建有消防站点集的最短路。 代码: //poj2607 //sepNINE #...

    57
    热度
  • [综合] poj 3037 Skiing 最短路spfa

    题意: 给一个R行C列的地图,g[i][j]表示该点的高度,相邻两点距离为1,初速度为起始点的v速度,末速度为初速*2^下降高度,求(1,1)到(R,C)的最短时间。 分析: 关键是搞清楚在每个点的速度只跟在点(1,1)的初速有关,跟怎么到这个点是没有关系的,因为他们之间的高度差恒定,之后就可以用s...

    58
    热度
  • [综合] poj 2552 模拟水题

    题意: 一列人,编号2,3,4,5。。。先选2,然后在没选的里每2个赶走一个,即赶走4,6,8.。。。在从剩下的里选第一个比如i,然后没i个赶走一个,如此反复,求第n个选到的人。 分析: 水题,直接模拟。 代码: #include<iostream> usingnamespacestd...

    93
    热度
  • [综合] poj 1946 Cow Cycling 动态规划

    题意: 有n头牛,每头都有能量e,要跑d圈,跑得过程中每分钟跑x圈(自己选择),领头的消耗x*x的能量,其他的消耗x的能量,问跑完d圈最少需要多少时间。 思路: 最后的结果肯定是前面n-1头领跑后奶牛n撞线。dp[i][j][k]为前i-1头已领跑,现在i领跑,一共跑了j圈,第i头牛消耗了k的能量。...

    50
    热度
  • [综合] poj 2491 Scavenger Hunt 字符串离散化

    题意: 乱序给出一条有n个结点的路径上的每对前前驱结点和后继结点,求原路径。 分析: 水题,直接保存每个结点的后继结点,然后找到开始结点遍历一遍输出就可以了,值得说说的是怎么用map来进行字符串离散化,即把一个字符串和一个整数对应,并给出整数能找到相应的字符串,请参考程序。 代码: //poj24...

    34
    热度
  • [综合] poj 1950 Dessert 深搜

    题意; 给n,问有多少和由1,2...n,和'+','-',’.‘(表示连接,4.5表示45)组成,值为0的表达式。 分析: 深搜,因为要枚举到“连接”的情况,所以传送pre表示上个表达式中最后一个数字。 代码: //poj1950 //sep9 #include<iostream> ...

    51
    热度
  • [综合] poj 1927 计算几何

    题意: 给三角形的三点坐标个一段长为L的绳,求绳子在三角形内最多能围多大面积。 分析: 难点是绳长大于三角形内接圆半径又小于三角形周长的情况,这种情况绳子在三角形内形成三段直线和三段弧,其中三段弧组成一个小圆(有从物理方面的证明)。求出比例后即可算面积。 代码: //poj1927 //sep9 ...

    41
    热度
  • [综合] poj 1383 Labyrinth 树的直径

    题意: 给一个迷宫,其中任意两个可以走的点之间只有一条路,求在这个迷宫里最长能走多远。 分析: 求树的直径,两次dfs即可。 代码: //poj1383 //sep9 #include<iostream> usingnamespacestd; constintmaxN=1024; ch...

    46
    热度
  • [综合] poj 1730 Perfect Pth Powers 精度修正

    题意: 给数x,求最大的整数p,使对某个整数b有x==b^p。 分析: 从大往小枚举p看是否找得到相应的b,当确定p后b==pow(x,1/p),算pow(x,1/p)肯定是会有误差的,解决的办法是将b,b+1,b-1分别带入验算,只要有一个满足我们就找到了相应的b。 代码: //poj1730 ...

    3
    热度
  • [综合] poj 3164 Command Network 最小树形图

    题意: 给一个有向图,求他的定点最小生成树。 分析: 有向图的定点最小生成树又称最小树形图,用朱刘算法解决,算法步奏详细解释: 首先判断是否存在最小树形图,从根结点dfs一遍。 除根节点外,对于其他所有顶点v,找一条最短的以v为终点的边。 判断步骤2中找的边是否会形成环,会成环转步骤4,不会转步...

    12
    热度
  • [综合] poj 3767 I Wanna Go Home 最短路spfa

    题意: 给一个无向图,每个点有属性支持A或B(点1的属性恒为A,点2恒为B),求点1到点2的最短路,所求的最短路径要满足要求:路径上的边两边的点的属性至多有一次不一样。 分析: 最短路问题就用spfa水吧~~d[v][0]表示从起点开始到v点的属性没有变化过,d[v][1]表示从起点到v属性已经变化...

    46
    热度
  • [综合] poj 2195 Going Home 二分图最小权匹配KM算法

    题意: 有n个人要回到n间房子里,每间房子只允许一个人,求n个人要走的最小距离和。 分析: 裸的二分图最小权匹配,KM搞之。 代码: //poj2195 //sep9 #include<iostream> usingnamespacestd; constintmaxN=128; cha...

    59
    热度
  • [综合] poj 2400 Supervisor, Supervisee KM求二分图+dfs输出所有解

    题意: 有n个Supervisor和Supervisee,他们之间相互有一个评分,现在要求一个匹配,所有人的评分和最小,并输出使评分和最小的所有匹配方案。 分析: KM算法求二分图的最小权匹配,并用dfs输出所有方案。 代码: //poj2400 //sep9 #include<iostre...

    95
    热度
  • [综合] poj 3686 The Windy's 二分图最小权和匹配KM

    题意: 给n个玩具和m家工厂,每个玩具只能在一家工厂加工,给出每个玩具在每家工厂需要的加工时间,求这n个玩具完成时间平均值的最小值。 分析: 求最小和容易联系到二分图的最小权和匹配,这题的问题是n与m的大小关系是不确定的,也是就是说可能会有多个玩具到同一家工厂里加工的情况,这似乎与匹配的定义相矛盾。...

    96
    热度
  • [综合] poj 2029 Get Many Persimmon Trees 暴力枚举

    题意: 给n个点和一个宽w高h的矩形,求该矩形最多能框住多少个点。 分析: O^2算法直接暴力枚举放置矩形右上角的点。 代码: //poj2029 //sep9 #include<iostream> usingnamespacestd; intmap[128][128]; intmai...

    74
    热度
  • [综合] poj 2516 Minimum Cost KM或最小费用流

    题意: 有k种物品,n个商店和m个供应站,每个商店对每种商品有需求量shopNeed[n][k],每个供应站对每种商品都有存货量supply[m][k],对于种类k的物品,他从供应站j到商店i的花费为cost[k][i][j],求让每个商店每种商品满足需求量的最小花费。 分析: 典型的最小费用最大流...

    68
    热度
  • [综合] poj 2366 Sacrament of the sum 尺取法的灵活运用

    题意: 给一个升序数列和一个降序数列,判读是否能从中各取一个数,使他们的和为10000. 思路: 尺取法是一种求最小区间的算法,通过设置不前移的指针p和不后移的指针q来求满足某个条件的最小区间。类似地,设置两个不前移的指针p,q,可设计O(n)算法。 代码: //poj2366 //sep9 #i...

    33
    热度
  • [综合] poj 2771 Guardian of Decency 最大独立集

    题意: 有n个人,其中有一些人在一起会搞呢飞起,现在他们要出去玩,求最多能去多少人。 分析: 若两个人会搞呢飞起则他们之间有一条边,转化为求最大独立集问题(二分图。。)。 代码: #include<iostream> #include<string> usingnamesp...

    71
    热度