摘要： Problem DescriptionIn the game of DotA, Pudge’s meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecutive metallic sticks which are of the same length.Now Pudge wants to do some operations on the hook.Let us number the consecutive metallic stick 閱讀全文

摘要： Problem Description很多學(xué)校流行一種比較的習(xí)慣。老師們很喜歡詢(xún)問(wèn)，從某某到某某當(dāng)中，分?jǐn)?shù)最高的是多少。這讓很多學(xué)生很反感。不管你喜不喜歡，現(xiàn)在需要你做的是，就是按照老師的要求，寫(xiě)一個(gè)程序，模擬老師的詢(xún)問(wèn)。當(dāng)然，老師有時(shí)候需要更新某位同學(xué)的成績(jī)。Input本題目包含多組測(cè)試，請(qǐng)?zhí)幚淼轿募Y(jié)束。在每個(gè)測(cè)試的第一行，有兩個(gè)正整數(shù) N 和 M ( 0<N<=200000,0<M<5000 )，分別代表學(xué)生的數(shù)目和操作的數(shù)目。學(xué)生ID編號(hào)分別從1編到N。第二行包含N個(gè)整數(shù)，代表這N個(gè)學(xué)生的初始成績(jī)，其中第i個(gè)數(shù)代表ID為i的學(xué)生的成績(jī)。接下來(lái)有M行。每一行有一個(gè) 閱讀全文

摘要： 描述在一面很長(zhǎng)的墻壁上，工人們用不同的油漆去刷墻，然而可能有些地方刷過(guò)以后覺(jué)得不好看，他們會(huì)重新刷一下。有些部分因?yàn)橹貜?fù)刷了很多次覆蓋了很多層油漆，toshio很好奇那些地方被刷過(guò)多少種顏色的油漆。輸入若干行輸入，每行兩個(gè)數(shù)字B[i],E[i](0<=B[i]<=E[i]<=200000)表示這次刷的墻壁是哪一段（假設(shè)每次刷的時(shí)候油漆顏色都和之前的不同），以0 0結(jié)束又若干行輸入，每行兩個(gè)數(shù)字begin[i],end[i]（0<=begin[i]<=end[i]<=200000）表示toshio詢(xún)問(wèn)的段，以0 0結(jié)束輸出對(duì)于每個(gè)toshio的詢(xún)問(wèn)輸出(end 閱讀全文

摘要： DescriptionConsider equations having the following form:a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0The coefficients are given integers from the interval [-50,50].It is consider a solution a system (x1, x2, x3, x4, x5) that verifies the equation, xi∈[-50,50], xi != 0, any i∈{1,2,3,4,5}.Determine how many sol 閱讀全文

摘要： 題目：http://poj.org/problem?id=1521題目大意：給定字符串，求哈夫曼編碼長(zhǎng)和它與等長(zhǎng)編碼的比值做這道題目的時(shí)候wrang了好幾次，但是，經(jīng)過(guò)調(diào)試之后，我徹底了解了哈夫曼樹(shù)的過(guò)程說(shuō)來(lái)相當(dāng)有價(jià)值了。在下面我也會(huì)分享出來(lái)的。View Code #include <iostream> #include "cstdio"#include "string"#include "cstring"#include <queue> using namespace std; struct Num{ int 閱讀全文

摘要： DescriptionFarmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needsN(1 ≤N≤ 20,000) planks of wood, each having some integer lengthLi(1 ≤Li≤ 50,000) units. He then purchases a single long board just long enough to saw into theNplanks (i 閱讀全文

摘要： 基本術(shù)語(yǔ) 哈夫曼樹(shù)又稱(chēng)為最優(yōu)樹(shù). 1、路徑和路徑長(zhǎng)度 在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱(chēng)為路徑。 通路中分支的數(shù)目稱(chēng)為路徑長(zhǎng)度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1， 則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)-1。 2、結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度 若將樹(shù)中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱(chēng)為該結(jié)點(diǎn)的權(quán)。 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。 3、樹(shù)的帶權(quán)路徑長(zhǎng)度 樹(shù)的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為WPL。Huffman的構(gòu)造方法 假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分... 閱讀全文

摘要： 暴雪公司有個(gè)經(jīng)典的字符串的hash公式先提一個(gè)簡(jiǎn)單的問(wèn)題，假如有一個(gè)龐大的字符串?dāng)?shù)組，然后給你一個(gè)單獨(dú)的字符串，讓你從這個(gè)數(shù)組中查找是否有這個(gè)字符串并找到它，你會(huì)怎么做？有一個(gè)方法最簡(jiǎn)單，老老實(shí)實(shí)從頭查到尾，一個(gè)一個(gè)比較，直到找到為止，我想只要學(xué)過(guò)程序設(shè)計(jì)的人都能把這樣一個(gè)程序作出來(lái)，但要是有程序員把這樣的程序交給用戶(hù)，我只能用無(wú)語(yǔ)來(lái)評(píng)價(jià)，或許它真的能工作，但也只能如此了。最合適的算法自然是使用HashTable（哈希表），先介紹介紹其中的基本知識(shí)，所謂Hash，一般是一個(gè)整數(shù)，通過(guò)某種算法，可以把一個(gè)字符串"壓縮"成一個(gè)整數(shù)，這個(gè)數(shù)稱(chēng)為Hash，當(dāng)然，無(wú)論如何，一個(gè)32位 閱讀全文

摘要： 在看哈希之前還是來(lái)看看“散列函數(shù)（哈希函數(shù)）”吧，后面會(huì)用到的。解決沖突的方法。 開(kāi)放定址法。如果h(k)已經(jīng)被占用，按如下序列探查： (h(k)+p(1))%TSize, (h(k)+p(2))%TSize, …,(h(k)+p(i))%TSize,… 其中，h(k)為哈希函數(shù)，TSize為哈希表長(zhǎng)，p(i)為探查函數(shù)。 在 h(k)+p(i-1))%TSize的基礎(chǔ)上，若發(fā)現(xiàn)沖突， 則使用增量 p(i) 進(jìn)行新的探測(cè)，直至無(wú)沖突出現(xiàn)為止。 其中，根據(jù)探查函數(shù)p(i)的不同，開(kāi)放定址法又分為 (1)線(xiàn)性探查法（p(i) = i : 1 , 2 , 3 , …）， ... 閱讀全文

摘要： DescriptionYou have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.InputInput consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message 閱讀全文