The Fourth Dimension Space

积性函数的一些证明(转)

在数论中的积性函数。对于正整数n的一个算术函数f(n)，当中f(1)=1且当a,b互质，f(ab)=f(a)f(b)，在数论上就称它为积性函数。

证明： f(n) = ∑g(d)^3 (d | n, g(d)表示d的约数个数）

求证: f(n) 是积性函数，即f(1) = 1, f(ab) = f(a) * f(b); a,b互质

(1)f(1) = g(1)^3 = 1 ^ 3 = 1

(2)f(n) = f(a) * f(b);

f(n) = ∑g(d)^3 (d | n, g(d)表示d的约数个数）

f(a) = ∑g(p)^3 (d | a, g(p)表示p的约数个数）

f(b) = ∑g(q)^3 (d | b, g(q)表示q的约数个数）

证明f(n) = f(a) * f(b)即证明∑g(d)^3  = ∑g(p)^3 * ∑g(q)^3

假设 d = p * q; //d为n中的某个约数，p为a中的某个约数，q为b中某个约数，总存在d = p * q

现需证明g(d)^3 = g(p)^3 * g(q)^3;

g(p)^3 * g(q)^3 = (g(p) * g(q)) ^ 3

////////////////////////////////////////////

将d质因数分解： d = p1^a1 * p2^a2 ……pj^aj

将p质因数分解： p = p1^b1 * p2^b2 ……pj^bj

将q质因数分解： q = p1^c1 * p2^c2 ……pj^cj

其中a1 = b1 + c1 , a2 = b2 + c2，…… aj = bj + cj;

因为p,q互质，所以ai = bi + ci中要么(bi == ai && ci == 0) ||  (ci == ai && bi == 0)这两种情况

g(d) = (a1 + 1) * (a2 + 1) * ……*(aj + 1);

g(p) = (b1 + 1) * (b2 + 1) * ……*(bj + 1);

g(q) = (c1 + 1) * (c2 + 1) * ……*(cj + 1);

所以g(d) = g(p) * g(q);

==> g(d)^3 = g(p)^3 * g(q)^3;

==> ∑g(d)^3  = ∑g(p)^3 * ∑g(q)^3

==> f(n) = f(a) * f(b)

从而得证f(n)是积性函数

f(n) = f(p1^a1) * f(p2 ^ a2) * f(p3 ^ a3) …… * f(pj^aj);

f(p1^a1) = ∑g(d)^3 (d | p1 ^ 3) 由p1是质因数

所以d的取值为p1^0, p1 ^ 1, p1^2, ……，p1^a1

g(p1^i) = i + 1;

故f(p1^a1) = (0 + 1) ^ 3 + (1 + 1) ^ 3 + …… + （a1 + 1) ^ 3 = (a1 + 1)^2 * (a1 + 2)^2 / 4;

以此类推，

所以最终f(n) = f(p1 ^ a1) * f(p2 ^ a2) * …… * f(pj ^ aj)

            = ((a1 + 1)^2 * (a1 + 2) ^2 / 4) * ((a2 + 1)^2 * (a2 + 2)^2 / 4) * …… *

                （(aj + 1)^2 * (aj + 2)^2 / 4);

将n质因数分解后进行统计即可。（本人代码效率不行，如果谁有更有效率的代码麻烦给我一个，让我学习学习）。

////////////////////////////////////////////////////////////////


转自：http://blog.sina.com.cn/s/blog_5c95cb070100ej4c.html

posted @ 2009-11-02 18:30 abilitytao 阅读(507) | 评论 (0) | 编辑 收藏

POJ 3219 二项式系数(数论，简单)

之所以要写个解题报告，不是因为这道题很难，而是因为一眼居然没看出来是统计质因数2出现的次数，太nc了，为了把公式记得牢一点，遂写此文~

题目意思很简单，就是让你求组合数C(n,k)是奇数还是偶数。
C(1, 0) = C(1, 1) = 1；
C(n, 0) = 1对于所有n > 0；
C(n, k) = C(n − 1, k − 1) + C(n − 1, k)对于所有0 < k ≤ n。
对于上述描述，可以直接无视之。。。

由于组合数C(n,k)=         n!
                                    ---------
                                     k!(n-k)!

posted @ 2009-11-01 01:43 abilitytao 阅读(469) | 评论 (0) | 编辑 收藏

POJ 1150 ——The Last Non-zero Digit(数论)

The first program

Consider the number N! factored into product of powers of prime numbers. It means N!=2ⁱ * 3^j * 5^k * 7^l * ... Note, that for each N>1 the power i is greater than k. It means, that the last non-zero digit of N! is the same as the last digit of N! / (2^k * 5^k). Therefore we can compute the result using the equation:

Number i can be obtained easily - we will divide each a=1,2,...,N by 2 until the resulting number is not divisible by 2 and after each division we will add one to the variable i. Number k can be obtained in the same manner. Let f(i) denotes the number which we obtain by dividing i by the 2^a * 5^b where a and b are the highest numbers such that the i is divisible by this product. Number (N! / (2ⁱ * 5^k)) mod 10 is equal to f(N!) mod 10 and can be computed as f(1) * f(2) * ... * f(N) mod 10. We will perform operation mod 10 after each multiplication in order to keep the resulting number as small as possible.

The advantege of this approach is that we do not need to implement arithmetics of large numbers. Some ideas used here are used in the second, more efficient program, as well.

The second program

The second program also computes the result as (2^i-k mod 10 * f(N!) ) mod 10. Numbers i and k are computed much more efficiently. More precisely

(We get zero after finite number of divisions.) Number k can be computed in the same way. After that we can compute i-k and we need to find 2^i-k mod 10. Observe, that

i.e. the period is 4 and we need only to compute (i-k) mod 4 and then to find corresponding last digit. This observation can help us to simplify computation of i and k - we do not need their exact values (that can be long) but we need only (i-k) mod 4.

We have shown how to compute 2^i-k mod 10. Now let us consider f(N!) mod 10 = ((f(1) mod 10) * (f(2) mod 10) * ... * (f(N) mod 10)) mod 10. Note, that f(i) mod 10 is always 1,3,7 or 9. If we knew, how many 3,7,9 are among (f(1) mod 10), (f(2) mod 10), ..., (f(N) mod 10), we could compute 3^a mod 10, 7^b mod 10, 9^c mod 10 in the similar way as we did for 2^i-k (last digits of powers of 3,7,9 are also periodical).

To compute the number of 3,7,9 among (f(1) mod 10), (f(2) mod 10), ..., (f(N) mod 10) is not so easy. We will divide numbers 1,2,...,N into groups so, that in each group are numbers with same quotient i/f(i) and we will compute number of 3,7,9 among (f(i) mod 10) for each such group separatelly (there are O(N²) such groups). First, let us consider a group in which i/f(i)=1. This is the group of all numbers not divisible by 2 and 5. The number of 3,7,9 in this group is the same as number of 3,7,9 among 1 mod 10, 2 mod 10, ..., N mod 10. This number can be counted easily - it is N div 10 + a where a is 1 if the last digit of N is at least 3 (resp. at least 7 or at least 9). Now let us consider a group in which i/f(i)=L (where L=2^a * 5^b). We obtain this group by taking each L-th number from the sequence 1,2,3,... and dividing it by L. It means that number of 3,7,9 for this group will be the same as the number of 3,7,9 among 1 mod 10, 2 mod 10, ..., (N div L) mod 10.

Now we know everything we needed for construction of a program. Since numbers in the input file are long, we need to implement arithmetics for long numbers. However, by careful implementation we can achieve that only division of a long number by small integer is necessary.



这个题怎么来做呢？先别急，我们先来讨论一下下面几个子问题：
1.如何求出n阶乘中质因数x(比如说5）出现的次数？
比如说15的阶乘 ：1*2*3*4*5*6*7*8*9*10*11*12*13*14*15
由于5这个质因数只在5的倍数里面才出现，所以我从5，10，15中各抽出一个5，这相当于有15/5个质因数5,之后5，10，15就变成了1，2，3；
由于非5的倍数显然不在考虑范围之内，所以我们只需继续讨论它的子问题3！即可。
这样，我们可以用递归来解决这个问题。有了这个方法，我们是不是能够轻易地解决n!末尾有多少个0呢？想想看...n!后0的个数是不是就和某个质因数的个数有关呢？^_^
比如说，我们要求5出现的次数，可以这样写：

int get5(int n)//计算n!中质因子5的出现次数
{
    if(n==0)
        return 0;
    return n/5+get5(n/5);
}

 2.如何求出n!阶乘最后非0位？
比如说我们要找10!最后非0位，由于质因数2和5组合之后会使得末尾产生0.那么我们不妨把10！中2，5质因数全部去掉，（但是请注意2的数目其实比5的要多，所以我们要在最后考虑多余的2对末位的影响）
如 1*2*3*4*5*6*7*8*9*10 去掉2 ，5 因子后 就是1*1*3*1*1*3*7*1*9*1，由于2，5因子已经被去除，那么剩下的数字末尾一定是3，7，9，1中四者之一。然后我们再求出这么一串数相乘以后末尾的数是几.最后再补上2对末位的影响即可！

总结一下，求10!最后一个非0位的步骤如下：
step1：首先将10!中所有2，5因子去掉；
step2：然后求出剩下的一串数字相乘后末尾的那个数。
step3：由于去掉的2比5多，最后还要考虑多余的那部分2对结果的影响。
step4：output your answer!

一个数列实际上可以分成偶数列和奇数列，以1*2*3*4*5*6*7*8*9*10为例

分成1 3 5 7 9,   2 4 6 8 10

这样我们尝试分别进行统计，可以发现，实际上2，4，6，8，10中的个数也就是1 2 3 4 5中的个数，也就是说我们又把这个问题划分成了一个原来问题的子问题。

f(n) = f(n/2) + g(n),g(n)表示奇数列中的数目，所以我们需要解决g(n)

再次观察g(n)

实际上又分成了两部分1 3 7 9 11 13 17 19 21。。。以及5的奇倍数5，15，25。。。说明又出现了子问题,如果要统计这个数列中末尾为x（1，3，7，9）的个数可以这样写：g(n,x) = n/10+(n%10 >= x)+g(n/5,x) 

这样利用了两个递归方程，我们就可以在lgn的时间内计算出末尾为1,3,7,9的数的个数了

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

int get2(int n)//计算n!中质因子2的出现次数
{
    if(n==0)
        return 0;
    return n/2+get2(n/2);
}

int get5(int n)//计算n!中质因子5的出现次数
{
    if(n==0)
        return 0;
    return n/5+get5(n/5);
}

/**///////////////////////////////////////////////////////////////////////////
int g(int n,int x)//计算f(1) to f(n) 中，奇数数列中末尾为x的数出现的次数
{
    if(n==0)
        return 0;
    return n/10+(n%10>=x)+g(n/5,x);
}

int getx(int n,int x)//计算f(1) to f(n)中，末尾为x的数的出现次数
{
    if(n==0)
        return 0;
    return getx(n/2,x)+g(n,x);
}
/**///////////////////////////////////////////////////////////////////////////

int table[4][4] =
{
        6,2,4,8,//2^n%10的循环节，注意如果2的个数为0时候，结果应该是1，要特殊处理。 
        1,3,9,7,//3
        1,7,9,3,//7
        1,9,1,9,//9    
};//3，7，9的循环节中第一位，刚好是1，故不需要考虑这些数字出现次数为0的情况。


int main()
{

    int n,m;
    int num2;
    int num3;
    int num5;
    int num7;
    int num9;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        num2=get2(n)-get2(n-m);
        num5=get5(n)-get5(n-m);
        num3=getx(n,3)-getx(n-m,3);
        num7=getx(n,7)-getx(n-m,7);
        num9=getx(n,9)-getx(n-m,9);
        int res=1;
        if(num5>num2)
        {
            printf("5\n");
            continue;
        }
        else 
        {
            if(num2!=num5)
            {
                res*=table[0][(num2-num5)%4];
                res%=10;
            }//如果num2==num5,那么2^0次方mod 10应该为1 ，而不是table中的6,所以要特殊处理。
            
            res*=table[1][num3%4];
            res%=10;
            res*=table[2][num7%4];
            res%=10;
            res*=table[3][num9%4];
            res%=10;
        }
        printf("%d\n",res);
    }
    return 0;
}

posted @ 2009-10-31 19:07 abilitytao 阅读(3578) | 评论 (8) | 编辑 收藏

POJ 2478 Farey Sequence(欧拉函数的应用)

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;


//基于素数筛选法，计算欧拉函数phi[1] to phi[MAX],复杂度约为n，很快
//传入三个数组:
//phi[]用于存放欧拉函数
//prime[]用来存放小于i的所有素数，这里其实是一个模拟堆栈
//isprime[]用来标志该数是不是素数，初始值为0
/**/////////////////////BEGEIN_TEMPLATE_BY_ABILITYTAO_ACM/////////////////////////
#define MAX 1000000
__int64 phi[MAX+1]={0};
__int64 prime[MAX+1]={0};
bool isprime[MAX+1]={0};
void get_phi()//这是一个基于素数筛选的线性算法，很快
{
    __int64 i,j;
    __int64 len=0;
    for(i=2;i<=MAX;i++)
    {
        if(isprime[i]==false) //false代表是质数
        {
            prime[++len]=i;
            phi[i]=i-1;
        }
        for(j=1;j<=len&&prime[j]*i<=MAX;j++)
        {
            isprime[prime[j]*i]=true;//true代表是合数
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];  
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
/**//////////////////////END_TEMPLATE_BY_ABILITYTAO_ACM///////////////////////////////

__int64 s[MAX];
int main()
{
    __int64 i;
    phi[1]=0;
    get_phi();
    for(i=2;i<=MAX;i++)
        s[i]=s[i-1]+phi[i];
    while(1)
    {
        scanf("%I64d",&i);
        if(i==0) break;
        printf("%I64d\n",s[i]);
    }
    return 0;
}

posted @ 2009-10-30 13:41 abilitytao 阅读(1670) | 评论 (0) | 编辑 收藏

pku 3164 最小树形图(Zhu-Liu Algorithm)

posted @ 2009-10-29 19:38 abilitytao 阅读(2163) | 评论 (2) | 编辑 收藏

TopCoder竞赛：C++, STL 用法快速入门（转）

下面总结了一些题目中常用的STL库的用法。

 
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <iostream>
 
using namespace std;
 
//递归
int GetN(int n)
{
if (n==1) return 1;
else return GetN(n-1);
}
 
void TestSTL_main( int argc, char* argv[] )
//void main( int argc, char* argv[] )
{
/******** STL **********/
 
//string的用法
{
string s = "mmmmm";
string s2("ss22");
s2.insert(2,"kkkkk"); //把"kkkkk"插到s2的第2个位置之前（位置从0开始）
s2+=s+"44444"+'c';
const char *pc = s.c_str();//把string转成C-style的string,以\0终了
const char *ptr1 = s.data();;//把string转成字符串
if (s2[2] == 'k') s2[2]='C';
s+="jkl";
s+='m';
s.push_back('\n'); //把'\n'（换行符）放在s的最后一个位置
reverse(s.begin(), s.end()); //反转
basic_string <char>::iterator str_Iter; //遍历
str_Iter = s.begin();
}
 
//vector的用法
{
vector<int> v;
v.push_back(8); //向v中插入元素，元素的值是8
int iLen = (int)v.size();
for(int i=0;i<iLen;i++)
{
int k = v[0]; //k==8
}
}
 
//map的用法
{
map<int, int> mp;
for(int i=0;i<3;i++)
{
mp[i]=i*2; //通过[第一个元素]来访问第二个元素
}
 
int total = 100;
map<int, int>::iterator it = mp.begin();
for(;it!=mp.end();it++) //遍历mp
{
total+=it->second; //通过iterator it来访问第二个元素
}
cout<<"total="<<total<<endl;
}
 
//算法
int n = GetN(5); //递归n!=n*(n-1)*(n-2)*…*1
int aa=10,bb=15;
int maxi = max(aa,bb); //最大值
int mini = min(aa,bb); //最小值
int absi = abs(-12); //绝对值
vector<string> v;
v.push_back("hello");
v.push_back("123");
v.push_back("no");
sort(v.begin(),v.end()); //按照字母顺序，把v里面的元素排序
int savei;
sscanf(v[0].c_str(), "%d", &savei); //把字符串“123”转换成数字123
cout<<"savei="<<savei<<endl;
char buf[100];
sprintf(buf,"v[1]=%d",savei); //把内容打印进字符串
cout<<"buf="<<buf<<endl;
 
}

posted @ 2009-10-27 15:35 abilitytao 阅读(740) | 评论 (2) | 编辑 收藏

TOPCODER入门教程(转)

本文根据经典的TC教程完善和改编。
TopCoder：http://www.topcoder.com/

基本规则
TopCoder的比赛类型很多，最常见的是周赛SRM（Single Round Match），另外还有TCHS SRM（TopCoder High School SRM，题目和SRM一样，仅限中学生参加，参赛者水平较低，据说涨rating很容易），马拉松（Marathon Matchs），还有TCOpen（每年两次的大比赛）之类的比赛。因为大多数人都在做SRM，所以本文介绍的TC比赛即为SRM。
SRM的规则总结起来就是一句话：75分钟做完3道难度递增的题。
TC的每个用户（handle）都有自己的积分（rating），从0-3000+不等。成绩越好，分数越高。
积分与颜色的对应为：白色——未参赛（unrated）；灰色——0~899；绿色——900~1199；蓝色——1200~1499；黄色——1500~2199；红色——2200+。另外排名最高的几个人在TC客户端中会变成红色靶子图标。
比赛分为两个Division，Div I和Div II。白色灰色和绿色的参加Div II，蓝色黄色和红色的参加Div I。Div I的题要比Div II难许多，一般DivII的最后一题和Div I的第一或第二题是一样的。无论是Div I或Div II。三道题目的Score一般为250, 500和1000。
TC的计分规则很诡异，可以见http://www.topcoder.com/wiki/display/tc/Algorithm+Competition+Rating+System，但基本是没人看的懂。不过，TC积分规则的基本思想很简单。
首先是SRM每道题的计分规则。题目从打开开始计时，随着时间的流逝，你这道题目可能得到的分数也越来越少。不过分数减少的速率会逐渐变慢（有人说是先快后慢再快再慢，我不清楚到底哪个是对的，不过总体趋势是越来越慢），一般1000分的题目在降低到300分的时候就基本不会再下降太多了。每道题点击Submit才算正式提交，如果Submit之后发现错误，还可以再次点击Submit修改提交，不过这样会扣除这道题一定的分数。
其次是TC的计分规则。复杂的数学公式很难看懂，但大概的计分思想是：根据此次比赛的得分算出一个这次比赛的rank，然后和以前的rank做比较，求出一个期望的rank，再根据这个期望的rank调整rating。而有时也会出现考得很砸但依然涨rating的情况，不过总体来说TC的计分公式是十分稳定的。

运行环境
TC的客户端是一个Java程序，所以需要JRE（Java Runtime Environment）或者JDK（Java Development Kit）来运行。如果平时不写Java程序的话，装JRE就可以了。毕竟JDK比JRE大一个数量级，下载慢。安装照着提示完成就行了。推荐使用1.4.1以后的版本，因为带了java web start，可以快速登陆。具体方法下一部分讲。
JRE下载地址（中文）：http://www.java.com/zh_CN/download/index.jsp

注册
原文在注册的地方没有详细说明，但很多人似乎对注册都有疑问。所以这里我来注册一个小号，并通过整个过程讲解如何注册。
首先打开http://www.topcoder.com/tc（本文后面TopCoder的主页都指这个网址），然后点击右上角的Register Now（没看到？你可能看到了一个Login，目光向下挪一点，那个红底白字的“Register Now”就在下面）。接下来会弹出http://www.topcoder.com/reg这个页面，因为我们要参加SRM，所以选择第一个，Competition Registration。如果要参加TCHS可以选择第二个High School (Secondary School) Registration。这些以后都可以更改（这里没有选的如果以后要选上，只需要更新个人设置并挑勾；如果选上的要撤销选择则需要点一个“Unregister”的链接）。这里选择项目的多少和后面的页面需要填写内容的多少相关，本文以只选择第一项为例。
需要填写的项目和对应的中文翻译如下：

* Given Name:  名
* Surname:     姓
* Address1:  地址1
Address2:  地址2
Address3:  地址3（如果一行写不开，就在三行中分别写）
* City:   城市
State (US Only):  地区（不在美国就不用选）
Postal Code:  邮编
Province:  省
* Country:  国家
* Country to represent:  代表国家（不知道啥意思，中国人两个都填China就行）
* Timezone:  时区（选Asia/Chongqing）
Phone Number:  电话号码
* Email Address:  电子邮件
* Confirm Email Address:  确认电子邮件地址（就是把电子邮件地址重新打一遍）
Email Notifications:  邮件提醒（就是它给你发邮件提醒什么东西）
- Algorithm Competitions  算法比赛，就是SRM和TCOpen
- Software Development Opportunities  貌似就是有软件开发的项目就告诉你
- Employment Opportunities  工作机会
- TopCoder News & Events  新闻
* Enable Member Contact:  允许成员联系（似乎就是说是不是让别人在TC上能找到你）
* Show / hide earnings:  显示/隐藏收入（大概是说别人是不是能看到你赚了多少钱，TC的比赛可是有钱赚的）
* User Name:  用户名（下面的话提醒你一定不要填错，因为注册多个用户是不符合规定的。据说有人因为别人在TC客户端和他打招呼说“怎么你拿小号上了”，那个人的号就被封了）
* Password:  密码
* Confirm Password:  确认密码
* Secret Question:  密码找回问题（找回密码时需要回答这个问题，注意至少要8个字符长，而一个中文字似乎算一个字符，所以最后可能要打几个问号补齐长度）
* Secret Question Response:  密码找回问题答案
Quote:  座右铭，就是个签名档之类的东西
* Student/Professional:  学生/职业程序员
* = required  带*的项目必填

填写之后点Term of Use下面的I Agree，再点Submit，完成提交。除了用户名别的以后似乎都可以改。
接下来进入Demographics页面，这个大概相当于一个注册用户情况调查。

* Age :  年龄
* Gender :  性别（Male男，Female女）
* Ethnic Background :  民族背景（似乎选Asian or Pacific Islander就行吧……）
* Primary Interest in TopCoder :  在TC的主要兴趣，看不懂的就选第一个吧，那个是说你的兴趣在奖金……
* Shirt Size :  T-Shirt大小（有的比赛会给排名前N的选手发T-Shirt，这里你需要选择适合自己的大小，如果选最后一个说明你不想要T-Shirt，人家也不发你了。TC的T-Shirt还是挺好看的，比AStar的好）
* College Major :  大学的专业
* College Major Description :  这个不知道啥意思，随便填点东西就行……
* Degree Program :  学位（从上到下分别为：准学士，学士，硕士，博士，中学生）
* Graduation Year :  毕业年份
* Graduation Month :  毕业月份
* Clubs / Organizations :  组织（一般选None，可以按住Ctrl点鼠标多选）
Other Clubs / Organizations :  其它组织
* School:  学校（点Choose School选择学校，可以搜索，不过为啥shanghaijiaotong university才2个人注册？！）
* Show / hide my school:  显示/隐藏我的学校
GPA:  不懂的自己百度去……
GPA Scale:  同上
Resume:  简历
* How did you hear about TopCoder?:  你怎么知道的TC，如果选了“Member Referral”的话，需要填写那个人在TC的用户名（欢迎填写sqybi~）
* = required

点Submit，进入Confirm页面，确认信息。如果有误可以点Edit修改，否则点最下面的Confirm提交。
接下来进入Success，提示你已经发送一封邮件到你的邮箱中，你必须去点击里面的链接激活用户。激活之后就可以使用这个用户了。

登录
登录的方法一般都是使用Java Web Start。
在TopCoder主页（http://www.topcoder.com/tc）最下方有一段话，第一句是“Load the Arena as an Applet or as a Java Web Start Application”。点“Java Web Start Application”，就会自动下载登陆需要的文件（一个jnlp格式的文件，本机装了JRE/JDK才能打开）。经测试在IE7下这个链接似乎不管用，在Firefox 3下正常。
然后运行下载下来的jnlp文件，就打开了TC客户端。第一次运行和有更新的时候会自动下载安装程序，等待即可，很快。
在我这里有时会提示“语法错误”，但没有任何影响，点“确定”就可以。启动可能会慢一些，耐心等待。
然后输入用户名密码，在Connection的地方选合适的登录方式（一般Direct就行，如果不行的话可以试试别的或者用AUTODETECT自动检测），在PROXY处设置代理，点GO登陆。这时可能还会提示语法错误，再确定就行，这个也没有什么影响。

界面
下面的图们来自原文，很经典，不打算改动了。请使用等宽字体浏览。
主界面：
———————————————————————–
|   Advertisements………….                                       |
———————————————————————–
| Main | Lobbies | Options | Practice Rooms | Active Contests | Help ||
———————————————————————–
|                                                 | Clock |           |
———————————————————————–
| Rating Key | Who’s here |                 Chat Area                 |
|     .      |            |                                           |
|     .      |            |                                           |
|     .      |            |                                           |
|     .      |            |                                           |
|     .      |            |                                           |
|————|            |                                           |
|  MESSAGES  |            |                                           |
|————|            |                                           |
|LEADER BOARD|            |                                           |
|————|            |                                           |
|            |            |                                           |
|            |            |——————————————-|
|            |            | >>_______________________________________ |
———————————————————————–
Advertisements 广告。
菜单项:
- Main里可以看在线名单和找人。
- Lobbies基本用不着，因为用户一般都在Chat Room 1。
- Options里是一些选项和颜色设置。
- Practice Rooms里有大量的练习，都是以前比赛的题目
- Active Contests只有有比赛的时候才有用，显示当前正在进行和将要进行的比赛以及比赛注册之类的东西。
- Help里是….不用说了吧。
Rating Key: handle的颜色是随着积分而改变的，这里显示了积分与颜色的关系。
MESSAGES: 比赛的时候这里有注册提示和clarification。
LEADER BOARD: 看每个room的最高分。
Who’s here: 当前room里的人。
Chat Area: 聊天。

练习
在Practice Rooms里随便选择一个room就可以进入practice了。
界面与主页面稍有变化，但基本相同，略去不画。主要的变化就是Who’s here分成了两块，多了一块Who’s assigned。这块显示的是谁被分到了这个room。因为是练习区，所以只要是在这里打开过题的都算是assigned。而在正式比赛中room是由TC分配的。这里显示的是被分配到这个room的人。界面上还有一个变化是Chat Area顶上多了三块。最左边的是一个下拉菜单。里面有三个分值，选择后就可以打开相应的题目。中间的summary可以看这个room里每个人的提交情况。
在practice room里只有coding phase。提交后要判的话需要自己选择Practice Options（多出来的菜单项）里的Run System Test。

比赛
每次比赛(除了1年两次的大赛)都需要在赛前3小时-5分钟之间登陆注册方可参加，注册需要在Active Contest菜单中，选择你要参加的那个比赛，再选择Register。注意比赛前5分钟注册停止，这时候如果没有注册就不能参赛了。而注册了没有打开题目也视为没有参赛，rating不变动。
然后TopCoder开始根据每个人的rating分配room，一般每个room都有高手和菜鸟，只不过如果你的rating高，和高手分在一起的概率高一些（当然也不一定是这样，比如我上次就和yuhch大牛分在了一起……）
分配完成后，Active Contest菜单中Register一项变成Enter。选择后可以直接进入你被分配到的room。Active Contest菜单最下面还有一项暗色背景的Room子菜单，可以进入各个room溜达。
进入自己room的时候一般离开始只有3分钟左右，静一下心就可以直接开始比赛了。coding phase的过程与practice基本相同。注意每题的得分是和用的时间相关（见前面的计分规则），而时间是从你打开该题开始算的。所以一题做完后可以不急着打开下一题，先放松一下。
75分钟的coding后是5分钟的intermission，这段时间是用来休息和聊天的。
然后就是最刺激的15分钟challenge phase，也就是通常说的cha人。打开summary，双击别人的各题Score可以打开那题的程序，如果觉得有错误就可以点左下的Challenge然后输入你认为他会错的输入数据，如果输入数据合法那么系统会用标程的输出和这个程序的输出对比，如果出现不同则cha人成功。成功的话你能得到50分，对方该题分数为0；而如果失败了，你会被减去25分。每个程序只能成功被cha一次，也就是说，如果有人cha掉了这个程序，你就不能再次cha。但是一个人可以cha某个程序很多次，直到这个程序被cha掉或者你放弃。
Challenge结束后就是System Test。这个过程一般比较慢，可以先走开做其他事，过20分钟再回来看结果。System Test中的测试数据有两种：一种是出题者准备的测试数据，一种是成功cha掉别人的数据。所以，TC中很少出现有bug的程序能通过System Test的情况。
结果出来后再过一段时间，就可以看到一系列message,比如rating更新了，新的practice room建好了以及可以通过主页查看这次比赛的数据了。这时比赛就宣告结束。

注意事项
1.在TC主页（http://www.topcoder.com/tc）上可以看到Next SRM，这是下次SRM的时间。注意我们的时间与他们刚好相差12小时，因此若时间是7月9日9:00 PM的话，这里是7月10日9:00 AM。还有要注意的是美国有夏令时，非夏令时的时候，还要再加1小时，就是7月10日10:00 AM。
2.Practice Rooms里写的程序只要点SAVE就可以保存，下次login的时候还可以看到，但是比赛时候的程序必须Submit才可以在coding phase结束后保存(coding phase结束前还是只要SAVE就可以的)。
3.若想cha别人的程序，自己必须是正分(0分也不行)，所以若没有一题有正确的程序但有很好的数据的话，随便交一道看上去正确的程序，然后在challenge的时候快下手，就可以赚到了。
4.客户端自带的编辑器只有基本的编辑功能和编译及测试功能，所以若觉得不方便的话可以使用parser和plugin，TC主页最下面有plugin的连接。每个plugin都有详细说明文档，这里不再赘述。
5.TC的FAQ：http://www.topcoder.com/?&t=support&c=index
6.最后一条，千万不要作弊，会有严重的后果。

SRM的输入输出
SRM是不用标准或文件输入和输出的，只要写一个类的一个成员函数。也就是说，你需要编写的并不是一个完整的程序，而是一个类。
输入是成员函数的参数，输出用return，所以经常需要STL中的vector和string。
因为TC的系统并不测试标准输出，所以标准输出可以当调试用。
下面以SRM 413 Div 2的1000分题目介绍程序的写法。
题目如下（选择不同的语言，题目描述会略有不同，本文以C++为例）：

Problem Statement
NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.

Let’s consider an infinite sequence A defined as follows:
A0 = 1;
Ai = A[i/p] + A[i/q] for all i >= 1, where [x] denotes the floor function of x. (see Notes)
You will be given n, p and q. Return the n-th element of A (index is 0-based).

Definition
Class:
InfiniteSequence
Method:
calc
Parameters:
long long, int, int
Returns:
long long
Method signature:
long long calc(long long n, int p, int q)
(be sure your method is public)

Notes
- [x] denotes the floor function of x which returns the highest integer less than or equal to x. For example, [3.4] = 3, [0.6] = 0.

Constraints
- n will be between 0 and 10^12, inclusive.
- p and q will both be between 2 and 10^9, inclusive.

Examples
0)
0
2
3
Returns: 1

A[0] = 1.

1)
7
2
3
Returns: 7

A[0] = 1; A[1] = A[0] + A[0] = 2; A[2] = A[1] + A[0] = 2 + 1 = 3; A[3] = A[2] + A[1] = 3 + 2 = 5; A[7] = A[3] + A[2] = 5 + 3 = 8.

2)
10000000
3
3
Returns: 32768

3)
256
2
4
Returns: 89

4)
1
1000000
1000000
Returns: 2

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

下面是我写的一个错误算法的程序，仅供参考格式用：

#include <string>
#include <vector>
class InfiniteSequence {
public:
long long calc(long long n, int p, int q) {
if (n == 0)
return 1;
else
return calc(n/p, p, q) + calc(n/q, p, q);
}
};

转自：http://sqybi.com/blog/archives/25

posted @ 2009-10-27 14:59 abilitytao 阅读(5762) | 评论 (0) | 编辑 收藏

记于松江维也纳宾馆

   22：59分，地点:松江维也纳宾馆
   洗完澡，大家都在看电视，于是偶就占着电脑，心里总是觉得有什么事情没有做完，突然想到写一篇博客当是一个很有意义的选择了吧^_^
   其实今天一整天几乎都是在旅行中度过的，早上8点半和CY,ZJH三个人一起坐车到火车站，然后随队一起坐上了去松江的火车。本来我以为是做动车的，但是貌似南京没有到松江的动车，所以我们乘坐了普快列车。大概下午6，7点才到的，下了火车，发现天已经黑了，我们赶紧坐车来到了维也纳宾馆，来到宾馆，总算感觉到有比赛的气氛了，右侧有好多好多穿着ACM制服的工作人员呢。我们抽完签，鱼头让我们8个先去餐厅吃饭，去餐厅的途中，有人说他看到了楼天成，真的么？难道他第二次复出？走过去才发现真的是楼教主，他对着墙上的画若有所思，难道在怀念当年ACM的岁月？呵呵，我跟他聊了一两句，然后就去餐厅吃饭，说实话，饭真的不怎么样，对于饭量大的人来说（比如我）根本就不够。。。吃完饭，大家都去了各自的房间，房间很不错的，还能免费上网呵~
   好吧，就到这啦，睡觉啦Zzzzz~~~~

posted @ 2009-10-23 23:19 abilitytao 阅读(230) | 评论 (0) | 编辑 收藏

匹配问题学习小结(POJ)

临行上海，决定把最近研究过的各种匹配题做个汇总，原因是这样既可以巩固自己对匹配问题的掌握，又可以借此复习一下匹配问题的各种外在表现形式。我认为，如果比赛中出到匹配，出题者在问题的算法上大做文章的可能性不大，大多数出题者一定会挖空心思来设计一个让你眼花缭乱的背景，借此来隐藏匹配问题的实质！

二分图最小覆盖的Konig定理及其证明

二分图：

顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。

最小覆盖：

最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝最大匹配数

Konig定理：

二分图的最小顶点覆盖数等于最大匹配数。

 证明：

 为主便叙述，假设G分为左边X和右边Y两个互不相交的点集。。。。。。

转自:http://hi.baidu.com/cjhh314/blog/item/ded8d31f15d7510c304e1591.html

POJ 1469 COURSES
学生选课问题，基础匹配问题。
有p节课，n个学生，每节课可以由指定的几个学生参加，但是每个学生只能参加一节课。现在问能不能找到一些学生使得他们：
1.每个学生匹配不同的一节课
2.每节课匹配一个学生。
就是求个最大匹配，看看匹配数是不是等于课程数。如果相等不就满足要求了么.


POJ 3041 Asteroids
在N*N的平面上有K颗小行星，现在你要摧毁他们，你的每一发子弹可以摧毁同一行，或者是同一列上的小行星，现在问你最少要多少子弹才能摧毁所有的小行星？
构图：如果在i行j列上有一颗小行星 则graph[i][j]=1,再求最大匹配即可。
这一题用到的结论是 ：最小顶点覆盖 = 最大匹配(最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联)

他想用最少数目的木板把所有有水的低洼处给覆盖上，前提是木板不能覆盖草地，但是可以重叠。
Sample:
4 4
*.*.
.***
***.
..*.

比如7号坑可以被横着的4号木板和竖着的3号木板盖住，把每个点的对应的横木板(4)和竖木板(3)中间连一条边的话,则问题转化为 找尽量少的边把这些点都盖住,根据定理便是求最大匹配数.

POJ 1422 Air Raid 空袭！
典型的最小路径覆盖题，城市之间单向相连，无环！问最少用多少个伞兵能遍历这张图。
根据定理：最小路径覆盖=顶点数-最大匹配数


POJ 3216 Repairing Company(*)
题目说的是一个城市里面有Q个点，有M项工作，每个工作有个工作地点pi,最晚开始时间ti，和工作需要的时间di.
从城市中的任意一个点到另一个点的直接时间又一个矩阵给出。不连通为-1.注意间接联通是被允许的。
我再这个题上哉了2次，汗啊。我总是以为二分图的顶点时基于城市中的点的，但实际上时基于工作。

这一题首先对给定的图做一次floyd，这样就能求出两个点之间最少需要走的时间。
然后判断两个工作之间是否存在先后关系

for(i=1;i<=m;i++)
    {

        scanf("%d%d%d",&work[i].p,&work[i].t,&work[i].d);
    }
    for(i=1;i<=m;i++)
        for(j=1;j<=m;j++)
        {

            if(work[i].t+work[i].d+g[work[i].p][work[j].p]<=work[j].t)
                graph[i][j]=1;
        }

最后做最小路径覆盖即可。注意这里的顶点数应该是工作数！这一题值得重点注意！！！
printf("%d\n",m-Hungary(m,graph));

POJ 2594 Treasure Exploration(*)
太经典了，最小路径覆盖之变形！如果题目中有暗示此图无环且路径是单向的话，必然是最小路径覆盖无疑！
这个题的题目意思和那个伞兵题差不多，但是伞兵走过的路径是可以交叉的，这样我们先做一个传递闭包，然后再连边做最小路径覆盖即可。

POJ 1034 The dog task
一个很明显的二分匹配，不过和计算几何联系起来了。这道题目建图很巧妙.以BOB行走的n-1条有向线段为X，m个景点为Y，二分匹配。


暂时总结到这，对于匹配问题，我只想说，匹配问题，你真的很"2"！

posted @ 2009-10-21 17:34 abilitytao 阅读(2315) | 评论 (1) | 编辑 收藏

并查集学习小节(POJ版)

posted @ 2009-10-18 21:31 abilitytao 阅读(3154) | 评论 (5) | 编辑 收藏