类似积分

题目:给你三种图形,圆心在x轴上的圆,中心在x轴上且边与x轴平行的正方形,中心在x轴上且边与x轴成45度的正方形。三种图形的边长、半径都是<=10的非负数。且中心坐标是绝对值<=10的整数。给你n个图形(n<=10),问你共覆盖了多少面积,精确到整数位
思路:这题比赛时没多想,其实抓住答案的精度非常粗略且图形很少,范围很小就比较好做了。用积分的思想,x从-20递增到20,每次增长0.001,对于特定的x,枚举所有图形,找到最大的y,y*0.001就是这个小矩形区域的面积,累加*2即可。

hdoj4696

除了x[1]以外,其他x[]都是通过t[]数组转移的,so,显然x数组的值是在c数组中选的。
分情况:
(1)m<=0 显然无解
(2)若c数组中全是2:<1>那么如果m是奇数,无解.<2>m是偶数,有解
(3)若c数组中有1:第一个x选1,然后扩展,直到x数组的和>=m,由于x数组元素的值只可能是1或2,so,最终的和要么等于m,要么等于m+1,如果是等于m+1,只要去掉第一个1,从把x[2]的值作为x[1]扩展x数组即可。

hdoj1222

不难得到有安全hole的条件是:
(1)n>=m:n能被m整除且m!=1
(2)m>n:
1)m%n!=0:n能被(m%n)整除且(m%n)!=1
2)m%n==0(因为这个没考虑导致run time error一次。。)
(3)注意特殊情况n=1,此时不管m是多少一定没有安全hole。。(因为这个WA一次。。)
起初在想一个比较傻的问题:n>m时是否可能出现第二(也可以是三、四等等)圈时没有走到访问过的点(错开了),而之后走第k圈的时候走到了一个以前访问过的点,之后循环访问这些点?
其实这是不可能的,这个问题有点二。。用反证可以证明:假设之后第k圈的时候访问了以前已经访问的某点,那么从这个时刻往前反推,当反推到第二圈时,可以发现推出的点并不是原来第二圈时走过的点(错开的点),矛盾。可知第二圈时不可能错开。(k=3试试,这样更好理解)

hdoj1073

几点收获:
1.gets能读取回车,但是它会自动把回车改为’\0′
2.gets不能读取空行(因为空行只有一个’\n’,gets()会把它变成’\0′,这样,字符串长度为0,相当于什么也没读到)
3.如何将两篇文章(也就是行数不定,且可能有空行)进行比较:将文章转成一个字符串,因为可能有空行,所以不能用gets(如果用gets,则一篇文章空行,一篇无空行,其他地方相同,转化成的字符串会完全相同),这时应当自己写一个会读取回车的函数,类似于gets(),但不会将’\n’转化为’\0′,这样就保证了有无空行是不同的(有空行会在转化成的字符串中有一个’\n’)

acm常见错误(添加中。。)

一直想写这些总结一下自己过去常犯的错误,但是总是忘记。。

(1)数组开小了

(2)精度问题,数开小了(__int64定义成int)

(3)精度问题,数转换错误(__int64赋值给int)

(4)char数组定义成int

(5)==写成=(很难查到的错误)

(6)变量未初始化

(7)变量初始化错误,想当然的初始化,特别是数组,有时候a[0]、a[len-1]等需要初始化为和其他元素不同的值,但不仔细分析就全赋为0就出错了

(8)getchar()(字符串相关题目,都懂得~~)

(9)语句块漏写括号(这个其实已经消灭了)

(10)if语句块大量嵌套时,一定要加上括号,防止else和else if混接在错误的if之后。养成良好习惯。。(上一条刚说已经消灭了,昨天做hdoj1426又出现这个错误了。。2012.12.28)

 

hdoj1106

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1106
这道题题意是将一串数字串以5为界分割成若干整数。看来本菜鸟的代码实现能力还是有待提高。。其实一直挺不喜欢字符串题的,虽然没有什么算法,但是一些细节足够折腾你半天了。。
思路:使用一个队列,用gets读入一行,从左开始遍历每个字符串中的每个字符。如果不是5,则将其入队,否则察看队列是否为空。若不空说明前面已入队一个完整整数,此时将其出队并转成整型。若为空,则说明前面的数字也为5。
最后考虑特殊情况,当字符串为5123时,由于最后面没有5,所以最后一个整数会留在队列中未被处理。所以最后要判断队列是否为空,若不空,则输出最后一个整数(当然,其实是转换到一个整型数组里,最后对这个数组排序就行了)

hdoj1113

http://acm.hdu.edu.cn/showproblem.php?pid=1113
字符串题,不难,开始NOT A VALID WORD后没有打印*号,WA了大半天。。。。
思路:将字典里的每个单词按字典序重排。重排后的单词和原来的单词作为一个字典结构体元素的域。对于每个要查找的单词,先按字母的字典序对其重排,然后在字典(结构体数组)中查找,如果找到则输出。
注意:字典中单词间要按字符串字典序排序,因为对于每个要查询的单词,如果字典中存在多个符合条件的单词,那么要按字典序输出单词。