-
[综合] poj 2748 Logs Stacking 递推公式的循环节
题意: 求f(n)=f(n-1)+2*f(n-2)+3*f(n-3)...(n-1)*f(1)+f(0),f(0)=f(1)=1的值。 分析: 转换为f(n)=3*f(n-1)-f(n-2)的二阶递推,用矩阵乘法可以做到logn的复杂度,可是由于测试用例数多和n实在太大,logn也超时。。其实n阶递...
37
热度 -
[综合] poj 2888 Magic Bracelet polya计数+矩阵统计路径数
题意: 用m种颜色涂n个小球组成的项链,其中k对颜色不能相邻,求一共有多少种方案。 分析: polya计数,难点是对于一个置换p,怎样确定在p下等价的方案数。设p的循环节数为i,如果没有限制显然是m^i,有限制的话怎么办呢?考虑将每一种方案转化为路径,比如a->b->c->a,那么...
73
热度 -
[综合] poj 1320 Street Numbers 解pell方程
题意: 解(2*n+1)^2-8*a^2=1. 分析: 令x=2*n+1,y=a,则转化为x^2-8*y^2=1的pell方程。pell方程详解 代码: //poj1320 //sep9 #include<iostream> usingnamespacestd;intmain() {i...
89
热度 -
[综合] poj 3406 Last digit 求组合数的最后非零数
题意: 求组合数C(n,m),n>=m的最后非0数。 分析: 与求排列数的最后非0数类似,要注意分母上以3结尾的数可能比分子上的多,要特殊处理。 代码: //poj3406 //sep9 #include<iostream> usingnamespacestd;inttable[...
60
热度 -
[综合] poj 2558 Genetic Code 深搜+打表
题意: 求一个长度为n的串n<=5000,它没有相邻且相同的子串。 分析: 一开始各种构造,后来发现可以深搜,输出结果的时候打表就可以了,原来O(3^5000)的程序也不是一定会超时的。。只要剪枝吊,照样可以搞。。 代码: //poj2558 //sep9 #include<iostr...
3
热度 -
[综合] poj 1849 Two 树形dp好题
题意: 可以转换为于在一棵树中,找m个叶子节点,使他们连线(重复部分只计一次)的距离和最大。 分析: m==2时求树的直径倒是简单,m>2时就要用树形dp了,有n*m^2的树形dp.对于树形dp,不仅仅每一棵子树可以看做一个子问题,每一个作为子树的子问题也可以看成是由一些更小的子问题构成,代码...
50
热度 -
[综合] poj 2361 Tic Tac Toe 五子棋模拟
//poj2361 //sep9 //与poj3075的区别是在游戏中的状态也合法 #include<iostream> #include<algorithm> usingnamespacestd; intway[8][3]={{0,1,2},{3,4,5},{6,7,8},...
83
热度 -
[综合] poj 3659 Cell Phone Network 树的最小点支配集
题意: 给一棵树,求它的最小点支配集。 分析: 树形dp,注意点支配集与点覆盖集的区别是点支配集是覆盖所有的点,点覆盖集是覆盖所有的边,看看这组数据就知道为什么每个点有3个状态了: 11 12 13 14 15 36 67 78 79 710 711代码: //poj3659 //sep9 #...
6
热度 -
[综合] poj 3517 And Then There Was One 约瑟夫问题
//poj3517 //sep9 #include<iostream> usingnamespacestd;intmain() {intn,k,m;while(scanf("%d%d%d",&n,&k,&m)==3&&(n|m|k)){intans...
74
热度 -
[综合] poj 2264 Advanced Fruits dp解LCS的对偶问题
题意: 给字符串a,b,求长度最短的包含a且包含b的字符串。 分析: 是个LCS的对偶问题,dp的方程也很像。 代码: //poj2264 //sep9 #include<iostream> usingnamespacestd; constintMAXN=128; intdp[MAXN...
51
热度 -
[综合] poj 1063 Flip and Shift 冒泡排序的扩展运用
题意: 给一个0,1组成的环,问是否可以通过交换间隔为1的两个数使所有1相邻。 分析: 冒泡排序就是交换相邻2个数可以把任何序列排成升序,用这一性质奇偶讨论下就好。 代码: //poj1063 //sep9 #include<iostream> usingnamespacestd;in...
69
热度 -
[综合] poj 1650 Integer Approximation “追赶法”搜索
题意: 给a,l,求n,d<=l,使|a-n/d|最小。 分析: 两个需要枚举的变量,由于两个变量有依赖关系,可采取“追赶法”,能在O(n)时间解决问题。 代码: //poj1650 //sep9 #include<iostream> #include<cmath> ...
0
热度 -
[综合] poj 1190 dfs+剪枝
题意: 维数为m,维度需枚举的深搜,剪枝很重要,手痒了随便找题写写没想到被卡了2个小时。。 代码: //poj1190 //sep9 #include<iostream> #include<cmath> usingnamespacestd; intN,M,ans,rm,mi...
60
热度 -
[综合] poj 1023 The Fun Number System 整数的表示
题意: 给一个整数n,求它是否可以被一个k位的01串表示,这个01串与整数的二进制表示类似,只不过每位表示的正负由一个输入字符串s给出。 分析: 理解了整数的唯一任意进制表示是由整数对任意数求商求余唯一这一公理导出之后这题就不难了,这题的细节是注意负数求余:-5/2=-2,-5%2=-1。 代码: ...
15
热度 -
[综合] poj 3244 Difference between Triplets 最值公式推导
题意: 给n个三元组,求任意一对i,j三元组d(i,j)的和,d(i,j)=max(ai-aj,bi-bj,ci-cj)-min(ai-aj,bi-bj,ci-cj);ai就是三元组i的第一个值,bi就是三元组i的第二个值。 分析: 首先要知道max(n,m)=n+m+|n-m|,min(n,m)=...
85
热度 -
[综合] poj 3372 Candy Distribution 数论
题意: 设f(x)=(x+1)*x/2mod(n),问f(x)是否可以构成n的一个完全剩余系。 分析: 网上很多证明一开始就说f(x)的周期为n,这是不对的。当n是奇数时f(x)周期T=n,当n为偶数时T=2*n,f(x+n)=f(x)+n/2。依据这3个性质可推出f(x)可以构成n的一个完全剩余系...
23
热度 -
[综合] poj 1036 Gangsters 简单dp
//poj1036 //sep9 //这种dp效率低会爆内存 #include<iostream> usingnamespacestd; constintMAXT=30012; constintMAXS=112; constintMAXN=112; intn,k,t; inta[MAXT...
23
热度 -
[综合] poj 1661 Help Jimmy 动态规划
题意: 给n个用左端点、右端点、高度标识的平台,问一个下落速度,移动速度均为1的点下落到地面的最小时间,其中每次下落距离不能超过输入值MAX. 分析: 动态规划ldp[i]表示从第i块木板左边下落到地面的最小时间,rdp[i]表示从第i块木板右边下落到地面的最小时间。 代码: //poj1661 ...
73
热度 -
[综合] poj 1126 Simply Syntax 右线性文法的归约
题意: 给字符串s判断是否符合文法X->CXX|DXX|EXX|IXX|NX|p~z。 分析: 线性文法直接归约就好。 代码; //poj1126 //sep9 #include<iostream> #include<string> usingnamespacestd...
94
热度 -
[综合] poj 3404 Bridge over a rough river 贪心
题意: 有n个人要坐船过河,每个人需要的时间已知,有一条最多容纳两个人的船,两个人坐船的时间为两人中的较大值,求所有人过河的最少时间。 分析: 设4个人分别要a<b<c<d的时间过河,可证明全局最优解中c与d是先过河的(不可能出现d过河然后b,c一起过河,可以d,c一起过河,也可以...
5
热度