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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

ACM World finals 2012  

2013-10-04 14:43:02|  分类: 集训队作业 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
OK,12年补完计划完成

Problem A
简要题意:
三维空间点的最小生成树,但是点会沿直线匀速运动。
求问最小生成树改变了多少次。
n<=50
简要题解:
利用最小生成树的环切性质。在某条边比另一条边更优的时候就进行替换,所以可以计算出每条边比另一条小的时刻,从小到大枚举时刻,一旦可以替换暴力重建最小生成树,因为很明显最终改变的次数不会特别多。

Problem B
简要题意:
给定一条曲线(多项式),计算其从l到r绕x旋转的体积,并且从l到r找到前8个位置,使得两两位置之间的体积为inc。
简单题解:
$\int_a^b f^2(x) dx$ 为a到b之间的体积。暴力积分即可。

Problem C
简要题意:
n个点的图,要求从点0出发到n-1,要求遍历所有n个点,然后再从n-1号点返回到点0。要求,从0到n-1访问的前h个点和从n-1到0访问的前h个点是相同的,h=n/2(取下整)。。可以重复经过一个点,但是只能访问一次。
n<=20。
简要题解:
从0和n-1分别出发进行状压dp。
时间复杂度为2^20*20*20。在uva上跑得蛮快。

Problem D
简要题意:
寻找一个串在第n个斐波那契串中的出现次数
保证答案在long long 之内
简单题解:
想搞那个碉堡的做法。。但是最终还是没搞出来。。。
于是写了个暴力。。

Problem E
简单题意:
n个点(n<=75),任意点对a,b,要么a控制b,要么b控制a。
选择最少的点,使得所有的点都被控制。。选择点a会控制a和其所控制的点。
简要题解:
显然logn个点是上限,那么答案不会超过6。暴搜加点剪枝可以再uva上过了。

Problem F
简单题意:
钥匙套在钥匙环上,钥匙环组成森林。
可以将钥匙取下安上,也可以将钥匙环断开连接。
首先最小化对钥匙的操作,然后最小化对钥匙环的操作,使得一种钥匙在一个钥匙环的联通块上,其余在令一个联通块上。
钥匙和钥匙环分别用大写小写英文字母标号。
简要题解:
显然同一个钥匙环上只有一种钥匙的,这个钥匙不会动。否则,必定是取下其中一种。由于这样的钥匙环只有13个,暴力枚举2^13。
然后暴力枚举取下的安在哪儿,26*26。
最后树形dp划分方案。

Problem G
简单题意:
标题:最大费用流——这种题肯定和网络流无关。
n个三维空间的房子,房子有管道连向其它房子,以及若干空洞。不同房子的空洞之间可以接管道,代价为房子的距离(必定大于等于1),也可以花费0.5的代价将一个空洞补上。
有源点S和源点T,你可以再源点S的房子施加任意多的水和水压,要使得T充满水且不漏水,注意,水往低处流和连通性原理等物理学知识。
n<=400。
简要题解:
显然就是要使得S和T连通,那么就是要找条S到T的路径,但是由于有些地方可能没水。。那么得枚举水压——也就是水最高为多少,得到可能充水的房子。接下来显然分连通性考虑。同一连通块就是连进一条边连出一条边,然后剩下的都得堵住,然后找到连通块之间的连边,求最短路即可。有些细节需要注意。
uva上比较卡常数,也得注意一下。

Problem H
简单题意:
给定一个凸多边形,机器人似乎是走直线,碰到墙就拐拐。
求问机器人碰到多边形的每条边的最短路是啥。
简要题解:
很多年前考场上就直接切了。。算法什么的忘了。

Problem I
简单题意:
网格,里面有镜子,询问从左上角进入的光线是否能够到达右下角,或者添加一个镜子之后是否能到达右下角?
简要题解:
第一问暴力模拟即可,预处理出从每个镜子往四个方向到达的镜子是哪个。
第二个问题,发现在一个位置添加一个镜子就相当于交换两条路径,那么从右下角出发的路径与左上角出发的路径的交点就是答案了。

Problem J
简单题意:
飞机飞,不能远离最近的基地距离超过K。
飞机飞,飞了C米就得到基地补汽油。
问飞机从a飞到b最少飞多少才能到达。基地个数<=25。
——真简单题吧!
飞机是在地球上飞的。。地球是个球体。。
简要题解:
做法就是暴力求出所有园交然后求最短路的经典做法。
只是问题全都到球面上了。。。
三维计算几何技能get!

Problem K
简单题意:
n个单调栈,栈中元素从小到大,类似于汉诺塔。
在一次操作中,你可以将栈从中分开,或者将一个栈拼到另一个栈上(当然得继续保证单调性)。
求将这n个栈合并的最小操作次数。
简要分析:
显然会先将这n个栈分裂,然后再拼到一起,设分成了ans块,答案就是2*ans-n-1。
那么怎么分割呢?考虑最后的栈,如果确定每个元素属于哪个栈,那么ans就是属于不同栈的相邻对数+1。
又显然对于相同大小的元素前属于相同的栈的元素可以等价为一个,那么我们可以dp了。
考虑得到大小为i的元素,最后一个元素属于哪个栈,设为f[i][j]。
枚举大小为i+1的元素所属的栈的顺序(只有第一个和最后一个有关系)进行转移。。
看我题解多详细!

Problem L
简要题意:
两个人游戏,分别有n和m个数。。两个人轮流操作。。
每次操作可以合并己方的两个数,或者删除对方一个比自己最大的那个数小的那个数。
求第一个人是否胜利。
简要分析:
首先,得到几个结论:
1.只会删除对方最大的数。
2.如果自己最大的数小于对方最大的数,且自己加上自己第二大的数还是小于对方最大的数的话,自己必败。
枚举第一人第一次操作是合并还是吃掉。。。
那么就轮到第二人了。。
接下来的游戏一定是固定的。。
如果自己最大的已经被吃掉了,那么只能合并。。否则只会一直被吃下去,然后轮到第一人,如果他能吃,那么他获胜,否则合并,一直这样下去。
然后如果自己最大的没被吃掉,如果自己可以吃掉对方最大的,那么自己就已经必胜了。否则也只能合并。。然后轮到对方。。一直这样下去。。
所以策略其实是非常简单的。。该死的uva一直给我submission error,害得我自己写了个程序来测试。。
  评论这张
 
阅读(639)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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