STEP BY STEP

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题意是用字符串描述的一棵四叉树，读取字符串获得最终叶子节点的颜色。输入是2个字符串，根据这2个字符串建立2个四叉树。然后对于，指定位置的叶子节点，如果2颗树的叶子颜色其中一个为黑色，那么ans++，输出的就是ans。
类似树形结构的东西，直接一个函数递归求解即可。函数参数，一般是字符串地址，当前位置，然后还有其它在递归时候需要用到的东西。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#define BLACK (1)
#define WHITE (2)
#define MAX (32)
int nStateA[MAX][MAX];
int nStateB[MAX][MAX];

char szOne[10000];
char szTwo[10000];

void GetState(int nState[MAX][MAX], char* pszLine, int nPos,
              int nSize, int nX, int nY)
{
    if (pszLine[nPos] == 'p')
    {
        ++nPos;
        GetState(nState, pszLine, nPos, nSize / 2, nX + nSize / 2, nY);
        GetState(nState, pszLine, nPos, nSize / 2, nX, nY);
        GetState(nState, pszLine, nPos, nSize / 2, nX, nY + nSize / 2);
        GetState(nState, pszLine, nPos, nSize / 2, nX + nSize / 2, nY + nSize / 2);
    }
    else
    {
        for (int i = nX; i < nX + nSize; ++i)
        {
            for (int j = nY; j < nY + nSize; ++j)
            {
                if (pszLine[nPos] == 'e')
                {

                    nState[i][j] = WHITE;
                }
                else
                {
                    nState[i][j] = BLACK;
                }
            }
        }         ++nPos;
    }
}

int main()
{
    int nCases;

    scanf("%d\n", &nCases);
    while (nCases--)
    {
        gets(szOne);
        gets(szTwo);
        int nPos = 0;
        GetState(nStateA, szOne, nPos, MAX, 0, 0);
        nPos = 0;
        GetState(nStateB, szTwo, nPos, MAX, 0, 0);
        int nAns = 0;
        for (int i = 0; i < MAX; ++i)
        {
            for (int j = 0; j < MAX; ++j)
            {
                if (nStateA[i][j] == BLACK || nStateB[i][j] == BLACK)
                {
                    nAns++;
                }
            }
        }
        printf("There are %d black pixels.\n", nAns);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 903 阅读时长 ≈ 1 分钟

这也是一个数学题，刚开始还真以为好难的样子，需要用到什么数论的理论啊。其实，只要去找规律就行了。
题意是给出一个进制，一个数字的最低位，和另外的一个数字，比如10进制，第一个数字的最低位是7，第二个数字是4，根据这些信息，和规则（XXXXX7 4 = 7XXXXX，例子: 179487 4 = 717948 ）求出第一个数字的最小长度。这个规则的意思是乘积是把第一个数字的最低位移动到最高位上去就行了。
貌似很难的样子，其实用笔在纸上求一下XXXXX7 4 = 7XXXXX就会发现。XXXXX7的每一位都是能够确定的，当然顺序是从最低位到最高位开始。因为知道最低位，所以次低位一定是最低位第二个数%base。以此类推，递归下去即可。最终条件是，没有进位了，而且乘积+原来的进位==最低位。
我用的递归完全可以改成循环的形式，这样速度应该会快些。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

这是一个很神的数学题吧。基本上过这个题的很多都会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边的值最接近，而且右边小于左边。能很快写对这个题真不是件容易的事情。。。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3.6k 阅读时长 ≈ 3 分钟

这是一个几何题。题意是给出一系列点，点最多才15个，求一个这里面的三个点组合出来的三角形，其面积是最大的，而且没有任何其它的点在这个三角形的内部和边界上。求三角形的面积，题目上面已经给了公式，也可以用0.5|a||b|sin(a,b)求，这里的a和b指的是2条边代表的向量。
现在就剩下一个问题了，怎么判断一个点在三角形的内部和边界上。在边界上，比较好判断，判断是否共线，然后再点是在线段的内部。
具体说明下，判断一个点在三角形内部的思路。我用的还是线性规划的思想。*如果该点在三角形的内部，那么任取三角形的一条边，该内部点和剩余的三角形的一个顶点必定在三角形的那条的边的同一侧。这个方法也可以推广到N边的凸多边形，证明的话很简单，因为线性规划一直在划分区域。所以，划分到最后围起来的区域就是凸多边形的内部了。
至于写代码的话，由于是第一次写这种几何题，写得很凌乱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

说实话，这个题不是我亲自推算出来。一直想到崩溃了，明知道只差一步，硬是无法想出来。实在想不出了，看了下别人解题报告上的解释。真的很惭愧很崩溃。。。这就是一个数列推理的题目吧。
给出一个数列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了。
公式：</span>

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.9k 阅读时长 ≈ 2 分钟

这又是一个数学题，不过我还是比较喜欢做这类数学杂题的。题目意思很简单，给2个十进制数，n和b。如果用b进制表示n!，需要多少位数，这个表示末尾会有多少个0。这个题并不需要什么高深的知识，这一点也是我喜欢做这类题的一个方法。
大家显然都知道求n！用10进制表示末尾会有多少个0的方法，就是求2 * 5最多有多少对。那么，b进制了。方法类似，发散一下想法而已。
我还是先说求多少位数的方法吧。 b的m-1次 看到这个不等式应该有想法了吧。两边同时取logb，就可以得到Σlogi(1<=i 再说怎么求末尾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=9t=7137start=30上说的数据还是wa了。而且我还发现log10计算精度高很多，如果log(这个是自然对数)去计算，这个网站上的数据都过不了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

这是一道数学题吧。想清楚之后就发现就是求累加和。
问题是给定一个正方形(体,超体)，求其中的所有的正方形(体,超体),长方形(体,超体)。 比如，4 4的正方形中，有14个正方形，22个长方形，4 4 4的立方体中有36个正方体，180个长方体。依次类推，超正方体指的是四维空间。
观察一下一个44正方形中，仔细验证一下就会发现，正方形的个数是 Σ(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)。意思是求ij的和，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)。这样的话，根本不需要使用这些难记忆的公式了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 960 阅读时长 ≈ 1 分钟

这是一个数学题，比较有意思。题意大致是：有2条平行的直线，第一条上面有m个点，第二条上面有n个点。那么连接这写点能产生mn条直线(不包括和原来的执行平行的直线)。问这mn直线最多有多少个内交点(意思是不属于原来m,n个点的交点)…
想来想去，推理了1个多小时才出来正式结果。感觉比较有意思，写篇博文记录下。我先是从反面排除，想了试了好久到最后还是发现无法排除干净。。。最后只能从正面开始求证了。我这样定义一条执行(i，j)，其中i代表在第一条直线中的端点，j代表在第二条直线中的端点。显然1 现在的话只要求出和直线(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)得到和式(mnn - mn - nn + n) / 2，再对这个式子进行i从1到m的累加。因为没有i了，其效果就是乘以m。然后最终的和除以2，所以最后的表达式是(mmnn - mmn - mnn + mn) / 4。这个式子显然是关于m,n对称的。这一点也可以验证这个式子的正确性。

程序写起来就很简单了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.9k 阅读时长 ≈ 3 分钟

这是一道很简单的题吧，大数都不需要用到，可是很悲剧wa了很久。确实写题太不严谨了，出了好多bug，甚至题意都没注意清楚。
这种题我一直忘记忽略前导’0’。还有题目没有给出最长的数字的长度，所以最好用string类。
使用longlong之前最好已经测试了OJ，是用%lld还是%I64d，如果OJ后台是linux下的g++，只能是%lld，Windows下的MinGW32(Dev-C++也一样用的是这个库)要用%I64d才能正确。所以预赛之前需要对普通题进行测试下。还有注意复合逻辑表达式是否写正确了，最近经常写错了，太郁闷了。
给自己提个醒吧，校赛这种题再不能迅速A掉基本太丢人了。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#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;
}