当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] poj 3678 Katu Puzzle 2-sat

    题意: 给一堆布尔表达式,问是否存在解。 分析: 2-sat的入门题,只需判断是否有解,不要求输出解。 代码: //poj3678 //sep9 #include<iostream> #include<stack> usingnamespacestd; constintma...

    63
    热度
  • [综合] poj 3905 Perfect Election 2-sat

    题意: 有n个候选人和m张选票,每张选票上有一种限制,问是否有一种让m张选票上的限制都满足的选举方案。 分析: 2-sat判断是否有解,不需输出解,标准化操作。 代码: //poj3905 //sep9 #include<iostream> #include<stack> ...

    49
    热度
  • [综合] poj 3207 Ikki's Story IV - Panda's Trick 2-sat

    题意: 在一个圆上有n个点,m条边将他们相连,问是否有一种连发使没有两条线相交。 分析: 每条线要么在圆内,要么在圆外,2-sat问题。 代码: //poj3207 //sep9 #include<iostream> #include<stack> usingnamespa...

    78
    热度
  • [综合] poj 2723 Get Luffy Out 2-sat

    题意: 有2*n把钥匙配成n对,每对中只能使用一把,另外有m道门,每道门能被2把药匙打开,问最多能从1开始按顺序打开多少道门。 分析: 二分枚举能打开的门数,用2-sat算法判断能否打开。 代码: //poj2723 //sep9 #include<iostream> #include...

    82
    热度
  • [综合] poj 3648 Wedding 2-sat

    题意: 给n对夫妻安排座位,每对夫妻相对而坐,给出m对特殊关系,有特殊关系的人不能一起坐在新娘对面。 分析: 2-sat+输出解。 代码: #include<iostream> #include<stack> #include<vector> #include&...

    1
    热度
  • [综合] poj 2749 Building roads 2-sat

    题意: 给n个村庄的坐标和两个特殊点s1,s2的坐标,现在要将每个村庄连到s1或s2上,使n个村庄间的最大距离最小。 分析: 二分任意两村庄间的最大距离,用2-sat判断该最大距离是否可行,二分的时候可以顺便记录答案,不用等最后区间为空时再输出l或l-1。 代码: //poj2749 //sep9...

    76
    热度
  • [综合] poj 2296 Map Labeler 2-sat

    题意: 在平面上给n个点,要在以每个点为中心向上或向下画一个边长为L的正方形,要保证这些正方形不能重叠,求可画正方形边长的最大值。 分析: 对于每个点,有向上或向下画两种状态,根据这个可以用2-sat建模。 代码: //poj2296 //sep9 #include<iostream>...

    25
    热度
  • [综合] poj 3683 Priest John's Busiest Day 2-sat

    题意: 有n场婚礼,每场婚礼的属性有开始时间,结束时间,和祷告持续时间,每场婚礼的祷告必须安排在婚礼的开始或者结束,问是否存在一种安排使得每场婚礼的祷告互不重叠,有的话输出安排方案。 分析: n场婚礼,每场婚礼的祷告只能在开始或结束,2-sat问题,建图时采用互斥排定思想,即如果时间段i与时间段j互...

    39
    热度
  • [综合] poj 3249 Test for Job 图上dp(记忆化搜索)

    题意: 给一个n个点的DAG,每个点有一个值p,现在要在图上找一个入度为0到出度为0的路径,使路径上的点的p值和最大。 分析: dp[v]记录以点v为起点能获得的最大值,搜一遍即可。 代码: //poj3249 //sep9 #include<iostream> usingnamesp...

    71
    热度
  • [综合] poj 3592 Instantaneous Transference 强连通缩点+在DAG上dp求最长路

    题意: 给一个地图,在每一点只能向下或向右走,其中标有‘*’点上有传送门可以传送到他指定的位置,标有数字的点上代表在该点可以得到的矿石,标有‘#’的点代表这点不能走,求从(0,0)点开始能最多获得多少矿石。 分析: 因为有传送门所以图中可能有环,缩点后在所得的DAG中求最长路就可以了。 代码: /...

    78
    热度
  • [综合] poj 1659 Frogs' Neighborhood 度序列可图化 贪心

    题意: 对一个无向图给出一个度序列,问他是否可简单图化。 分析: 根据Havel定理,直接贪心即可。 代码: //poj1659 //sep9 #include<iostream> #include<algorithm> usingnamespacestd; structN...

    12
    热度
  • [综合] poj 1112 Team Them Up! 二分图染色+dp

    题意: 给n个人和一些认识关系,要将这n个人分成两队,每队的人之间都互相认识,求一种方案使两队的人数差最小。 分析: 对原图求逆得到新图g,g中如果有边(a,b),那么a,b不能在一个队,对新图进行二分图染色就能求得一种方案了。但题目要使人数差最小,所以还要dp一下。dp[i][j]表示前i个连通分...

    34
    热度
  • [综合] poj 2021 Relative Relatives 排序

    题意: 给m个三元组(str1,str2,age)表示孩子str2比父亲str1大age岁,要将所有人按年龄从大往小输出,如有年龄相同的情况按字典序从大到小输出。 分析: 用map将每个人与一个id对应,求出年龄后不需要在每个人的信息上直接排序,可以在id上间接排序。 代码: //poj2021 ...

    73
    热度
  • [综合] poj 1975 Median Weight Bead floyd算法

    题意: 给n颗豆和m个重量关系,要求有几个豆不可能是重量排在第n/2个的。 分析: 在原图和他的逆图上两次floyd算出对每颗豆有多少豆比它重和比它轻。 代码: //poj1975 //sep9 #include<iostream> #include<vector> usi...

    35
    热度
  • [综合] poj 2337 Catenyms 有向图欧拉路径

    题意: 给一些字符串,问是否可以把这些字符串连成一排,使前一个串的最后一个字符和后一个串的第一个字符一样。 分析: 把每个字符串都看成边就转化为有向图的欧拉路径(回路)问题了,这种O(e)的暴搜很巧妙。 代码: //poj2337 //sep9 #include<iostream> #...

    6
    热度
  • [综合] poj 1386 Play on Words 有向图欧拉路径判断

    题意: 给n个单词,问是否可以将他们排成一排,使得前一个单词的末字符和后一个单词的首字符相同。 分析: 把每个单词看成一条边,转化为有向图是否存在欧拉路径问题。 代码: //poj1386 //sep9 #include<iostream> #include<vector>...

    62
    热度
  • [综合] poj 1300 Door Man 无向图欧拉路径存在判断

    题意: 给n个房间和m道门以及起点,问是否可以从起点到0号房间,经过每道门恰好一次。 分析: 把门看作边则是无向图是否存在欧拉路的问题。 代码: //poj1300 //sep9 #include<iostream> usingnamespacestd; constintmaxN=32...

    38
    热度
  • [综合] poj 1780 Code 有向图输出欧拉路径+非递归深搜

    题意: 给一个数字n,n位数的密码最多有10^n个,现在要求一个字符串包含这10^n个串恰好各一次且字典序最小。 分析: 把每个可能的串看作边,构成这个串的两个n-1位数看作点则转化为欧拉路径问题,比如n==4时有u=423,v=239,e=4239.这题用递推会暴,要使用dfs的非递归写法:whi...

    9
    热度
  • [综合] poj 3616 Milking Time dp+树状数组

    题意: 给一堆区间,每个区间有开始时间s,结束时间e,和收益w,现在要找一些区间使收益和最大,且区间之间的间隔最小为r。 分析: 这道题用dp做是简单题,用dp+树状数组做是中等题。dp问题的关键是对状态的定义。有两种方法,一:dp[k]表示按开始时间排序到第k个区间能取得的最大收益。二:dp[t]...

    84
    热度
  • [综合] poj 3734 Blocks 组合计数

    题意: 给长度为n的串,串中每位可用0,1,2,3,求0的个数和1的个数都为偶数的串数。 思路: 组合计数,4^n=(2+1+1)^4,ans=sum[i=0...n](c(n,i)2^i*sum[k=n-i且为偶数,t=0,2,...k](c(k,t));最后推出4^(n-1)+2^(n-1)。 ...

    81
    热度