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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

清华集训  

2013-12-12 17:15:42|  分类: 日记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 Day1 T3 扑克牌

丽洁的题。
简要题意:
 我们有N张纸牌,每张牌都有数字和颜色两个属性。今天我心情不错,想把这N张牌排成一行,使得相邻的两个要么颜色相同要么数字相同。数字在0到9之间,颜色有红黄蓝三种(用012来表示)。想让你求出方案数。


这题我考场上拿了60分,怒刷存在感。。
其实本题的正解相当好写好想好调,而且跑得飞快。。
尽管丽洁开了10s时限,但实际上完全用不着。。本机都是1s跑出来了。。

好了,稍微分析下题目。。
我们首先想办法将相邻的数分成两类:
1.颜色相同。
2.只有数相同。

我们将所有靠第二类边相邻的数归为一组,对于相邻的两组,前者的右端点和后者的左端点颜色一定是一样的。。
我们可以想到什么呢?
可以将一组看成连接端点颜色的一条边!
那么假设我们分好了组。
剩下的就是在三个点的图中求出欧拉回路的个数!
这样的图有多少个呢?暴搜一下大概有2*10^6种。。我们只要搞出分组方案就能dp了!

分组方案也很好计算的。。
因为只有数字相同的才会在一组。。
考虑一个数字,题目中说了数字和颜色相同的卡片不超过3个。。也就是说我们只是对至多9张卡牌分组而已。。暴搜。。可以发现这样的分组方案不超过200(具体超过了没我也不记得了。。不过反正跑得飞快的)。
对于不同数字的话,就可以直接用一个dp进行合并。。

这样程序就很好写了。。


Day2 T1 卡内存
范浩强的题:
题意。。。很复杂啊。。
给定一个可逆函数,能够根据当前的H值,位数,选定的bool值x_i,得到新的H值。。
要求确定序列的x值。。
使得得到的所有H值的某个函数值最小。。。
H<=2^20
n<=5000
n*H<=5*10^7
时限:5s
内存:8MB
比较丧心病狂的题。。
时间复杂度nHlogn的分治。。

首先这题nH的背包很简单。。而且用滚动数组优化也很容易求得最优解。。
但是本题空间限制比较丧心病狂。。
所以必须使用分治。。。
解决区间(l,r)的问题,我们可以通过dp算出mid的H值。。从l到mid dp一次,从r到mid dp一次。。。
然后求出mid的之后,分别处理区间(l,mid-1),(mid+1,r)这两个区间。。
这样空间复杂度O(H)
时间复杂度O(nHlogn)。。。
写完之后卡了下常数开了O2才过。。

我要说的不是这种做法。。当时我在考场上想了很久这题,也想出了一种nHlogn的做法,并且不需要这个函数可逆。。但是我写完后发现常数太大于是放弃了。。
现在想起来,我觉得我的做法比标程做法好多了。。

其实我们可以不分治的。。我们可以进行分块。。。
将整个序列分成N/25块。。
用n*N/25 * H的空间存下每一块开头的那个玩意儿的dp值,开short的话加上滚动数组空间是够的。。
然后用滚动数组暴力dp。。
dp出来之后倒推。。
对于每一块,我们知道这块结束时H值是多少,也知道开头的每个H值的最优值。。但由于函数不存在可逆性。。所以我们一次暴力枚举这块的第一个未确定的x值是什么,然后做dp,看是否能够取得最优值。。
这样时间复杂度就是25* nHlogn的。。常数贼大。。肯定过不了。。
但是有了可逆性。。我们就可以暴力在x值确定了足够多之后,暴枚,逆推。。可以减少不小的常数。过不过得了我不知道,反正分治的常数也不小,说说总没什么关系吧。。
  评论这张
 
阅读(1189)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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