Songer_Wa-CSDN博客

原创 POJ 3190(Stall Reservations 区间贪心)

/*给出n个牛的挤奶区间 *一头牛在那个时间必须占用一个牛棚，每个牛棚至多一头牛生产 *问最少准备的牛棚数 */#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespac

2016-03-29 23:44:05 611

原创 POJ 3187(Backward Digit Sums 穷竭搜索，杨辉三角性质)

//题意略#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;typedef long long ll;typedef pair P;const int

2016-03-28 22:57:15 438

原创 POJ 3050(Hopscotch 穷竭搜索)

/*给一个5*5的矩阵 *从某一个位置开始能够向上下左右走 *求所有走了6步后，走过的矩阵元素(数字)的序列 */#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespa

2016-03-28 22:53:16 402

原创 Aizu 0525(Osenbei 穷竭搜索)

/* 翻煎饼，1正面朝上，0反面朝上， * 每次可翻某一行或者某一列 * 问最大正面朝上数 */#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;t

2016-03-28 22:46:40 433

原创 POJ 1328(Radar Installation 区间贪心)

/*雷达安在x轴上 *给出n个岛的坐标 *求最少能覆盖所有岛的雷达数 */#include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;typ

2016-03-28 22:41:30 370

原创 POJ 2376 Cleaning Shifts 区间贪心

#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;typedef long long ll;typedef pair P;const int INF=0

2016-03-28 21:41:03 377

原创 POJ 3009 Curling 2.0 （dfs)

调了接近两个小时不容易啊，索性写个博客惩罚一下自己。题目大意:溜冰壶，冰壶有起点终点，问由起点到终点最小投掷数，最小投掷数大于10或者终点不可达输出-1冰壶一旦投掷，会朝着一个方向行走，知道滑出平台、撞到石块或到达终点。撞到石块会停并且石块消失。思路：DFS枚举投掷方向即可，不用标记是否走过（因为有石块的影响）#include#include

2016-03-25 19:06:16 668

原创算法导论第三章函数的增长 3.2习题个人解答

3.2-1 证明：若f(n)和g(n)是单调递增的函数，则f(n)+g(n)也是单调递增的，此外，若f(n)和g(n)是非负的，则f(n)*g(n)也是单调递增的. 证：1.取任意实数m>n,总有 f(m)+g(m)-[f(n)+g(n)] ≥ 0,故它是单调递增的.2.取任意实数m>n，l 若f(m),f(n),g(m),g(n)都为正，那么就有f(m)*g(m)/[f(

2015-11-21 20:45:20 4392 1

原创算法导论第三章函数的增长，3.1练习个人解答（Sor)

3.1-1 假设f(n)与g(n)都是渐近非负函数。使用Θ记号的基本定义来证明max(f(n),g(n)) = Θ(f(n)+g(n))。证：不妨假设max(f(n),g(n)) = f(n),则0 ≤ g(n)/f(n) ≤ 1设有正常量c1,c2,n0,使得所有对n ≥ n0，有0 ≤ c1*f(n) ≤ f(n) + g(n) ≤ c2*f(n) 解得 c1 ≤ 1

2015-11-20 20:36:56 3793 1

原创数论概论第五章习题解答（下）（宋二娃的BLOG）

5.5 （a）n 算法长度终止值 21 8 1 13 10 1 31 107 1 （b）当n >= 3，n

2015-08-04 22:25:25 1526

原创数论概论第五章习题解答(上）（宋二娃的BLOG）

5.1 唔，虽然很简单，但是我还是把代码贴出来吧 #include using namespace std; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int main() { int a,b; while(cin >> a

2015-08-04 20:43:07 1427

原创 UVA 1572 Self-Assembly 拓扑排序

2015-08-04 10:01:17 517

原创数论概论第四章高次幂之和与费马大定理习题解答（宋二娃的BLOG)

4.2 (a) 根据提示（寻求形如（a，b，c）=（xz，yz，z^2）的解）PS：c>=b>=a>=1 ①（2*35,3*35,35*35）=（70,105,1225） ②（2*72,4*72,72*72）=（144,288,5184） ③略（二娃比较懒） ④a^3 + b^3 = c^3 ==> x^3 * z^3 + y^3 * z^3 = z^4 ==>x^3 + y^3 = z

2015-08-04 00:59:28 1898

原创挑战程序设计竞赛 1.61 nlogn算法

问题如下： OK，这道题非常简单，朴素算法我就不说了，书上也给出了朴素O(n^3)的代码，但是同时也告诉我们还有更高效的算法，我当时琢磨了一下，排序，确定其中两个再用二分查找可以的到一个O(n^2logn)的算法，但是同样不高效。然后，然后.....我发现这道题居然是一道贪心......怎么贪呢？代码如下：#include#include#include

2015-04-25 15:40:12 718

原创 POJ 1952 LITTLE SHOP OF FLOWERS（DP动归，最长递减子序列）

题目地址：http://poj.org/problem?id=1952 BUY LOW, BUY LOWERTime Limit: 1000MS Memory Limit: 30000KTotal Submissions: 8651 Accepted: 2994

2015-01-25 16:32:05 505

Songer_Wa的专栏