昨晚和今天早上把博弈的理论过了一下,好!下午开始做题,看了下别人的解题报告。
个人觉得无论从存储优化,还是判重上都还值得商榷,或许是牛人不原意优化了吧!
好吧,那只有LLV来做这种工作了!
先贴个转化之后的编码图
1.顶点序号转成从0开始;
2.边序号[红色]:
考虑输入[v1,v2]->Edge的转化,做一个简单映射:v1+v2->Edge[从堆那里来的思路],注意到有些边不符合,
于是可以在代码是硬编码[3,4]->8,[4,5]->15,[6,7]->16,[7,8]->17,[8,9]->18.
这样可以省去一个二维或者一维数组!
3.用一个unsigned int[bitset<18>]来标示当前的边状态,所有状态为0,表示到达终态!
4.OK,还有一个让我很头痛的问题,怎么在加入一边之后来判断影响的三角形呢?
  • 开始想到了hash,但肯定效率不高,这是可以预料的。因为我要做一个以插入边为主键,然后对应三角形序号为value的链接表,而且每次要从头到尾遍历一次,即使加入状态标志[当前三角形是否填满],换言之,这个方法的复杂度是O(e)的,非常不爽!
  • 仔细想下呢,如果我用一个char SEdge[0..8]=3来表示三角形当前还有几边需要填充,再加上一个边,三角形映射表[这个表是固定的,可以在全局里面写死,注意一边可能对应两个三角形,因此是一个char[1…18][0..1],char EdgeTri[1…18]=所在三角形标号;那不就足够了!初始时,将SEdge初始化为0[memset肯定比我for快的多],边位图变为0xff[18];然后每次插入一边[查找位图的1位],就将对应三角形边char的数目增1[最多2个三角形]。由于边是不可能重复插入的,而且不用查找,这样应该要快点。

我唯一担心的就是空间开太大了,在估算下每个博弈状态state[unsigned int,char myCount,char rivalCount,char SEdge[9]],博弈的函数可以不用hash,因为我已经用unsigned int来代表一个棋盘格局了,那直接f[unsigned int]就可以了.

那state:15bytes,f[2^18],俄!256K,加入A-B剪刀有些状态应该用不到的,还好,还好!大概思路整理出来了,下面看我把你切掉~~~~[估计转化的时候,我多半要晕的,小心为上,还不晓得代码要写多长,诚邀牛人,高手,大虾来指点下,不晓得这个思路还能优化不]

写代码之前,整理下思路:

1.f[2^18]表示A先手,A比B多获得的三角形数。[那我们最终比那个多就可以了,CountA,CountB其实不用放入函数,但为了能实现主观剪刀,还是留到起,作为函数的输入,一旦CountA或者CountB超过5,博弈树就不用扩展了!]

2.我们以f[2^18]为e(s),A-B剪刀以此为依据,开始时alpha=0,beta=10[题目情景下的设计],剩下的东西还有没?Hash应该不用了,f[2^18]已经存在!

热身动手,切题!

 
 

Advertisements