STEP BY STEP

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

这个题不错，居然需要在dfs里面写bfs。题意类似于图像识别里面，搜索一张图像里面的某个指定区域里面有几个斑点，题意里面的斑点是指色子。


30 15
…………………………
…………………………
………………………..
…**……*…………
…X*…..X*………..
…*….*X…………
…X…..**………….
…*…….…………..
…………………………
……..**……..**…..
…….X**…..X**X…..
……*……**…..
…..**X…….X**X…..
……..……..*…..
…………………………
比如上面这个30 15的图片里面，一共有四个区域，作为区域的底色，然后是求区域里面有多少个X的块。这个题单纯dfs的话，很没办法，因为无法一次性把连接在一起的X都搜索了。比如，
5 5

XXX*X XXX*X ..... X***X XX*** 的时候，dfs很明显就会出现问题，因为会先离开X块，再次回到X块，计数就会出现问题了。因此只能遇到X的时候，进行一次bfs，将与其相连接的X全部搜索掉。。。并且找到与当前X块相连接的一个*的位置，如果有这样的位置，就继续进行dfs。

</div>
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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;

int nW, nH;
char szData[100][100];
bool bVisit[100][100];
int nNum;
int nDice[100];
int nAdd[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

bool IsPosOk(int i, int j)
{
    return i >= 0  i < nH  j >= 0  j < nW;
}

struct POS
{
    int nI;
    int nJ;
};

bool Bfs(int nI, int nJ)
{
    bool bRet = false;
    queue<POS> qp;
    POS pos = {nI, nJ};
    int i = nI, j = nJ;

    qp.push(pos);
    while (qp.empty() == false)
    {
        POS head = qp.front();
        qp.pop();

        for (int m = 0; m < 4; ++m)
        {
            int nNextI = head.nI + nAdd[m][0];
            int nNextJ = head.nJ + nAdd[m][1];

            if (IsPosOk(nNextI, nNextJ)  bVisit[nNextI][nNextJ] == false)
            {
                if (szData[nNextI][nNextJ] == 'X')
                {
                    bVisit[nNextI][nNextJ] = true;
                    POS pos = {nNextI, nNextJ};
                    qp.push(pos);
                }
                else if (szData[nNextI][nNextJ] == '*')
                {
                    bRet = true;
                    nI = nNextI;//   这里是返回新的dfs位置
                    nJ = nNextJ;
                }
            }
        }
    }

    return bRet;
}

void dfs(int i, int j, int nNum)
{
    bVisit[i][j] = true;
    if (szData[i][j] == 'X')
    {
        nDice[nNum]++;
        bool bDfs = Bfs(i, j);//扩散掉当前连通的所有'X'
        if (bDfs == false)
        {
            return;
        }
        else
        {
            dfs(i, j, nNum);
        }
    }

    for (int m = 0; m < 4; ++m)
    {
        int nNextI = i + nAdd[m][0];
        int nNextJ = j + nAdd[m][1];

        if (IsPosOk(nNextI, nNextJ)  bVisit[nNextI][nNextJ] == false
                 szData[nNextI][nNextJ] != '.')
        {
            dfs(nNextI, nNextJ, nNum);
        }
    }
}

int main()
{
    int nCases = 1;

    while (scanf("%d%d", &nW, &nH), nW + nH)
    {
        for (int i = 0; i < nH; ++i)
        {
            scanf("%s", szData[i]);
        }
        memset(bVisit, false, sizeof(bVisit));
        memset(nDice, 0, sizeof(nDice));
        nNum = 0;

        for (int i = 0; i < nH; ++i)
        {
            for (int j = 0; j < nW; ++j)
            {
                if (szData[i][j] == 'X'  bVisit[i][j] == false)
                {
                    dfs(i, j, nNum);
                    nNum++;
                }
            }
        }
        sort(nDice, nDice + nNum);

        printf("Throw %d\n", nCases++);
        for (int i = 0; i < nNum; ++i)
        {
            printf("%d%s", nDice[i], i == nNum - 1 ? "\n" : " ");
        }
        printf("\n");
    }

    return 0;
}

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

这是一个貌似很麻烦的题，题目要求是将一颗用ascii码绘画出来的树，转换为其一种字符串表示，这种字符串表示好像是叫做什么广义表什么的。
比如，
A

|

B C D

| |

E F G 对应的字符串表示 **(A(B()C(E()F())D(G())))**

</div>
比较纠结的是如何读取数据，如何递归，如果建立树的话，也麻烦，因为还是颗不定叉的树。最主要的是如何方便地递归。最后知道了一个比较巧妙的方法，先一次性把一组数据读入字符串数组里面，再在这个字符串数组上进行递归处理。这样的话，就能很方便的找到树里面节点
的关系了。
而一次读一个字符就想进行递归是没办法确定节点的关系的，不递归估计更很难写，完全没头绪。。。

代码如下：

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
#include <stdio.h>
#include <stdlib.h>

char szLines[210][210];
int nNumOfLine;

void GetAns(int i, int j)
{
    //printf("i:%d, j:%d, %c\n", i, j, szLines[i][j]);

    if (szLines[i][j] != '\0')
    {
        putchar(szLines[i][j]);
        //printf("%c", szLines[i + 1][j]);
        if (szLines[i + 1][j] == '|')
        {
            int nBeg, nEnd;
            nBeg = nEnd = j;
            while (nBeg >= 0  szLines[i + 2][nBeg] == '-')
            {
                --nBeg;
            }
            while (szLines[i + 2][nEnd] == '-')
            {
                ++nEnd;
            }
            //printf("nBeg:%d, nEnd:%d\n", nBeg, nEnd);
            putchar('(');
            for (int k = nBeg; k             {
                if (szLines[i + 3][k] != ' '  szLines[i + 3][k] != '\0')
                {
                    GetAns(i + 3, k);
                }
            }
            putchar(')');
        }
        else
        {
            printf("()");
        }
    }

}

int main()
{
    int nN;
    char ch;

    scanf("%d", &nN);
    getchar();
    while (nN--)
    {
        nNumOfLine = 0;
        memset(szLines, 0, sizeof(szLines));
        while (gets(szLines[nNumOfLine]), szLines[nNumOfLine][0] != '#')
        {
            //printf("%s\n", szLines[nNumOfLine]);
            nNumOfLine++;
        }
        if (nNumOfLine == 0)
        {
            printf("()\n");
            continue;
        }
        int i, j;
        i = 0;
        for (j = 0; szLines[0][j] == ' '; ++j);
        //printf("i:%d, j:%d\n", i, j);
        putchar('(');
        GetAns(i, j);
        putchar(')');
        putchar('\n');
    }

    return 0;
}

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

这个题目的意思是要计算一些c语言表达式的值。这些表达式有+-还有++，—操作符与a-z这些变量组合而成。a-z的权值是1-26。比如，表达式 c+f—+—a，得出值是9，其它变量的值也需要计算出来。
这个题目感觉比较麻烦，刚开始一点思路也没有，还写了个错误的方法，浪费了时间。后面我的思路是 （+，-） （—，++）（变量）（—，++），这个匹配式子的意思是先处理二元操作符，然后处理前置，再处理变量，再处理后置，如果发现没有后置操作符，则把读取的数据重新写回数据流里面，下次再处理。

代码如下：

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
#include <stdio.h>
#include <string.h>
#include <sstream>
#include <algorithm>
using namespace std;
struct INFO
{
    char ch;
    int nValue;
    char chAdd;
    bool operator < (const INFO info) const
    {
        return ch < info.ch;
    }
};

INFO infos[200];
char szLine[200];

bool GetNextChar(stringstream ss, char ch)
{
    while (ss >> ch)
    {
        if (ch != ' ');
        {
            return true;
        }
    }
    return false;
}

int main()
{
    while (gets(szLine))
    {
        printf("Expression: %s\n", szLine);
        memset(infos, 0, sizeof(infos));
        stringstream ss(szLine);
        char ch;
        int nNum = 0;
        int nValue = 0;
        char chOper;
        bool bOk = true;
        bool bFirst = true;
        while (1)
        {
            if (bFirst)
            {
                chOper = '+';
                bFirst = false;
            }
            else
            {
                bOk = GetNextChar(ss, ch);
                if (!bOk) break;
                chOper = ch;
            }

            bOk = GetNextChar(ss, ch);
            if (!bOk) break;

            if (ch == '-')//前置--
            {
                bOk = GetNextChar(ss, ch);
                if (!bOk) break;//-
                bOk = GetNextChar(ss, ch);
                if (!bOk) break;//读取字母

                infos[nNum].ch = ch;
                infos[nNum].nValue = ch - 'a';

                if (chOper == '+')
                {
                    nValue += infos[nNum].nValue;
                }
                else
                {
                    nValue -= infos[nNum].nValue;
                }
                ++nNum;
            }
            else if (ch == '+')//前置++
            {
                bOk = GetNextChar(ss, ch);
                if (!bOk) break;//+
                bOk = GetNextChar(ss, ch);
                if (!bOk) break;//读取字母

                infos[nNum].ch = ch;
                infos[nNum].nValue = ch - 'a' + 2;

                if (chOper == '+')
                {
                    nValue += infos[nNum].nValue;
                }
                else
                {
                    nValue -= infos[nNum].nValue;
                }
                ++nNum;
            }
            else
            {
                infos[nNum].ch = ch;
                infos[nNum].nValue = ch - 'a' + 1;

                if (chOper == '+')
                {
                    nValue += infos[nNum].nValue;
                }
                else
                {
                    nValue -= infos[nNum].nValue;
                }
                //读取后置操作符
                char chOne;
                char chTwo;
                bOk = GetNextChar(ss, chOne);
                if (!bOk)
                {
                    ++nNum;
                    break;
                }
                bOk = GetNextChar(ss, chTwo);
                if (!bOk)
                {
                    ++nNum;
                    break;
                }

                if (chOne == chTwo)
                {
                    if (chOne == '+')
                    {
                        infos[nNum].chAdd = '+';
                    }
                    else
                    {
                        infos[nNum].chAdd = '-';
                    }
                }
                else
                {
                    ss.putback(chTwo);
                    ss.putback(chOne);
                }
                ++nNum;
            }
        }

        printf("    value = %d\n", nValue);
        sort(infos, infos + nNum);
        for (int i = 0; i < nNum; ++i)
        {
            if (infos[i].chAdd == '+')
            {
                infos[i].nValue++;
            }
            else if (infos[i].chAdd == '-')
            {
                infos[i].nValue--;
            }
            printf("    %c = %d\n", infos[i].ch, infos[i].nValue);
        }
    }

    return 0;
}

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