当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] poj 2041 Unreliable Message 字符串处理

    水题,直接贴代码。 //poj2041 //sep9 #include<iostream> usingnamespacestd; charmode[128]; charori[128],res[128]; intlen; voidJ() { ori[0]=res[len-1];for(...

    64
    热度
  • [综合] poj 3498 March of the Penguins 点流量有限制的最大流

    题意: 给n块浮冰的坐标,每块浮冰上的企鹅数和能承受跳起的次数,求有哪些浮冰能让企鹅能到一起。 分析: 拆点将点流量的限制转化为边流量的限制,求最大流。 代码: //poj3498 //sep9 #include<iostream> #include<queue> #inc...

    5
    热度
  • [综合] poj 3254 Corn Fields 状态压缩dp

    题意: 给一块m行n列的土地,有一些格可以种树,另外一些不可以,树不能相邻,问一共有多少种种法。 分析: 从后往前种,子问题向父问题扩展,当种到某一格时只有他和他后面的n-1个格子的情况对它有影响,故对这n个格子进行编码为状态S,表示种完(多米诺骨牌那题是放置前,注意区别,都可行)这n个格子的状态。...

    98
    热度
  • [综合] poj 2135 Farm Tour 最小费用流入门模板

    题意: 求点1到点n再从点n回点1不经过同一条路的最短路。 分析: 建图容易,给一组针对求两次最短路的数据: 451211310024100231341 接下来上最小费用流的模板就好。 代码: //poj2135 //sep9 #include<iostream> #include&l...

    13
    热度
  • [综合] poj 2126 Factoring a Polynomial 数学多项式分解

    题意: 给一个多项式,求它在实数域内的可分解性。 分析: 代数基本定理。 代码: //poj2126 //sep9 #include<iostream> usingnamespacestd;intmain() {intn;scanf("%d",&n);inta,b,c;scan...

    13
    热度
  • [综合] poj 1628 Deduction 模拟

    题意: 给一些蕴含式和一个为真的语句集合,求总共能推导出的语句集合。 分析: 维护一个里面语句都为真的集合就好。ps,这水题居然只有一百多人做出来。。 代码: //poj1628 //sep9 #include<iostream> #include<set> #includ...

    55
    热度
  • [综合] poj 1406 Starship Hakodate-maru 暴力枚举

    水题,直接贴代码。 //poj1406 //sep9 #include<iostream> usingnamespacestd; __int64f1[2024]; __int64f2[3024]; intmain() {__int64index1=0,index2=0,n;for(in...

    6
    热度
  • [综合] poj 2585 Window Pains 暴力枚举排列

    题意: 在4*4的格子中有9个窗口,窗口会覆盖它之下的窗口,问是否存在一个窗口放置的顺序使得最后的结果与输入相同。 分析: 在数据规模较小且不需要剪枝的情况下可以暴力(思路清晰代码简单),暴力一般分为枚举子集(for(s=0;s<1<<n;++s))和枚举排列(next_permu...

    97
    热度
  • [综合] poj 3390 Print Words in Lines 动态规划

    题意: 给n个单词的长度和每行最多能放的字符数m,每行产生的值为(m-x)^2,x是该行的字符数(包括单词之间的空格),求把所有单词放完产生的值的最小和。 分析: 动态规划很重要的就是状态的定义,在由子问题向父问题推进的过程中,定义的状态要能对之前的所有情况进行总结,比如背包问题中dp[i][v]中...

    34
    热度
  • [综合] poj 1959 Darts 允许重复组合

    水题,直接贴代码。 //poj1959 //sep9 #include<iostream> usingnamespacestd; intn; intf[128]; intsolve() {intx,y,z,sum=0;for(x=0;x<=n&&x<=60;...

    23
    热度
  • [综合] poj 1723 SOLDIERS 中位数

    题意: 给n个士兵的坐标,要把他们移动到水平且相邻的一行,求最小步数。 分析: 中位数法,y方向易求,x方向x0->n+i与x0-i->n是对应的,故也可以转换成y方向的情况。 代码: //poj1723 //sep9 #include<iostream> #include...

    34
    热度
  • [综合] poj 3129 How I Wonder What You Are! 点积求两向量夹角

    水题,直接贴代码。 //poj3129 //sep9 #include<iostream> #include<cmath> usingnamespacestd; constdoubleeps=0.00000001; structP{doublex,y,z; }p[512],...

    29
    热度
  • [综合] poj 3709 K-Anonymous Sequence dp斜率优化

    题意: 给长度为n的非严格递增数列a0,a1...an-1,每一次操作可以使数列中的任何一项的值减小1。现在要使数列中每一项都满足其他项中至少有k-1项和它相等。求最少操作次数。 分析: dp[i]:=只考虑前i项情况下,满足要求的最小操作次数。 s[i]:=a0+a1+...+ai,则dp[i]=...

    69
    热度
  • [综合] poj 3636 Nested Dolls 动态更新表的二分查找

    题意: 给n个玩具,每个有属性w,h。如果w1<w2且h1<h2那么玩具1可放在玩具2里,问最后最少能有几个玩具。 分析: w升序,w相同时h降序排序后是可以贪心的,这里使用了动态维护表的二分算法,表里动态维护了每堆玩具中h的最大值(所以w相同时h要降序)。这题我一开始一看是个拓扑图还想...

    78
    热度
  • [综合] poj 3977 Subset 折半枚举

    题意: 给n(n<=35)个数,求一个它的子集,使其中元素和的绝对值最小。 分析: 折半枚举。 代码: //poj3977 //sep9 #include<iostream> #include<map> usingnamespacestd; typedeflonglo...

    3
    热度
  • [综合] poj 3735 Training little cats 矩阵的幂

    题意: 给一个长度为n的数列,初始化为0,有3种操作:1)将某个元素增加1;2)将某个元素置0;3)交换两个元素。现在给出包含k个操作的一组操作,求m组操作后数列的状态。 分析: 找出初始矩阵A和转移矩阵T后就可以用快速幂计算了。 代码: //poj3735 //sep9 #include<...

    45
    热度
  • [综合] poj 3691 DNA repair AC自动机+dp

    题意: 给n个模式串和1个主串,求主串最少改变多少个字符才能不含n个模式串中的任何一个。 分析: 多模式串匹配问题可以考虑ac自动机,把自动机构造出来后在上面dp,dp[len][s]表示主串到len个字符且位于自动机son状态时的最优值,则dp[len][son]=min(dp[len][s],d...

    44
    热度
  • [综合] poj 2778 DNA Sequence AC自动机+矩阵幂加速

    题意: 给m个模式串,问长度为n的所有串中不含所有模式串的串有几个。 分析: 构造完ac自动机后将自动机转换为状态转移矩阵,mat[i][j]表示一步从状态i到状态j的方法数。最后用矩阵幂加速。ps:求模运算很慢,尽量放在for循环外层。 代码: //poj2778 //sep9 #include...

    45
    热度
  • [综合] poj 3208 Apocalypse Someday 自动机+dp

    题意: 求第n个包含3个连续6的数。 分析: 设状态0表示末尾没有6,状态1表示末尾有1个6,状态2表示末尾有2个6,状态3表示末尾有3个6或之前有3个6,可构造出确定状态自动机。然后对该自动机进行dp,a[i][j]表示位于自动机的j状态,再走i步,能包括含3个6的数的个数。之后再用数位dp的思想...

    50
    热度
  • [综合] poj 1625 Censored! AC自动机+dp+高精度

    题意: 给p个模式串,求长度为m的所有串中不含任意模式串的串的个数。 分析: 这道题不让求模,所以要用高精度,但是在矩阵乘法里用高精度花销太大,好在长度m不大,可以一步一步dp出来。在dp里加个高精度是个很有意思的事情,详见代码。 代码: //poj1625 #include<iostrea...

    62
    热度