posts - 7,comments - 3,trackbacks - 0

第一次写网络赛的题解,福州赛区网络赛作为我第一年ACM最后一次网络赛酱油,画了一个很像逗号的句号.....好吧,还得为北京现场赛准备啊准备.......

这次酱油打的很犀利,貌似出第一题很快,之后节奏就总比师兄们慢一步.....囧死了,名次很顺利的入手,就没啥了,写下题解吧。

 

题目链接 

 

第一题:A Card Game

坑爹的题目叙述,仰慕杰哥非常犀利的YY出题意,ans = a[1] / N......好吧,现在证明一下啊。

首先,我们假设取牌的顺序是一个序列,我们考虑可行序列存在的情况:对于序列中任意一个数i的后面一个数j,必然要放在第i堆里面,因为值为i的数有a[i]个,所以在i后面的数也恰好有a[i]个,所以a[i]数放在了第i堆,符合题目约束了。

由于游戏从第一个堆开始,第一个数是没有前驱的,所以,如果最后一个数不是1,那么第一堆必然是a[1] + 1个数了,与约束不符合。而且,如果最后一个数不是1,记为i的话,就只有a[i] - 1个后继了。

所以,综上,只有最后一个数为1,那么堆容量a[i]才会符合约束,而我们能根据序列构造一种符合情况的分摊和取牌方案,所以,题目变为了:N个数的全排列,其中最后一个是1的概率.....

先从a[1]个1里面取一个1,有a[1]种方案,之后剩下N-1个数全排列(N-1)!,符合结尾是1的方案数是a[1] * (N-1)!种,所以解就是a[1] / N。

 

第二题:Abalone 

这游戏....没玩过啊.....膜拜华中科技大斩杀此题并且是FB啊.....

 

第三题:Aircraft

一道计算几何的问题,和VIJOS上面的一道DP题WALL挺像的,不过那个是正方形,这个是圆形。

首先很容易想到就是最短路了,因为N范围很小,枚举所有圆的交点,之后你要么过圆心,要么过交点,之后最短路,不过有个trick,就是很多圆排列那种情况,可以不过任何交点圆心直接到达。所以,对于那种情况,分段判断一下这个线段是否整个在园中就行了。这个判断是相当繁杂的,先求出线段与圆的所有交点,之后对这些点排序,判断相邻两个点之间的线段是否在圆上就OK了....

 

第四题:Carcassonne

达哥犀利的AC了此题,我们都知道是DP,但是我比赛的时候怎么也没想出转移方程....好吧,插头DP咱不会.....

赛后想到了高中时候写过的多米诺,和这个很像,两个解法,状态压缩DP和矩阵乘法....后者我忘了....

状态压缩DP:状态就是每行下面连成的图案状态(最多3^12状态数)

转移方程f[row][next_line] = sum(f[row - 1][pre_line])其中,pre_line和next_line是该行合法状态时,上一行图案和下一行图案。

 

第五题:Catan

非常犀利的一道题,卡掉了华中科技大AK全场的机会,而且,这个游戏我没玩过,也就没看题了.....

 

第六题:Random Sequence

一道数学题。

结论:我们设序列a是长度为i所有情况的综合(就是不除以那个2^n),b序列是b[i] = a[i] - a[i-1] * 2,观察b数列我们可以特出,如果是i偶数,那么b[i] = 2 * b[i-1],如果是i奇数,那么就等于C((i+1)/2)(i+1)(i+1里面取一半....)b序列有了,a也就有了,除以2^n,得解。

下面论证一下这个YY式子出的式子是对的.....

首先,我们可以知道a[i] >= a[i-1] * 2,因为i-1序列长度增加了,解的种类增加,而且上限也增加了,这就是为什么会大于,由于长度存在奇偶性质,所以奇位和偶位增加一位的情况有一样了......

之后....具体的.....我也说不清楚了.....总之,数学归纳法出来的是对的,而理论上.....我不是数学家。。

 

第七题:Random Maze

这道题看了,没写,因为等我看着道题的时候,已经马上收场了.....看完这道题后我淡定地打开了数独......

说一下思路吧,改变每条表的权值为a-b,添加一条终点指向起点的特殊边,这样保证里每个点出入度相等的条件,之后找出所有负向环正向,如果环中没有那个特殊边,就是impossible,不过对于搜环和重边的问题,我还真没有啥好方法.....SPFA吧......

下面是来自Starvae的解题:最小费用最大流(膜拜)

下面是直接建图的方法。

我们的答案保存在sum中。

初始时每个点的in[] out[] 都为0, in[i] 表示第i这个点需要in[i]条指向i的边才能满足i这个点的入度平衡。

对于每条边,如果a <= b 那么建 v->u的边,流量为1, 权值为b-a。 sum+= a;

此时, u->v 被翻转, 所以in[v] ++, out[u] ++.

否则 建 u->v的边, 流量为1, 权值为a-b。 sum += b;

此时, u->v 没有被翻转, 所以in[] out[] 不改变

然后添加一条终点指向起点的边, 直接in[s] ++; out[t] ++;

然后新建超级源汇S,T。

对于每个点i, 如果in[i] > out[i] . 建边S->i, 权值为0, 流量为in[i] – out[i];

否则的话 建边 i->T ,权值为0, 流量为out[i] – in[i];

然后跑一次最小费用最大流。

如果最后从S出去的边没有满流的话 就是impossible。

否则答案即为sum+ mincost.

 

第八题:SanguoSHA

呃,很暴力的一道题,6!* 6!真心能接受啊......

全排列自己的武将,和对方全排列的比,如果完胜,输出,不完胜,下一个排列。

next_permutation函数很好用。

 

第九题:Squiggly Sudoku

模板题吧.....算是吧......强大的Dancing Links,高中为了玩数独,弄了它好久....而且现在也没弄明白,读入比较特殊,DFS一下,之后果断十字链表......

 

第十题:War

又是一个游戏题......

题目很短,而且开场被FB,之后我果断读题,YY了两个题意,先杀死时间最长的或者先杀死需要最少了,师哥看了数据果断否定了我第二个YY,之后开始敲,一个sort,出解,感觉速度挺快了....可是就这样还被落在了第二页,仰慕众神牛队的速度啊......

 

总结:这次网络赛,背景都是游戏,还都是我没玩过的游戏.......三国杀除外......我了个去啦,在中国,是吧,主流游戏就是三国杀,WOW,DOTA,SC2,您老倒好,弄些外国的游戏......好吧,不吐槽了,感觉题挺好的,难水分明.....网络流那道我真TM的没看出来是网络流啊......还有那两个我题都懒得看的题......我老怀疑有时候我不是在打ACM比赛,我像在考GRE.....第一次写这么全的题解报告,大家多批评吧......

而且,这次网络赛酱油打的很好,很专业,打出了国际水平~~~~~

posted on 2011-10-15 22:15 LLawliet 阅读(619) 评论(2)  编辑 收藏 引用 所属分类: 赛区题解

FeedBack:
# re: 2011 ACM/ICPC 福州赛区网络赛解题报告
2012-08-08 19:07 | wangs
大牛哪个学校的?  回复  更多评论
  
# re: 2011 ACM/ICPC 福州赛区网络赛解题报告
2012-08-09 14:52 | LLawliet
@wangs
吉大的...  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理