链接:
http://poj.grids.cn/practice/2818这其实就是一个简单的移位密码算法题,只是多了个循环而已,密码学里面也指出过循环运算是没有效果的,所以题目估计也就考察了这一点,如果没有找出循环周期,此题会一直超时的...
刚开始,我就直接模拟K次加密,显然超时了,当时还不信了,以为简单至此。。。
后面我就开始改进了,刚开始是把周期计算和加密放在一起写了,样例也过了,但是还是一直错...
没办法再改,我改成把周期求出来,再对加密次数K取模后,再进行运算...
好吧,还是一样wa,后面就变成PE了。。。
最后,这个题经过我近2个小时的奋战,终于过了,一共错了近10次吧...第一次提交是距现在1个多小时前了...
最后发现错误的原因还是换行输出的地方错了,题目要求是每一组中间有个空行,我则输出的是每次计算后有个空行...
实在无语...
思维不严谨啊...
代码:
#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行左右,逻辑也显得过于复杂了,
得不偿失。。。整个过程是6*6的一个占一个箱子,5*5的也必须一个占一个箱子,但是需要补11个1*1的,
4*4的也是一个占一个箱子,但是需要补5个2*2的,如果2*2的不足够,则用1*1的代替,
3*3的4个占一个箱子,但是会有余数,可能余下1,2,3个3*3的箱子,这个时候必须非情况考虑,
1个3*3的需要和5个2*2的,7个1*1的组合,2个3*3的需要和3个2*2的,6个1*1的组合,
3个3*3的需要和1个2*2的,5个1*1的组合,最后考虑9个2*2的装一个箱子,多余的2*2用1*1的去填充尽量挤满一个箱子,
最后36个1*1的装一个箱子,余下的1*1的也必须占一个箱子。。。
这个过程说出来已经非常复杂了,更何况用代码写,我费了九牛二虎之力才写出来,WA了一次才AC了...
代码:
#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个3*3时候需要填几个2*2的可以存储在数组里面,这样就可以不用写重复代码了,
如果再从整体考虑余下多少个格子,就不用用贪心算法模拟装箱子的过程了。。。
代码如下:
#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;
}
这个blog的申请时间估计已经有1个多星期了。。。那是在我最无聊的时刻吧。。。从前天起的前面6天外出旅行了,用的是生物能,用我们自己的双脚踩车去了新宁崀山。从长沙到哪里也有300多公里。想起这6天的种种,收获颇丰。我也不是来写这篇游记的,所以这次旅行也不想说得过多了。
我以后会很少在 qzone 和 人人 以及 百度空间 上更新任何文章了。不管是发牢骚还是记录些学习感悟,都不会写在那上面了。如果有熟人有心看到过我这个blog的话,就不必要去看其它地方的了,那里只有我以前的胡乱感受。
一恍大学过了3年多了,大四了,保研也确定了3个多星期了。前2个星期,则完全是在宿舍宅了半个月。第三个星期,鼓起勇气出去旅行。说实话,一直到那天早上我都犹豫要不要去的了。后面的3天,基本上每天都有12小时在路上奔走。第一天非常难受,刚过猴子石大桥就感觉受不了了,还好出城的时候走的慢,一直跟在李后面。。。出城后,到暮云,到湘潭,那个上午就感觉用够了全部力量了。下午开走前,真的怀疑过接下来该怎么办。。。在路上的那种难受感觉说也说不出来,其实我身体很虚的那种。在宿舍宅了3年多,生活没有规律,饮食也不够。第一天真的非常难受。走不动的时候,我老是想一些这几年让我痛不欲生的事情,我永远也无法改变无法解决,但是又最后会把错误归咎到自己身上的事情。真的痛不欲生。。。也许,这就是生命。生命就是一场旅行,虽然很痛,但是沿途还有风景,这种旅行本身就具备了最大的意义。
真的是万事开头难,第二天就没有那么强烈的感觉了。虽然,还是没有力气,还是很难受,但是还是稍微适应了点了。坚持才是胜利,这句话在这个时候很对。第三天,我完全感觉跟前面2天不同了,这一天我能够骑到前面去了,虽然这一天的路最烂,最陡。。。不要以为成功就是那么容易,即使经过3天的艰苦车行。我们还是没有到达目的地,我们只是到了新宁的一个镇,离县城还是有50多公里,这边路这么烂,基本上在修的烂国道,而且还带盘山的那种。第四天,只能做中吧去了,坐车时候受到了鄙视比骑车时更多,车放在里面而不是后备箱确实碍着太多人了,农村里面的车也挤成那样了,我也一直不会说什么好话。。。第四天,我们终于出了县城到了景区。到景区大门的时候,就开始虚脱了,不是因为长途跋涉,而是因为肠胃不好,发作了,拉了个肚子之后整个人就虚脱了。唉,确实不是这么容易啊。。。
第四天我们看了一个景区,第五天看了二个更爽的景区,每天基本也是活动12小时以上。感谢住的地方那么干净,老板娘做的菜也那么好吃。如果再去一定会住那里,也会向别人推荐那里。那个家庭宾馆我们还拍了照。一路所有的照片都在qq空间里面了。。。
说了不写游记的,我还是写了这么多的。。。这篇游记如果真的认真写实在太长了,一路也没有记日记。这5天多的感受,比我大学里面任何时间的感觉受激烈很多。我收获了很多很多。本来就打算以此作为开始,重开我的人生的。这辈子做过太多不堪的事情了,是时候为了自己,不受任何世俗观念影响做点事情了。。。