這也算一個數學類的雜題吧。題目本身比較有意思，解題的思路很需要猜想。題目的意思用+和-去替代式子(? 1 ? 2 ? ... ? n = k)中
的？號，對于指定的K，求最小的n。
For example: to obtain k = 12 , - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。
這個題，我的思路大致如下。首先，K可能是正的也是負的，而且顯然負的情況，有相應的正對應情況。那么考慮所有k為正的情況。
由于k一定小于等于n*(n+1)/2的，所以可以先求出這樣的最小n。這個可以二分搜索，或者直接用解不等式方程(不過這種方法一直wa了)。
然后就剩下的是第二點了，假設a + b = n*(n+1)/2, a - b = k。可以得到
n*(n+1)/2 - k = 2 * b。意思是，必須滿足
n*(n+1)/2
和k的差為偶數。假如滿足了，這樣的n是不是一定OK了？？？
答案是肯定的，這一點就是需要猜想的地方了。因為，仔細觀察下，1到n的數字可以組合出任意的1到 n*(n+1)/4之間的數字，這個數字
即是b。至于證明，可以用數學歸納法從n==1開始證明了。。。至此已經很簡單了。
由于求n存在2種不同的方法，而且我開始用解一元二次不等式的方法求的N，出現了浮點誤差，一直WA了。后面改成二分才過了。。。
代碼如下：
#include <stdio.h>
#include <math.h>
int GetN(int nK)
{
int nBeg = 1;
int nEnd = sqrt(nK * 2) + 2;
while (nBeg <= nEnd)
{
int nMid = (nBeg + nEnd) / 2;
int nTemp = (nMid * nMid + nMid) / 2;
if (nTemp >= nK)
{
nEnd = nMid - 1;
}
else
{
nBeg = nMid + 1;
}
}
return nEnd + 1;
}
int main()
{
int nK;
int nTest;
scanf("%d", &nTest);
while (nTest--)
{
scanf("%d", &nK);
if (nK < 0)
{
nK *= -1;
}
//int nN = ceil(sqrt(2 * fabs(1.0 * nK) + 0.25) - 0.5 + 1e-9);
//上面那種方法存在浮點誤差,wa了三次
int nN = GetN(nK);
while (1)
{
if (((nN * nN + nN) / 2 - nK) % 2 == 0)
{
printf("%d\n", nN);
break;
}
++nN;
}
if (nTest)
{
printf("\n");
}
}
return 0;
}
說實話，這個題不是我親自推算出來。一直想到崩潰了，明知道只差一步，硬是無法想出來。實在想不出了，看了下別人解題報告上
的解釋。真的很慚愧很崩潰。。。這就是一個數列推理的題目吧。
給出一個數列ci（1<=ci<=n)，然后給出數列ai中的a0和a(n+1)。并給出一個公式ai = ( a(i-1) + a(i+1) ) / 2 - ci。題目的意思
是讓求a1。大家在很久以前的高中時代一定做過很多的數列題，所以我一看到這個題還是感覺很親切的。然后就開始推算。我把上面那
個公式，從i==1到i==n，全部累加起來。消去2邊一樣的項，得到一個結果
a1 + an = a0 + a(n+1) - 2 Σci(1<=i<=n)。從這
個公式，我只能得到a1和an 的和。想來想去都無法直接求出a1的值。但是，我也知道如果能求出a1，那么ai中的任何其它項都是能求
出來的。我猜想a1和an相等，提交當然wa了。然后，我猜想ai是a0和a(n+1)的i分點，提交還是wa了。后面這個猜想倒是合理點，但是
還是有不嚴謹的地方，因為那樣，a1的值之和a0，a(n+1)，c1這三個值有關系了。
這個題其實以前我想了一下，沒想出來。然后今天重新想的時候可能受以前的影響，限制了一個思路。那就是，再對式子a1 + an =
a0 + a(n+1) - 2 Σci(1<=i<=n)進行累加。其實，也有a1 + a(n-1) = a0 + an - 2 Σci(1<=i<=n-1)。這樣累加n次，剛好可以把
a2-an全部消去。可以得到，一個式子(n+1)a1 = n * a0 + a(n+1)- 2 ΣΣ cj(1<=j<=i) (1<=i<=n)。那么就可以直接求出a1了。
公式：
代碼如下：
#include <stdio.h>
#include <string.h>
int main()
{
int nCases;
int nN;
double a0, an1;
double a1;
double ci[3000 + 10];
double c;
double sum;
scanf("%d", &nCases);
while (nCases--)
{
scanf("%d", &nN);
scanf("%lf%lf", &a0, &an1);
sum = 0.0;
memset(ci, 0, sizeof(ci));
for (int j = 1; j <= nN; ++j)
{
scanf("%lf", &c);
ci[j] = ci[j - 1] + c;//ci[j]代表數列ci中第1-j項的和
sum += ci[j];
}
a1 = (nN * a0 + an1 - 2 * sum) / (nN + 1);
printf("%.2f", a1);
putchar('\n');
if (nCases)
{
putchar('\n');
}
}
return 0;
}
這又是一個數學題，不過我還是比較喜歡做這類數學雜題的。題目意思很簡單，給2個十進制數，n和b。如果用b進制表示n!，
需要多少位數，這個表示末尾會有多少個0。這個題并不需要什么高深的知識，這一點也是我喜歡做這類題的一個方法。
大家顯然都知道求n！用10進制表示末尾會有多少個0的方法，就是求2*5最多有多少對。那么，b進制了。方法類似，發散一下想法而已。
我還是先說求多少位數的方法吧。
b的m-1次 <= n！<= b的m次（PS，這個不等式如果把b換成10大家一定會明白的），
看到這個不等式應該有想法了吧。兩邊同時取logb，就可以得到
Σlogi(1<=i<=n) <= m，m直接就求出來了。m即是位數。
再說怎么求末尾0的，發散下想法，我們也可以對n！中的每個因子試著求b的因子對，一共有多少對。但是，后面發現這樣不行，
因為比如b是16，1和16是一對因子，2和8是一對因子，4和4是一對因子，也就是因為2也是4的因子，這樣計算因子對就會重復了。
但是對于b等于10的情況，可以例外而已。
呵呵，考慮其它的方法。求素數因子。任何數字都可以被分解為一些素數因子的乘積，這是毋容置疑的。那么，我們去分解n！中的
小于等于b的素數因子，并將其個數存儲在數組里面。然后死循環的去分解b的素數因子，能夠完全分解一次
(具體看下代碼，不好描述），ans就加1。否則，已經沒有末尾0了。
雖然提交了16次才過。不過最后還算不錯吧，只用了0.508s。相比20s的時間界限，很小了。網上有些過的代碼，跑一個數據都要
幾分鐘。。。PS：uva上那些神人，怎么用0.0s算出來的，很難想象啊。
這個題目還有個很大的需要注意的地方，就是浮點數的精度問題。前面講到求位數需要用到log函數，log函數的計算精度就出問題了。
最后需要對和加一個1e-9再floor才能過。特別需要注意這一點，因為開始我的程序過了所有的http://online-judge.uva.es/board/viewtopic.php?f=9&t=7137&start=30上說的數據還是wa了。而且我還發現
log10計算精度高很多，如果log(這個是自然對數)去計算，這個網站上的數據都過不了。
#include <stdio.h>
#include <string.h>
#include <math.h>
int nN, nB;
int nDivisor[1000];
int GetDigit(int nN, int nB)
{
double fSum = 0.0;
for (int i = 2; i <= nN; ++i)
{
fSum += log10(i);
}
fSum /= log10(nB);
return floor(fSum + 1e-9) + 1;
}
int GetZero(int nN, int nB)
{
memset(nDivisor, 0, sizeof(nDivisor));
for (int i = 2; i <= nN; ++i)
{
int nTemp = i;
for (int j = 2; j <= nTemp && j <= nB; ++j)//這樣循環就可以進行素數因子分解了
{
while (nTemp % j == 0)
{
nDivisor[j]++;
nTemp /= j;
}
}
}
int nAns = 0;
while (1)
{
int nTemp = nB;
for (int j = 2; j <= nTemp; ++j)//分解nB
{
while (nTemp % j == 0)
{
if (nDivisor[j] > 0)//如果還可以繼續分解
{
--nDivisor[j];
}
else //直接可以goto跳出多重循環了
{
goto out;
}
nTemp /= j;
}
}
++nAns;
}
out:
return nAns;
}
int main()
{
while (scanf("%d%d", &nN, &nB) == 2)
{
int nDigit = GetDigit(nN, nB);
int nZero = GetZero(nN, nB);
printf("%d %d\n", nZero, nDigit);
}
return 0;
}
我們2個人和一個大二的小學弟，學弟以前沒有基礎，完全處于復雜度還不會估計的醬油狀態。說實話，這次剛開始還不錯，1個半小時左右就出了2個題，當時排在第8。也許這次的題有點難，其實也沒那么難，畢竟有人做出了8道題，而且是人，不是神。他們比我們強很多，雖然其余的隊基本多的就到4個題了。最悲劇的是，我們后面都沒有出題，I題和J題是最可能出的，還有那2個異或，如果勇敢的想下去做下去的話，也是可能的。說實話，還是得怪我，快2個星期沒怎么刷題了，就是忙這所謂的畢設。 我一直算那種想法比較好的，容易出想法，容易來靈感，但是這次真的也很好的反應了我們的水平，還是非常不夠。這半年多的努力，學會了很多東西，但是更多的還是不會的東西。這半年來最幸運的是，我的訓練方法是正確的。其實，也是因為我本身就是想學算法，不是急功近利的那種，所以，一直以來都不看解題報告，基本靠自己思考。ACM真的是一件有趣的事情，高中自然沒這個本事和運氣基礎OI。大一就學了個C語言，大二學了點C++，Windows程序設計和數據結構。大二暑假，訓練了不到一個月的ACM，后面就一直處于醬油狀態了。其實，我真的算想法還不錯的人，所以，我才一直對別人怎么想出我那些不會的題目感興趣。其實，最有趣的東西應該就是怎么想出這些東西來了。 我們隊最大的不足就是我們時間還比較短。看一下我寫過的acm代碼，還是從2011年11月6號開始的，而且最開始我還在寫百練上的那些程序設計導引上的代碼。從那個時候開始算OJ上過了的題量，即使算上參加的所有比賽，估計也不會超過200個，還有那么多的水題。。。有的時候，真的是一題見血，一題就給了我N多的啟發。看書基本也是從正月開始看的算導，現在還有一部分沒看完。無論怎么樣，至少還有機會繼續搞下去。還有可能去參加區域賽，這就是最大的安慰。所有的其它事情，都可以放棄，但是ACM這次不能放棄，不能猶豫，不能妥協了。人無再少啊。。。 我其實也不是很喜歡計劃的那種，一般是做一個大致的期望，然后每天做一些事情朝那個方向努力。所幸的是，從大一學C語言開始，我就發現，學編程，學計算機科學，以及到現在的學算法，這些都是我喜歡的事情，連被英語單詞，我都覺得有意思了。所以，這樣下去也不錯，不至于無聊，并且有所收獲，而且朝著我的目標。但是，這一次不能這樣了。僅僅這樣完全不夠，ACM應該需要點其它的東西，需要那種更強大的付出然后那種不計回報的堅持吧。應該說過程就是最大的收獲了，即使最后連個紀念獎都沒有。。。紀念獎應該都有，不至于擔心。。。
剛剛ACM校賽頒獎了，還是二等獎，本來是滿懷期待去領一等獎的。。。校內第四名，整個第八名。。。基本上已經盡了了，第3個小時40分鐘左右還是校內第二的，出了5道題。。。最后沒有出題了。有一個是網絡流的題，因為不熟悉沒寫。讓寫了其它題，那個題據說是騰訊的面試題。比較麻煩，不好過。那個題估計題目數據比較弱，被人爆了。因為后面想想出題人的說的一個解法不是很嚴謹。無論怎么樣，第三年參加校賽還是沒有拿一等獎。這一次，我沒有在打醬油了。。。準備了近半年，還是弄得個這樣的結果。。。唉。。。 從去年騎車去崀山回來之后，基本絕大部分時間都放在學算法上面了。poj百練刷了100道左右的題，uva上面50道左右的題。最重要的是，我沒有看一個解題報告，我全部是自己想出來A掉的。。。今年開始看的算法導論，到現在基本快看完網絡流了，雖然圖論看得不怎么樣，也沒做些什么訓練。大二大三就沒有認真搞過ACM，當時以為一定會去工作，c++和vc桌面開發學得比較多，時間散開得比較范。以前一直處于打醬油中，只有大二暑假集訓做了一定量的題。因為比賽去了一定次數，一直被虐中，心里也從沒放棄過ACM。既然保研了，最有意義的事情就只能是ACM了。從那個時候起，宅了半年吧。這學期畢業設計一點也沒做，就交了報告。唉，尤其這學期真的很揪心啊。畢設搞不好會做得很爛，上次中期檢查0%的進度。過幾天又得重新檢查了。這一段時間的希望都一直寄托在校賽上面，拿一個一等獎，也對得起當了這么多次水軍了。想不到，唉。。。真不知道，大學這么幾年都干了些什么。。。
最近一直沒跟很多人聯系，對不住了，我一直都很宅，不過我一直都把你們都朋友。。。打算搞定畢設后繼續ACM，一直到秋季區域賽全部結束，至死方休吧，暑期留校集訓，然后繼續留校刷題吧，一直刷到區域賽，把題量刷到300（寧肯刷水題也不允許刷解題報告）吧。有此打算學弟們，可以跟我和吳尚聯系。如果區域賽再連個銅獎都拿不回來，會遺憾終生的。。。
謹以此文祭奠我悲催的ACM歷程！！！
Fig: A 4x4 Grid Fig: A 4x4x4 Cube 這是一道數學題吧。想清楚之后就發現就是求累加和。
問題是給定一個正方形(體,超體)，求其中的所有的正方形(體,超體),長方形(體,超體)。 比如，4 * 4的正方形中，有14個正方形，
22個長方形，4 * 4 * 4的立方體中有36個正方體，180個長方體。依次類推，超正方體指的是四維空間。
觀察一下一個4*4正方形中，仔細驗證一下就會發現，正方形的個數是 Σ(4 - i + 1) * (4 - i + 1)(其中i從1到4)，長方形的個數是
Σ(4 - i + 1) (其中j從1到4) * Σ(4 - j + 1)(其中j從1到4)。如果變成3維的就多一層k，k也從1變化到4。如果變成4維的就再多一層l，
l也從1變化到4。
然后變換一下，就可以得到s2(n) = 1^1 + 2^2 + ... + n^n，s3(n)則是對立方的累加和，s4(n)則是對四次方的累加和。
再計算r2(n)。可以先把正方形包括在內計算出所有的和。那么r2(n) = Σ(n - i + 1) * Σ(n - j + 1) - s2(n)。如果直接進行這個式子
的求和話很復雜。再觀察一下這個式子，因為n - i + 1的變化范圍就是1到n，那么上面的式子可以變化為 r2(n) = ΣΣi * j - s2(n)。
意思是求i*j的和，i和j都是從1變化到n。很簡單就可以得到r2(n) = pow(n * (n + 1) / 2, 2) - s2(n)。同樣的求和可以得到，
r3(n) = pow(n * (n + 1) / 2, 3) - s3(n)。r4(n) = pow(n * (n + 1) / 2, 4) - s4(n)。
另外如果不知道平方和，立方和，四次方和的公式，也可以迭代計算，復雜度也是O(100)。這樣的話，根本不需要使用這些難記憶的公式了。
代碼如下：
#include <stdio.h>
#include <math.h>
unsigned long long s2[101];
unsigned long long r2[101];
unsigned long long s3[101];
unsigned long long r3[101];
unsigned long long s4[101];
unsigned long long r4[101];
int main()
{
unsigned long long i = 0;
while (i <= 100)
{
s2[i] = i * (i + 1) * (2 * i + 1) / 6;//平方和
s3[i] = i * i * (i + 1) * (i + 1) / 4;//立方和
s4[i] = i * (i + 1) * (6 * i * i * i + 9 * i * i + i - 1) / 30;//四次方和
r2[i] = pow(i * (i + 1) / 2, 2) - s2[i];
r3[i] = pow(i * (i + 1) / 2, 3) - s3[i];
r4[i] = pow(i * (i + 1) / 2, 4) - s4[i];
++i;
}
int nN;
while (scanf("%d", &nN) != EOF)
{
//printf("%I64u %I64u %I64u %I64u %I64u %I64u\n", s2[nN], r2[nN], s3[nN], r3[nN], s4[nN], r4[nN]);
printf("%llu %llu %llu %llu %llu %llu\n", s2[nN], r2[nN], s3[nN], r3[nN], s4[nN], r4[nN]);
}
return 0;
}
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=1731 這是一個數學題，比較有意思。題意大致是：有2條平行的直線，第一條上面有m個點，第二條上面有n個點。那么連接這寫點能產生m*n
條直線(不包括和原來的執行平行的直線)。問這m*n直線最多有多少個內交點(意思是不屬于原來m,n個點的交點)...
想來想去，推理了1個多小時才出來正式結果。感覺比較有意思，寫篇博文記錄下。我先是從反面排除，想了試了好久到最后還是發現無法
排除干凈。。。最后只能從正面開始求證了。我這樣定義一條執行(i，j)，其中i代表在第一條直線中的端點，j代表在第二條直線中的端點。
顯然1 <= i <= m，而且1 <= j <= n。
現在的話只要求出和直線(i，j)相加的直線有多少條，然后對i，j進行累加求和。再對和除以2就能得到答案了。
那么有多少條直線能和直線(i，j）相交了。很顯然，和(i,j)相交的直線的端點必須在其兩側。意思是在第一條直線中的端點范圍為
[1, i - 1],在第二條直線中的端點范圍為[j + 1, n]，總結(i - 1) * (n - j) 條直線。但是還有第二種情況,在第一條直線中的端點范圍
為[i + 1, m], 在第二條直線中的端點范圍為[1, j - 1]，總結(m - i) * (j - 1) 條直線。
總計sum = i * n + i - m -n + j (m - 2 * i + 1) 條直線。
再求
Σsum（j從1到n)得到和式(m*n*n - m*n - n*n + n) / 2，再對這個式子進行i從1到m的累加。因為沒有i了，其效果就是乘以m。
然后最終的和除以2，所以最后的表達式是(m*m*n*n - m*m*n - m*n*n + m*n) / 4。這個式子顯然是關于m,n對稱的。
這一點也可以驗證這個式子的正確性。
程序寫起來就很簡單了，代碼如下：
#include <iostream>
using namespace std;
int main()
{
long long m, n;
int nCases = 0;
while (cin >> m >> n, m + n != 0)
{
long long a = m * m;
long long b = n * n;
cout << "Case " << ++nCases << ": "
<< (a * b - a * n - b * m + m * n) / 4 << endl;
}
return 0;
}
這是一道很簡單的題吧，大數都不需要用到，可是很悲劇wa了很久。確實寫題太不嚴謹了，出了好多bug，甚至題意都沒注意清楚。
這種題我一直忘記忽略前導'0'。
還有題目沒有給出最長的數字的長度，所以最好用string類。
使用longlong之前最好已經測試了OJ，是用%lld還是%I64d，如果OJ后臺是linux下的g++，只能是%lld，Windows下的MinGW32
(Dev-C++也一樣用的是這個庫)要用%I64d才能正確。所以預賽之前需要對普通題進行測試下。
還有注意復合邏輯表達式是否寫正確了，最近經常寫錯了，太郁悶了。
給自己提個醒吧，校賽這種題再不能迅速A掉基本太丟人了。
代碼如下：
#include <stdio.h>
#include <limits.h>
#include <
string.h>
#include <algorithm>
using namespace std;
#define MAX (10000)
char szIntMax[20];
char szLine[MAX];
char szOne[MAX];
char szTwo[MAX];
char szOper[10];
char* MyItoa(
int nNum,
char* pszNum,
int nBase)
{
int nLen = 0;
while (nNum)
{
pszNum[nLen++] = nNum % nBase + '0';
nNum /= nBase;
}
reverse(pszNum, pszNum + nLen);
pszNum[nLen] = '\0';
return pszNum;
}
bool IsBigger(
char* pszOne,
int nLenOne,
char* pszTwo,
int nLenTwo)
{
//printf("pszOne:%s, pszTwo:%s\n", pszOne, pszTwo);
if (nLenOne != nLenTwo)
{
return nLenOne > nLenTwo;
}
else {
for (
int i = 0; i < nLenOne; ++i)
{
if (pszOne[i] != pszTwo[i])
{
return pszOne[i] > pszTwo[i];
}
}
return false;
}
}
int StripHeadZero(
char* pszNum)
{
int nLen = strlen(pszNum);
int i;
for (i = 0; i < nLen && pszNum[i] == '0'; ++i);
if (i == nLen)
{
pszNum[0] = '0';
pszNum[1] = '\0';
nLen = 2;
}
else {
char* pszWrite = pszNum;
char* pszRead = pszNum + i;
nLen = 0;
while (*pszRead)
{
*pszWrite++ = *pszRead++;
++nLen;
}
*pszWrite = '\0';
}
return nLen;
}
int main()
{
int nIntMax = INT_MAX;
MyItoa(nIntMax, szIntMax, 10);
int nLenMax = strlen(szIntMax);
while (gets(szLine))
{
if (szLine[0] == '\0')
{
continue;
}
sscanf(szLine, "%s%s%s", szOne, szOper, szTwo);
printf("%s %s %s\n", szOne, szOper, szTwo);
StripHeadZero(szOne);
StripHeadZero(szTwo);
int nLenOne = strlen(szOne);
int nLenTwo = strlen(szTwo);
bool bFirst =
false;
bool bSecond =
false;
if (IsBigger(szOne, nLenOne, szIntMax, nLenMax))
{
printf("first number too big\n");
bFirst =
true;
}
if (IsBigger(szTwo, nLenTwo, szIntMax, nLenMax))
{
printf("second number too big\n");
bSecond =
true;
}
if (bFirst || bSecond)
{
if (szOper[0] == '+' || (szOper[0] == '*' && szOne[0] != '0' && szTwo[0] != '0'))
{
printf("result too big\n");
}
}
else {
long long nOne, nTwo;
sscanf(szLine, "%lld%s%lld", &nOne, szOper, &nTwo);
long long nResult;
if (szOper[0] == '+')
{
nResult = nOne + nTwo;
}
else if (szOper[0] == '*')
{
nResult = nOne * nTwo;
}
//printf("%I64d\n", nResult);
if (nResult > INT_MAX)
{
printf("result too big\n");
}
}
}
return 0;
}
這個題，粗看之下還沒怎么看懂，這個應該跟我英語水平有關系。然后再看輸入輸出，漸漸的才明白什么意思。原來是要把2*N張破紙組合
成N張一樣的紙。我歷來思維比較隨便，不是很嚴謹的那種。然后，想了一下發現一定會有大于等于N張破紙片是符合前半部分模式的。
那么，可以建一個字典樹，把所有的是前半張紙的找出來。然后根據這前半張紙，找出剩下的后半張紙（因為知道一整張紙的長度，所以知道
剩下的半張紙的長度）。但是寫出來就發現這樣不嚴謹，是不對的。因為單純根據已經找出來的前半張紙，無法確定后半張紙（事實上，只能
確定其長度而已）。
那么只能找其它方法了，再檢查了下數據范圍，發現比較小，那么意味著可以暴力求解了。好吧，那就深搜吧。我把所有的破紙片按照它們
的長度分成一些集合，對于長度為len的紙片集合，只要與長度為nAnsLen - len的紙片集合進行搜索匹配，找出一個可行的解即可了。我又
想當然的認為只要匹配一對集合即可了，那么很顯然又是錯的了。好吧，我只能對所有集合進行匹配了。對每一對集合進行深搜回溯來匹配待
選的Ans，而這個Ans是從第一對集合中搜索出來的答案。
代碼寫得很冗長，很復雜，差不多200多行了。真的是水平有限，這種題很明顯應該有更方便的解法的，而且我的代碼應該不至于寫得這么
亂的。
后面還是錯了很多次，發現了很多bug，比如我如果搜索長度為nAnsLen/2的集合時就必須進行特殊處理。還有最后一個樣例后面不能輸
出’\n'，而且uvaoj不能對這個換行判PE，一直是WA，實在是讓人崩潰。
#include <stdio.h>
#include <string.h>
#define MAX (256 + 10)
#define MAX_NUM (150)
char szLines[MAX_NUM][MAX];
char szAns[MAX];
struct SET
{
int nNum;
char szLines[MAX_NUM][MAX];
bool bUsed[MAX];
};
SET sets[MAX];
char szTmpOne[MAX];
char szTmpTwo[MAX];
int nAnsLen;
bool bFind;
void dfs(int nI, int nNum)
{
if (nNum == 0)
{
bFind = true;
}
else
{
for (int i = 0; i < sets[nI].nNum && !bFind; ++i)
{
for (int j = 0; j < sets[nAnsLen - nI].nNum && !bFind; ++j)
{
if (nI == nAnsLen - nI && i == j)
{
continue;
}
if (!sets[nI].bUsed[i] && !sets[nAnsLen - nI].bUsed[j])
{
strcpy(szTmpOne, sets[nI].szLines[i]);
strcat(szTmpOne, sets[nAnsLen - nI].szLines[j]);
strcpy(szTmpTwo, sets[nAnsLen - nI].szLines[j]);
strcat(szTmpTwo, sets[nI].szLines[i]);
//printf("%s\n", szAns);
if (strcmp(szTmpOne, szAns) == 0 || strcmp(szTmpTwo, szAns) == 0)
{
sets[nI].bUsed[i] = sets[nAnsLen - nI].bUsed[j] = true;
if (!bFind)
{
if (nI == nAnsLen - nI)
{
dfs(nI, nNum - 2);
}
else
{
dfs(nI, nNum - 1);
}
}
sets[nI].bUsed[i] = sets[nAnsLen - nI].bUsed[j] = false;
}
}
}
}
}
}
bool Find(int nI)
{
bFind = false;
for (int i = 0; i < sets[nI].nNum && !bFind; ++i)
{
for (int j = 0; j < sets[nAnsLen - nI].nNum && !bFind; ++j)
{
if (nI == nAnsLen - nI && i == j)
{
continue;
}
sets[nI].bUsed[i] = true;
sets[nAnsLen - nI].bUsed[j] = true;
strcpy(szAns, sets[nI].szLines[i]);
strcat(szAns, sets[nAnsLen - nI].szLines[j]);
if (nI == nAnsLen - nI)
{
dfs(nI, sets[nI].nNum - 2);
}
else
{
dfs(nI, sets[nI].nNum - 1);
}
if (bFind)
{
for (int k = nI + 1; k <= nAnsLen / 2; ++k)
{
bFind = false;
dfs(k, sets[k].nNum);
if (!bFind)
{
break;
}
}
if (bFind)
{
return true;
}
}
strcpy(szAns, sets[nAnsLen - nI].szLines[j]);
strcat(szAns, sets[nI].szLines[i]);
if (nI == nAnsLen - nI)
{
dfs(nI, sets[nI].nNum - 2);
}
else
{
dfs(nI, sets[nI].nNum - 1);
}
if (bFind)
{
for (int k = nI + 1; k <= nAnsLen / 2; ++k)
{
bFind = false;
dfs(k, sets[k].nNum);
if (!bFind)
{
break;
}
}
if (bFind)
{
return true;
}
}
sets[nI].bUsed[i] = false;
sets[nAnsLen - nI].bUsed[j] = false;
}
}
return false;
}
void Search()
{
for (int i = 0; i <= nAnsLen; ++i)
{
if (sets[i].nNum)
{
Find(i);
break;
}
}
}
int main()
{
int nCases;
#ifdef CSU_YX
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
scanf("%d\n", &nCases);
int nNum = 0;
int nTotalLen = 0;
while (gets(szLines[nNum]), nCases)
{
if (szLines[nNum][0] == '\0' && nNum != 0)
{
nAnsLen = nTotalLen * 2 / nNum;
memset(szAns, 0, sizeof(szAns));
Search();
printf("%s\n\n", szAns);
memset(sets, 0, sizeof(sets));
memset(szLines, 0, sizeof(szLines));
nNum = 0;
nTotalLen = 0;
--nCases;
}
else if (szLines[nNum][0] != '\0')
{
int nLen = strlen(szLines[nNum]);
nTotalLen += nLen;
strcpy(sets[nLen].szLines[sets[nLen].nNum], szLines[nNum]);
++sets[nLen].nNum;
++nNum;
}
}
return 0;
}
這是算法導論習題11.1-4。
具體題目如下：
解決該題目的要點：
1.由于是無窮大的數組，所以無法事先初始化該數組。
2.所提供的方案必須是O（1）。
3.使用的額外空間只能是O（n），這樣平均到每一個項上的空間都是O（1）。
一時之間好像沒有一點頭緒，在幾個群里面發問了，網上搜了很久也沒有找到答案，后面一群里有個高人給了個鏈接，里面有解法。
鏈接地址：http://www.cnblogs.com/flyfy1/archive/2011/03/05/1971502.html，這篇文章里面另外給了個pdf，這個pdf估計是解法
的來源。偽代碼寫得不給力，不過前面的英文描述卻很清晰。說實話，這個方法很巧妙。
解法大概的意思如下：
開一個額外的數組A，A[0]表示A數組元素的數目(當然不包括A[0]本身)，A[i]代表插入的第i個元素的key。假設原來的無窮大數組用Huge
表示，如果Huge[i](直接尋址，假設i就是key)有效，則表示其在A數組中的索引。那么如果A[Huge[i]] == i 而且 Huge[i] <= A[0] &&
Huge[i] > 0，則表示i這個位置已經有元素插入了。
插入：A[0]++;A[A[0]] = key; Huge[key] = A[0];
搜索: A[Huge[i]] == i && Huge[i] <= A[0] && Huge[i] > 0 則return true;
刪除: 先搜索該位置是否有元素, 如果Search(key)成功，則先把Huge[ A[A[0]] ] = Huge[key]，
然后交換A[A[0]]和A[Huge[key]]，A[0]--即可。
所有操作都是O（1），平均到每一個項，使用的空間都是O（1）。
我用代碼實現的模擬如下：
#include <stdio.h>
#include <vector>
#include <algorithm>
using std::swap;
using std::vector;
#define INF (100)
int nHuge[INF];
//假設這個巨大的數組是無法初始化的
vector<
int> vA;
void Init()
{
vA.push_back(0);
//添加A[0]表示元素的數目
}
void Insert(
int nKey)
{
vA[0]++;
nHuge[nKey] = vA[0];
vA.push_back(nKey);
}
bool Search(
int nKey)
{
if (nHuge[nKey] > 0 && nHuge[nKey] <= vA[0] && vA[nHuge[nKey]] == nKey)
{
return true;
}
return false;
}
void Delete(
int nKey)
{
if (Search(nKey))
{
nHuge[ vA[vA[0]] ] = nHuge[nKey];
//將huge的最后一個元素中存儲的A數組的索引改為nHuge[nKey]
swap(vA[vA[0]], vA[nHuge[nKey]]);
//交換key
--vA[0];
vA.erase(vA.end() - 1);
}
}
#define MAX (10)
int main()
{
Init();
int i;
for (i = 0; i < MAX; ++i)
{
Insert(i);
}
for (i = 0; i < MAX; ++i)
{
printf("Search:%d %s\n", i, Search(i) ==
true? "Success" : "Failure");
}
printf("\n");
Delete(4);
Delete(9);
Delete(1);
for (i = 0; i < MAX * 2; ++i)
{
printf("Search:%d %s\n", i, Search(i) ==
true? "Success" : "Failure");
}
return 0;
}