I am a bachelor student in Computer Science and Technology at Nanjing University of Science and Technology,
interset in cpmputer algorithm.Previously, I was at the Jinling High School.
The thing I am doing most in my off-hour is ACM/ICPC contest.I wish I could get a Gold medal before I am retired,so
I must devote all my spare time in it in the coming year.If I found I couldn't realize the dream after the regional
in my junior.I will retire immediately.
So,in the next winter holiday,I must do a lot of exercises about algorithm.This is detail:
I have 30 days.I believe I could finish 10 problems in one day if Idevote all my time in it.So I must finish 200
problems in the holiday,I have solved 211 problems in poj,and I wish I will havesolved 400 problems so as to get
into the top 15 in the rank of my school after the winter holiday!
The company commander of in military training said:"Low-key person & high-profile work".Haha,I know ltj_njust
will see this,so if I hadn't finished doing this ,I will invite you have a big dinner when the new term begins.
Learn an algorithm every and then finish the problems about it in poj.Just be simple!
For the CET-6 is coming tomorrow,I write this passage in English,but i found it none of use ...
昨晚做了一道题，开了一个int [5000][5000]的数组，OLE了，虽然可以用short [5000][5000]猥琐过,但毕竟只是特殊情况
正确的方法是滚动数组压缩存储，整理了一下网上的资料：
利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。不过经常还是用在DP题目中，因为DP题目是一个自下而上的扩展过程，我们常常用到是连续的解，前面的解往往舍弃！所以用滚动数组可以说是很有必要的。
滚动数组 举个简单的例子：
int i, d[100];
d[0] = 1;
d[1] = 1;
for (i = 2; i < 100; i++)
d[i] = d[i - 1] + d[i - 2];
printf("%d", d[99]);
上面这个循环d[i]只依赖于前两个数据d[i - 1]和d[i - 2];
为了节约空间用滚动数组的做法
int d[3];
d[0] = 1;
d[1] = 1;
for (i = 2; i < 100; i++)
d[i % 3] = d[(i - 1) % 3] + d[(i - 2) % 3];
printf("%d", d[99 % 3]);
注意上面的取余运算，我们成功地只保留了需要的最后3个解，数组好象在“
滚动”一样，所以叫滚动数组
//DP
对于二维也可以用（代码可能不太正确和完善，但是可以理解例子）:
int i,j,d[100][100];
for(i=1;i<100;i++)
for(j=0;j<100;j++)
d[i][j]=d[i-1][j]+d[i][j-1];
上面的d[i][j]只依赖于d[i-1][j],d[i][j-1];
运用滚动数组
int i,,j,d[2][100];
for(i=1;i<100;i++)
for(j=0;j<100;j++)
d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];
滚动数组实际是一种节省空间的办法，时间上没啥优势，多用于DP中，举个
例子吧：
一个DP，平常如果需要1000×1000的空间，其实根据DP的无后效性，可以开成2×1000，然后通过滚动，获得和1000×1000一样的效果。滚动数组常用于DP之中，在DP过程中，我们在由一个状态转向另一个状态时，很可能之前存储的某些状态信息就已经无用了，例如在01背包问题中，从理解角度讲我们应开DP[i][j]的二维数组，第一维我们存处理到第几个物品，也就是阶段了，第二维存储容量，但是我们获得DP[i],只需使用DP[i - 1]的信息，DP[i - k],k>1都成了无用空间，因此我们可以将数组开成一维就行，迭代更新数组中内容，滚动数组也是这个原理，目的也一样，不过这时候的问题常常是不可能缩成一维的了，比如一个DP[i][j]需要由DP[i - 1 ][k],DP[i - 2][k]决定，i<n，0<k<=10;n <= 100000000;显然缩不成一维,正常我们应该开一个DP[100000005][11]的数组，结果很明显，超内存，其实我们只要开DP[3][11]就够了DP[i%3][j]由DP[(i - 1)%3][k]和DP[(i - 2)%3][k]决定，空间复杂度差别巨大。
我的递归思维一直很差，潜意识里总是觉得这种思维不是真正的解决问题，所以，总是想用递推思维思考问题。
给定二叉树的前序和中序，输出后序是数据结构中的基本问题，我一直不敢上机实践，就怕自己做不出来。恰好今晚有两个战友，无聊之极，试一试，果断AC了，当然，这题poj的数据比较弱，我去了zoj，依然ac，估计水题没必要出强大数据吧。
期末要考《数据结构》这题给了我很大信心，真的！
很难想象，这是我poj的第206题，呵呵，今晚战胜了心魔，熬夜，值了！！！
贴一个poj上的递推代码，很漂亮。
#include <iostream>
#include <string>
using namespace std;
string f(string s1,string s2)
{
if(s1.length()==1) return s1;
else if(s1.length()==0) return "";
else
{
size_t m=s1.find(s2[0]);
return f(s1.substr(0,m),s2.substr(1,m))+f(s1.substr(m+1),s2.substr(m+1))+s2[0];
}
}
int main()
{
string s1,s2,s;//s1为preorder traversal s2为inorder traversal
while(cin>>s1>>s2)
{
s=f(s2,s1);
cout<<s<<endl;
}
return 0;
}
偷偷把我的代码放到最后，就不解释了吧。。。
/*
* File: main.cpp
* Author: lmm333
* Created on 2010年12月16日
*/
#include <iostream>
#include <string>
using namespace std;
char a[30],b[30];
void f(int a1,int b1,int a2,int b2){
int l,r,p2,i;
char p1=a[a1];
for(i=a2;i<=b2;i++){
if(b[i]==p1)break;
}
l=i-a2;
r=b2-i;
if(l==0);
else if(l==1)
put("%c",b[a2]);
else f(a1+1,i-1,a2,i-1);
if(r==0);
else if(r==1)
put("%c",b[i+1]);
else f(a1-a2+i+1,b1,i+1,b2);
put("%c",b[i]);
}
int main(){
int l;
while(scanf("%s%s",a,b)!=EOF){
l=strlen(a);
f(0,l-1,0,l-1);
puts("");
}
}
http://acm.cist.bnu.edu.cn/contest/problem_show.php?pid=4058
description
ZY最近遇到了一种奇妙的数，这种数可以表示成1 + 2 + 3 + ... + n的和，若每个数代表若干个小球，则将这些小球堆起来，就成了一个三角形(如图)
*
* *
* * *
* * * *
所以这种数被称为是三角数，ZY惊奇地发现任意两个连续的三角数之和是一个平方数，但他还想知道是否三角数本身就可以是一个平方数，于是他苦思冥想，终于找到了几个三角平方数，问题是这样的数存在无限多个吗？于是他又去请教FYJ大牛，FYJ大牛瞬间就秒杀了这个问题，得出了肯定的回答，为了一同膜拜FYJ大牛，ZY请你帮忙编写一个程序，给定输入k,输出第k个三角平方数所对应的平方数
例如,第3个三角平方数为 s = 1 + 2 + 3 + ... + 49 = 1225 = 352.
这题关于 pell数 佩尔数
1 = 1 × 1
6 = 2 × 3
35 = 5 × 7
204 = 12 × 17
可以在右边的两列数中都推出如下的递推式：
P(0)=0
P(1)=1
P(n)=2*P(n-1)+P(n-2)
这个数列被称为是佩尔数，它可以写成如下形式：
((P(k+1)+P(k))*P(k))^2=((P(k-1)+P(k))^2*((P(k-1)+P(k))^2-(-1)^k))/2
附递推代码：
#include <stdio.h>
int main()
{
int T, k, i, x1, x2;
scanf("%d", &T);
while(T--) {
scanf("%d", &k);
x1 = 1, x2 = 1;//x1是第一列 x2是第二列
for(i = 1; i < k; ++i) {
x2 = 2 * x1 + x2;
x1 = x2 - x1;
}
printf("%d\n", x1 * x2);
}
return 0;
}
ps1:关于pell数很好的一篇论文
http://wapedia.mobi/zh/%E4%BD%A9%E5%B0%94%E6%95%B0?t=2.
ps1:几个有名的两项递推数列：
费波那契数:0、 1、 1、 2、 3、 5、 8、 13、 21、 34、 55、 89、 144、 233、 377、 610、 987、 1597、 2584、 4141、 6765等。
卢卡斯数 (Lucas Number):2、 1、 3、 4、 7、 11、18、 29、 47、 76、 123、 199、 322、 521、 843、 1364、 2207、 3571、 5781、 9349 等
佩尔数 (Pell Number):0、 1、 2、 5、 12、 29、 70、 169、 408、 985、 2378、 5741等。
佩尔 - 卢卡斯数 (Pell - Lucas Number) :2、 2、 6、 14、 34、 82、 198、 478、 1154、 2786、 6726等。
其实都是 卢卡斯数列 (Lucas Sequence) 的特殊形式，详见http://baike.baidu.com/view/1327998
身边的同学，做poj的最多，也有做USACO的。
我的风格是以赛代练，所以练习以比赛为主，oj用于搞专题训练。
最近各高校的校赛很多，不少都挂在网上，题目难度都不大，而且很多都能找到解题报告，所以最近一直到寒假开始我准备一这些比赛为主。
另外，cf srm每周都有（本周难得都在周末，而且难得地时间重合，真是尴尬），可以的话尽量做一做，尤其是cf，每次的前两题都是可以做的，还能够练习代码速度，dreamming3000每场都做，所以讨论起来也比较方便。
计划大概就是这样，反正每周至少两场小比赛吧。
附：
cf44官方解题报告，我只做出2题，呵呵
http://codeforces.com/blog/entry/931
