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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

ACM World finals 2010  

2013-10-18 21:34:47|  分类: 集训队作业 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
写完这道题,我就。。我就。。我就去颓baldr sky
===========================================
感觉WF的题没意思。。所以暂时不做了。。

Problem B:
题意:
给定一串编码,求验证and解码。。。
编码是长度为5的01串,与数字和'-'对应,用0隔开。
最开始和最后是开始/结束编码。
由于是扫描进来的,所以0表示的是窄区间,1表示的是宽区间。
宽区间的长度是窄区间的两倍。
最后两个编码CK用做验证。
求问该编码是否合法。
题解:
就是个模拟题。。但是很蛋疼啊有些地方。
反正我是找了份标程对着改了改才过。。原因未知。
UPD:原因找到了。。宽的区域要求严格是窄的区域的两倍,也就是目标区域分别为x和2x。。而我在写程序的时候相当然地分别求出宽的区域和窄的区域的x然后比较其倍数关系是否在一个足够小的范围——但这样是有bug的。。而且我的足够小的范围并不是很小。

Problem C:
题意:
n*m的网格。。有w(w<=1000)个水平的墙。
你只能往右或往上。
问有多少个格子无法到达(m,n)这个店。
题解:
离散化然后暴力。。
注意(m,n)这个点可以被占据。

Problem D:
一棵树,你要占据每个节点。你可以派军队从任意点出发访问所有点。
每个点需要a人攻占,然后消耗b人。
问最少需要的人数。
简要题解:
显然枚举根,然后类似树形dp。
关键是访问顺序,每个子树由两个玩意儿描述:(a,b),a为至少需要的人数,b为消耗的人数。
意识流一下,人数是不断消耗的,所以让a从大到小似乎就可以了。。
但是这时错滴。
那么考虑两个人a1,b1,a2,b2。
若前者必须在后者前面
由before>a1,before>a2
before-b1>=a2
before-b2<a1
得a1+b2>before>=a2+b1
得到a1-b1>a2-b2。
就此排序即可。

Problem F:
简要题意:
 就是
the Loser 9:59:07 
这样的图
the Loser 9:59:13 
黑点是高度
the Loser 9:59:24 
然后要求绘制等高线
the Loser 9:59:40 
求最后等高线的长度和
简要题解:
暴力算就行了。。没啥可说的


Problem J:
r*c,你可以将巧克力一分为二划分
问是否能够得到各位小伙伴要求的巧克力而且刚好没有剩余。
小伙伴的个数<=15。
简要题解:
确定了小伙伴的集合和一块巧克力的一边长,另一边长就得到了。
于是可以集合dp。
卡了下常数才过T_T。

  评论这张
 
阅读(482)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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