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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

ACM World finals 2011  

2013-10-11 17:08:24|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
写一道水题就去完成各种无聊的任务去了。。

Problem A
简要题意:
你每次可以加一个数A,或者乘上M。
要求一种操作步骤,使得操作次数最少,且字典序最小(加A为'A',乘M为'M'),使得所有p,q之中的数进行这些操作之后都大于等于r小于等于s。
简要题解:
操作步骤对应于:
x*M^i+p*K。
枚举i。
然后可以计算出K的范围,用数位dp找出那个表示成M进制最小的数(注意K>M^i的情况,不过不麻烦)。
我代码好长。。估计有什么好办法吧。

Problem B
简要题意:
可以旋转平移和缩放,操作数很小。。问是否有,或有多种操作使得给定的三个点变到对应的三个点。
简要题解:
暴枚三个点的对应方式和旋转方式(旋转只有40种可能,题意给定)
然后剩下两个分别是对应于x坐标和y坐标的方程组。。很容易滴
于是就没有于是了。

Problem C
简要题意:
\epsfbox{p5130a.eps}
请识别如上图像。
简要题解:
每个图形的洞的个数都是不同的。。数数就行了。

Problem D
简要题意:
n*n的网格,有些格子放了东西,或还没放,或不能放,一格最多只能放一个东西。
要求放些东西使得:
放的东西最多
第i行放的和第i列放的一样多
每行每列的个数小于等于总个数的A/B。
简要题解:
暴枚每行每列最多放的东东个数。O(n)
然后最大费用可行流模型。
参考这儿吧。。。以前一直对于负权边很不拿手的说

Problem E
简要题意:
1000*1000的地图,上面有些点。
回答20个询问:求点P,使得离其曼哈顿距离小于r的点数最多。
简要题解:
坐标旋转45度。
枚举位置,然后用前缀和数组算出里面的点数即可。

Problem F
简要题意:
在第Di天你可以用Pi的价格买入每天收益为Gi的物品i,然后你可以再任意天花Ri<Pi卖掉。
第一天有K元,问D天的最大收益。
简要题解:
f[i]=f[j]-Pj+Rj+(Di-Dj)*Gj
状态转移方程。
cdq分治即可O(nlogn)

Problem G
简要题意:
很多木棍有序放置,你可以将连续的玩意合起来拼成一个多边形。。
求最终得到的若干多边形和最大。
简要题解:
由于原来做过,所以没有仔细想。
显然拼一个多边形的话,是要放在圆上,所以二分半径,分两种情况讨论。。这是经典题目。
但是麻烦的是此题O(n^3)dp当然可以过。。但是有O(n^2)的做法。。
注意为何会存在多个多边形?
那一定是存在一个特别长的木棍使得拼成的多边形很小或不存在。。。所以说删掉这根递归下去即可。

Problem H
简要题意:
HNOI2012原题。
简要题解:
HNOI2012原题都不会,我真心智商堪忧。。

Problem I
简要题意:
呃。。。僵尸要吃掉你的脑袋
于是僵尸会来追捕你,每回合你和僵尸都可以朝着八个方向移动(八连通)
问你最多可以撑多少个回合。
简要题解:
二分答案。
判断是否存在一个点,这个点你能到达,而僵尸不能到达。
注意到一个点可以到达的位置是个矩形,用扫描线即可。

Problem J
简要题意:
用最少个数,且字典序最大的方式使用\sum{i^2} 和\sum{(2*i+1)^2}来表示出数N(n<=10^6)。
简要题解:
01背包问题而已
注意用longlong来存下一种表示方式。。可以卡常数。

Problem K
简要题意:
给定一个多边形,问多宽的管道允许该多边形通过
多边形允许旋转。
简要题解:
求出凸包,对于每条边计算离其最远的点是哪个,比较即可。
  评论这张
 
阅读(427)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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