ZOJ 3050 Die Board Game (bfs)

ZOJ 3050 Die Board Game

色子在坐标上滚动,给定起始点的位置和状态,看看能不能从起点走到终点并且和题目中给出的终点状态一样,求出最少步数的,n,m<=100.

刚开始我是一点想法都没有,后来看了网上的解题报告,说是每个坐标上都有24种状态,我们可以将带有状态的地图看成一个三维的map[i][j][state],这样就可以通过广搜来解决了,我又无语了,这都是谁想出来的啊,这么巧妙,刚开始由于不知道状态之间怎样转换,昨天想到了,就在今天早上A掉~

(更多…)

继续阅读 →

ZOJ 1003 Crashing Balloon(dfs)

ZOJ 1003 Crashing Balloon

踩气球,气球上的分值为1-100间的数,参赛者的初始分数为1,每踩一个气球就把气球的分数乘以自己的分数,得到比分,最后选手会声明自己的比分,但是有的人可能计算错误,所以最后的分数可能不正确,判断一下两个分数是否能产生….

刚接触acm的时候就看到这个题了..当时是什么思路也没有,现在又看还是不会,我总是想着把,所有的分解情况都列出来再进行比较,但是貌似不可行.今天忍不住偷偷看了别人的代码(貌似我已经几个月没有看过别人的代码了),顿时就震精了,为什么我想不到呢? 😥
(更多…)

继续阅读 →

ZOJ 1107 FatMouse and Cheese(DP)

ZOJ 1107 FatMouse and Cheese

给出一个地图,每个点上有相应数量的cheese,从(0,0)开始,每到一个格子就把这个格子里的cheese吃光,每走一步方向只能是上下左右,每一步最多的格子数为k,每一步之后的一格所包含的cheese数量要比之前一格多…怎样才能使得所得的cheese数最多呢,输出最多的cheese数.

刚开始我想的搜索,但是无门.但是看题之前已经知道是dp了,就一直往那方面想,一开始就想到了从cheese最大点开始,把他相应范围内的最大数更新一下,也就是dp[i][j] = map[i][j] + (与i,j在合法范围内dp[*][*]最大值),dp[i][j]表示从(i,j)开始所能得到的最多cheese。但是想想实现起来比较麻烦。昨天晚上睡觉上微博的时候,突然想到把这些点按照cheese数排列,然后从前往后进行dp,相当于LIS,只不过中间的限制条件比较多。按照这个思路,我写出代码,并且ac掉:
(更多…)

继续阅读 →

ZOJ 1953 Advanced Fruits(LCS)

ZOJ 1953 Advanced Fruits

A掉这个题我十分激动,很久没有做dp题了,因为不是很开窍,前两天,累了就趴在床上看算导,翻到动态规划,没想到很顺利地从头到尾看完了,所以就像尝试下dp….这个属于最长公共子序列,以前做过不过这个题需要记录路径,由于路径不唯一,所以是special judge,两个字符串要合并成一个,并且公共部分只输出一次,这其中的细节认真想想就可以做出来..1Y,很高兴~

(更多…)

继续阅读 →

ZOJ 1004 Anagrams by Stack

ZOJ 1004 Anagrams by Stack

这个题很早就看到了,但是当时关于栈没有很好的运用,而且还需要用递归所以就放过了。。今天重拾这个题,感觉应付起来很轻松,可能是因为进步了吧,嘿嘿。。1A~

i代表入栈操作,o代表弹出,对于一个字符串,从第一个字符开始,进行一系列的栈操作,问有没有可能出栈的字符可以按顺序组成另外一个字符串。ok函数表示得到的io操作是否能得到另外一个串。

(更多…)

继续阅读 →

ZOJ 1094 Matrix Chain Multiplication

ZOJ 1094 Matrix Chain Multiplication

矩阵链乘的时候,不同的结合方式所需要的运算次数不同,肯定存在一个乘法次数最少的结合方式(可以用dp求出),此题以此为背景,给出结合方式,求出所需要的乘法次数.算是经典的栈的应用,维护两个栈,KUO是括号的栈,M表示矩阵栈,从每一个表达式的开始,遇到左括号和矩阵就压入相应的栈,遇到右括号就进行栈顶两个元素的运算,直到最后。如果某两个元素不能相乘,输出error

(更多…)

继续阅读 →

二项式系数 – Binomial Coefficients

二项式系数是组合数学中十分重要的基本知识,各种应用都少不了他.今天做了两个题,顺便总结下:

这个是我们了解到的最基本的形式,当k=0时,上式值为1,当k>n时,值为0;

帕斯卡三角中的每个数相当于顶上两侧数的加和,也可以用组合的思想来解释这个公式:

从n个人中选出k个人,我们先看其中的A某,如果他不在这k个人中,那么就相当于从n-1个人中挑出k个人,如果他在这k个人中,那么剩下的k-1个人就要从n-1个人中挑选.根据加法原理,总的数量就是这两种情况的和.
(更多…)

继续阅读 →

ZOJ 1274 Getting Chorded(模拟)

zoj 1274 Getting Chorded

“钢琴的音符有12种,A,A# (A-sharp), B, C, C#, D, D#, E, F, F#, G, and G#,同时按下三个音符,有三种情况,一种是Major chord,一种是Minor chord,最后一种是什么都不是unrecognized,假设按下的这三个音符按顺序排列分别是a,b,c,如果ab中间隔3个,bc之间隔2个,那么整个结果就是a Major chord,如果ab中间隔2个,bc之间隔3个,那么整个结果是a Minor chord(假定12种音符在琴键上是循环排列),给定三个音符,然你判断结果是上述三种中的哪一种”

由于他给的音符的顺序不确定,大小写也不确定,一个音符的两个名称给哪个也不确定,而且输出是要求原样,类型要输出大写,-___-……所以我们一步一步来。。。保留输入的形式方便输出;把音符的两个名称转化为带#的形式,然后转换成大写;比较恶心的是他的顺序也不确定,但是给定的三个它们的最终结果是一样的,那么给12种音符赋值为20,21,22,23,2……210,211,  三种的值相加是唯一的,所以。。。。。

代码很丑,体现了我做模拟题的一贯风格:
(更多…)

继续阅读 →

ZOJ 2803 Crashing Robots

ZOJ 2803 Crashing Robots

“机器人模拟,给定一个A*B的地图,给定N个机器人的初始位置和方向,然后会有M个操作,判断这M是否能正常执行,如果能,输出“OK”,否则输出是出界还是与另外的机器人相撞。操作是一步一步执行的,没有两个同时发生,’R’,’L’,’F’分别表示向右转,向左转,向前进一步……”

步骤比较繁,但是没有什么陷阱,考耐心。此题麻烦的就是方向的转化,用一个dir数组保存方向的变化量,然后每个方向对应一个变化量。

(更多…)

继续阅读 →