当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] poj 2441 Arrange the Bulls 状压dp入门

    题意: 将n头牛和m个栏做匹配,求匹配方案数。 分析: 开始暴搜tle了,还是要用状压dp,dp[i][s]表示前i头牛匹配栏的状态为s时可行的方案数。 代码: //poj2441 //sep9 #include<iostream> usingnamespacestd; constin...

    6
    热度
  • [综合] poj 3157 Java vs C++ 模拟

    题意: 将java和c++中的变量名相互转换,比如:long_and_mnemonic_identifier装换为longAndMnemonicIdentifier。 思路: 直接模拟遍历替换,陷阱很多。。 代码: //poj3157 //sep9 #include<iostream>...

    22
    热度
  • [综合] poj 2530 Tetris Alphabet 拓扑排序

    题意: 给一个俄罗斯方块的游戏截图,其中每个输入块都用字母A-Z标志出,求输入块的字典序最小的输入顺序。 分析: 即求字典序最小的拓扑序。 代码: //poj2530 //sep9 #include<iostream> usingnamespacestd; charmap[54][32...

    85
    热度
  • [综合] poj 2627 Gopher and hawks 最短路

    题意: 给老鼠的速度v和移动时老鼠在洞外的最长时间m、地面上n个点的坐标,问老鼠是否可以从洞1到洞2,可以的话求最少跳数。 分析: 裸的最短路,注意精度。 代码: //poj2627 //sep9 #include<iostream> #include<queue> usi...

    30
    热度
  • [综合] poj 2289 Jamie's Contact Groups 二分+网络流

    题意: 让n个点和m个点对应,一个n只能对应一个m,一个m可以对应多个n,对每个n给出他能对应的m点集合,求m对应n多数的最小值。 分析: 网络流+二分。 代码: //poj2289 //sep9 #include<iostream> #include<queue> usi...

    2
    热度
  • [综合] poj 3614 Sunscreen 网络流或二分图多重匹配或优先队列

    题意: 有C头牛,每头牛有它可以接受的药的最小值和最大值,有L瓶药,每瓶药有一个值u和它最多能给v头牛用,求最多有多少头牛能满足。 分析: 网络流或二分图多重匹配或优先队列,这道题优化了我的dinic模板,原来的模板会TLE。。。 代码: //poj3614 //sep9 #include<...

    20
    热度
  • [综合] poj 3298 Antimonotonicity 贪心

    题意: 求一个序列的最大子序列,该子序列满足:a1>a2<a3>a4.....。 分析: 贪心,从极大值起交替取这个序列中极小值、极大值。 代码: //poj3298 //sep9 #include<iostream> usingnamespacestd; const...

    23
    热度
  • [综合] poj 1691 Painting A Board 拓扑序+dfs

    题意: 一个木板上被分成了很多区域,每个区域要涂上一种特定的颜色,当涂一个区域的时候,它上方与它有重合部分的区域必须之前要涂好。求最少需要拿几次画笔(拿一次画笔可以涂颜色相同的多个区域)。 分析: 上方与它有重合部分的区域必须之前要涂好这个限制可以用拓扑序来描述,每次涂有很多种可以涂的颜色,dfs就...

    91
    热度
  • [综合] poj 2442 Sequence 优先队列的运用

    题意: 给m行,每行n个数,从每行取一个数计算和,求前n小的和。 分析: 优先队列的运用,主要是make_heap,pop_heap,push_heap三个STL函数的用法。 代码: //poj2442 //sep9 #include<iostream> #include<alg...

    12
    热度
  • [综合] poj 3481 Double Queue STL中map的运用

    题意: 维护一个集合,操作有1:加入一个元素,2:删除最大元素,3:删除最小元素。 分析: map本质是个容器,且具有第一个关键字有序的性质,所以用它来水水就好啦~ 代码: //poj3481 //sep9 #include<iostream> #include<map> u...

    93
    热度
  • [综合] poj 1609 Tiling Up Blocks dp入门之记忆化搜索

    题意: 给n个二元组(a,b),要在其中找最长的序列,使得对序列中的任意i<j,有ai<=aj且bi<=bj。 分析: 设dp[a][b]代表以(a,b)结尾的最长序列长度,记忆化搜索即可。 代码: //poj1609 //sep9 #include<iostream>...

    76
    热度
  • [综合] poj 1204 Word Puzzles 静态trie树解决多模式串匹配问题

    题意: 给一个二维字符数组和w个模式串,求这w个模式串在二维字符数组的位置。 分析: 静态trie树。 代码: //poj1204 //sep9 #include<iostream> usingnamespacestd; constintmaxN=1024; constintmaxM=...

    27
    热度
  • [综合] poj 3579 Median 二分查找与lower_bound

    题意: 给n个数,他们两两之间较大数减去较小数总共有n*(n-1)/2个数,要求这些数的中位数。 分析: 两次二分,第一次枚举答案,第二次判断该数是否可能成为中位数。 代码: //poj3579 //sep9 #include<iostream> #include<algorit...

    35
    热度
  • [综合] poj 3444 Wavelet Compression 模拟水题

    水题,直接贴代码。 //poj3444 //sep9 #include<iostream> usingnamespacestd; constintmaxN=260; inta[maxN],b[maxN];intmain() {inti,n,m;while(scanf("%d",&...

    15
    热度
  • [综合] poj 3292 Semi-prime H-numbers 筛数打表

    题意: 给定n,求1至n中有多少个数能仅表示成两个(4*x+1,x>=1)的数之积。 分析: 打表,一开始的list[i*j]代表i*j的组成方式数,不需要用乘法,加法就好。 代码: //poj3292 //sep9 #include<iostream> usingnamespa...

    79
    热度
  • [综合] poj 1416 Shredding Company 模拟+枚举

    题意: 给一个目标数和一个待分割数,可以对待分割数进行任意划分,比如将带分割数12305分为12,30,5,问将分好的数加起来最接近且不超过目标数的分割方案。 分析: 关键是在对带分割数的任意划分,直接for循环枚举状态,比如状态10101(二进制)表示将12305分为1,23,05. 代码: #...

    47
    热度
  • [综合] poj 1164 The Castle dp区域计数水题

    水题,直接贴代码。 //poj1164 //sep9 #include<iostream> usingnamespacestd; inta[64][64]; intdp[64][64]; intn,m; constintwest=1,north=2,east=4,south=8; vo...

    51
    热度
  • [综合] poj 2546 Circular Area 两圆面积交

    题意: 给两个圆,求它们的面积交。 分析: 海伦公式,余弦定理等可解。 代码: //poj2546 //sep9 #include<iostream> #include<cmath> usingnamespacestd; constdoublepi=acos(-1.0);i...

    81
    热度
  • [综合] poj 2507 Crossed ladders 二分解方程

    题意: 给两把梯子的长度x,y和他们交点的高度c,求两梯子底部之间的距离。 分析: 化简后得方程c/sqrt(x^2-w^2)+c/sqrt(y^2-w^2)=1,f(w)=c/sqrt(x^2-w^2)+c/sqrt(y^2-w^2)单调增,可以二分解,注意精度。 代码: //poj2507 /...

    25
    热度
  • [综合] poj 1717 Dominoes 01背包

    题意: 给两列数,a1,a2..an和b1,b2..bn,可以交换ak和bk,求让两列数和的差的绝对值最小的最少交换次数。 分析: 动态规划,dp[x]表示a1,..am进过交换达到和为x的最小交换次数。dp[x+a]<-dp[x],dp[x+b]<-dp[x]+1。 代码: //po...

    73
    热度