当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] poj 3587 The Biggest Cake 正弦定理

    题意: 给n个点,求其中3个点构成三角形的最大外接圆半径。 分析: 正弦定理,A/sina=B/sinb=C/sinc=ABC/(2*s)=2*R。 代码: //poj3587 //sep9 #include<iostream> #include<cmath> usingn...

    56
    热度
  • [综合] poj 3286 How many 0's? 按位统计

    题意: 给m<=n,求从m写到n,一共写多少个0. 分析: 按位算当某位是0时左边有多少种情况,右边有多少种情况,注意左边的情况数为-1时(这时遍历到最高位)是为了把右边多加的情况减去,也就是把0作为开头时的情况减去。 代码: //poj3286 //sep9 #include<ios...

    21
    热度
  • [综合] poj 3480 John anti-SG博弈

    题意: 跟经典的nim除了胜利条件不一样(nim当游戏者面对空的决策集判负,anti-SG当游戏者面对空的决策集判负),其他都一样。 分析: 设全局状态为s,单个游戏为t。先手必胜条件:(g(s)!=0&&Existg(t)>1)||(g(s)==0&&Anyg...

    14
    热度
  • [综合] poj 2429 GCD LCM Inverse miller_rabin素数判定和pollard_rho因数分解

    题意: 给gcd(a,b)和lcm(a,b),求a+b最小的a和b。 分析: miller_rabin素数判定要用费马小定理和二次探测定理。pollard_rho因数分解算法导论上讲的又全又好,网上的资料大多讲不清楚。 代码: //poj2429 //sep9 #include<iostrea...

    97
    热度
  • [综合] poj 1284 Primitive Roots 求素数元根数

    题意: 给奇素数p,求p有多少原根。 分析: phi(p-1),数论有具体证明。 代码: //poj1284 #include<iostream> usingnamespacestd;intmain() {intn;while(scanf("%d",&n)==1){--n;in...

    90
    热度
  • [综合] poj 2417 Discrete Logging 数论baby_step,giant_step算法

    题意: 给p,b,n求最小的l使b^l==n(modp)。 题意: 相当于在0~p-1内搜索l满足同余式,baby_step,giant_step相当于分块的二分搜索,设m=sqrt(p),则将p分为m*m,在m块内每块进行m个数的二分搜索。 代码: //poj2417 //sep9 #includ...

    33
    热度
  • [综合] poj 2191 Mersenne Composite Numbers 大数分解

    题意: 给k,求i是素数且在1~k内并且2^i-1是合数的情况,并将它分解。 分析: 枚举1至i然后用miller_rabin素数判定和pollard_rho因数分解即可。 代码: //poj2191 //sep9 #include<iostream> #include<map&...

    56
    热度
  • [综合] poj 2886 Who Gets the Most Candies? 线段树动态求第k大的数

    题意: n个小孩站一圈,每个小孩拿一个数字,从第k个孩子开始出局,然后下一个出局的孩子是刚刚出局的孩子之前或之后第v个(刚刚出局的孩子的数字是+v则之后v个,-v则之前v个),这样所有孩子终将出局,第p个出局的孩子得f(p)分,f(p)定义为p的因子个数。求分数最高的孩子。 分析: 设顺时针为正方向...

    79
    热度
  • [综合] poj 3111 K Best 参数搜索之牛顿迭代法

    题意: 给n个元素,每个元素有两个属性(v,w),现在要从中选k个,使sum(v)/sum(k)最大。 分析: 参数搜索的入门题,牛顿迭代比二分快很多。 代码: //poj3111 //sep9 #include<iostream> #include<algorithm> ...

    79
    热度
  • [综合] poj 2728 Desert King 参数搜索解最优比例生成树

    题意: 图中每条边有两个权值(cost,len),求其一棵生成树,使sum(cost)/sum(len)最小。 分析: 转化为求边权为s0*len-cost的最大生成树+牛顿迭代。s0为具有单调性迭代系数。 代码: //poj2728 //sep9 #include<iostream>...

    50
    热度
  • [综合] poj 3621 Sightseeing Cows 负环探测解参数搜索

    题意: 有向图中每个点有一个欢乐值,边有边权,要求一条环路,使环路上欢乐值得和/路径和最大。 分析: 二分参数,判断是否存在负权,这里判负圈没用spfa,用的是一种效率很高的方法。 代码: //poj3621 //sep9 #include<iostream> #include<...

    93
    热度
  • [综合] poj 1275 Cashier Employment 差分约束

    差分约束模板题,差分约束是判断联立不等式组是否有解的一种方法,建图是关键。 代码: //poj1275 //sep9 #include<iostream> #include<queue> usingnamespacestd; constintmaxM=10024; cons...

    29
    热度
  • [综合] poj 2112 Optimal Milking 二分+最大流

    根据这题可以总结出处理网络流问题中需要“跳过”某一节点的办法(跳过是指需要占用经过某一节点但又不占用其流量):1.floyd求全局最优路径建图前直接跳过。2.拆点成A-A1,A-A1是经过该点的实际流量,并由A1流出相同的流量。+oo流进A,A->B1走需要跳过的流量。 代码: //poj2...

    20
    热度
  • [综合] poj 2125 Destroying The Graph 最小点权覆盖

    题意: 求一个图的最小点权覆盖。 分析: 拆点转化为求最小割。 代码: //poj2125 //sep9 #include<iostream> #include<queue> #include<algorithm> usingnamespacestd; cons...

    14
    热度
  • [综合] poj 2391 Ombrophobic Bovines 二分+最大流

    同poj2112. 代码: //poj2391 //sep9 #include<iostream> #include<queue> #include<algorithm> usingnamespacestd; typedeflonglongll;constint...

    55
    热度
  • [综合] poj 3046 Ant Counting 多项式乘法解可重组合数

    题意: 裸的求可重组合数。 分析: 多项式乘法求系数的应用啊,不用dp。 代码: //poj3046 //sep9 #include<iostream> usingnamespacestd; constintmaxN=1024; constintmaxL=100024; constin...

    16
    热度
  • [综合] poj 2497 Strategies 模拟水题

    水题,直接贴代码。 //poj2497 //sep9 #include<iostream> #include<algorithm> usingnamespacestd; inta[32]; intmain() {intcases,c=0;scanf("%d",&ca...

    5
    热度
  • [综合] poj 2425 A Chess Game grundy值

    题意: 给一个拓扑图,在一些点上有棋子,两个玩家每次轮流将一颗棋子沿有向边移动一次,无法移动则失败。 分析: 理解nim和状态的grundy值两下就敲出来了。 代码: //poj2425 //sep9 #include<iostream> #include<vector> ...

    26
    热度
  • [综合] poj 2537 Tight words 概率dp

    分析: 用计数dp思想:DP[I][J]=(DP[I-1][J-1]+DP[I-1][J]+DP[I-1][J+1]),最后再除pow(k+1,n)容易爆精度,改用概率dp思想DP[I][J]=(DP[I-1][J-1]+DP[I-1][J]+DP[I-1][J+1])/(k+1)即可。 代码: ...

    87
    热度
  • [综合] poj 3744 Scout YYF I 概率dp+矩阵乘法

    分析: dis(k,v1,v2)函数求到当前位置概率为v1,到当前位置之前一步的概率为v2,前进k步到达位置的概率,然后矩阵加速。 代码: //poj3744 //sep9 #include<iostream> #include<algorithm> usingnamesp...

    26
    热度