The Fourth Dimension Space

積性函數(shù)的一些證明(轉(zhuǎn))

在數(shù)論中的積性函數(shù)。對于正整數(shù)n的一個算術(shù)函數(shù)f(n)，當中f(1)=1且當a,b互質(zhì)，f(ab)=f(a)f(b)，在數(shù)論上就稱它為積性函數(shù)。

證明： f(n) = ∑g(d)^3 (d | n, g(d)表示d的約數(shù)個數(shù)）

求證: f(n) 是積性函數(shù)，即f(1) = 1, f(ab) = f(a) * f(b); a,b互質(zhì)

(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的約數(shù)個數(shù)）

f(a) = ∑g(p)^3 (d | a, g(p)表示p的約數(shù)個數(shù)）

f(b) = ∑g(q)^3 (d | b, g(q)表示q的約數(shù)個數(shù)）

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

假設(shè) d = p * q; //d為n中的某個約數(shù)，p為a中的某個約數(shù)，q為b中某個約數(shù)，總存在d = p * q

現(xiàn)需證明g(d)^3 = g(p)^3 * g(q)^3;

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

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

將d質(zhì)因數(shù)分解： d = p1^a1 * p2^a2 ……pj^aj

將p質(zhì)因數(shù)分解： p = p1^b1 * p2^b2 ……pj^bj

將q質(zhì)因數(shù)分解： q = p1^c1 * p2^c2 ……pj^cj

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

因為p,q互質(zhì)，所以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)是積性函數(shù)

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

f(p1^a1) = ∑g(d)^3 (d | p1 ^ 3) 由p1是質(zhì)因數(shù)

所以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質(zhì)因數(shù)分解后進行統(tǒng)計即可。（本人代碼效率不行，如果誰有更有效率的代碼麻煩給我一個，讓我學(xué)習(xí)學(xué)習(xí)）。

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


轉(zhuǎn)自：http://blog.sina.com.cn/s/blog_5c95cb070100ej4c.html

posted @ 2009-11-02 18:30 abilitytao 閱讀(519) | 評論 (0) | 編輯 收藏

POJ 3219 二項式系數(shù)(數(shù)論，簡單)

之所以要寫個解題報告，不是因為這道題很難，而是因為一眼居然沒看出來是統(tǒng)計質(zhì)因數(shù)2出現(xiàn)的次數(shù)，太nc了，為了把公式記得牢一點，遂寫此文~

題目意思很簡單，就是讓你求組合數(shù)C(n,k)是奇數(shù)還是偶數(shù)。
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。
對于上述描述，可以直接無視之。。。

由于組合數(shù)C(n,k)=         n!
                                    ---------
                                     k!(n-k)!

posted @ 2009-11-01 01:43 abilitytao 閱讀(528) | 評論 (0) | 編輯 收藏

POJ 1150 ——The Last Non-zero Digit(數(shù)論)

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階乘中質(zhì)因數(shù)x(比如說5）出現(xiàn)的次數(shù)？
比如說15的階乘 ：1*2*3*4*5*6*7*8*9*10*11*12*13*14*15
由于5這個質(zhì)因數(shù)只在5的倍數(shù)里面才出現(xiàn)，所以我從5，10，15中各抽出一個5，這相當于有15/5個質(zhì)因數(shù)5,之后5，10，15就變成了1，2，3；
由于非5的倍數(shù)顯然不在考慮范圍之內(nèi)，所以我們只需繼續(xù)討論它的子問題3！即可。
這樣，我們可以用遞歸來解決這個問題。有了這個方法，我們是不是能夠輕易地解決n!末尾有多少個0呢？想想看...n!后0的個數(shù)是不是就和某個質(zhì)因數(shù)的個數(shù)有關(guān)呢？^_^
比如說，我們要求5出現(xiàn)的次數(shù)，可以這樣寫：

int get5(int n)//計算n!中質(zhì)因子5的出現(xiàn)次數(shù)
{
    if(n==0)
        return 0;
    return n/5+get5(n/5);
}

 2.如何求出n!階乘最后非0位？
比如說我們要找10!最后非0位，由于質(zhì)因數(shù)2和5組合之后會使得末尾產(chǎn)生0.那么我們不妨把10！中2，5質(zhì)因數(shù)全部去掉，（但是請注意2的數(shù)目其實比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因子已經(jīng)被去除，那么剩下的數(shù)字末尾一定是3，7，9，1中四者之一。然后我們再求出這么一串數(shù)相乘以后末尾的數(shù)是幾.最后再補上2對末位的影響即可！

總結(jié)一下，求10!最后一個非0位的步驟如下：
step1：首先將10!中所有2，5因子去掉；
step2：然后求出剩下的一串數(shù)字相乘后末尾的那個數(shù)。
step3：由于去掉的2比5多，最后還要考慮多余的那部分2對結(jié)果的影響。
step4：output your answer!

一個數(shù)列實際上可以分成偶數(shù)列和奇數(shù)列，以1*2*3*4*5*6*7*8*9*10為例

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

這樣我們嘗試分別進行統(tǒng)計，可以發(fā)現(xiàn)，實際上2，4，6，8，10中的個數(shù)也就是1 2 3 4 5中的個數(shù)，也就是說我們又把這個問題劃分成了一個原來問題的子問題。

f(n) = f(n/2) + g(n),g(n)表示奇數(shù)列中的數(shù)目，所以我們需要解決g(n)

再次觀察g(n)

實際上又分成了兩部分1 3 7 9 11 13 17 19 21。。。以及5的奇倍數(shù)5，15，25。。。說明又出現(xiàn)了子問題,如果要統(tǒng)計這個數(shù)列中末尾為x（1，3，7，9）的個數(shù)可以這樣寫：g(n,x) = n/10+(n%10 >= x)+g(n/5,x) 

這樣利用了兩個遞歸方程，我們就可以在lgn的時間內(nèi)計算出末尾為1,3,7,9的數(shù)的個數(shù)了

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

int get2(int n)//計算n!中質(zhì)因子2的出現(xiàn)次數(shù)
{
    if(n==0)
        return 0;
    return n/2+get2(n/2);
}

int get5(int n)//計算n!中質(zhì)因子5的出現(xiàn)次數(shù)
{
    if(n==0)
        return 0;
    return n/5+get5(n/5);
}

/**///////////////////////////////////////////////////////////////////////////
int g(int n,int x)//計算f(1) to f(n) 中，奇數(shù)數(shù)列中末尾為x的數(shù)出現(xiàn)的次數(shù)
{
    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的數(shù)的出現(xiàn)次數(shù)
{
    if(n==0)
        return 0;
    return getx(n/2,x)+g(n,x);
}
/**///////////////////////////////////////////////////////////////////////////

int table[4][4] =
{
        6,2,4,8,//2^n%10的循環(huán)節(jié)，注意如果2的個數(shù)為0時候，結(jié)果應(yīng)該是1，要特殊處理。 
        1,3,9,7,//3
        1,7,9,3,//7
        1,9,1,9,//9    
};//3，7，9的循環(huán)節(jié)中第一位，剛好是1，故不需要考慮這些數(shù)字出現(xiàn)次數(shù)為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應(yīng)該為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 閱讀(3593) | 評論 (8) | 編輯 收藏

POJ 2478 Farey Sequence(歐拉函數(shù)的應(yīng)用)

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


//基于素數(shù)篩選法，計算歐拉函數(shù)phi[1] to phi[MAX],復(fù)雜度約為n，很快
//傳入三個數(shù)組:
//phi[]用于存放歐拉函數(shù)
//prime[]用來存放小于i的所有素數(shù)，這里其實是一個模擬堆棧
//isprime[]用來標志該數(shù)是不是素數(shù)，初始值為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()//這是一個基于素數(shù)篩選的線性算法，很快
{
    __int64 i,j;
    __int64 len=0;
    for(i=2;i<=MAX;i++)
    {
        if(isprime[i]==false) //false代表是質(zhì)數(shù)
        {
            prime[++len]=i;
            phi[i]=i-1;
        }
        for(j=1;j<=len&&prime[j]*i<=MAX;j++)
        {
            isprime[prime[j]*i]=true;//true代表是合數(shù)
            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 閱讀(1675) | 評論 (0) | 編輯 收藏

pku 3164 最小樹形圖(Zhu-Liu Algorithm)

posted @ 2009-10-29 19:38 abilitytao 閱讀(2180) | 評論 (2) | 編輯 收藏

TopCoder競賽：C++, STL 用法快速入門（轉(zhuǎn)）

下面總結(jié)了一些題目中常用的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轉(zhuǎn)成C-style的string,以\0終了
const char *ptr1 = s.data();;//把string轉(zhuǎn)成字符串
if (s2[2] == 'k') s2[2]='C';
s+="jkl";
s+='m';
s.push_back('\n'); //把'\n'（換行符）放在s的最后一個位置
reverse(s.begin(), s.end()); //反轉(zhuǎn)
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”轉(zhuǎn)換成數(shù)字123
cout<<"savei="<<savei<<endl;
char buf[100];
sprintf(buf,"v[1]=%d",savei); //把內(nèi)容打印進字符串
cout<<"buf="<<buf<<endl;
 
}

posted @ 2009-10-27 15:35 abilitytao 閱讀(748) | 評論 (2) | 編輯 收藏

TOPCODER入門教程(轉(zhuǎn))

本文根據(jù)經(jīng)典的TC教程完善和改編。
TopCoder：http://www.topcoder.com/

基本規(guī)則
TopCoder的比賽類型很多，最常見的是周賽SRM（Single Round Match），另外還有TCHS SRM（TopCoder High School SRM，題目和SRM一樣，僅限中學(xué)生參加，參賽者水平較低，據(jù)說漲rating很容易），馬拉松（Marathon Matchs），還有TCOpen（每年兩次的大比賽）之類的比賽。因為大多數(shù)人都在做SRM，所以本文介紹的TC比賽即為SRM。
SRM的規(guī)則總結(jié)起來就是一句話：75分鐘做完3道難度遞增的題。
TC的每個用戶（handle）都有自己的積分（rating），從0-3000+不等。成績越好，分數(shù)越高。
積分與顏色的對應(yīng)為：白色——未參賽（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的計分規(guī)則很詭異，可以見http://www.topcoder.com/wiki/display/tc/Algorithm+Competition+Rating+System，但基本是沒人看的懂。不過，TC積分規(guī)則的基本思想很簡單。
首先是SRM每道題的計分規(guī)則。題目從打開開始計時，隨著時間的流逝，你這道題目可能得到的分數(shù)也越來越少。不過分數(shù)減少的速率會逐漸變慢（有人說是先快后慢再快再慢，我不清楚到底哪個是對的，不過總體趨勢是越來越慢），一般1000分的題目在降低到300分的時候就基本不會再下降太多了。每道題點擊Submit才算正式提交，如果Submit之后發(fā)現(xiàn)錯誤，還可以再次點擊Submit修改提交，不過這樣會扣除這道題一定的分數(shù)。
其次是TC的計分規(guī)則。復(fù)雜的數(shù)學(xué)公式很難看懂，但大概的計分思想是：根據(jù)此次比賽的得分算出一個這次比賽的rank，然后和以前的rank做比較，求出一個期望的rank，再根據(jù)這個期望的rank調(diào)整rating。而有時也會出現(xiàn)考得很砸但依然漲rating的情況，不過總體來說TC的計分公式是十分穩(wěn)定的。

運行環(huán)境
TC的客戶端是一個Java程序，所以需要JRE（Java Runtime Environment）或者JDK（Java Development Kit）來運行。如果平時不寫Java程序的話，裝JRE就可以了。畢竟JDK比JRE大一個數(shù)量級，下載慢。安裝照著提示完成就行了。推薦使用1.4.1以后的版本，因為帶了java web start，可以快速登陸。具體方法下一部分講。
JRE下載地址（中文）：http://www.java.com/zh_CN/download/index.jsp

注冊
原文在注冊的地方?jīng)]有詳細說明，但很多人似乎對注冊都有疑問。所以這里我來注冊一個小號，并通過整個過程講解如何注冊。
首先打開http://www.topcoder.com/tc（本文后面TopCoder的主頁都指這個網(wǎng)址），然后點擊右上角的Register Now（沒看到？你可能看到了一個Login，目光向下挪一點，那個紅底白字的“Register Now”就在下面）。接下來會彈出http://www.topcoder.com/reg這個頁面，因為我們要參加SRM，所以選擇第一個，Competition Registration。如果要參加TCHS可以選擇第二個High School (Secondary School) Registration。這些以后都可以更改（這里沒有選的如果以后要選上，只需要更新個人設(shè)置并挑勾；如果選上的要撤銷選擇則需要點一個“Unregister”的鏈接）。這里選擇項目的多少和后面的頁面需要填寫內(nèi)容的多少相關(guān)，本文以只選擇第一項為例。
需要填寫的項目和對應(yīng)的中文翻譯如下：

* Given Name:  名
* Surname:     姓
* Address1:  地址1
Address2:  地址2
Address3:  地址3（如果一行寫不開，就在三行中分別寫）
* City:   城市
State (US Only):  地區(qū)（不在美國就不用選）
Postal Code:  郵編
Province:  省
* Country:  國家
* Country to represent:  代表國家（不知道啥意思，中國人兩個都填China就行）
* Timezone:  時區(qū)（選Asia/Chongqing）
Phone Number:  電話號碼
* Email Address:  電子郵件
* Confirm Email Address:  確認電子郵件地址（就是把電子郵件地址重新打一遍）
Email Notifications:  郵件提醒（就是它給你發(fā)郵件提醒什么東西）
- Algorithm Competitions  算法比賽，就是SRM和TCOpen
- Software Development Opportunities  貌似就是有軟件開發(fā)的項目就告訴你
- Employment Opportunities  工作機會
- TopCoder News & Events  新聞
* Enable Member Contact:  允許成員聯(lián)系（似乎就是說是不是讓別人在TC上能找到你）
* Show / hide earnings:  顯示/隱藏收入（大概是說別人是不是能看到你賺了多少錢，TC的比賽可是有錢賺的）
* User Name:  用戶名（下面的話提醒你一定不要填錯，因為注冊多個用戶是不符合規(guī)定的。據(jù)說有人因為別人在TC客戶端和他打招呼說“怎么你拿小號上了”，那個人的號就被封了）
* Password:  密碼
* Confirm Password:  確認密碼
* Secret Question:  密碼找回問題（找回密碼時需要回答這個問題，注意至少要8個字符長，而一個中文字似乎算一個字符，所以最后可能要打幾個問號補齊長度）
* Secret Question Response:  密碼找回問題答案
Quote:  座右銘，就是個簽名檔之類的東西
* Student/Professional:  學(xué)生/職業(yè)程序員
* = required  帶*的項目必填

填寫之后點Term of Use下面的I Agree，再點Submit，完成提交。除了用戶名別的以后似乎都可以改。
接下來進入Demographics頁面，這個大概相當于一個注冊用戶情況調(diào)查。

* Age :  年齡
* Gender :  性別（Male男，F(xiàn)emale女）
* Ethnic Background :  民族背景（似乎選Asian or Pacific Islander就行吧……）
* Primary Interest in TopCoder :  在TC的主要興趣，看不懂的就選第一個吧，那個是說你的興趣在獎金……
* Shirt Size :  T-Shirt大小（有的比賽會給排名前N的選手發(fā)T-Shirt，這里你需要選擇適合自己的大小，如果選最后一個說明你不想要T-Shirt，人家也不發(fā)你了。TC的T-Shirt還是挺好看的，比AStar的好）
* College Major :  大學(xué)的專業(yè)
* College Major Description :  這個不知道啥意思，隨便填點東西就行……
* Degree Program :  學(xué)位（從上到下分別為：準學(xué)士，學(xué)士，碩士，博士，中學(xué)生）
* Graduation Year :  畢業(yè)年份
* Graduation Month :  畢業(yè)月份
* Clubs / Organizations :  組織（一般選None，可以按住Ctrl點鼠標多選）
Other Clubs / Organizations :  其它組織
* School:  學(xué)校（點Choose School選擇學(xué)校，可以搜索，不過為啥shanghaijiaotong university才2個人注冊？！）
* Show / hide my school:  顯示/隱藏我的學(xué)校
GPA:  不懂的自己百度去……
GPA Scale:  同上
Resume:  簡歷
* How did you hear about TopCoder?:  你怎么知道的TC，如果選了“Member Referral”的話，需要填寫那個人在TC的用戶名（歡迎填寫sqybi~）
* = required

點Submit，進入Confirm頁面，確認信息。如果有誤可以點Edit修改，否則點最下面的Confirm提交。
接下來進入Success，提示你已經(jīng)發(fā)送一封郵件到你的郵箱中，你必須去點擊里面的鏈接激活用戶。激活之后就可以使用這個用戶了。

登錄
登錄的方法一般都是使用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才能打開）。經(jīng)測試在IE7下這個鏈接似乎不管用，在Firefox 3下正常。
然后運行下載下來的jnlp文件，就打開了TC客戶端。第一次運行和有更新的時候會自動下載安裝程序，等待即可，很快。
在我這里有時會提示“語法錯誤”，但沒有任何影響，點“確定”就可以。啟動可能會慢一些，耐心等待。
然后輸入用戶名密碼，在Connection的地方選合適的登錄方式（一般Direct就行，如果不行的話可以試試別的或者用AUTODETECT自動檢測），在PROXY處設(shè)置代理，點GO登陸。這時可能還會提示語法錯誤，再確定就行，這個也沒有什么影響。

界面
下面的圖們來自原文，很經(jīng)典，不打算改動了。請使用等寬字體瀏覽。
主界面：
———————————————————————–
|   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里是一些選項和顏色設(shè)置。
- Practice Rooms里有大量的練習(xí)，都是以前比賽的題目
- Active Contests只有有比賽的時候才有用，顯示當前正在進行和將要進行的比賽以及比賽注冊之類的東西。
- Help里是….不用說了吧。
Rating Key: handle的顏色是隨著積分而改變的，這里顯示了積分與顏色的關(guān)系。
MESSAGES: 比賽的時候這里有注冊提示和clarification。
LEADER BOARD: 看每個room的最高分。
Who’s here: 當前room里的人。
Chat Area: 聊天。

練習(xí)
在Practice Rooms里隨便選擇一個room就可以進入practice了。
界面與主頁面稍有變化，但基本相同，略去不畫。主要的變化就是Who’s here分成了兩塊，多了一塊Who’s assigned。這塊顯示的是誰被分到了這個room。因為是練習(xí)區(qū)，所以只要是在這里打開過題的都算是assigned。而在正式比賽中room是由TC分配的。這里顯示的是被分配到這個room的人。界面上還有一個變化是Chat Area頂上多了三塊。最左邊的是一個下拉菜單。里面有三個分值，選擇后就可以打開相應(yīng)的題目。中間的summary可以看這個room里每個人的提交情況。
在practice room里只有coding phase。提交后要判的話需要自己選擇Practice Options（多出來的菜單項）里的Run System Test。

比賽
每次比賽(除了1年兩次的大賽)都需要在賽前3小時-5分鐘之間登陸注冊方可參加，注冊需要在Active Contest菜單中，選擇你要參加的那個比賽，再選擇Register。注意比賽前5分鐘注冊停止，這時候如果沒有注冊就不能參賽了。而注冊了沒有打開題目也視為沒有參賽，rating不變動。
然后TopCoder開始根據(jù)每個人的rating分配room，一般每個room都有高手和菜鳥，只不過如果你的rating高，和高手分在一起的概率高一些（當然也不一定是這樣，比如我上次就和yuhch大牛分在了一起……）
分配完成后，Active Contest菜單中Register一項變成Enter。選擇后可以直接進入你被分配到的room。Active Contest菜單最下面還有一項暗色背景的Room子菜單，可以進入各個room溜達。
進入自己room的時候一般離開始只有3分鐘左右，靜一下心就可以直接開始比賽了。coding phase的過程與practice基本相同。注意每題的得分是和用的時間相關(guān)（見前面的計分規(guī)則），而時間是從你打開該題開始算的。所以一題做完后可以不急著打開下一題，先放松一下。
75分鐘的coding后是5分鐘的intermission，這段時間是用來休息和聊天的。
然后就是最刺激的15分鐘challenge phase，也就是通常說的cha人。打開summary，雙擊別人的各題Score可以打開那題的程序，如果覺得有錯誤就可以點左下的Challenge然后輸入你認為他會錯的輸入數(shù)據(jù)，如果輸入數(shù)據(jù)合法那么系統(tǒng)會用標程的輸出和這個程序的輸出對比，如果出現(xiàn)不同則cha人成功。成功的話你能得到50分，對方該題分數(shù)為0；而如果失敗了，你會被減去25分。每個程序只能成功被cha一次，也就是說，如果有人cha掉了這個程序，你就不能再次cha。但是一個人可以cha某個程序很多次，直到這個程序被cha掉或者你放棄。
Challenge結(jié)束后就是System Test。這個過程一般比較慢，可以先走開做其他事，過20分鐘再回來看結(jié)果。System Test中的測試數(shù)據(jù)有兩種：一種是出題者準備的測試數(shù)據(jù)，一種是成功cha掉別人的數(shù)據(jù)。所以，TC中很少出現(xiàn)有bug的程序能通過System Test的情況。
結(jié)果出來后再過一段時間，就可以看到一系列message,比如rating更新了，新的practice room建好了以及可以通過主頁查看這次比賽的數(shù)據(jù)了。這時比賽就宣告結(jié)束。

注意事項
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結(jié)束后保存(coding phase結(jié)束前還是只要SAVE就可以的)。
3.若想cha別人的程序，自己必須是正分(0分也不行)，所以若沒有一題有正確的程序但有很好的數(shù)據(jù)的話，隨便交一道看上去正確的程序，然后在challenge的時候快下手，就可以賺到了。
4.客戶端自帶的編輯器只有基本的編輯功能和編譯及測試功能，所以若覺得不方便的話可以使用parser和plugin，TC主頁最下面有plugin的連接。每個plugin都有詳細說明文檔，這里不再贅述。
5.TC的FAQ：http://www.topcoder.com/?&t=support&c=index
6.最后一條，千萬不要作弊，會有嚴重的后果。

SRM的輸入輸出
SRM是不用標準或文件輸入和輸出的，只要寫一個類的一個成員函數(shù)。也就是說，你需要編寫的并不是一個完整的程序，而是一個類。
輸入是成員函數(shù)的參數(shù)，輸出用return，所以經(jīng)常需要STL中的vector和string。
因為TC的系統(tǒng)并不測試標準輸出，所以標準輸出可以當調(diào)試用。
下面以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);
}
};

轉(zhuǎn)自：http://sqybi.com/blog/archives/25

posted @ 2009-10-27 14:59 abilitytao 閱讀(5769) | 評論 (0) | 編輯 收藏

記于松江維也納賓館

   22：59分，地點:松江維也納賓館
   洗完澡，大家都在看電視，于是偶就占著電腦，心里總是覺得有什么事情沒有做完，突然想到寫一篇博客當是一個很有意義的選擇了吧^_^
   其實今天一整天幾乎都是在旅行中度過的，早上8點半和CY,ZJH三個人一起坐車到火車站，然后隨隊一起坐上了去松江的火車。本來我以為是做動車的，但是貌似南京沒有到松江的動車，所以我們乘坐了普快列車。大概下午6，7點才到的，下了火車，發(fā)現(xiàn)天已經(jīng)黑了，我們趕緊坐車來到了維也納賓館，來到賓館，總算感覺到有比賽的氣氛了，右側(cè)有好多好多穿著ACM制服的工作人員呢。我們抽完簽，魚頭讓我們8個先去餐廳吃飯，去餐廳的途中，有人說他看到了樓天成，真的么？難道他第二次復(fù)出？走過去才發(fā)現(xiàn)真的是樓教主，他對著墻上的畫若有所思，難道在懷念當年ACM的歲月？呵呵，我跟他聊了一兩句，然后就去餐廳吃飯，說實話，飯真的不怎么樣，對于飯量大的人來說（比如我）根本就不夠。。。吃完飯，大家都去了各自的房間，房間很不錯的，還能免費上網(wǎng)呵~
   好吧，就到這啦，睡覺啦Zzzzz~~~~

posted @ 2009-10-23 23:19 abilitytao 閱讀(245) | 評論 (0) | 編輯 收藏

匹配問題學(xué)習(xí)小結(jié)(POJ)

臨行上海，決定把最近研究過的各種匹配題做個匯總，原因是這樣既可以鞏固自己對匹配問題的掌握，又可以借此復(fù)習(xí)一下匹配問題的各種外在表現(xiàn)形式。我認為，如果比賽中出到匹配，出題者在問題的算法上大做文章的可能性不大，大多數(shù)出題者一定會挖空心思來設(shè)計一個讓你眼花繚亂的背景，借此來隱藏匹配問題的實質(zhì)！

二分圖最小覆蓋的Konig定理及其證明

二分圖：

頂點可以分類兩個集合X和Y，所有的邊關(guān)聯(lián)在兩個頂點中，恰好一個屬于集合Ｘ，另一個屬于集合Ｙ。

最小覆蓋：

最小覆蓋要求用最少的點（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個點關(guān)聯(lián)。可以證明：最少的點（即覆蓋數(shù)）＝最大匹配數(shù)

Konig定理：

二分圖的最小頂點覆蓋數(shù)等于最大匹配數(shù)。

 證明：

 為主便敘述，假設(shè)G分為左邊X和右邊Y兩個互不相交的點集。。。。。。

轉(zhuǎn)自:http://hi.baidu.com/cjhh314/blog/item/ded8d31f15d7510c304e1591.html

POJ 1469 COURSES
學(xué)生選課問題，基礎(chǔ)匹配問題。
有p節(jié)課，n個學(xué)生，每節(jié)課可以由指定的幾個學(xué)生參加，但是每個學(xué)生只能參加一節(jié)課。現(xiàn)在問能不能找到一些學(xué)生使得他們：
1.每個學(xué)生匹配不同的一節(jié)課
2.每節(jié)課匹配一個學(xué)生。
就是求個最大匹配，看看匹配數(shù)是不是等于課程數(shù)。如果相等不就滿足要求了么.


POJ 3041 Asteroids
在N*N的平面上有K顆小行星，現(xiàn)在你要摧毀他們，你的每一發(fā)子彈可以摧毀同一行，或者是同一列上的小行星，現(xiàn)在問你最少要多少子彈才能摧毀所有的小行星？
構(gòu)圖：如果在i行j列上有一顆小行星 則graph[i][j]=1,再求最大匹配即可。
這一題用到的結(jié)論是 ：最小頂點覆蓋 = 最大匹配(最小覆蓋要求用最少的點（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個點關(guān)聯(lián))

他想用最少數(shù)目的木板把所有有水的低洼處給覆蓋上，前提是木板不能覆蓋草地，但是可以重疊。
Sample:
4 4
*.*.
.***
***.
..*.

比如7號坑可以被橫著的4號木板和豎著的3號木板蓋住，把每個點的對應(yīng)的橫木板(4)和豎木板(3)中間連一條邊的話,則問題轉(zhuǎn)化為 找盡量少的邊把這些點都蓋住,根據(jù)定理便是求最大匹配數(shù).

POJ 1422 Air Raid 空襲！
典型的最小路徑覆蓋題，城市之間單向相連，無環(huán)！問最少用多少個傘兵能遍歷這張圖。
根據(jù)定理：最小路徑覆蓋=頂點數(shù)-最大匹配數(shù)


POJ 3216 Repairing Company(*)
題目說的是一個城市里面有Q個點，有M項工作，每個工作有個工作地點pi,最晚開始時間ti，和工作需要的時間di.
從城市中的任意一個點到另一個點的直接時間又一個矩陣給出。不連通為-1.注意間接聯(lián)通是被允許的。
我再這個題上哉了2次，汗啊。我總是以為二分圖的頂點時基于城市中的點的，但實際上時基于工作。

這一題首先對給定的圖做一次floyd，這樣就能求出兩個點之間最少需要走的時間。
然后判斷兩個工作之間是否存在先后關(guān)系

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;
        }

最后做最小路徑覆蓋即可。注意這里的頂點數(shù)應(yīng)該是工作數(shù)！這一題值得重點注意！！！
printf("%d\n",m-Hungary(m,graph));

POJ 2594 Treasure Exploration(*)
太經(jīng)典了，最小路徑覆蓋之變形！如果題目中有暗示此圖無環(huán)且路徑是單向的話，必然是最小路徑覆蓋無疑！
這個題的題目意思和那個傘兵題差不多，但是傘兵走過的路徑是可以交叉的，這樣我們先做一個傳遞閉包，然后再連邊做最小路徑覆蓋即可。

POJ 1034 The dog task
一個很明顯的二分匹配，不過和計算幾何聯(lián)系起來了。這道題目建圖很巧妙.以BOB行走的n-1條有向線段為X，m個景點為Y，二分匹配。


暫時總結(jié)到這，對于匹配問題，我只想說，匹配問題，你真的很"2"！

posted @ 2009-10-21 17:34 abilitytao 閱讀(2333) | 評論 (1) | 編輯 收藏

并查集學(xué)習(xí)小節(jié)(POJ版)

posted @ 2009-10-18 21:31 abilitytao 閱讀(3174) | 評論 (5) | 編輯 收藏