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

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

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

阅读全文 »

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

这也是一个很简单的题目,大家一看都知道用什么方法了,当然如果是查找的话,顺序查找是不行的,
方法一,是用map,建立个map<string, string>的字典,注意不要想当然用map<char, char>,
那样得动态分配内存,或者还是先开个大数组存好字典,其结果还是多浪费了内存…
排序+二分也不错的,因为数据量确实很大,而且题目也建议用c的io输入,所以这样再建立map<string, string>
中间还得转换一下…
总之做这个题还是很顺利的,就wa了一次,原因是2分写错了,我也很久没在oj上写2分了…

代码如下:

阅读全文 »

链接: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;
}

链接:http://poj.grids.cn/practice/1017
说实话
这就是个简单的装箱子问题,很容易想清楚装箱子的过程,而且这个过程是满足贪心算法的,
所以只需要用代码模拟整个装箱子的过程即可,但是这样真的就足够了吗???
我刚开始就是用代码模拟这个手动过程了,虽然AC了,但是代码有150行左右,逻辑也显得过于复杂了,
得不偿失。。。整个过程是66的一个占一个箱子,55的也必须一个占一个箱子,但是需要补11个11的,
4
4的也是一个占一个箱子,但是需要补5个22的,如果22的不足够,则用11的代替,
3
3的4个占一个箱子,但是会有余数,可能余下1,2,3个33的箱子,这个时候必须非情况考虑,
1个3
3的需要和5个22的,7个11的组合,2个33的需要和3个22的,6个11的组合,
3个3
3的需要和1个22的,5个11的组合,最后考虑9个22的装一个箱子,多余的22用11的去填充尽量挤满一个箱子,
最后36个1
1的装一个箱子,余下的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;
}
阅读全文 »