加载中…
个人资料
曹鹏博士
曹鹏博士 新浪个人认证
  • 博客等级:
  • 博客积分:0
  • 博客访问:112,789
  • 关注人气:136
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

浙江省第8届程序设计竞赛解题报告

(2011-04-16 21:04:05)
标签:

zoj

acm

online

judge

算法

浙江

省赛

zju

杂谈

分类: acm算法

题外话:

         这次省赛与校赛一共出了33道题,校赛选了10题,省赛选了13题。本来校赛我就想出题,没时间出……后来,我一共出了7道题,但是由于各种原因(例如题目太简单或者太难,或者和已有的题目冲突等等),只有省赛的1道题L是我的题,而且是简单题。

言归正传:

         这套题目质量挺高的,每个题除作者外,应该都至少有两个人验证过。全部的题我都验证过。很喜欢这套题。总体难度描述下,A可以秒杀掉,M基本上也算秒杀吧,FM差不多,F要查找,M要排序。BL是纸老虎题。此外,最简单的应该是D,直接模拟。以上都属于没有啥算法的题。再接下来就没有太简单了。非要分出来可能简单点的是C,就是考排序。然后,个人认为可能K简单点,矩阵乘法嘛,不过不同的人可能感觉不一样。然后可能就是I了,就是简单的计算几何。再然后J需要一个速度快的网络流,G是一个中档偏难的dpH是一个难的dpE是一个最难的计算几何,可以压轴了。如果好好做的话,5题应该没问题的(ABFLM)。

         题难度排序,同一括号里面的难度差不多。

(ABFLM)<(D)<(CKI)<(JG)<(H)<(E)

从题型上说,除去没算法的题,涉及了网络流、计算几何、动态规划、分治(二分)等算法。

题目分析:

A  Ordinal Numbers

         规则给定,给出整数,输出序数词。

         秒杀。看十位上的数字,无论x/10也好,还是写入到字符串看倒数第二位也好,反正十分简单,不多说。

B  Conic Section

描述了一大堆,就是给定二次曲线方程ax2+bxy+cy2+dx+ey+f=0,判断它是什么曲线。(圆、椭圆、双曲线、抛物线)。题目给定的b始终为0。所以说没有坐标轴旋转的事。纸老虎啊。

其实a=0或者c=0就是抛物线。

ac异号就是双曲线。

ac同号,相等是圆(其实圆也是椭圆……),不等是普通的椭圆。

C  Old Labels

         刚见到这个题时,我读得不太懂。事实上是这样的,给定一棵有根树。建立一个trie树。(每个节点有标号从0开始标,同一个节点的孩子标号不能相同)。这样从根到每个叶子都有一条路径,每个路径可以理解为一个字符串(或者说就是vector<int>),把这些字符串都排好序,形成一个字符串的有序集合。求一种标号方式,使得这个字符串集合的字典序最小。字符串集合的字典序定义为两个排好序的字符串集合中从小到大对每个字符串以字典序比大小,直到比出来为止。

         做法就是递归地做,假设以某节点的所有孩子为根的子树都已经标好了(这些子树的根没标号),那么这个节点连接孩子时应该怎么标号?显然,较“小”的孩子标号比较小,于是问题转变为对它所有孩子为根节点的子树排序。其实就是对树排序。一棵树其实就是一堆路径(字符串)的集合,即从它的根(虽然还没标号)到其全部叶子的那些路径,都由小到大排好序。但这时,比较两棵树不是用普通的字典序了,因为假设一棵树A包含了树B的全部的字符串,而AB包含的字符串更多,而A,B的根具有共同的父亲C,C应该给A的根更小的标号。也就是说,在没比出来的情况下,先结束的树(路径比较少的)应该排在后面。其实就是相当于给每棵树附加了一个字典序无穷大的串,再按字典序比较。然后就可以直接做了。

         最初我用vector<vector<int>  >保存了一棵树的全部路径。然后当它父亲给孩子标号的时候,在每条路径前面加一个标号,并把全部孩子的路径都存到父亲节点的vector<vector<int> >下。对孩子排序实际上就是对其存放的vector<vector<int> >排序,这样做是最直接暴力的,但验证时MLE了……其实在一个孩子的所有路径加上前面的那个标号并存入父亲的vector<vector<int> >的时候,这个孩子本身的那个vector<vector<int> >已经没用了,于是我在这时把孩子的那些vector都清空。结果是可以通过的,但是比较慢。

         后来我没有保存路径。假设现在要计算节点x, 节点x的孩子在二维数组con[x][]里面。则我现在需要对con[x][0]..con[x][d[x]-1]排序。(d[x]是节点x的度)。其实排序就用algorithm库里的sort函数即可。问题就是那个cmp函数怎么写。(就像每个问题最关键的gao()函数怎么写一样^_^ 这个cmp比较复杂,而且因为没保存路径,所以是递归的……其实也是相当的暴力。比较两棵树a,b那么我就沿着a递归地枚举a的所有路径(从根到叶子),然后a那边标号怎么走b那边沿同样沿着标号这样走。如果在走路的过程中,一方已经结束了(路径短),则路径短的那方小(这个就是字符串的字典序)。如果路径始终都一样,但是一方的路径多,则路径多的那一方小(前已叙述过)。

         如此我们就对x的所有孩子排好序了。然后顺着给每个孩子标号0..d[x]-1就可以了。最后,从根再遍历一次全树,记录下来所有路径就行了。路径条数等于树叶个数。

D  String Successor

         简单题,根据规则直接模拟。注意,进位。而且要是多1位的话,字母没关系就是A或者 a,而数字是1,而非0。(即9变为10,而不是变为00

E  Wall-nut Bowling

         我认为最难的题。Vls在这次出的3道题中,两道计算几何,一道dp。这题和另外那个dp都算得上难题了。题目背景很有趣,植物大战僵尸,但假设僵尸不动。用坚果打僵尸,撞到上下边界以45度角反射,撞到僵尸也会45度反射,僵尸可以看作点。因为题目规模很大,直接模拟反射来反射去的很麻烦。所以一个好办法是,把反射轨道上的点连起来。这样通过不断next,找到所有被击中的点。思路是如此的简单,但是做起来是如此的麻烦。

定义坐标系,就按题目说的吧x水平向右,y竖直向下,另外可以把坐标(x,y)都减小1,让它们从0开始。同时把n也减少1,这样y的范围是[0..n]。关键一点是轨道上的点,无论怎么反射在上边界(或者说下边界)的截距是对n*2 取模是相同的。这样可以用n*2的数组把“截距”相同的点都存好。

x从大到小处理。要使得某个点的下一个点恰好能知道。很麻烦,在上下边界的点y=0,y=nnext点是唯一的,所以它们比较好连。而普通的点,可能朝上,也可能朝下。我的做法是建立两个“假点”,一个在上边界,一个在下边界,当“碰到”上边界的“假点”时,实际上它的next应该是下边界对应的那个“假点”的next(因为根本碰不到上边界的假点,直接反到下边界去了),同理,“碰到”下边界的假点时,next值应该是上边界对应的八个假点的next。所有点都用双向链表连起来。代码太长了,就不全贴了。有兴趣的可以找我要代码,不过,还是建议自己写,很锻炼的……我只贴一下我建立链表的代码,这个也不短了。

                --a[i].first;

                            --a[i].second;

                            b[numb].prev=0;

                            b[numb].next=line[y=a[i].second];

                            b[numb].num=i-j;

                            b[numb].y=y;

                            if (line[y]) {

                                     line[y]->prev=&b[numb];

                            }

                            line[y]=&b[numb];

                            if (a[i].second==0) {

                                     uplist[numu].prev=uplist[numu].other=0;

                                     uplist[numu].next=list[x=a[i].first%M];

                                     uplist[numu].at=&b[numb];

                                     if (list[x]) {

                                               list[x]->prev=&uplist[numu];

                                     }

                                     b[numb].up=b[numb].down=list[x]=&uplist[numu];

                                     ++numu; 

                            }

                            else if (a[i].second==n) {

                                     downlist[numd].prev=downlist[numd].other=0;

                                     downlist[numd].next=list[x=(a[i].first+n)%M];  //截距

                                     downlist[numd].at=&b[numb];

                                     if (list[x]) {

                                               list[x]->prev=&downlist[numd];

                                     }

                                     b[numb].up=b[numb].down=list[x]=&downlist[numd];

                                     ++numd;

                            }

                            else {

                                     ux=a[i].first+a[i].second;   //上假点的截距

                                     dx=n-a[i].second+a[i].first;  //下假点的截距

                                     uplist[numu].prev=downlist[numd].prev=0;

                                     uplist[numu].next=list[x=(dx+n)%M];

                                     if (list[x]) {

                                               list[x]->prev=&uplist[numu];

                                     }

                                     downlist[numd].next=list[ux%=M];

                                     if (list[ux]) {

                                               list[ux]->prev=&downlist[numd];

                                     }

                                     b[numb].up=list[ux]=&uplist[numu];

                                     b[numb].down=list[x]=&downlist[numd];

                                     uplist[numu].other=&downlist[numd];

                                     downlist[numd].other=&uplist[numu];

                                     uplist[numu].at=downlist[numd].at=&b[numb];

                                     ++numu;

                                     ++numd;

                            }

                            ++numb;

         其中a[i].first,a[i].second就是(x,y)

bnode型数组,是真正存放僵尸的点。uplist,downlistsave型的数组,存放这个点开始往上或下弹到哪里,这两个数组里的点都是边界点,但是上下边界与list的名称无关。list是一个长度为2*n,存放截距模(2*n)后相同的点的指针数组, line是长度为(n+1)的指针数组,存放水平线的点,它们的类型分别为,node*,save*。类型定义如下:

struct node {

         node *prev,*next,*other; 

//other是专门给假点使用的,为删除一个假点时把对应的假点也删除

         save *at;    //存放真正在b数组的的哪里

};

 

struct save {

int y;

save *prev,*next;

int num;       //僵尸数目

node *up,*down;

};

list, uplist, downlist只是工具而已,是帮助b建立连接的,list的数组下标含义在上边界x=0的截距。M2*nline[y]记录的是水平线上的点,这样坚果碰到通过line数组找到第一个打到的点,然后根据up,down找到弹到的点,再不断next,就完成了一条轨道。要达到的就是这样的效果——通过next可以方便找到轨道上下一个点。

然后就是每次把num0的节点删除,这个相对简单点,就是双向链表删除元素。但要注意删除“假点”时,要删除两个(上下边界相对应的假点),而且要把next指向的那两个链表对调(othernext接到this后面, this->next接到other 后面),还有line数组里也要删,总之同时维护若干个链表真麻烦!

F  Kagome Kagome

         也可以秒杀掉。直接查找某个名字的位置x,输出(x+n/2)%n位置的名字即可。

G  Palm Up and Palm Down

         又一道比较麻烦的dp题。题目意思比较有趣,手心手背,在我们那个年代叫做“黑白黑”……召唤80后的回忆。然后少部分的人留下,要是一样多的话,谁也不能走,再继续,直到剩下两个人,他们玩石头、剪子、布,输得那个人悲剧。现在给定每个人出“黑 白”还有石头、剪子、布的比率,求游戏期望进行多少轮,以及最后剩的那一个悲剧的人最可能是哪些人,以及他悲剧的概率。

         显然的2n表示状态。对一个状态x来讲,我们用num[x]表示x的二进制表示中1的个数,用allblack[x]表示这些人全部出黑的概率,类似定义allwhite[x],这两个东西可以打表算出。e[x]表示轮数期望。

如果num[x]<=1 e[x]=0

如果num[x]=2,只剩两个人,则期望是一个人赢另外一个人概率的倒数。这个就根据石头、剪子、布的概率很容易算出来……

num[x]>2

A=sigma(allwhite[i]*allblack[j])*e[x] 其中i|j=x, i&j=0 ,num[i]=num[j] 即把x中的为1bit分为个数相同的两部分,显然只有num[x]为偶数时才做得到,否则A0.

   B=sigma(allwhite[i]*allblack[j])*e[(num[i]<num[j])?i:j] 其中i|j=x ,i&j=0,num[i]!=num[j]即把x中的位1bit分为个数不同的两部分。

则有e[x]=A+B+1

其实看一下e[x]-A,的系数恰好是B中的系数和。(也就是说AB的那些系数和为1),所以e[x]-A=bitsigma(allwhite[i]*allblack[j])*e[x]=t*e[x]  其中i|j=x i&j=0 num[i]!=num[j] (其中tB中的系数和)

所以我们对于x,枚举i,然后j=x^i,这样有了ij,就可以累加出B,并顺便算出其系数和t,然后(B+1)/t即可以得到e[x]

         我们是由小到大循环x的,所以再计算e[x]时,e[i],e[j]都已经计算好了。只是要注意无穷大的处理。无穷大一种是t0,一种是有些期望是无穷大,并且系数非0

         类似的,我们可以计算出每个状态出现的概率。设为p     

         p[2n]=1, 我们可以逆推。对于p[x],会影响小于x的状态,而那些状态恰好是上面计算的ij

         同样,如果num[x]=2概率要自己算出剩下悲剧那个人的概率,并且累加到num[i]=1的状态上。

         num[x]>2时,同样把x中位1bit分成两部分。类似上面描述,只不过是逆推,对所有i|j=x i&j=0 num[i]!=num[j]的状态,要在p[(num[i]<num[j])?i:j]上累加上allblack[i]*allwhtie[j]/tot[x]*p[x]

其中tot[x]是在前面算x状态的轮数期望时计算的那个t值。(可以保存起来)。

         这样我们在用一个“大”的状态x,更新了它所有影响的“小”的状态。

         最后num[]=1n个状态为所求,找到概率最大的人就好了。

         顺便说一下对每个x,如何枚举状态i,直接循环从0x的话,复杂度会很高,成了22n,事实上很多状态i是没用的,因为要保证i中的位1bitx的真子集。所以可以for (i=(x-1)&x;i;i=(i-1)&x), 这样可以保证真子集的条件。而复杂度跟x1的个数有关。总体复杂度是 sigma(c(y,n)*2y) y0n,这个正好是3=(1+2)n次方的2项展开式。所以总体复杂度是3n,对于n=13来讲413313大很多。

H  BCD Code

就是要求区间[A,B]之间,把组成一个数的全部数字都用四位二进制数表示出来(含首0),问不出现某些固定0-1模式的数有多少个。比较难的题,可以建立经典的AC自动机。当然本题的特殊性是模式串长不超过20,而且都是01,所以也可以不用AC自动机。需要表示的是现在产生的串的后缀是哪个模式的最长前缀。也就是一个(x,y)表示现在产生的串的后缀(前面那些位都没用)是第x个模式串的前y位。而且要求y尽可能大,如果y值相同的时候,位保证唯一性,可以取比较小的x。然后初始是空串,可以认为是第0个模式串的前0位。从(0,0)开始进行bfs,对当前串末尾分别加0、加1,看看能否转到其他状态,对于转换到的状态的判断就是枚举,然后判断,因为全是0,1,而且不超过20位,所以可以用位运算直接取出一个模式的连续某些bit。这样到最后产生了一个状态之间的转换图。(从某个状态经过0到哪里,经过1到哪里),状态总个数不超过21×100=2100个。这是偷懒的做法。其实这样写的代码也未必短多少。正规的做法,还是先建立trie,然后算fail指针,建立起AC自动机。

但最后都是建立状态转换图,从当前状态经过0跳到哪里,经过1跳到哪里。只不过不用自动机的话是直接枚举出状态转换,而又利用了题目本身的性质,可以使用位运算。而用AC自动机则是通过fail指针计算的。

然后就是动态规划了。一种直接的思路是计算所有小于x的合法数的个数f(x),结果是f(B)-f(A-1)。那么可以定义动态规划的状态,dp[n][state][cmp], 第一维表示当前产生的数的十进制的位数,第2个表示当前的状态,对应于状态图的节点,第三个是当前产生的数与x的前n十进制位组成的串的字典序的大小(有三种情况,大于,小于,等于)。然后状态转换也不复杂。循环n,从n开始枚举一位数字(注意不能有首0),然后从state利用状态图看看是否合法,计算出新的state’。(一个数字对应42进制数,把state添加一个数字对应了状态机的4步状态转换,把这个打表存起来是一个提速的办法,即存一个[state][10]的数组,记录下state经过一个数字最终转换到的新的state),再根据以前的cmp和新加的这位数字计算出新的cmp’,然后累加上来,即dp[n+1][state’][cmp’]+=dp[n][state][cmp]

最后注意,当n小于x的十进制位数时,无论cmp位什么结果,都要累加进最终结果。而当n刚好等于x的十进制位数时,这时第三维的字典序就是实际数和x大小顺序,所以只能把字典序不大于x的那些结果累加进来,这也是状态表示中第三维存在的意义。

还有一个稍微麻烦一点但是更快一点的办法就是多加一维数组表示状态,把状态改为dp[n][state][cmpa][cmpb],最后两维记录当前产生的n位数与A的前n位的字典序关系,以及与B的前n位字典序之间的关系。也是同样的办法计算、累加。这样做状态转换麻烦点,但是只dp一次就可以累加出最后结果,所以比前一种dp快一点。而之前的方法需要dp两次求差值。

关于AC自动机,网上有很多资料,讲得很详细,其实就是个trie树加上fail指针。就是KMP算法在多串上的推广。关于AC自动机,我又在zoj上找了两个题:

Zoj 3430可以用这个解决,当然直接暴力也是可以过的……

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3430

还有一个难一点的题 zoj3190

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3190

感兴趣的可以试试看。

I   Lego Bricks

         给定一些圆盘和线段,问能否使线段都稳定。Vls的计算几何题向来是很难的,关键看对于稳定的理解……把线段从中间截断成两段。那么看每条小线段是否稳定。小线段稳定如果:(1 它和一条已经稳定的线段有公共点。 或者(2 它和某一个圆盘有公共点。(圆盘的意思是圆形的区域而不仅仅是边界)。 如果两条小线段都满足稳定条件,整条线段是稳定的。就这么不断地扩散,稳定线段不断增多,如果能否使得所有线段都稳定。复杂度O(n2)

J  Assignment

         很有趣的题。就是网络流。边容量给定,网络容量给定,有两个人A,B, A先给定一个最大流,并且保证每条边流量必须为整数,B给每条边设定单位流量的费用,所有边的单位流量总费用之和不超过一个阈值p。边过了流量就要支付单价乘以流量那么多的费用(1 如果A希望总费用尽可能低,而B希望总费用尽可能高,则最后总费用是多少。(2)反过来A希望总费用尽可能高,而B希望总费用尽可能低,那么最后总费用又是多少。

         对于(1)B只要把P全部分给流量最大的边即可让总费用最大。所以A的目的是让这个最大流里流量最大的边的流量尽可能小。所以我们可以二分,如果二分到一个值x,刚好使得所有边的容量上界定为x时(当然还要满足自身容量),最大流减小了。则(x+1)就是流量最大边的最小可能流量值了。所以结果是(x+1)*p

         对于(2),B只要把P全部分给流量最小的边即可让总费用最小。所以A的目的是让这个最大流里面流量最小的边的流量尽可能大。同样的二分,如果二分一个值y,刚好使得所有边的容量下界定为y时,最大流减小。则(y-1)就是流量最小的边的最大可能流量值了。所以结果就是(y-1)*p

         注意(2)是一个有上下界的最大流问题。而且由于时间限制,本题需要一个比较快速的网络流。另外,最后结果是乘积形式,可能超过了int,所以要使用long long

K  Mistwald

         题目意思是给定一个有向图(最多25个节点,每个节点的出度最多为4),给定起点和终点,然后从起点开始走,走到终点就停止,否则一直往下走,问能不能P步到达终点。也就是说从起点出发,走一条长度为P的路径,路径中间点不能经过终点(但可以反复经过其他点)。如果从起点出发P步后,不能到达终点,就是False,如果可以到达终点也可以到其他别的点,就是Maybe,如果P步后只能到达终点(到别的点没有长度为P的路径),则是Yes

         显然的矩阵乘法。图的临接矩阵A p次方Ap中为1的元素(i,j)表示节点i到节点j有一条长度为p的路径(经历的节点可能重复)。要理解矩阵的含义,两个矩阵相乘如果(x,y)元素为1,而(y,z)元素为1,则结果(x,z)元素为1,这表明通过yxz连起来了。而题目要求经过终点就不能走了,所以在做矩阵乘法时,需要把(x,n-1 (n-1,y)这样决定的(x,y)去掉。(n-1表示终点)。做乘法时,中间点小心一点就好了。矩阵乘法和floyd在本质上是一样的……

         矩阵的P次方运用的是经典的log(P)的算法。最后看一下结果矩阵的首行(0行)里面有几个1,以及(0,n-1)是不是1,来决定结果。

         一般矩阵的乘法要n3的复杂度。这个矩阵规模很小,n只有25,而且矩阵元素是0或者1,所以我们可以把每行用一个整数表示,每列也用一个整数表示,元素值按bit压缩至int里。实际上就是用两个数组,一个表示行向量r,一个表示列向量c,然后在做乘法时可以用位运算,r[i]&c[j]来决定结果矩阵(i,j)位置是0还是1,当然结果矩阵也要同时保存行向量和列向量,另外还是要去掉中间点为终点的转换。这样复杂度就只有n2了。

L  Javabeans

纸老虎题,有n个盒子,第i个盒子里有i个东西,每次选取一些盒子,然后从这些盒子中每个都取出相同数目的东西。问至少几次可以把盒子清空?

         把每个盒子看成集合。有n个集合,分别有1…n个元素。具体每种集合有多少个是没意义的,因为我们可以把具有相同元素的集合同时操作,所以我们可以用集合的种类代替集合的个数。假设,每次选取k个集合。从这k个集合里拿东西,则这k个集合拿过之后还是k个不同的集合(有可能有一个成空集),所以至少还有(k-1)个不同的集合,而除这k个外还有(n-k)个不同的集合。所以拿完之后不同集合的个数至少变为了r=max(k-1,n-k)。考虑当n是偶数时当k=n/2时,r取最小值,max(k-1,n-k)=n/2,当n为奇数时,k=(n+1)/2,r取最小值max(k-1,n-k)=(n-1)/2。这个最小值是剩余集合数的一个下界。

其实这个下界是可以达到的:

n是偶数时,从元素个数不少于n/2的全部集合里都拿n/2个,则,剩余集合元素个数变为了1,2……n/2,问题规模缩小了一半。

n是奇数时,从元素个数不少于(n+1)/2的集合里都拿(n+1)/2个,则剩余集合元素个数变为了1,2,…(n-1)/2,问题规模也缩小了一半。

而在c语言中,除以2是下取整的,所以无论n为奇数还是偶数,一次操作之后集合个数至少变成了n/2,并且有办法可以达到这个最小值。

于是,最少拿的次数就是每次把n不断除以2,除到0为止。即n2进制表示中的bit数。

 Median

秒杀吧。排序一下,取中间的1个或两个的平均值。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:蟒山游记
后一篇:放风筝
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇蟒山游记
    后一篇 >放风筝
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有