STEP BY STEP

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

链接: http://poj.grids.cn/practice/2774

这个题可以用二分解,虽然也有dp的解法。可能用二分解这个题不是很明显,但是确实是可以的。最大的解就是所有的棍子长/要求的棍子数,最小的解是0,直接在其中进行二分即可。这个题属于二分出最大满足条件的解的情况。这个题为什么能够二分了。我是这样想的。首先,解空间确实是有序的吧,从数字0-数字nSum/nK。其次,对于任意一个处于这个范围内的数字,只有满足和满足题目要求2种情况,那么和我们二分数字有什么区别了,我们二分一个有序数组,看里面有没有某个数字,是不是也只要判断下nMid满足是否条件是吧。所以,这个题是可以二分的。二分的条件就是解空间有序的,或者可以方便在解空间里面跳跃。而且这个题的二分还需要点技巧,因为是查找满足条件的最大解。

代码:

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
#include 
#include 
#include 
#define MAX (10000 + 10)
using namespace std;
int nN, nK;
int nWoods[MAX];
bool IsAnsOk(int nAns)
{
    if (nAns == 0)
    {
        return true;
    }
    else
    {
        int nTotal = 0;
        for (int i = nN - 1; i >= 0; --i)
        {
            nTotal += nWoods[i] / nAns;
            if (nTotal >= nK)
            {
                return true;
            }
        }
        return false;
    }
}
int SearchAns(int nMax)
{
    int nBeg = 0, nEnd = nMax;
    while (nBeg <= nEnd)
    {
        int nMid = (nBeg + nEnd) / 2;
        if (IsAnsOk(nMid))
        {
            nBeg = nMid + 1;
        }
        else
        {
            nEnd = nMid - 1;
        }
    }
    return nBeg - 1;
}
int main()
{
    while (scanf("%d%d", &nN, &nK) == 2)
    {
        int nSum = 0;
        for (int i = 0; i < nN; ++i)
        {
            scanf("%d", &nWoods[i]);
            nSum += nWoods[i];
        }
        sort(nWoods, nWoods + nN);
        int nMax = nSum / nK;
        printf("%d\n", SearchAns(nMax));
    }
    return 0;
}

所以,只是把==换成了IsAnsOk函数调用而已…而且由于这是查找最大解,返回值做了下变化而已…
仔细分析二分的写法(我的另一篇文章(标题是关于密码的一个解题报告)有说明),
其实写出查找最大解和最小解的二分都不是件麻烦的事情…

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

链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1219

这个题就是求出所有结点的距离之后,再找出某个结点,该结点离其它结点的最大距离是所有结点中是最小的…
解法1:深搜出所有结点间的距离,但是会超时,即使深搜的过程使用中记忆化搜索(就是用2维数组保存已经搜出的答案,如果后面的搜索需要用到直接使用即可)…
解法2:Floyd算法,3重循环直接找出所有结点之间的最短距离
解法3:对每一个结点应用一次迪杰斯特拉算法,找出所有结点与其它结点间的最短距离…

解法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
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
#include <stdio.h>
#include <string.h>
#define MAX  (100 + 10)
#define INF (1000000 + 10)
int nN, nM;
int nDis[MAX][MAX];
void SearchAll()
{
    for (int k = 0; k < nN; ++k)
    {
        for (int i = 0; i < nN; ++i)
        {   
            for (int j = 0; j < nN; ++j)
            {
                if (nDis[i][k] + nDis[k][j] < nDis[i][j])
                {
                    nDis[i][j] = nDis[j][i] = nDis[i][k] + nDis[k][j];
                }
            }
        }
    }
}
int main()
{
    while (scanf("%d%d", &nN, &nM) == 2)
    {
        for (int i = 0; i < nN; ++i)
        {
            for (int j = 0; j < nN; ++j)
            {
                if (i == j)
                {
                    nDis[i][j] = 0;
                }
                else
                {
                    nDis[i][j] = INF;
                }
            }
        }
        while (nM--)
        {
            int nX, nY, nK;
            scanf("%d%d%d", &nX, &nY, &nK);
            nDis[nX][nY] = nDis[nY][nX] = nK;
        }
        SearchAll();
        bool bOk = false;
        int nMin = 1 << 30;

        for (int i = 0; i < nN; ++i)
        {
            int nTemp = 0;
            int j = 0;
            for ( ; j < nN; ++j) 
            { 
                if (i == j) continue; 
                if (nDis[i][j] == INF) 
                { 
                    break; 
                } 
                else 
                { 
                    if (nDis[i][j] > nTemp)
                    {
                        nTemp = nDis[i][j];
                    }
                }
            }
            if (j == nN)
            {
                bOk = true;
                if (nTemp < nMin)
                {
                    nMin = nTemp;
                }
            }
        }

        if (bOk)
        {
            printf("%d\n", nMin);
        }
        else
        {
            printf("Can not\n");
        }
    }
    return 0;
}

关于Floyd算法,可以这样理解…比如刚开始只取2个结点i,j,它们的距离一定是dis(i,j),但是还有其它结点,需要把其它结点也慢慢加进来,所以最外层关于k的循环意思就是从0至nN-1,把所有其它结点加进来,比如加入0号结点后,距离dis(i,0)+dis(0,j)可能会比dis(i,j)小,如果是这样就更新dis(i,j),然后后面加入1号结点的时候,实际上是在已经加入0号结点的基础上进行的处理了,效果变成dis(i,0,1,j),可能是最小的,而且中间的0,1也可能是不存在的,当然是在dis(i,j)原本就是最小的情况下…
这个算法可以用下面这个图片描述…

解法3:

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
#include <stdio.h>
#include <string.h>
#define MAX  (100 + 10)
#define INF (1000000 + 10)
int nN, nM;
int nDis[MAX][MAX];
void Search(int nSource)
{
    bool bVisit[MAX];
    memset(bVisit, false, sizeof(bVisit));
    bVisit[nSource] = true;
    for (int i = 0; i < nN - 1; ++i)
    {
        int nMin = INF;
        int nMinPos = 0;
        for (int j = 0; j < nN; ++j)
        {
            if (!bVisit[j] && nDis[nSource][j] < nMin)
            {
                nMin = nDis[nSource][j];
                nMinPos = j;
            }
        }
        if (bVisit[nMinPos] == false)
        {
            bVisit[nMinPos] = true;
            for (int j = 0; j < nN; ++j)
            {
                if (nDis[nSource][nMinPos] + nDis[nMinPos][j] < nDis[nSource][j])
                {
                    nDis[nSource][j] = nDis[nSource][nMinPos] + nDis[nMinPos][j];
                }
            }
        }
    }
}
void SearchAll()
{
    for (int k = 0; k < nN; ++k)
    {
        Search(k);
    }
}
int main()
{
    while (scanf("%d%d", &nN, &nM) == 2)
    {
        for (int i = 0; i < nN; ++i)
        {
            for (int j = 0; j < nN; ++j)
            {
                if (i == j)
                {
                    nDis[i][j] = 0;
                }
                else
                {
                    nDis[i][j] = INF;
                }
            }
        }
        while (nM--)
        {
            int nX, nY, nK;
            scanf("%d%d%d", &nX, &nY, &nK);
            nDis[nX][nY] = nDis[nY][nX] = nK;
        }
        SearchAll();
        bool bOk = false;
        int nMin = 1 << 30;
        for (int i = 0; i < nN; ++i)
        {
            int nTemp = 0;
            int j = 0;
            for ( ; j < nN; ++j) 
            { 
                if (i == j) continue; 
                if (nDis[i][j] == INF) 
                { 
                    break;
                } 
                else
                { 
                    if (nDis[i][j] > nTemp)
                    {
                        nTemp = nDis[i][j];
                    }
                }
            }
            if (j == nN)
            {
                bOk = true;
                if (nTemp < nMin)
                {
                    nMin = nTemp;
                }
            }
        }
        if (bOk)
        {
            printf("%d\n", nMin);
        }
        else
        {
            printf("Can not\n");
        }
    }
    return 0;
}

迪杰斯特拉算法的核心思想是维护一个源点顶点集合,任何最短路径一定是从这个顶点集合发出的…
初始化时,这个集合就是源点…
我们从该其它结点中选出一个结点,该结点到源点的距离最小…
显然,这个距离就是源点到该结点的最短距离了,我们已经找到了答案的一部分了…然后,我们就把该结点加入前面所说的顶点集合…
现在顶点集合更新了,我们必须得更新距离了…由于新加入的结点可能发出边使得原来源点到某些结点的距离更小,也就是我们的源点变大了,边也变多了,所以我们的最短距离集合的值也必须变化了…
该算法一直循环nN-1次,直至所有的点都加入源点顶点集合…

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

链接: http://poj.grids.cn/practice/2814

这个题目可以枚举或者直接暴力。但是,这之前必须弄明白答案的解空间。。。也就是解可能的情况。。。很简单,一共有9种移动方案。也很了然的知道对于某种方案使用N次的效果等同于N%4的效果,也就是说某种方案只可能使用0,1,2,3次。。。一共有9种方案,那么一共就只有4^9种可能的解。。。这么小的解空间,无论用什么方法都不会超时了。。。暴力可以才用9重循环,或者深搜,当时觉得写9重循环是件很糗的事情,就果断深搜了。。。
如果这题才用枚举的方法的话,思考方式还是那样先确定假设解的部分情况,通过已经知道的规则确定解的其它情况,然后求出这个解,判断这个解是否满足题目要求。。。比如,我们可以枚举1,2,3号方案的情况,根据规则确定其它方案的使用情况,求出所有方案的使用情况后,判断假设的解是否满足要求就可以了…

我才用的是dfs+剪枝,这个题目其实题意或者说答案有误,因为答案是搜索找到第一个解,而不是所谓的最短序列的解,当然如果数据使得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
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
#include <stdio.h>
int nMinTimes;
int nPath[40];
bool bFind = false;
char* szMoves[10] =
{
    NULL,
    "ABDE",
    "ABC",
    "BCEF",
    "ADG",
    "BDEFH",
    "CFI",
    "DEGH",
    "GHI",
    "EFHI"
};
bool IsPosOK(int* nPos)
{
    for (int i = 0; i < 9; ++i) { if (nPos[i]) { return false; } } return true; } void Move(int nChoose, int nTimes, int* nPos) { if (nTimes > 0)
    {
        char* pszStr = szMoves[nChoose];
        while (*pszStr)
        {
            nPos[*pszStr - 'A'] = (nPos[*pszStr - 'A'] + nTimes) % 4;
            ++pszStr;
        }
    }
}
void MoveBack(int nChoose, int nTimes, int* nPos)
{
    if (nTimes > 0)
    {
        char* pszStr = szMoves[nChoose];
        while (*pszStr)
        {
            nPos[*pszStr - 'A'] = (nPos[*pszStr - 'A'] - nTimes + 4) % 4;
            ++pszStr;
        }
    }
}
void Cal(int nChoose, int* nPos, int* nUsed, int nUsedTimes)
{
    if (nChoose == 10)
    {
        if (IsPosOK(nPos) && !bFind)
        {
            nMinTimes = nUsedTimes;
            for (int i = 0; i < nMinTimes; ++i)
            {
                nPath[i] = nUsed[i];
            }
            bFind = true;
        }
        return;
    }
    for (int i = 0; i <= 3; ++i)
    {
        Move(nChoose, i, nPos);
        for (int j = 0; j < i; ++j)//放入i次的nChoose
        {
            nUsed[nUsedTimes + j] = nChoose;
        }
        if (!bFind)
        {
            Cal(nChoose + 1, nPos, nUsed, nUsedTimes + i);
        }
        MoveBack(nChoose, i, nPos);
    }
}
int main()
{
    int nPos[9];
    int nUsed[40];
    for (int i = 0; i < 9; ++i)
    {
        scanf("%d", &nPos[i]);
    }
    Cal(1, nPos, nUsed, 0);
    for (int i = 0; i < nMinTimes; ++i)
    {
        printf("%d", nPath[i]);
        if (i != nMinTimes - 1)
        {
            putchar(' ');
        }
        else
        {
            putchar('\n');
        }
    }

    return 0;
}

这道题其实我wa了近10次,原因就是Move和MoveBack写错了,没有移动nTimes次,而前面一直写成了1,昨晚wa得实在无语了…今天晚上检查才突然发现的…
这半个多月做了60道题了,都没有改动这低级的bug习惯…实在无语…递归,回溯,剪枝都写上了…唉…实在无语…还不如直接9重循环,多省心…真不该歧视某种方法的…

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

链接：http://poj.grids.cn/practice/1183/

方法1:
本题很容易推断出 ,a = (b * c - 1) / (b + c), 由于需要求(b+c)的最小值,根据高中的函数思想,如果(b+c)能够转换为关于b或者c的函数就好办了,刚好这里已经有个b和c的关系式子了,可以推导出(b+c) = (c^2+1)/(c-a),这个时候只需要求f(c)的最小值,但是c必须取整数,对这个函数可以求导,也可以进行变形,变形后可以得到f(c) = (c-a) + 2 a + (a^2+1)/(c-a)。
令x=c-a,那么可以得到(b+c)=f(x)=x + 2 a+(a^2+1)/x, 其中x必须是整数,到现在为止就是一个用程序模拟高中时候学过的双曲线函数的求最值问题了,我们知道该函数的极值点是sqrt(a^2+1),但是由于x必须是整数,
我们必须从极值开始往下和往上找到一个最小值,然后取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
#include <stdio.h>
#include <iostream>
#include <math.h>
//b + c = (c^2 + 1) / (c - a) = (c-a) + (2 * a) + (a^2 + 1) / (c -a)
//令c-a = t, f(t) = t + 2*a + (a^2+1)/ t
//因为f(t)在sqrt(a^2+1)时取最小值,但是由于t只能取整数,
//所以,必须从极值点往下和往上寻找最小的值,然后取2者中最小的
int main()
{
    long long a;
    while (std::cin >> a)
    {
        long long nTemp = a * a + 1;
        long long nDown =  sqrt(nTemp);
        long long nUp = nDown;
        long long one, two;

        while (nTemp % nDown )
        {
            nDown--;
        }
        one = 2 * a + nTemp / nDown + nDown;

        while (nTemp % nUp )
        {
            nUp++;
        }
        two = 2 * a + nTemp / nUp + nUp;

        std::cout << (one < two ? one : two) << std::endl;
    }
    return 0;
}

方法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
#include <stdio.h>
#include <iostream>
#include <math.h>

//a = (b*c-1)/(b+c)
//令b = a + m, c = a + n, c >= b
//-> a*(2*a+m+n) = (a+m)*(a+n)-1
//m*n = a^2 + 1  (n>=m)
//所以,求出a^2+1所有因子对,取其中m+n最小的即可
int main()
{
    long long a;
    while (std::cin >> a)
    {
        long long m, n;
        long long nTemp = a * a + 1;
        long long nMax = sqrt(nTemp);
        long long nRes = 1 + nTemp;
        for (m = 2; m <= nMax; ++m)
        {
            if (nTemp % m == 0)
            {
                n = nTemp / m;
                if (m + n < nRes)
                {
                    nRes = m + n;
                }
            }
        }

        std::cout << 2 * a + nRes << std::endl;
    }
    return 0;
}

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

链接: http://poj.grids.cn/practice/2797/

这题乍看之下确实没什么思路,后面终于明白题意了,然后突然想到可以用字典树做,速度当然会是非常快的…
但是其实还有一种更简单的方法,那就是对所有字符串排序之后,每个字符串的前缀长度其实就是由其前一个和后一个字符串共同决定,
nLen = max(nOne, nTwo), nOne 和 nTwo就分别代表当前字符串和前后字符串公告部分的长度+1后的值…
代码写出来写非常简单…同学这样实现了下,也轻松过了…

然后我就辛苦的写了一棵字典树…可能我的写法不是很标准,因为我没参考什么模板,自己硬想出来怎么写的…
我的想法是开一个静态大数组,第一个结点作为根,不存储数据,从第二个结点开始作为自由空间分配…
其实,就是对26颗字典树虚拟了个无数据的根结点…
使用了虚拟的根结点后,代码比用26个根结点简洁很多…
刚开始我就假设1-26号结点分别为a-z,作为26颗树的根,
而且下26个结点的位置我用的是索引,没用指针,后面换成了指针,代码看起来更舒服了…

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>
#include <string.h>
#define LETTER_NUM 26
#define WORD_LEN_MAX 25
#define WORD_NUM_MAX 1030
#define NODE_MAX (WORD_LEN_MAX * WORD_NUM_MAX + 10)
struct WORD_TREE
{
    char ch;
    WORD_TREE* next[LETTER_NUM];
    int nTime;
};
WORD_TREE tree[NODE_MAX];
WORD_TREE* pFreeNode = tree + 1;//第一个结点作为头结点,不存储数据
char szWords[WORD_NUM_MAX][WORD_LEN_MAX];
void AddToTree(char* pszStr)
{
    WORD_TREE* pTree = tree;
    while (*pszStr && pTree->next[*pszStr - 'a'])
    {
        pTree = pTree->next[*pszStr - 'a'];
        pTree->nTime++;
        ++pszStr;
    }
    while (*pszStr)
    {
        pFreeNode->ch = *pszStr;
        pFreeNode->nTime++;
        pTree->next[*pszStr - 'a'] = pFreeNode;
        pTree = pFreeNode;
        ++pszStr;
        ++pFreeNode;
    }
}
int FindPrefix(char* pszStr)
{
    WORD_TREE* pTree = tree;
    int nLen = 0;
    while (*pszStr)
    {
        ++nLen;
        pTree = pTree->next[*pszStr - 'a'];
        if (pTree->nTime <= 1)
        {
            break;
        }
        ++pszStr;
    }
    return nLen;
}
int main()
{
    int nCount = 0;
    while (scanf("%s", szWords[nCount]) != EOF)
    {
        AddToTree(szWords[nCount]);
        nCount++;
    }
    for (int i = 0; i < nCount; ++i)
    {
        int nLen = FindPrefix(szWords[i]);
        printf("%s ", szWords[i]);
        for (int j = 0; j < nLen; ++j)
        {
            putchar(szWords[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

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

链接：[http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1207]

问题描述是：给定一个大于0的整数N(1<=N<=10^8),判断其是否可能是一个直角三角形的直角边(这个三角形的三条边必须都是整数)…
这个题还是做得我挺郁闷的。。。刚开始完全没思路。。。后面没办法，硬着头皮往下想。
对于勾股定理a^2 + b^2 = c^2，假设N是a,可以得到a^2 = (c + b) * (c -b), 那么(c + b)和(c - b)是a^2的2个因子,而且(c+b)>=a,(c-b)<=a。。。
到这一步已经可以用程序轻松解决出来了,但是对于任意一个整数N来说,其复杂度都是O(N),那么计算量还是很大的…
这个时候只需要枚举1-N,求出a^2的2个因子,然后求c和b,如果能得出c和b都是正整数那么,就满足条件了…
但是这样还是过不了题,因为数据量不会这么小…数据量好像有10000组。。。
那么还需要推导出进一步的结论…
因为1和a^2一定是a^2的一对因子,那么(c+b) = a^2和(c-b) = 1一定可以成功,
则可以推导出，2 c = a^2 + 1。
要c可解,a必须为奇数,那么可以推导出如果a是奇数,一定是直角边了。。。
如果a是偶数了,可以化简为 4 (a / 2) ^ 2 = 4 （c + b) \ (c - b) = (2c + 2b) * (2c - 2b) = a ^ 2，那么继续推导也可以得到一样的结果了…

结论就是:对于大于等于3的正整数都可以是一条直角边(>=3也可以根据上面的c和b是正整数推导出来)…

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

链接: http://poj.grids.cn/practice/2820
链接: http://poj.grids.cn/practice/2801

为啥把这2个不相干的题目放在一起了…说实话这其实也是二个容易的题目,尤其第二个更容易想到…第一个也许暂时
没那么容易想出来。。。
而且感觉第一个古代密码还挺有意思的…判断一个字符串是否能够通过移位和替换方法加密成另外一个字符串。。。
至于第二个,各位去看看题目吧。。。
也是个解法跟题目不大相关的题目。。。
这2个题最大的特点和共同点就是解法和题目意思想去甚远。。。
所以我觉得做这种二丈和尚摸不早头脑的题,思维应该往跟题意背离的方向思考。。。

尤其第一个题，如果只看代码,即使代码可读性再好，也不知道代码有何意义，有何目的，跟题意有啥关系。。。
不过第一个居然轻松AC了,虽然我2b得搞了个ce和re出来了…
第一个的转换方法是,计算出现的字符’A’-‘Z’的出现次数,然后从大小排序,如果针对加密后的字符串得到的结果一直大于等于
加密前的字符串得到的结果,表明答案是YES…具体还是看代码吧…

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

using std::sort;
bool Greater(int one, int two)
{
    return one > two;
}

int main()
{
    char szOne[110];
    char szTwo[110];
    int nNumOne[26];
    int nNumTwo[26];

    while (scanf("%s%s", szOne, szTwo) == 2)
    {
        memset(nNumOne, 0, sizeof(int) * 26);
        memset(nNumTwo, 0, sizeof(int) * 26);

        char* psz = szOne;
        while (*psz)
        {
            ++nNumOne[*psz - 'A'];
            ++psz;
        }
        psz = szTwo;
        while (*psz)
        {
            ++nNumTwo[*psz - 'A'];
            ++psz;
        }
        sort(nNumOne, nNumOne + 26, Greater);
        sort(nNumTwo, nNumTwo + 26, Greater);
        bool bIsYes = true;
        for (int i = 0; i < 26; ++i)
        {
            if (nNumOne[i] < nNumTwo[i])
            {
                bIsYes = false;
                break;
            }
        }
        if (bIsYes)
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
    }

    return 0;
}

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

链接: http://poj.grids.cn/practice/2804/

这也是一个很简单的题目,大家一看都知道用什么方法了,当然如果是查找的话,顺序查找是不行的,
方法一,是用map,建立个map的字典,注意不要想当然用map,
那样得动态分配内存,或者还是先开个大数组存好字典,其结果还是多浪费了内存…
排序+二分也不错的,因为数据量确实很大,而且题目也建议用c的io输入,所以这样再建立map
中间还得转换一下…
总之做这个题还是很顺利的,就wa了一次,原因是2分写错了,我也很久没在oj上写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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <string.h>
#include <algorithm>

#define MAX_WORD_LEN 11
#define MAX_DICTION_ITEM (100000 + 10)

using std::sort;

struct Dictionary
{
    char szWord[MAX_WORD_LEN];
    char szEnglish[MAX_WORD_LEN];
};

Dictionary diction[MAX_DICTION_ITEM];

bool CmpDictionItem(Dictionary one, Dictionary two)
{
    return strcmp(one.szWord, two.szWord) < 0;
}

int FindEnglish(char* pszWord, int nItemNum)
{
    int nBeg = 0, nEnd = nItemNum - 1;
    int nCmp = 0;

    while (nBeg <= nEnd)
    {
        int nMid = (nBeg + nEnd) / 2;
        nCmp = strcmp(pszWord, diction[nMid].szWord);
        if (nCmp == 0)
        {
            return nMid;
        }
        else if (nCmp < 0)
        {
            nEnd = nMid - 1;
        }
        else
        {
            nBeg = nMid + 1;
        }
    }

    return -1;
}

int main()
{
    char szStr[30];
    char szWord[MAX_WORD_LEN];
    int nCount = 0;
    int nAnsItem = 0;

    while (fgets(szStr, 29, stdin), szStr[0] != '\n')
    {
        sscanf(szStr, "%s%s", diction[nCount].szEnglish, diction[nCount].szWord);
        ++nCount;
    }
    sort(diction, diction + nCount, CmpDictionItem);
    while (scanf("%s", szWord) == 1)
    {
        if ((nAnsItem = FindEnglish(szWord, nCount)) != -1)
        {
            printf("%s\n", diction[nAnsItem].szEnglish);
        }
        else
        {
            printf("eh\n"); 
        }
    }

    return 0;
}

其实我的主要目的是为了指出二分的写法,大家看我的FindEnglish函数,传递的是数组的地址和数组的长度,
然后我写函数体的时候用的是[]的形式,就是下确界,上确界,这样最重要的是需要考虑循环的条件是<还是
<=,其实这也很好判断,因为上界和下界都能够取到,所以=是成立的…而且修改right的时候,必须将right = mid - 1,
原因也是因为这是上确界,
但是如果是上不确界了,那么等号就必须去掉,而且right也只能修改为mid,因为mid-1就是确界了,而mid才是上不确界…
想到这个程度的话,以后写只有唯一解二分就应该不会出错了…但是写查找满足条件的最大或者最小解的二分还需要其它技巧…

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

链接: [http://poj.grids.cn/practice/2964/]

这本来就是一个简单的题目,但是还是值得我用一篇文章的位置。大家都做过闰年的题目,这只是闰年的一个升级版。。。本来我不至于这么纠结这个题目的,一看到题目,
我就考虑到了一次次减去天数来加年数和月份,而且我还想在读入数据之前初始化一个存储2000-9999年每年有多少天得数组…这样就可以避免循环时候计算每年的天数了…但是我还是怕时间不够,所以我想到了个O(1)的算法…
那就是按照题目的说明,其实每400是一个周期的,但是我前面写代码的时候把4年当中一个小周期,100年当中一个中周期,400年当中一个大周期,同样的处理了…
事实上,只能对400作为周期处理,其它的必须分类讨论,虽然代码写出来很复杂,而且我也因为出现这个bug错了无数次,但是我还是感觉非常值得的…因为这是我独立思考的成果,耗费了多少时间和精力倒是无所谓…写算法题,目的不仅仅应该是学习了多少个算法,而是在于能力的提高,个人的严谨性,思考问题的完整性等等…一直觉得自己思考问题时候有创意,但是完整性和严谨性很低…

下面贴我的代码吧,只用了10ms,如果采用第一种方法则需要60ms-70ms…

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

#define SMALL (365 * 3 + 366)
#define MID   (SMALL * 25 - 1)
#define BIG (MID * 4 + 1)

char* pszWeekdays[7] =
{
    "Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"
};

int nDaysOfMon[2][13] =
{
    {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};

void GetMonthAndDay(int nDays, bool bIsLeap, int* nMon, int* nDay)
{
    int nChoose = 0;
    int i = 0;

    if (bIsLeap)
    {
        nChoose = 1;
    }
    *nMon = *nDay = 0;
    i = 1;
    while (nDays > nDaysOfMon[nChoose][i])
    {
        nDays -= nDaysOfMon[nChoose][i];
        ++i;
    }
    *nMon = i;
    *nDay = nDays;
}

void CountSmall(int* pnDays, int* pnPastYears, int* pnMon, int* pnDay)
{
    if (*pnDays >= 3 * 365)//4
    {
        *pnPastYears += 3;
        *pnDays -= 365 * 3;
        GetMonthAndDay(*pnDays + 1, true, pnMon, pnDay);
    }
    else//1-3
    {
        *pnPastYears += *pnDays / 365;
        *pnDays %= 365;
        GetMonthAndDay(*pnDays + 1, false, pnMon, pnDay);
    }
}

int main()
{
    int nPastDays = 0;
    int nPastYears = 0;
    int nYear = 0, nMon = 0, nDay = 0;

    while (scanf("%d", &nPastDays), nPastDays != -1)
    {
        int nTemp = nPastDays;
        nPastYears = 0;

        if (nTemp < 366)
        {
            GetMonthAndDay(nTemp + 1, true, &nMon, &nDay);
            nPastYears = 0;
        }
        else
        {
            nPastYears++;
            nTemp -= 366;

            nPastYears += (nTemp / BIG) * 400;
            nTemp %= BIG;

            if (nTemp >= MID * 3)//301-400年(以4为周期)
            {
                nTemp -= MID * 3;
                nPastYears += 300;

                nPastYears += nTemp / SMALL * 4;
                nTemp %= SMALL;

                CountSmall(&nTemp, &nPastYears, &nMon, &nDay);
            }
            else//1-300年
            {
                nPastYears += nTemp / MID * 100;
                nTemp %= MID;

                if (nTemp >= SMALL * 24)//97-100年(4个平年)
                {
                    nTemp -= SMALL * 24;
                    nPastYears += 4 * 24;

                    nPastYears += nTemp / 365;
                    nTemp %= 365;
                    GetMonthAndDay(nTemp + 1, false, &nMon, &nDay);

                }
                else//1-96年
                {
                    nPastYears += nTemp / SMALL * 4;
                    nTemp %= SMALL;

                    CountSmall(&nTemp, &nPastYears, &nMon, &nDay);
                }
            }
        }
        printf("%d-%02d-%02d %s\n", nPastYears + 2000, nMon, nDay, pszWeekdays[nPastDays % 7]);
    }

    return 0;
}

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

链接:http://poj.grids.cn/practice/2818
这其实就是一个简单的移位密码算法题,只是多了个循环而已,密码学里面也指出过循环运算是没有效果的,所以题目估计也就考察了这一点,如果没有找出循环周期,此题会一直超时的…
刚开始,我就直接模拟K次加密,显然超时了,当时还不信了,以为简单至此。。。
后面我就开始改进了,刚开始是把周期计算和加密放在一起写了,样例也过了,但是还是一直错…
没办法再改,我改成把周期求出来,再对加密次数K取模后,再进行运算…
好吧,还是一样wa,后面就变成PE了。。。
最后,这个题经过我近2个小时的奋战,终于过了,一共错了近10次吧…第一次提交是距现在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
#include <stdio.h>
#include <string.h>
#define N_MAX 200 + 10
int main()
{
    int nN = 0;
    int nNArr[N_MAX];//密钥
    int nK = 0;
    char szMsg[N_MAX];
    char szMsgBckup[N_MAX];//字符串备份
    int nCir[N_MAX];//周期
    int nMsgLen = 0;
    int nPos = 0;
    int i, j;

    while (scanf("%d", &nN), nN != 0)
    {
        for (i = 1; i <= nN; ++i)
        {
            scanf("%d", &nNArr[i]);
        }

        for (i = 1; i <= nN; ++i)//计算周期
        {
            nPos = i;
            for (j = 1; ; ++j)
            {
                nPos = nNArr[nPos];
                if (nPos == i)
                {
                    nCir[i] = j;
                    break;
                }
            }
        }

        while (scanf("%d", &nK), nK != 0)
        {
            getchar();//销掉空格
            gets(szMsg + 1);
            nMsgLen = strlen(szMsg + 1);
            for (i = nMsgLen; i < nN; ++i)
            {
                szMsg[1 + i] = ' ';
            }
            szMsg[1 + nN] = '\0';
            strcpy(szMsgBckup + 1, szMsg + 1);

            for (i = 1; i <= nN; ++i)
            {
                nPos = i;
                int nTimes = nK % nCir[i];
                for (j = 1; j <= nTimes; ++j)
                {
                    nPos = nNArr[nPos];
                }
                szMsg[nPos] = szMsgBckup[i];
            }

            printf("%s\n", szMsg + 1);
        }
        printf("\n");
    }

    return 0;
}