这也算一个数学类的杂题吧。题目本身比较有意思，解题的思路很需要猜想。题目的意思用+和-去替代式子(? 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;
}