小数的分数逼近，题目的思路是挺简单的，假设A=N/D，那么N=[D*A]或者N=[D*A]+1，按照这个公式对D进行枚举，不断更新最佳值即可。下面是我的WA的代码：

#include <stdio.h>
#include <math.h>

int main(int argc, char *argv[])
{
    double A;
    int L;
    int N, D;
    double delta;
    double min;
    
    while (scanf("%lf%d", &A, &L) != EOF)
    {
        min = 10 * L;

        int i;
        
        for (i = 0; i * A <= L && i <= L; ++i)
        {
            int temp_D = i;
            int N1 = (int) i * A;
            double delta1 = fabs(A - (double) N1 / i);

            int N2 = (int) i * A + 1;
            double delta2 = fabs(A - (double)N2 / i);

            if (delta1 < delta2 && delta1 < min)
            {
                D = temp_D;
                N = N1;
                min = delta1;
            }
            else if(delta1 > delta2 && delta2 < min)
            {
                D = temp_D;
                N = N2;
                min = delta2;
            }
        }

        printf("%d %d\n", N, D);
    }
    
    return 0;
}

由于没有测试数据，所以也不知道这道题目究竟错在哪里。我也找来了AC的代码：

#include<stdio.h>
#include<math.h>

int main(void)
{
    double min;
    double A;
    long i;
    long j;
    long N;
    long D;
    long L;
    long pd;
    long pn;

    while (scanf("%lf %ld", &A, &L) != EOF)
    {
        pn = -999999;
        pd = 1;
        min = 9999999;

        for (D=1; D<=L; ++D)
        {
            N = (long)(D * A);
   
            if (N > L)
            {
                break;
            }
   
            for (i=0; i<=1; ++i)
            {
                if (fabs(min - A) > fabs((double)(N+i)/(double)D - A))
                {
                    pn = N+i;
                    pd = D;
                    min = (double)(N+i)/(double)D;
                }
            }
        }
  
        if (pn == -999999)
        {
            for (D=1; D<=L; ++D)
            {
                for (N=1; N<=L; ++N)
                {
                    if (fabs(min - A) > fabs((double)N/(double)D - A))
                    {
                        pn = N;
                        pd = D;
                        min = (double)N/(double)D;
                    }
                }
            }
        }
  
        printf("%ld %ld\n", pn, pd);
    }

    return 0;
}

但是这段AC的代码在输入3.33 9的时候给出的答案是10 3，显然是错误的答案。困惑中。求高人指点。

奋斗了一个星期，用了各种卑鄙无耻的手段（比如有些代码看懂之后就不再自己写了直接提交ac），终于凑够了150道题目，获得了zoj暑期选拔新手上路的资格。关于新手上路，大概意思就是利用六月月赛和周末散场选拔赛筛选出28人左右的队伍进入校队参加暑期集训。不过我对这个基本不抱太大的期望，毕竟我清楚自己的斤两，尽力而为吧。有这个新手上路的资格已经很不错了（虽然掺杂了很多不诚实的成分……我承认，我以后搞不了学术，因为我不够诚实，有时太过功利……）

业余更新了gentoo系统到testing state，安装了gnome 2.30，暂时告别fvwm-crystal（因为某些细节不够完美——我也不会配置，没有时间学）。中途碰上了各种包依赖性问题，进一步了解了portage和gentools。

LInuaApp版主转正，有个材化学院的博士生chxb找到了我帮忙装一个分子计算的软件Material Studio，装过的过程一波三折，首先是他要装opensuse，我看了半天也没装上，就建议他装最新出来的ubuntu 10.04，最终在我的帮助下，以硬盘安装的形式成功装了ubuntu 10.04——这也是我第一次尝试硬盘安装，以前嫌麻烦，都是用u盘或者光盘的，其实也没有想象中那么麻烦。第二天chxb告诉我说软件装不上，于是我又帮忙分析原因，搞七搞八搞了一个多小时，原来是系统中没有csh的原因——因为安装脚本的开头写着"#!/bin/csh"……我琢磨这软件也太user-friendly了，即便是安装失败，起码给个提示……于是我搞定了ubuntu的软件源，一条sudo apt-get install csh后软件就成功地进入了安装界面……chxb泪流满面，握着我的手说：“兄弟啊，你可真是高手……从去年开始那个安装失败的界面我不知道看了有多少次了，你一到就手到擒来，太感谢了”……恭维得我浑身起毛——就我这点斤两，只有自己清楚。第三次呢，是软件装上了却跑不起来。于是我又帮忙分析程序脚本，大概看懂了叫本的意思，最终定位到问题出在软件中自带的perl解释器上。果不其然修改了脚本用了系统的/usr/bin/perl后，程序就呼呼地跑了起来，结果又是一痛恭维——说我这样的人才不读博士可惜了云云……但是软件的并行始终没有搞出来，算是一点遗憾。

原先我觉得我很菜，觉得要申请版主一定要精通c++、bash、python，acm过硬，有了LPI证书云云，其实也不是，论坛的作用就在交流，交流中学习进步，这才是学习之道。就像这次安装程序，老实说我略懂bash，对perl一点不懂，也从未尝试过硬盘安装，不过这些问题都被我顺利的定位解决，可见，知识是死的，方法是活的，勇于尝试交流才能进步。有时自己是太好面子了。

周六的时候zjg的tank告诉我说自己的xp浏览器被劫持了。于是我尝试着远程桌面帮她修电脑（远程桌面也是第一次玩），参考百度文库上的教程，没想到一次就成功了。想来ms的东西做的还真是挺user-friendly的。看现象大概是浏览器劫持，自己照着教程改了改注册表，重启了几次也没有好——这时我又想起linux的好处了，真是吃里扒外的东西。最后下了金山网盾，随便搞了搞，竟然搞好了，于是又是一番恭维——由此得出会修电脑软件的男生骗起来小女生还是挺容易的，呵呵。

晚上又收到了mike的邀请，问我有没有兴趣参与ibus-sunpinyin的一些工作，我当然求之不得。对于mike本人，我还是挺崇拜的，当我还在宿舍通宵安装xp的时候，人家已经是cc98linux版主了。虽然有时我不太欣赏其略显傲慢的姿态，不过我欣赏这种姿态背后的资本。百度了下ibus-sunpinyin，发现这个项目在linux输入法中算是后起之秀，鼎鼎大名了。下载了源代码，看到了很多.py文件，计划着什么时候了解下python。不过对于输入法来说我是个门外汉，看项目主页上的说明，感觉难度不小，加上我最近也实在没时间，就回复说等暑假再看。

有对比就有差距，类似于ibus-sunpinyin还有一个ibus-sougoupycc，是quark发起的，也是很受欢迎很有前途的一个输入法项目。记得大一时用过的ZJG上网软件，用了之后感觉颇为不错，最后发现这个软件的作者竟然是和我一届的quark。现在，mike、quark都是我的同班同学，有对比就有差距，有差距就用动力，一点一点来吧。

新的星期，要开始回归课业了——因为六月底要开始考试了，具体来说自己还有编译、网络、j2ee三个project没有开始着手，一堆作业要补，3－4场的新手上路选拔比赛，再熬一个月。暑假打算买个mac本本。能进校队当然好，否则的话也该开始着手准备实习了。恩，繁忙充实的生活总是好的。^_^。

在实验室睡了一宿。昨儿一激动改了/etc/make.conf：

ACCEPT_KEYWORDS="~x86"

主要是想体验一下传说中的gnome 2.30和gnome shell，探索半天才知道我原来的gentoo用的是stable version，这样一改就改成“以后要用testing version"。

sudo emerge -avuND world

这下好了，乖乖，总共有573个软件包要更新，需要下载1.7G的东西。天知道这1.7G的代码在我的本本上要编译多长时间。不过，量小非君子，无毒不丈夫，索性心一横，就输了yes，让本本自己在那边呼啸去了。

编译到170左右个包时出现了麻烦，libmtp无法编译，我一看是因为其依赖的libpng是1.2版本的，而gentoo testing version的libpng是1.4版本的，这样来来回回搞了许久，终于在google上找到了这篇文章，暂且解决了这个问题。

折腾期间又扫了一眼emerge man page，了解了几个有用的参数如：

• --skip-first
• --keep-going
• --resume

中途还有几个blocked的包，解决方法大概是先uninstall再reinstall，一般就行了；再不行看看USE参数，略微改一下，总之，元发行版，麻烦与灵活共存。

编译的过程emacs死掉了，于是再也无法打开^~~^……就这能干看一些题目。zoj 1372，第一眼一看就是图论的题目。反正也是闲着，临阵磨枪，找来了算法导论，补补图论的基础知识。进一步了解了BFS和DFS，看懂了最小生成树的Prim算法，并参照着别人的代码，采用邻接矩阵的方式，还AC了。真实不容易啊。不过收获也是大大的。

代码： 

#include <iostream>
#include <string>
using namespace std;

const long max_points = 100;
const long infinity = 1000001;

int p, r, length, g[max_points][max_points];
bool flag;

class vertex
{
public:
    int distance;
    bool visited;
};

vertex v[max_points];

void initial()
{
    for(int i = 1; i <= p; i++)
        for(int j = 1; j <= p; j++)
            g[i][j] = infinity;
}

void prim(int origin)
{
    int temp_min;
    int temp_v = 0;
    int sum = 0;

    for(int i = 1; i <= p; i++)
    {
        v[i].distance = g[i][origin];
        v[i].visited = false;
    }

    v[origin].distance = 0;
    v[origin].visited = true;

    sum++;

    while (sum < p)
    {
        temp_min = infinity;
        for(int i = 1; i <= p; i++)
            if(v[i].visited == false && v[i].distance < temp_min)
            {
                temp_min = v[i].distance;
                temp_v = i;
            }
        
        if(temp_min < infinity)
        {
            length += v[temp_v].distance;
            v[temp_v].visited = true;
            sum++;
        }
        else
        {
            flag = true;
            break;
        }

        for(int i = 1; i <= p; i++)
        {
            if(v[i].visited == false && v[i].distance > g[i][temp_v])
            {
                v[i].distance = g[i][temp_v];
            }
        }
    }
}

int main(int argc, char *argv[])
{
    int a, b, c;

    while(cin >> p)
    {
        if(p == 0)
            break;
        cin >> r;

        initial();

        for(int i = 0; i < r; i++)
        {
            cin >> a >> b >> c;
            if(c < g[a][b])
                g[a][b] = g[b][a] = c;
        }
        length = 0;
        prim(1);

        cout << length << endl;
    }

    return 0;
} 

简单题，不知道为什么开始WA了一下。

题目大意是给定一组n个数，那么共有n(n-1)/2个数对，求出所有的互质数对，就是这样。gcd的写法还是值得背下来的。

代码：

#include <stdio.h>
#include <math.h>

int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}

int main(int argc, char *argv[])
{
    int num;
    int inta[60];
    int i, j;
    int result;

    while (scanf("%d", &num))
    {
        if (num == 0)
        {
            break;
        }
        
        for (i = 0; i < num; ++i)
        {
            scanf("%d", &inta[i]);
        }

        result = 0;
        
        for (i = 0; i < num; ++i)
        {
            for (j = i + 1; j < num; ++j)
            {
                if (gcd(inta[i], inta[j]) == 1)
                {
                    result++;
                }
            }
        }

        if (result == 0)
        {
            printf ("No estimate for this data set.\n");
        }
        else
        {
            printf ("%.6lf\n", sqrt(3.0*num*(num-1)/result));
        }
        
    }
    
    return 0;
}

时间紧迫，继续水题……太不道德了……

题意很明确，给定一个数列[tex]a_i(i = 0, 2, \cdots, n)[/tex]， 对于[tex]m[/tex]，求有多少个partial sum能被m整除，所谓partial sum是[tex]\sum_{i = j}^{k} a_i, j, k \in 1, \cdots n}[/tex]。

想法也很简单。第一种方法是求出所有的partial sum，然后分别判断是否能被m整除，[tex]O(n^3)[/tex]的复杂度。

第二种想法是设定[tex]\sigma_j = \sum_{i=0}^{j} a_i, j = 0, 1, 2, \cdots, n}, \delta_{ij} = \sigma_j - \sigma_k = \sum_{i = k+1}^{j}a_i[/tex]，判断[tex]\delta_{ij}[/tex]能否被[tex]m[/tex]整除。[tex]O(n^2)[/tex]复杂度。照此想法编程，确是TLE：

#include <stdio.h>

#define max_len 10001

int main(int argc, char *argv[])
{
    int n, m;
    int inta[max_len];
    int sum[max_len+1];
    
    while (scanf("%d%d", &n, &m) != EOF)
    {
        int i, j;

        for (i = 0; i < n; ++i)
        {
            scanf("%d", &inta[i]);
        }

        for (i = 0; i <= n; ++i)
        {
            sum[i] = 0;
            for (j = 0; j < i; ++j)
            {
                sum[i] += inta[j];
            }
        }

        int num = 0;
        for (i = 0; i < n; ++i)
        {
            for (j = i + 1; j <= n; ++j)
            {
                if (((sum[j] - sum[i]) % m) == 0)
                {
                    num++;
                }
            }
        }
        printf ("%d\n",num);
    }
    
    return 0;
}

不得不另寻出路。依稀记得当初算法课上关于最大子段和的问题，其复杂度也是一点点从[tex]O(n^3) -> O(n^2) -> O(n \log(n)) -> O(n)[/tex]，在此百度如下两篇文章，茅塞顿开：

• http://hi.baidu.com/hi_chf/blog/item/50017817903f0e11972b43e9.html
• http://bloodybat.blog.hexun.com/2788438_d.html

 大体思路是继续第二种想法，设[tex]\phi_j = \sigma_j \bmod m[/tex]，如果存在[tex]j_k, k = 1, 2, \cdots, n[/tex]，那么[tex]\phi_{j_k} - \phi_{j_s}[/tex]表示一个符合条件的partial sum，此类partial sum可以利用组合数公式[tex]c(n, 2) = \frac{n(n-1)}{2}[/tex]求出。最后注意考虑0这个特殊数字的情况。程序参照上面两篇博客整理下，代码如下： 

#include <string.h>
#include <stdio.h>

int c_sum[5001];

int main ()
{
    int i, n, m;
    int temp, sum, num;
    
    while (scanf("%d %d", &n, &m) != EOF)
    {
        sum = 0, num = 0;
        memset(c_sum, 0, sizeof(int) * (m + 1));
        for (i = 0; i < n; i++)
        {
            scanf("%d", &temp);
            sum = (sum + temp) % m;
            if (!sum)
                num++;
            c_sum[sum]++;
        }
        for (i = 0; i < m; i++)
            num += c_sum[i] * (c_sum[i] - 1) / 2;
        printf ("%d\n", num);
    }
    return 0;
}

路漫漫其修远兮，加油加油。