Mar 20
  • 1 - Life, the Universe, and Everything[TEST]
    模拟题,只需要按照要求做就可以了。
  • 2 - Prime Generator[PRIME1]
    先用筛法求出$\sqrt{n}$范围内的质数,然后对指定的区间再使用筛法就可以了。不需要特别的优化。
  • 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]
Mar 20

动态规划。我们先预处理出必要的区间段信息,然后发现其满足单调性,于是采用单调性优化。我们使用的是f(x)=min{f(i)+w(i,x)}这一经典模型,二分求出决策就可以了,总的复杂度是$O(KL\log L)$

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

Mar 19

题目给出了一个数列的前若干项,要求推测后面的项。我们很容易想到拉格朗日插值法,但是精度就变成了一个大问题。这个问题虽然保证了所有的值都是整数,但是并没有保证其多项式的系数也是整数,因此在计算方面存在很大的困难。

除了插值法,求解这种数列问题我们有更好的差分方法,过程中完全不涉及浮点数操作。比如说,对于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.

Mar 14
  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类不可以被继承。
Mar 11

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的使用差不多。