2012年5月8日
这也是一个数学题，刚开始还真以为好难的样子，需要用到什么数论的理论啊。其实，只要去找规律就行了。
题意是给出一个进制，一个数字的最低位，和另外的一个数字，比如10进制，第一个数字的最低位是7，第二个数字是4，
根据这些信息，和规则（XXXXX7 * 4 = 7XXXXX，例子
: 179487 * 4 = 717948 ）求出第一个数字的最小长度。这个
规则的意思是乘积是把第一个数字的最低位移动到最高位上去就行了。
貌似很难的样子，其实用笔在纸上求一下XXXXX7 * 4 = 7XXXXX就会发现。XXXXX7的每一位都是能够确定的，当然
顺序是从最低位到最高位开始。因为知道最低位，所以次低位一定是最低位*第二个数%base。以此类推，递归下去即可。
最终条件是，没有进位了，而且乘积+原来的进位==最低位。
我用的递归完全可以改成循环的形式，这样速度应该会快些。
代码如下：
#include <stdio.h>
int nBase;
int nTwo;
int nOneLow;
int GetMin(int nLow, int nCarry, int nNum)
{
//printf("nLow:%d, nCarry:%d, nNum:%d\n", nLow, nCarry, nNum);
int nTemp = nCarry + nLow * nTwo;
if (nTemp == nOneLow)
{
return nNum;
}
return GetMin(nTemp % nBase, nTemp / nBase, nNum + 1);
}
int main()
{
//freopen("out.txt", "w", stdout);
while (scanf("%d%d%d", &nBase, &nOneLow, &nTwo) == 3)
{
printf("%d\n", GetMin(nOneLow, 0, 0) + 1);
}
return 0;
}
2012年5月7日
这是一个很神的数学题吧。基本上过这个题的很多都会wa10多次，而且这个题好像简单的枚举其中的一个指数值都能过，可能是
数据量比较小。
但是，这个题还是有数学的解法的。但是，即使找到了这个正确的解法，过题的话，也是一件很困难的事情。题意大致如下：一只猫，
高度为H，戴了一个帽子，帽子里面有N只猫（N是常数，且未知），同样帽子里面的猫也戴了帽子，但是这些猫的高度变成了H / (N + 1)，
会向下取整。以此递归下去，直到最后的猫的高度都为1为止。现在，给出H和高度为1的猫的数量。要求的是高度大于1的猫的数量，
以及所有猫的高度之和。
很别扭吧。通过上面的信息，得出2个式子。假设one代表为高度为1的猫的数量。one = N的n次。H >= (N + 1)的n次。注意第
二个式子不一定取等号，因为很多时候都是不能整除的。现在要求N和n。2个方程解2个未知数，应该能解出来。但是，注意的是其中
一个还是不等式。。。
指数关系很多时候会转换为对数的关系。所以，继续求对数，有lgH >= n * lg(N + 1)。其中，由第一个式子可以得到n = lg(one)
/ lg(N)。那么最终转换为：lgH >= (lg(one) / lgN) * lg(N + 1)。换个形式就是lgH / lg(One) >= lg(N + 1) / lgN。现在，已经很
清晰了。因为，函数lg(N + 1) / lg(N) 是
单调递减的。看到单调的函数，马上就会知道可以二分了。意思是，我们可以二分出一个N让
lg(N + 1) / lgN 最接近lgH / lg(One)，而且是小于lgH / lg(One)的。剩下的工作就只是求和而已了。
写二分的时候，有一个地方可以注意一下。因为 lg(N + 1) / lgN 可能会出现除数为0的情况，所以可以进一步转换为
lgH * lgN >=
lg(N + 1) * lg(one)。 也是求一个N让上面那个不等式2边的值最接近，而且右边小于左边。
能很快写对这个题真不是件容易的事情。。。
代码如下：
#include <stdio.h>
#include <math.h>
int main()
{
int nInitH, nOnes;
int nN, n;
while (scanf("%d%d", &nInitH, &nOnes), nInitH + nOnes)
{
int nBeg = 1;
int nEnd = nOnes;
int nMid;
while (nBeg <= nEnd)
{
nMid = (nBeg + nEnd) / 2;
double fRes = log10(nInitH) * log10(nMid);
double fTemp = log10(nMid + 1) * log10(nOnes);
if (fabs(fRes - fTemp) < 1e-10)
{
//printf("Find nN:%d\n", nMid);
nN = nMid;
break;
}
else if (fTemp > fRes)
{
nBeg = nMid + 1;
}
else
{
nEnd = nMid - 1;
}
}
n = floor(log10(nInitH) / log10(nN + 1) + 1e-9);
//printf("nN:%d, n:%d\n", nN, n);
int nSum = 0;
int nLazy = 0;
int nNum = 1;
for (int i = 0; i <= n; ++i)
{
nSum += nNum * nInitH;
nLazy += nNum;
nNum *= nN;
nInitH /= (nN + 1);
}
printf("%d %d\n", nLazy - nOnes, nSum);
}
return 0;
}
这是一个几何题。题意是给出一系列点，点最多才15个，求一个这里面的三个点组合出来的三角形，其面积是最大的，而且没有任何其它
的点在这个三角形的内部和边界上。求三角形的面积，题目上面已经给了公式，也可以用0.5*|a|*|b|*sin(a,b)求，这里的a和b指的是2条
边代表的向量。
现在就剩下一个问题了，怎么判断一个点在三角形的内部和边界上。在边界上，比较好判断，判断是否共线，然后再点是在线段的内部。
具体说明下，判断一个点在三角形内部的思路。我用的还是线性规划的思想。
如果该点在三角形的内部，那么任取三角形的一条边，
该内部点和剩余的三角形的一个顶点必定在三角形的那条的边的同一侧。这个方法也可以推广到N边的凸多边形，证明的话很简单，
因为线性规划一直在划分区域。所以，划分到最后围起来的区域就是凸多边形的内部了。
至于写代码的话，由于是第一次写这种几何题，写得很凌乱。
代码如下：
#include <stdio.h>
#include <math.h>
#define MAX (20)
int nN;
struct Point
{
char szLabel[5];
int x;
int y;
};
Point points[MAX];
//三点是否共线
bool IsOneLine(int nOne, int nTwo, int nThree)
{
int nA = points[nTwo].x - points[nOne].x;
int nB = points[nTwo].y - points[nOne].y;
int nC = points[nThree].x - points[nOne].x;
int nD = points[nThree].y - points[nOne].y;
return (nA * nD == nB * nC);
}
//点nOne和点nTwo是否在直线(nBeg,nEnd)的同一侧(不能在直线上)
bool IsSameSide(int nBeg, int nEnd, int nOne, int nTwo)
{
//求直线的向量
int nA = points[nBeg].x - points[nEnd].x;
int nB = points[nBeg].y - points[nEnd].y;
//直线方程为nB(x - points[nBeg].x) - nA(y - points[nBeg].y) = 0
//分别用nOne和nTwo的坐标代入直线方程计算结果，然后将结果相乘
//乘积必须大于0
int nRes = (nB * (points[nOne].x - points[nBeg].x) - nA * (points[nOne].y - points[nBeg].y))
* (nB * (points[nTwo].x - points[nBeg].x) - nA * (points[nTwo].y - points[nBeg].y));
if (nRes > 0)
{
//printf("点:%d,点:%d,在直线nBeg:%d, nEnd:%d的同一侧\n", nOne, nTwo, nBeg, nEnd);
}
return nRes > 0;
}
//点是否在三角形(nOne, nTwo, nThree)外部
bool PointOutTriangle(int nOne, int nTwo, int nThree, int nPoint)
{
//前面3个ifelse是判断点是否在边上
if (IsOneLine(nOne, nTwo, nPoint))
{
if ((points[nOne].x - points[nPoint].x) * (points[nTwo].x - points[nPoint].x) <= 0)
{
return false;
}
}
else if (IsOneLine(nOne, nThree, nPoint))
{
if ((points[nOne].x - points[nPoint].x) * (points[nThree].x - points[nPoint].x) <= 0)
{
return false;
}
}
else if (IsOneLine(nTwo, nThree, nPoint))
{
if ((points[nTwo].x - points[nPoint].x) * (points[nThree].x - points[nPoint].x) <= 0)
{
return false;
}
}
//下面的IsSameSide如果nPoint在直线的(nOne,nTwo)的外侧也会判断为假
//所以需要先在上面判断点是否在边的内侧
return !(IsSameSide(nOne, nTwo, nThree, nPoint)
&& IsSameSide(nOne, nThree, nTwo, nPoint)
&& IsSameSide(nTwo, nThree, nOne, nPoint));
}
bool IsValid(int nOne, int nTwo, int nThree)
{
if (IsOneLine(nOne, nTwo, nThree))
{
//printf("点:%d,%d,%d共线\n", nOne, nTwo, nThree);
return false;
}
for (int i = 0; i < nN; ++i)
{
if (i == nOne || i == nTwo || i == nThree)
{
continue;
}
if (!PointOutTriangle(nOne, nTwo, nThree, i))
{
//printf("点:%d, 在三角形:%d,%d,%d内部\n", i, nOne, nTwo, nThree);
return false;
}
}
return true;
}
//计算三角形(nOne, nTwo, nThree)的面积
double GetArea(int nOne, int nTwo, int nThree)
{
return 0.5 * fabs((points[nThree].y - points[nOne].y) * (points[nTwo].x - points[nOne].x)
- (points[nTwo].y - points[nOne].y) * (points[nThree].x - points[nOne].x));
}
int main()
{
while (scanf("%d", &nN), nN)
{
for (int i = 0; i < nN; ++i)
{
scanf("%s%d%d", points[i].szLabel, &points[i].x, &points[i].y);
}
double fMaxArea = 0.0;
int nI = -1, nJ = -1, nK = -1;
for (int i = 0; i < nN - 2; ++i)
{
for (int j = i + 1; j < nN - 1; ++j)
{
for (int k = j + 1; k < nN; ++k)
{
if (IsValid(i, j, k))
{
//printf("i:%d,j:%d,k:%d valid\n", i, j, k);
double fArea = GetArea(i, j, k);
//printf("Area:%f\n", fArea);
if (fArea > fMaxArea)
{
nI = i;
nJ = j;
nK = k;
fMaxArea = fArea;
}
}
}
}
}
printf("%s%s%s\n", points[nI].szLabel, points[nJ].szLabel, points[nK].szLabel);
}
return 0;
}
2012年5月4日
这也算一个数学类的杂题吧。题目本身比较有意思，解题的思路很需要猜想。题目的意思用+和-去替代式子(? 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;
}
2012年5月3日
说实话，这个题不是我亲自推算出来。一直想到崩溃了，明知道只差一步，硬是无法想出来。实在想不出了，看了下别人解题报告上
的解释。真的很惭愧很崩溃。。。这就是一个数列推理的题目吧。
给出一个数列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;
}
2012年5月2日
这又是一个数学题，不过我还是比较喜欢做这类数学杂题的。题目意思很简单，给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;
}
2012年4月30日
我们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应该需要点其它的东西，需要那种更强大的付出然后那种不计回报的坚持吧。应该说过程就是最大的收获了，即使最后连个纪念奖都没有。。。纪念奖应该都有，不至于担心。。。
2012年4月15日
刚刚ACM校赛颁奖了，还是二等奖，本来是满怀期待去领一等奖的。。。校内第四名，整个第八名。。。基本上已经尽了了，第3个小时40分钟左右还是校内第二的，出了5道题。。。最后没有出题了。有一个是网络流的题，因为不熟悉没写。让写了其它题，那个题据说是腾讯的面试题。比较麻烦，不好过。那个题估计题目数据比较弱，被人爆了。因为后面想想出题人的说的一个解法不是很严谨。无论怎么样，第三年参加校赛还是没有拿一等奖。这一次，我没有在打酱油了。。。准备了近半年，还是弄得个这样的结果。。。唉。。。 从去年骑车去崀山回来之后，基本绝大部分时间都放在学算法上面了。poj百练刷了100道左右的题，uva上面50道左右的题。最重要的是，我没有看一个解题报告，我全部是自己想出来A掉的。。。今年开始看的算法导论，到现在基本快看完网络流了，虽然图论看得不怎么样，也没做些什么训练。大二大三就没有认真搞过ACM，当时以为一定会去工作，c++和vc桌面开发学得比较多，时间散开得比较范。以前一直处于打酱油中，只有大二暑假集训做了一定量的题。因为比赛去了一定次数，一直被虐中，心里也从没放弃过ACM。既然保研了，最有意义的事情就只能是ACM了。从那个时候起，宅了半年吧。这学期毕业设计一点也没做，就交了报告。唉，尤其这学期真的很揪心啊。毕设搞不好会做得很烂，上次中期检查0%的进度。过几天又得重新检查了。这一段时间的希望都一直寄托在校赛上面，拿一个一等奖，也对得起当了这么多次水军了。想不到，唉。。。真不知道，大学这么几年都干了些什么。。。
最近一直没跟很多人联系，对不住了，我一直都很宅，不过我一直都把你们都朋友。。。打算搞定毕设后继续ACM，一直到秋季区域赛全部结束，至死方休吧，暑期留校集训，然后继续留校刷题吧，一直刷到区域赛，把题量刷到300（宁肯刷水题也不允许刷解题报告）吧。有此打算学弟们，可以跟我和吴尚联系。如果区域赛再连个铜奖都拿不回来，会遗憾终生的。。。
谨以此文祭奠我悲催的ACM历程！！！
2012年4月14日
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;
}
2012年4月12日
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;
}