STEP BY STEP

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

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

链接：http://poj.grids.cn/practice/1017
说实话这就是个简单的装箱子问题,很容易想清楚装箱子的过程,而且这个过程是满足贪心算法的,
所以只需要用代码模拟整个装箱子的过程即可,但是这样真的就足够了吗？？？
我刚开始就是用代码模拟这个手动过程了,虽然AC了,但是代码有150行左右,逻辑也显得过于复杂了,
得不偿失。。。整个过程是66的一个占一个箱子,55的也必须一个占一个箱子,但是需要补11个11的,
44的也是一个占一个箱子,但是需要补5个22的,如果22的不足够,则用11的代替,
33的4个占一个箱子,但是会有余数,可能余下1,2,3个33的箱子,这个时候必须非情况考虑,
1个33的需要和5个22的,7个11的组合,2个33的需要和3个22的,6个11的组合,
3个33的需要和1个22的,5个11的组合,最后考虑9个22的装一个箱子,多余的22用11的去填充尽量挤满一个箱子,
最后36个11的装一个箱子,余下的1*1的也必须占一个箱子。。。
这个过程说出来已经非常复杂了,更何况用代码写,我费了九牛二虎之力才写出来,WA了一次才AC了…

代码:

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>
int main()
{
    int one, two, three, four, five, six;
    int num = 0;
    while (scanf(“%d%d%d%d%d%d”, &one, &two, &three, &four, &five, &six) == 6)
    {
        if (one == 0 && two == 0 && three == 0 && four == 0 && five == 0 && six == 0)
        {
            break;
        }
        num = six;
        num += five;
        if (one > five * 11)
        {
            one -= five * 11;
        }
        else
        {
            one = 0;
        }
        num += four;
        if (two > four * 5)
        {
            two -= four * 5;
        }
        else
        {
            if (one > four * 5 * 4 – two * 4)
            {
                one -= four * 5 * 4 – two * 4;
            }
            else
            {
                one = 0;
            }
            two = 0;
        }
        num += three / 4;
        three = three % 4;
        if (three == 1)
        {
            if (two > 5)
            {
                two -= 5;
                if (one > 7)
                {
                    one -= 7;
                }
                else
                {
                    one = 0;
                }
            }
            else
            {
                if (one > 27 – two * 4)
                {
                    one -= 27 – two * 4;
                }
                else
                {
                    one = 0;
                }
                two = 0;
            }
            ++num;
        }
        if (three == 2)
        {
            if (two > 3)
            {
                two -= 3;
                if (one > 6)
                {
                    one -= 6;
                }
                else
                {
                    one = 0;
                }
            }
            else
            {
                if (one > 18 – two * 4)
                {
                    one -= 18 – two * 4;
                }
                else
                {
                    one = 0;
                }
                two = 0;
            }
            ++num;
        }
        if (three == 3)
        {
            if (two > 1)
            {
                two -= 1;
                if (one > 5)
                {
                    one -= 5;
                }
                else
                {
                    one = 0;
                }
            }
            else
            {
                if (one > 9 – two * 4)
                {
                    one -= 9 – two * 4;
                }
                else
                {
                    one = 0;
                }
                two = 0;
            }
            ++num;
        }
        num += two / 9;
        two = two % 9;
        if (two)
        {
            if (one > 36 – two * 4)
            {
                one -= 36 – two * 4;
            }
            else
            {
                one = 0;
            }
            ++num;
        }
        num += one / 36;
        if (one % 36)
        {
            ++num;
        }
        printf(“%d\n”, num);
    }
    return 0;
}

这样的写法显然不好吧。。。首先,余下1,2,3个33时候需要填几个22的可以存储在数组里面,这样就可以不用写重复代码了,
如果再从整体考虑余下多少个格子,就不用用贪心算法模拟装箱子的过程了。。。
代码如下:

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
#include <stdio.h>
int main()
{
    int one, two, three, four, five, six;
    int num = 0;
    int twoPlace[4] = {0, 5, 3, 1};
    int remTwo, remOne;
    while (scanf("%d%d%d%d%d%d", &one, &two, &three, &four, &five, &six) == 6)
    {
        if (one == 0 && two == 0 && three == 0 && four == 0 && five == 0 && six == 0)
        {
            break;
        }
        num = six + five + four + (three + 3) / 4;
        remTwo = four * 5 + twoPlace[three % 4];
        if (two > remTwo)
        {
            num += (two – remTwo + 8) / 9;
        }
        remOne = 36 * num – 36 * six – 25 * five – 16 * four – 9 * three – 4 * two;
        if (one > remOne)
        {
            num += (one – remOne + 35) / 36;
        }
        printf(“%d\n”, num);
    }
    return 0;
}

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

链接：

http://poj.grids.cn/practice/2808

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

int main()
{
    int L, M;
    int nTrees[10005] = {0};
    int start, end;
    int nCount = 0;

    scanf("%d%d", &L, &M);
    while (M--)
    {
        scanf("%d%d", &start, &end);
        for (int i = start; i <= end; ++i)
        {
            nTrees[i] = 1;
        }
    }

    for (int i = 0; i <= L; ++i)
    {
        if (nTrees[i] == 0)
        {
            nCount++;
        }
    }

    printf("%d\n", nCount);
    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
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <stdlib.h>
#define M_MAX 100 + 2
struct Area
{
    int start;
    int end;
};
int CompareArea(const void *elem1, const void *elem2)
{
    return ((Area*)elem1)->start - ((Area*)elem2)->start;
}
int main()
{
    Area area[M_MAX], temp;
    int L = 0;
    int M = 0;
    int count = 0;
    scanf("%d%d", &L, &M);
    for (int i = 0; i < M; ++i)
    {
        scanf("%d%d", &area[i].start, &area[i].end);
    }
    qsort(area, M, sizeof(Area), CompareArea);

    temp = area[0];
    for (int i = 1; i < M; ++i)
    {
        if (area[i].start <= temp.end)
        {
            if (area[i].end > temp.end)
            {
                temp.end = area[i].end;
            }
        }
        else
        {
            count += temp.end - temp.start + 1;
            temp = area[i];
        }
    }
    count += temp.end - temp.start + 1;

    printf("%d\n", L + 1 - count);

    return 0;
}

整个算法的时间复杂度是 O(M * logM) + O(M)…