- 1 - Life, the Universe, and Everything[TEST]
模拟题,只需要按照要求做就可以了。 - 2 - Prime Generator[PRIME1]
先用筛法求出范围内的质数,然后对指定的区间再使用筛法就可以了。不需要特别的优化。 - 4 - Transform the Expression[ONP]
中缀转后缀,经典问题,用栈操作就可以了。 - 5 - The Next Palindrome[PALIN]
只需要提取出前半部分,然后累加再判断是否符合要求就可以了。 - 6 - Simple Arithmetics[ARITH]
注意到水平线的长度只和直接相邻的上下两行有关。 - 8 - Complete the Sequence![CMPLS]
见SPOJ 8 - Complete the Sequence![CMPLS]。 - 10 - Complicated Expressions[CMEXPR]
利用中缀转后缀的结果进行去括号是比较稳妥的做法。分析表达式树也是可行的。 - 11 - Factorial[FCTRL]
简单题。 - 14 - I-Keyboard[IKEYB]
见SPOJ 14 - I-Keyboard[IKEYB]。 - 15 - The Shortest Path[SHPATH]
见SPOJ 15 - The Shortest Path[SHPATH]。 - 16 - Sphere in a tetrahedron[TETRA]
见SPOJ 16 - Sphere in a tetrahedron[TETRA]。 - 22 - Triangle From Centroid[TRICENTR]
平面几何题。我们先求出基本的三边长、三条高的长度。然后,建立坐标系,算出外心的坐标。由欧拉线的性质可知,重心到外心的距离是重心到垂心距离的一半,所以可以得到答案。 - 23 - Pyramids[PIR]
与TETRA一题方法一样。 - 24 - Small factorials[FCTRL2]
简单题。 - 25 - Pouring water[POUR1]
见SPOJ 25 - Pouring water[POUR1]。 - 27 - Sorting Bank Accounts[SBANK]
就是简单的排序,用gets()应该可以保证不会超时。 - 29 - Hash it![HASHIT]
Hash表的简单应用。 - 31 - Fast Multiplication[MUL]
高精度乘法,可以使用FFT等算法。其实直接压位也可以过。 - 32 - A Needle in the Haystack[NHAY]
KMP算法就可以过了。不过如果按照题目中给的提示,采用动态内存分配程序似乎有点慢。 - 33 - Trip[TRIP]
动态规划,没什么难度。 - 39 - Piggy-Bank[PIGBANK]
背包问题,动态规划解决之。 - 40 - Lifting the Stone[STONE]
求多边形的重心,一般采用三角剖分做,剖分的中心点往往是原点。 - 42 - Adding Reversed Numbers[ADDREV]
简单题。 - 54 - Julka[JULKA]
简单题。 - 375 - Query on a tree[QTREE]
见SPOJ 375 - Query on a tree[QTREE]。 - 861 - Counting inversions[SWAPS]
见SPOJ 861 - Counting inversions[SWAPS]。 - 1644 - Trees[TREEOI14]
见SPOJ 1644 - Trees[TREEOI14]。
动态规划。我们先预处理出必要的区间段信息,然后发现其满足单调性,于是采用单调性优化。我们使用的是f(x)=min{f(i)+w(i,x)}这一经典模型,二分求出决策就可以了,总的复杂度是。
#include <cstdio> #include <climits> #include <cstring> #include <stack> using namespace std; const int MAXN = 90+5; struct status { int u,b,e; status(int _u,int _b,int _e) : u(_u),b(_b),e(_e) {} status() {} }; char ma[MAXN],mb[MAXN]; int n,m,f[MAXN][MAXN],w[MAXN]; int p[MAXN][MAXN],r[MAXN],g[MAXN][MAXN]; stack<status> st[MAXN]; int tdec[MAXN]; int main() { int ncase; scanf("%d",&ncase); for (int loop = 1; loop<=ncase; loop++) { scanf("%d%d",&m,&n); scanf("%s%s",ma,mb); for (int i = 1; i<=n; i++) scanf("%d",&w[i]); for (int i = 1; i<=n; i++) { g[i][i] = w[i]; for (int j = i+1; j<=n; j++) g[i][j] = g[i][j-1]+w[j]*(j-i+1); } f[0][0] = 0; st[1].push(status(1,1,n)); for (int i = 1; i<=m; i++) { while (!st[i].empty()) { status tmp = st[i].top(); for (int j = tmp.b; j<=tmp.e; j++) p[i][j] = tmp.u; st[i].pop(); } for (int j = i; j<=n; j++) f[i][j] = f[i-1][p[i][j]-1]+g[p[i][j]][j]; if (i<m) { st[i+1].push(status(i+1,i+1,n)); for (int j = i+2; j<=n; j++) { while (!st[i+1].empty()) { int u = st[i+1].top().u; int b = st[i+1].top().b; if (j<=b && f[i][u-1]+g[u][b]>f[i][j-1]+g[j][b]) st[i+1].pop(); else break; } int u = st[i+1].top().u; int e = st[i+1].top().e; if (j<=e && f[i][u-1]+g[u][e]>f[i][j-1]+g[j][e]) { int l = st[i+1].top().b,r = e; // (] while (l+1<r) { int mid = (l+r)/2; if (j<=mid && f[i][u-1]+g[u][mid]>f[i][j-1]+g[j][mid]) r = mid; else l = mid; } st[i+1].top().e = l; st[i+1].push(status(j,l+1,n)); } else if (e+1<=n) st[i+1].push(status(j,e+1,n)); } } } for (int i = m,j = n; i>0; i--) { r[i] = p[i][j]; j = r[i]-1; } r[m+1] = n+1; printf("Keypad #%d:\n",loop); for (int i = 1; i<=m; i++) { printf("%c: ",ma[i-1]); for (int j = r[i]; j<r[i+1]; j++) printf("%c",mb[j-1]); printf("\n"); } printf("\n"); } return 0; }
Your program in C++ from 2010-03-19 08:54:48 ran for 0.53 seconds and used 2792 KB of memory.
题目给出了一个数列的前若干项,要求推测后面的项。我们很容易想到拉格朗日插值法,但是精度就变成了一个大问题。这个问题虽然保证了所有的值都是整数,但是并没有保证其多项式的系数也是整数,因此在计算方面存在很大的困难。
除了插值法,求解这种数列问题我们有更好的差分方法,过程中完全不涉及浮点数操作。比如说,对于1 2 4 7 11 16 22 29这个数列,我们对于每一项做其和前一项的差,也就是2-1=1, 4-2=2, 7-4=3, ....这样,我们得到一个1阶差分:1, 2, 3, 4, 5, 6, 7。我们再求得2阶差分是:1, 1, 1, 1, 1, 1。这时,规律已经有些明显了。
也就是说,对于任意一个存在合理多项式通项的数列,用差分的方法是可以得到它的解的:只要求得这个n项数列的n-1阶差分,然后倒推回去就可以了。代码如下:
#include <cstdio> #include <cstring> using namespace std; const int MAXN = 100+5; int n,m,s[MAXN][MAXN]; int main() { int ncase; scanf("%d",&ncase); while (ncase--) { scanf("%d%d",&n,&m); for (int i = 0; i<n; i++) scanf("%d",&s[0][i]); for (int i = 1; i<n; i++) for (int j = 0; i+j<n; j++) s[i][j] = s[i-1][j+1]-s[i-1][j]; for (int i = 1; i<=m; i++) s[n-1][i] = s[n-1][0]; for (int i = n-2; i>=0; i--) for (int j = 0; j<m; j++) s[i][n-i+j] = s[i][n-i+j-1]+s[i+1][n-i+j-1]; for (int i = 0; i<m-1; i++) printf("%d ",s[0][n+i]); printf("%d\n",s[0][n+m-1]); } return 0; }
Your program in C++ from 2010-03-18 12:22:31 ran for 0.52 seconds and used 2576 KB of memory.
- 可以将构造器的访问权限设置为private。
- 在构造器中调用构造器只能调用一次,且只能放在调用的起始处。
- 初始化的顺序是先静态对象后非静态。
- static的含义:
- 表示该域或方法与任何包含该域或方法的任何对象没有关联。
- 作为方法,不能使用this(意味着不能调用非static方法)。
- 垃圾回收只与内存有关,并不等于析构(finalize()不同于析构函数)。
- Java中没有C/C++的条件编译语句,可以使用import导入不同的包来代替这个功能。
- 在同一个目录中且没有设定所属包的编译单元(文件)被看成属于这个包的“默认包”(Netbeans中叫做“缺省包”)。
- 所有的类都继承自Object这个原始类。
- 与this类似,我们可以使用super来表示一个类的基类,与this具有相同的使用方法。
- 不要滥用继承,组合和代理也是不错的选择,特别是在不需要向上转型时。
- 可以使用@Override注解来防止自己犯没有覆写的错误。
- 向上转型并没有改变一个类本身,比如Base b = new Derived(),b指向的仍然是一个Derived类。这是因为动态的类型本身仅仅由其存储空间决定,所以引用作为一个地址并不影响类型本身。
- 空白final变量必须要使用前被初始化。
- 使用final的原因:
- 锁定方法,防止被继承类修改。
- 写出可以在运行时被确定的代码,从而可以内嵌调用。
- 所有private方法都是隐式final的。
- final类不可以被继承。
Java的输入输出也是基于“流”的概念,和C++采用的概念很相似。流分为输入流(Input Stream)和输出流(Output Stream)两种。
java.io包为我们提供了多种数据流,大致分为字节流和字符流两种。它们的区别在于字节流是以8字节为单位处理文件,而字符流是以16字节为单位。这区别其实就是以byte为单位还是以Unicode码字符为单位,又由于Java本身更倾向于Unicode,所以字符流兼容性会好一点。
下文中的所有类、方法和接口都可以在java.sun.com上找到相关的文档。
字节流主要是从InputStream和OutputStream中派生出的,大致有:
- FileInputStream、FileOutputStream
- PipedInputStream、PipedOutputStream
- ByteArrayInputStream、ByteArrayOutputStream
- FilterInputStream、FilterOutputStream
- DataInputStream、DataOutputStream
- BufferedInputStream、BufferedOutputStream
字节流提供了DataInputStream和DataOutputStream作为数据流的类,可以较方便地读取数据。
而字符流是从Reader和Writer中派生出的,有:
- InputStreamReader、OutputStreamWriter
- FileReader、FileWriter
- CharArrayReader、CharArrayWriter
- PipedReader、PipedWriter
- FilterReader、FilterWriter
- BufferedReader、BufferedWriter
- StringReader、StringWriter
字符流提供的接口和字节流类似,但是把其中的参数换成了字符或者字符数组。
我们可以使用上面的类来建立比较方便的输入输出过程,比如:
BufferedReader buffReader = new BufferedReader(new FileReader(“XXX.xxx”)); BufferedWriter buffWriter = new BufferedWriter(new FileWriter(“XXX.xxx”));
另外Java还提供了Scanner这个封装得很好的类进行读入。经过我的测试BufferedReader、BufferedWriter类的速度并不比C++的速度慢很多,而Scanner相对很慢,但是比较方便。另外,BufferedWriter还可以再放入PrintWriter中(这也是一个字符流的类,对应的字节流类是PrintStream):
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("XXX.xxx")));
而PrintWriter封装得也很好,和System.out的使用差不多。