STEP BY STEP

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

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