注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

20141207地大校赛题目小结  

2014-12-08 18:13:00|  分类: 杂记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
去地大参加校赛打了个酱油,写了5题第6名,总结下题目:
A:1号水题,循环一遍,记录下星期几和采了多少金币即可。

B:2号水题,分解因数,最后从小到大输出所有因数(除1和n)。

D:3号题,打印心形代码,只有84个位置需要替换,先把输入的字符串转换下,然后替换到心形代码里,填不满的地方用无效字符代替就好。需要注意下转义字符的输出。

C:4号题,n*m的矩阵,分割k次,问怎么分割使得面积最小的子矩阵面积最大。
分类贪心下就好,首先判断n+m-2>=k是否成立,否则无解。
然后判断下n%(k+1)==0 || m%(k+1)==0是否成立,成立则输出n/(k+1)*m或m/(k+1)*n。
然后分类讨论,n和m将小的放前面,
第一类k+1<=n,一种全部横切,一种全部纵切,return两种较大值;
第二类k+1<=m,一种全部纵切,一种横切n-1次,剩下的纵切,return两种较大值;
第三类k>1>m,一种横切n-1次,剩下的纵切,一种纵切m-1次,剩下的横切,return两种最大值。

G:n本书,已知每本书的长度和宽度,现在要叠书,要求下面书的长度和宽度要大于等于上面的,问最少能堆几堆。
这题和套娃问题(Nested Dolls)很像,已知每个娃娃的高度和宽度,问最少能套成几个娃娃。和这题不一样的地方是里面娃娃的高度和宽度要求小于外面的娃娃。
套娃问题解法:
先排序,高度从大到小,相等按宽度从小到大排(因为不可以等于),然后取n个宽度构成数组。
这部分贪心下,看前面有没有比当前大的,有就替换成当前的长度,否则ans++。
本题解法:
先排序,长度从小到大,相等按宽度从小到大排,然后取n个宽度构成数组。
这部分贪心下,看前面有没有比当前小的,有就把前面的替换成当前的长度,没有的话ans++。
比赛的时候这部分求了最长递减子序列的长度过了,当时也不知道为什么这样也可以,后来百度了发现有个定理:
Dilworth定理:对于一个偏序集,最少链划分等于最长反链长度。
Dilworth定理的对偶定理:对于一个偏序集,其最少反链划分数等于其最长链的长度。

E:
比赛时不会做,后来问了buaa大神,是lattice_count计数问题,可以把原问题转换成求直线y=q/p*x(0<=x<=(p-1)/2)与x轴构成的区域内整数点个数。

F:
这题也是请教了buaa大神才会的,不论是向上取整还是向下取整,小数部分都会减掉,所以把所有小数部分相加为sum,向上取整一次,则sum-1,所以只要看最多能够向上取整几次就可以了。统计下有多少个非整数可以减,但是上限是n。

其他题目来不及看了,总结结束。感谢地大提供如此宝贵的机会,感谢buaa李珎大神的悉心指点,感谢!
  评论这张
 
阅读(95)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017