The Fourth Dimension Space

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

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

證明： f(n) = ∑g(d)^3 (d | n, g(d)表示d的約數(shù)個(gè)數(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ù)個(gè)數(shù)）

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

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

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

假設(shè) d = p * q; //d為n中的某個(gè)約數(shù)，p為a中的某個(gè)約數(shù)，q為b中某個(gè)約數(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;

因?yàn)閜,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ù)分解后進(jìn)行統(tǒng)計(jì)即可。（本人代碼效率不行，如果誰有更有效率的代碼麻煩給我一個(gè)，讓我學(xué)習(xí)學(xué)習(xí)）。

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


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

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

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

之所以要寫個(gè)解題報(bào)告，不是因?yàn)檫@道題很難，而是因?yàn)橐谎劬尤粵]看出來是統(tǒng)計(jì)質(zhì)因數(shù)2出現(xiàn)的次數(shù)，太nc了，為了把公式記得牢一點(diǎn)，遂寫此文~

題目意思很簡單，就是讓你求組合數(shù)C(n,k)是奇數(shù)還是偶數(shù)。
C(1, 0) = C(1, 1) = 1；
C(n, 0) = 1對(duì)于所有n > 0；
C(n, k) = C(n − 1, k − 1) + C(n − 1, k)對(duì)于所有0 < k ≤ n。
對(duì)于上述描述，可以直接無視之。。。

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

posted @ 2009-11-01 01:43 abilitytao 閱讀(528) | 評(píng)論 (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.



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

int get5(int n)//計(jì)算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組合之后會(huì)使得末尾產(chǎn)生0.那么我們不妨把10！中2，5質(zhì)因數(shù)全部去掉，（但是請(qǐng)注意2的數(shù)目其實(shí)比5的要多，所以我們要在最后考慮多余的2對(duì)末位的影響）
如 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中四者之一。然后我們?cè)偾蟪鲞@么一串?dāng)?shù)相乘以后末尾的數(shù)是幾.最后再補(bǔ)上2對(duì)末位的影響即可！

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

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

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

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

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

再次觀察g(n)

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

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

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

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

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

/**///////////////////////////////////////////////////////////////////////////
int g(int n,int x)//計(jì)算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)//計(jì)算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的個(gè)數(shù)為0時(shí)候，結(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 閱讀(3594) | 評(píng)論 (8) | 編輯 收藏

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

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


//基于素?cái)?shù)篩選法，計(jì)算歐拉函數(shù)phi[1] to phi[MAX],復(fù)雜度約為n，很快
//傳入三個(gè)數(shù)組:
//phi[]用于存放歐拉函數(shù)
//prime[]用來存放小于i的所有素?cái)?shù)，這里其實(shí)是一個(gè)模擬堆棧
//isprime[]用來標(biāo)志該數(shù)是不是素?cái)?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()//這是一個(gè)基于素?cái)?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) | 評(píng)論 (0) | 編輯 收藏

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

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

TopCoder競(jìng)賽：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個(gè)位置之前（位置從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的最后一個(gè)位置
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; //通過[第一個(gè)元素]來訪問第二個(gè)元素
}
 
int total = 100;
map<int, int>::iterator it = mp.begin();
for(;it!=mp.end();it++) //遍歷mp
{
total+=it->second; //通過iterator it來訪問第二個(gè)元素
}
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); //絕對(duì)值
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)容打印進(jìn)字符串
cout<<"buf="<<buf<<endl;
 
}

posted @ 2009-10-27 15:35 abilitytao 閱讀(748) | 評(píng)論 (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（每年兩次的大比賽）之類的比賽。因?yàn)榇蠖鄶?shù)人都在做SRM，所以本文介紹的TC比賽即為SRM。
SRM的規(guī)則總結(jié)起來就是一句話：75分鐘做完3道難度遞增的題。
TC的每個(gè)用戶（handle）都有自己的積分（rating），從0-3000+不等。成績?cè)胶?，分?jǐn)?shù)越高。
積分與顏色的對(duì)應(yīng)為：白色——未參賽（unrated）；灰色——0~899；綠色——900~1199；藍(lán)色——1200~1499；黃色——1500~2199；紅色——2200+。另外排名最高的幾個(gè)人在TC客戶端中會(huì)變成紅色靶子圖標(biāo)。
比賽分為兩個(gè)Division，Div I和Div II。白色灰色和綠色的參加Div II，藍(lán)色黃色和紅色的參加Div I。Div I的題要比Div II難許多，一般DivII的最后一題和Div I的第一或第二題是一樣的。無論是Div I或Div II。三道題目的Score一般為250, 500和1000。
TC的計(jì)分規(guī)則很詭異，可以見http://www.topcoder.com/wiki/display/tc/Algorithm+Competition+Rating+System，但基本是沒人看的懂。不過，TC積分規(guī)則的基本思想很簡單。
首先是SRM每道題的計(jì)分規(guī)則。題目從打開開始計(jì)時(shí)，隨著時(shí)間的流逝，你這道題目可能得到的分?jǐn)?shù)也越來越少。不過分?jǐn)?shù)減少的速率會(huì)逐漸變慢（有人說是先快后慢再快再慢，我不清楚到底哪個(gè)是對(duì)的，不過總體趨勢(shì)是越來越慢），一般1000分的題目在降低到300分的時(shí)候就基本不會(huì)再下降太多了。每道題點(diǎn)擊Submit才算正式提交，如果Submit之后發(fā)現(xiàn)錯(cuò)誤，還可以再次點(diǎn)擊Submit修改提交，不過這樣會(huì)扣除這道題一定的分?jǐn)?shù)。
其次是TC的計(jì)分規(guī)則。復(fù)雜的數(shù)學(xué)公式很難看懂，但大概的計(jì)分思想是：根據(jù)此次比賽的得分算出一個(gè)這次比賽的rank，然后和以前的rank做比較，求出一個(gè)期望的rank，再根據(jù)這個(gè)期望的rank調(diào)整rating。而有時(shí)也會(huì)出現(xiàn)考得很砸但依然漲rating的情況，不過總體來說TC的計(jì)分公式是十分穩(wěn)定的。

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

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

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

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

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

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

登錄
登錄的方法一般都是使用Java Web Start。
在TopCoder主頁（http://www.topcoder.com/tc）最下方有一段話，第一句是“Load the Arena as an Applet or as a Java Web Start Application”。點(diǎn)“Java Web Start Application”，就會(huì)自動(dòng)下載登陸需要的文件（一個(gè)jnlp格式的文件，本機(jī)裝了JRE/JDK才能打開）。經(jīng)測(cè)試在IE7下這個(gè)鏈接似乎不管用，在Firefox 3下正常。
然后運(yùn)行下載下來的jnlp文件，就打開了TC客戶端。第一次運(yùn)行和有更新的時(shí)候會(huì)自動(dòng)下載安裝程序，等待即可，很快。
在我這里有時(shí)會(huì)提示“語法錯(cuò)誤”，但沒有任何影響，點(diǎn)“確定”就可以。啟動(dòng)可能會(huì)慢一些，耐心等待。
然后輸入用戶名密碼，在Connection的地方選合適的登錄方式（一般Direct就行，如果不行的話可以試試別的或者用AUTODETECT自動(dòng)檢測(cè)），在PROXY處設(shè)置代理，點(diǎn)GO登陸。這時(shí)可能還會(huì)提示語法錯(cuò)誤，再確定就行，這個(gè)也沒有什么影響。

界面
下面的圖們來自原文，很經(jīng)典，不打算改動(dòng)了。請(qǐng)使用等寬字體瀏覽。
主界面：
———————————————————————–
|   Advertisements………….                                       |
———————————————————————–
| Main | Lobbies | Options | Practice Rooms | Active Contests | Help ||
———————————————————————–
|                                                 | Clock |           |
———————————————————————–
| Rating Key | Who’s here |                 Chat Area                 |
|     .      |            |                                           |
|     .      |            |                                           |
|     .      |            |                                           |
|     .      |            |                                           |
|     .      |            |                                           |
|————|            |                                           |
|  MESSAGES  |            |                                           |
|————|            |                                           |
|LEADER BOARD|            |                                           |
|————|            |                                           |
|            |            |                                           |
|            |            |——————————————-|
|            |            | >>_______________________________________ |
———————————————————————–
Advertisements 廣告。
菜單項(xiàng):
- Main里可以看在線名單和找人。
- Lobbies基本用不著，因?yàn)橛脩粢话愣荚贑hat Room 1。
- Options里是一些選項(xiàng)和顏色設(shè)置。
- Practice Rooms里有大量的練習(xí)，都是以前比賽的題目
- Active Contests只有有比賽的時(shí)候才有用，顯示當(dāng)前正在進(jìn)行和將要進(jìn)行的比賽以及比賽注冊(cè)之類的東西。
- Help里是….不用說了吧。
Rating Key: handle的顏色是隨著積分而改變的，這里顯示了積分與顏色的關(guān)系。
MESSAGES: 比賽的時(shí)候這里有注冊(cè)提示和clarification。
LEADER BOARD: 看每個(gè)room的最高分。
Who’s here: 當(dāng)前room里的人。
Chat Area: 聊天。

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

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

注意事項(xiàng)
1.在TC主頁（http://www.topcoder.com/tc）上可以看到Next SRM，這是下次SRM的時(shí)間。注意我們的時(shí)間與他們剛好相差12小時(shí)，因此若時(shí)間是7月9日9:00 PM的話，這里是7月10日9:00 AM。還有要注意的是美國有夏令時(shí)，非夏令時(shí)的時(shí)候，還要再加1小時(shí)，就是7月10日10:00 AM。
2.Practice Rooms里寫的程序只要點(diǎn)SAVE就可以保存，下次login的時(shí)候還可以看到，但是比賽時(shí)候的程序必須Submit才可以在coding phase結(jié)束后保存(coding phase結(jié)束前還是只要SAVE就可以的)。
3.若想cha別人的程序，自己必須是正分(0分也不行)，所以若沒有一題有正確的程序但有很好的數(shù)據(jù)的話，隨便交一道看上去正確的程序，然后在challenge的時(shí)候快下手，就可以賺到了。
4.客戶端自帶的編輯器只有基本的編輯功能和編譯及測(cè)試功能，所以若覺得不方便的話可以使用parser和plugin，TC主頁最下面有plugin的連接。每個(gè)plugin都有詳細(xì)說明文檔，這里不再贅述。
5.TC的FAQ：http://www.topcoder.com/?&t=support&c=index
6.最后一條，千萬不要作弊，會(huì)有嚴(yán)重的后果。

SRM的輸入輸出
SRM是不用標(biāo)準(zhǔn)或文件輸入和輸出的，只要寫一個(gè)類的一個(gè)成員函數(shù)。也就是說，你需要編寫的并不是一個(gè)完整的程序，而是一個(gè)類。
輸入是成員函數(shù)的參數(shù)，輸出用return，所以經(jīng)常需要STL中的vector和string。
因?yàn)門C的系統(tǒng)并不測(cè)試標(biāo)準(zhǔn)輸出，所以標(biāo)準(zhǔn)輸出可以當(dāng)調(diào)試用。
下面以SRM 413 Div 2的1000分題目介紹程序的寫法。
題目如下（選擇不同的語言，題目描述會(huì)略有不同，本文以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.

下面是我寫的一個(gè)錯(cuò)誤算法的程序，僅供參考格式用：

#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) | 評(píng)論 (0) | 編輯 收藏

記于松江維也納賓館

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

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

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

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

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

二分圖：

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

最小覆蓋：

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

Konig定理：

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

 證明：

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

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

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


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

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

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

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


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

這一題首先對(duì)給定的圖做一次floyd，這樣就能求出兩個(gè)點(diǎn)之間最少需要走的時(shí)間。
然后判斷兩個(gè)工作之間是否存在先后關(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;
        }

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

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

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


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

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

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

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