richard-desktop

• 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.

1. 可以将构造器的访问权限设置为private。
2. 在构造器中调用构造器只能调用一次，且只能放在调用的起始处。
3. 初始化的顺序是先静态对象后非静态。
4. static的含义：
   • 表示该域或方法与任何包含该域或方法的任何对象没有关联。
   • 作为方法，不能使用this（意味着不能调用非static方法）。
5. 垃圾回收只与内存有关，并不等于析构（finalize()不同于析构函数）。
6. Java中没有C/C++的条件编译语句，可以使用import导入不同的包来代替这个功能。
7. 在同一个目录中且没有设定所属包的编译单元（文件）被看成属于这个包的“默认包”（Netbeans中叫做“缺省包”）。
8. 所有的类都继承自Object这个原始类。
9. 与this类似，我们可以使用super来表示一个类的基类，与this具有相同的使用方法。
10. 不要滥用继承，组合和代理也是不错的选择，特别是在不需要向上转型时。
11. 可以使用@Override注解来防止自己犯没有覆写的错误。
12. 向上转型并没有改变一个类本身，比如Base b = new Derived()，b指向的仍然是一个Derived类。这是因为动态的类型本身仅仅由其存储空间决定，所以引用作为一个地址并不影响类型本身。
13. 空白final变量必须要使用前被初始化。
14. 使用final的原因：
    • 锁定方法，防止被继承类修改。
    • 写出可以在运行时被确定的代码，从而可以内嵌调用。
15. 所有private方法都是隐式final的。
16. 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的使用差不多。