STEP BY STEP

发表于 分类于 ， 阅读次数： 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;
}

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

这个题，粗看之下还没怎么看懂，这个应该跟我英语水平有关系。然后再看输入输出，渐渐的才明白什么意思。原来是要把2 * N张破纸组合成N张一样的纸。我历来思维比较随便，不是很严谨的那种。然后，想了一下发现一定会有大于等于N张破纸片是符合前半部分模式的。
那么，可以建一个字典树，把所有的是前半张纸的找出来。然后根据这前半张纸，找出剩下的后半张纸（因为知道一整张纸的长度，所以知道剩下的半张纸的长度）。但是写出来就发现这样不严谨，是不对的。因为单纯根据已经找出来的前半张纸，无法确定后半张纸（事实上，只能确定其长度而已）。
那么只能找其它方法了，再检查了下数据范围，发现比较小，那么意味着可以暴力求解了。好吧，那就深搜吧。我把所有的破纸片按照它们的长度分成一些集合，对于长度为len的纸片集合，只要与长度为nAnsLen - len的纸片集合进行搜索匹配，找出一个可行的解即可了。我又想当然的认为只要匹配一对集合即可了，那么很显然又是错的了。好吧，我只能对所有集合进行匹配了。对每一对集合进行深搜回溯来匹配待选的Ans，而这个Ans是从第一对集合中搜索出来的答案。
代码写得很冗长，很复杂，差不多200多行了。真的是水平有限，这种题很明显应该有更方便的解法的，而且我的代码应该不至于写得这么乱的。后面还是错了很多次，发现了很多bug，比如我如果搜索长度为nAnsLen/2的集合时就必须进行特殊处理。还有最后一个样例后面不能输出’\n’，而且uvaoj不能对这个换行判PE，一直是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
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#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;
}

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

这是算法导论习题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
表示，如果Hugei有效，则表示其在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）。

我用代码实现的模拟如下：

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

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

题目意思很简单就是计算含括号的四则运算表达式的值。这个题目很坑爹，刚做的时候，题目描述里面只说里面会有空格，后面居然把题目描述改了。所以，这个题无论怎么改，都是不对。因为，不知道是哪个坑爹的出题人，把数据里面加了\t，难道出题人以为\t也是空格。估计，后面修改题目描述，也是发现这个问题后才改的。这可是还是哥了，改了无数多遍，不处理非法数据就超时，略过非常数据当然直接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
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
#include <stdio.h>
#define MAX (100 + 10)
char szData[MAX];

void TrimSpace(char* pszData)
{
    char* pszRead = pszData;
    char* pszWrite = pszData;
    while (*pszRead)
    {
        //由于数据中有\t,与先前题目描述不符合,不处理掉就直接超时了
        if (*pszRead != ' ' && *pszRead != '\t')
        {
            *pszWrite++ = *pszRead;
        }
        ++pszRead;
    }
    *pszWrite = '\0';
}

//nKind代表前一个运算符合的优先级,开始时是0,+-是1,*/是2
double Cal(char*& pszData, int nKind)
{
    double fAns = 0.0;
    while (*pszData && *pszData != ')')//表达式终止的条件是到达'\0'或者碰到右括号
    {
        if (*pszData >= '0' && *pszData <= '9')
        {
            fAns = 10 * fAns + *pszData - '0';
            ++pszData;
        }
        else if (*pszData == '+')
        {
            if (nKind >= 1)
            {
                return fAns;
            }
            ++pszData;
            fAns += Cal(pszData, 1);
        }
        else if (*pszData == '-')
        {
            if (nKind >= 1)
            {
                return fAns;
            }
            ++pszData;
            fAns -= Cal(pszData, 1);
        }
        else if (*pszData == '*')
        {
            if (nKind >= 2)
            {
                return fAns;
            }
            ++pszData;
            fAns *= Cal(pszData, 2);
        }
        else if (*pszData == '/')
        {
            if (nKind >= 2)
            {
                return fAns;
            }
            ++pszData;
            fAns /= Cal(pszData, 2);
        }
        else if (*pszData == '(')
        {
            ++pszData;
            fAns = Cal(pszData, 0);
            ++pszData;//移到')'后面
            return fAns;//一个括号内的是一个完整的表达式,因此直接返回
        }
    }

    return fAns;
}

int main()
{
    while (gets(szData))
    {
        TrimSpace(szData);
        char* pszData = szData;
        printf("%.4f\n", Cal(pszData, 0));
    }
}

一个递归函数能计算出表达式的值，而且能处理优先级和括号，如果是以前的话，我应该是写不出来的。再把算法的实现细节改改，应该也能计算出浮点数的表达式了。

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

这是个简单的字符串处理题目。看题目，数据应该不是很大，直接暴力处理可以过。如果为了加快搜索速度，在中间输入过程中排序，再二分很麻烦，速度也快不了多少，因为只是输入的过程中需要查找。但是，这个题其实很好用map做，代码量可以少很多，也很简洁。
写这篇blog的目的是为了提醒自己，容易题再这样错下去，真的很伤人心，学什么都没必要了，当时打算继续搞ACM的目的之一就是为了提高代码正确率。这个题，不仅细节部分没看清楚，而且写代码时候把比较函数里面的one.nLost写成了one.nGet，查错了1个多小时，还让队友帮忙查错了好久，真的很无语。写程序确实可以debug，但是这也让我养成了很严重的依赖debug的习惯。
人生不可以debug，人生不可以重来。记得以前很多次很多事情就是开始无所谓，后面悲催到底，无限后悔。

代码如下：

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
#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#define MAX (100)
using std::map;
using std::string;
using std::vector;
using std::sort;

struct INFO
{
    INFO()
    {
        nScore = nGet = nLost = 0;
    }

    string strName;
    int nScore;
    int nGet;
    int nLost;
    bool operator < (const INFO& one) const
    {
        if (nScore != one.nScore)
        {
            return nScore > one.nScore;
        }
        else if (nGet - nLost != one.nGet - one.nLost)//这里把one.nLost写成了one.nGet
        {
            return nGet - nLost > one.nGet - one.nLost;
        }
        else if (nGet != one.nGet)
        {
            return nGet > one.nGet;
        }
        else
        {
            return strName < one.strName;
        }
    }
};

int main()
{
    int nN;

    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    while (scanf("%d", &nN) == 1)
    {
        int nLast = nN * (nN - 1);
        char szOne[MAX];
        char szTwo[MAX];
        int nOne, nTwo;

        map<string, INFO> myMap;
        for (int i = 0; i < nLast; ++i)
        {
            scanf("%s %*s %s %d:%d", szOne, szTwo, &nOne, &nTwo);
            //printf("%s %s %d %d\n", szOne, szTwo, nOne, nTwo);

            string strOne = szOne;
            myMap[strOne].strName = strOne;
            myMap[strOne].nGet += nOne;
            myMap[strOne].nLost += nTwo;

            string strTwo = szTwo;
            myMap[strTwo].strName = strTwo;
            myMap[strTwo].nGet += nTwo;
            myMap[strTwo].nLost += nOne;

            if (nOne > nTwo)
            {
                myMap[strOne].nScore += 3;
            }
            else if (nOne == nTwo)
            {
                myMap[strOne].nScore += 1;
                myMap[strTwo].nScore += 1;
            }
            else
            {
                myMap[strTwo].nScore += 3;
            }
        }

        map<string, INFO>::iterator it;
        vector<INFO> myVt;
        for (it = myMap.begin(); it != myMap.end(); it++)
        {
            myVt.push_back(it->second);
        }

        sort(myVt.begin(), myVt.end());
        for (int i = 0; i < myVt.size(); ++i)
        {
            printf("%s %d\n", myVt[i].strName.c_str(), myVt[i].nScore);
        }
        printf("\n");
    }

    return 0;
}

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

两个栈实现一个队列
要求：只能使用栈的pop和push，以及测试栈是否为空三个操作。
实现思路：
队列里面使用stack one 和 stack two。
进队列时，直接进入栈one即可。
出队列时，从two弹出一个元素，如果two里面的元素为空，则将one里面的元素依次弹出并压入two中，再从two弹出一个元素返回。

用STL里面的stack模拟实现queue的代码如下：

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

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stack>
using std::stack;

template<class T> class CQueue
{
public:
    CQueue()
    {
        nSize = 0;
    }

    void clear()
    {
        while (!one.empty())
        {
            one.pop();
        }
        while (!two.empty())
        {
            two.pop();
        }
    }

    void push(const T& t)
    {
        one.push(t);
        ++nSize;
    }

    void pop()
    {
        if (two.empty())
        {
            while (!one.empty())
            {
                two.push(one.top());
                one.pop();
            }
        }
        two.pop();
        --nSize;
    }

    T& front()
    {
        if (two.empty())
        {
            while (!one.empty())
            {
                two.push(one.top());
                one.pop();
            }
        }
        return two.top();
    }

    T& back()
    {
        return one.top();
    }

    bool empty()
    {
        return nSize == 0;
    }

private:
    stack<T> one;
    stack<T> two;
    int nSize;
};

#define MAX 20

int main()
{
    CQueue<int> q;

    srand(time(NULL));
    for (int i = 0; i < MAX; ++i)
    {
        q.push(i);

        if (rand() % 2)
        {
            printf("front: %d\n", q.front());
            q.pop();
        }
    }

    while (!q.empty())
    {
        printf("front: %d\n", q.front());
        q.pop();
    }

    return 0;
}

两个队列实现一个栈
要求：只能使用从队列的尾部入和头部出，以及测试队列是否为空三个操作。
实现思路：
队列里面使用queue one 和 stack two。
进栈时，根据当前元素是全部存储在哪个队列而选择从one或者two的尾部进入。
出栈时，假设当前元素都存储在one里面，则不断出队列，直到队列为空之前的所有元素一次进入队列two，而one里面的最后一个元素作为栈弹出的值返回。
对于当前元素是存储在哪个队列里面，可以设置变量标记，初始化时候存储在one里面，操作一次，由于元素要倒转，则存储位置会变一次。

用STL里面的queue模拟实现的stack代码如下：

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

#include <stdio.h>
#include <queue>
using std::queue;

template<class T> class CStack
{
public:
    CStack()
    {
        nSize = 0;
        nTime = 1;
    }

    void clear()
    {
        while (!one.empty())
        {
            one.pop();
        }
        while (!two.empty())
        {
            two.pop();
        }
    }

    void push(const T& t)
    {
        if (nTime % 2)
        {
            one.push(t);
        }
        else
        {
            two.push(t);
        }
        ++nSize;
    }

    void pop()
    {
        if (nTime % 2)
        {
            while (!one.empty())
            {
                T t = one.front();
                one.pop();
                if (!one.empty())
                {
                    two.push(t);
                }
            }
        }
        else
        {
            while (!two.empty())
            {
                T t = two.front();
                two.pop();
                if (!two.empty())
                {
                    one.push(t);
                }
            }
        }

        nTime = (nTime + 1) % 2;
        --nSize;
    }

    T& top()
    {
        if (nTime % 2)
        {
            while (!one.empty())
            {
                T t = one.front();
                one.pop();
                if (!one.empty())
                {
                    two.push(t);
                }
                else
                {
                    two.push(t);
                    nTime = (nTime + 1) % 2;
                    return two.back();
                }
            }
        }
        else
        {
            while (!two.empty())
            {
                T t = two.front();
                two.pop();
                if (!two.empty())
                {
                    one.push(t);
                }
                else
                {
                    one.push(t);
                    nTime = (nTime + 1) % 2;
                    return one.back();
                }
            }
        }
    }

    bool empty()
    {
        return nSize == 0;
    }

private:
    queue<T> one;
    queue<T> two;
    int nSize;
    int nTime;
};

#define MAX 20

int main()
{
    CStack<int> stack;

    for (int i = 0; i < MAX; ++i)
    {
        stack.push(i);
    }

    while (!stack.empty())
    {
        printf("top: %d\n", stack.top());
        stack.pop();
    }

    return 0;
}