8da编程无高手

[复制链接]

lvan

912 主题	3 好友	2万积分

大和

发消息

电梯直达

1楼

发表于 2011-9-28 19:17 |只看该作者 |正序浏览

SRM 500
20

三月
万众瞩目的SRM 500如期到来，可以说整场比赛还是比较圆满的，没有出什么问题，题目也还算好。

注册的时候询问了是否要把奖金捐献给rem，于是我成功捐献了不知道多少钱……注册阶段非常疯狂，不到2个小时2100个坑就被注册满了，众多神牛只能因此无奈围观，不过Petr、ACRush和tourist等大神都如约而至。

比赛总的来说较难，250题目很长，属于乱搞题；500是个分形、几何题，sample比较弱，容易fail；1000是个暴力枚举计数题。最终Petr连过三题强势夺冠，尽显王者风范。250我折腾了一会儿折腾出来了，500想到了正确的做法可惜在很小的地方写出了一个bug最终FST了，1000没想到暴力的做法。

以下是简单的解题报告：

1. 250P MafiaGame
2<=N<=500个人进行投票选举，其中有M<=50个人有明确的投票对象。每一轮投票有一个候选人集合（初始为所有的N个人），首先，所有人中有明确投票对象且对象在候选人集合中的先投票；接着，还没投票的人随机等概率投票给当前票数最少的人。每一轮结束后，如果票数最多的只有一个人，则投票结束，此人胜出，否则所有票数最多的人作为候选人集合，进入下一轮新的投票。问胜出概率最高的人胜出概率是多少，或者投票活动会无限循环下去。

首先我们考虑第一轮投票的结果，有两种情况。如果M个明确对象中有重复元素，则至少有人得到两票或者以上，当M个明确投票对象投完后，剩下N-M票会分布在至少N-M+1个人中，这些人只能得到最多一票，于是后面的这些票都是没用的，因此，在这种情况下，M个明确对象中得票数最多的那些进入下一轮。第二种情况，M个明确投票没有重复元素，则最后的投票结果会是人手一票，投票过程无限循环。

前一种情况下，假设有A个元素进入第二轮，我们可以发现这A个元素互相之间是完全等价的，因此，如果投票过程不会无限循环的话，每个获胜的概率都应该是1/A。所以我们的任务就是判断之后的投票过程是否会无限循环，在忽略的不同对象之间的差异后，剩下的其实就是个模拟的过程，A个候选对象每个获得B票，剩下的N-A*B票分布在A个对象中，如果A|N-A*B，则这轮过去后候选人集合不变，过程循环；否则，(N-A*B)%A个人成为新的候选人集合，当A变成1时选举结束。

2. 500P FractalPicture
考虑一个分形图案，第一代时，图案是一条(0,0)点到(0,81)点的虚线，其中(0,0)点为虚线的根点。从第i代到第i+1代时，每条虚线作如下变换：假设端点为a和b，其中a是根点，则取线段ab上的点c，满足ac=2ab，之后生成两个新的线段cd和ce，其中cd为cb绕着c点顺时针旋转90度，ce为cb绕着c点逆时针旋转90度，这时ac变成实线，cb,cd,ce为虚线，根点都为c。现在给一个平行于坐标轴且四个顶点坐标都为整数的矩形，问第500代分形图像中，位于矩形边上或者内部的线段总长度为多少。

这题主要的突破点是考虑到矩形的坐标为整数点，而分形图像没递归一层变的长度就缩短1/3，到第五层后，整个分形过程都只在单元方格中进行了，可以统一计算而不用递归到第500层。对于一条分形到第五层的长度为1的虚线，如果线在矩形内部，则这个虚线之后衍生出来的所有线段都在矩形内部；如果线在举行边上，则衍生出来的线段有一半在矩形内部。一条长度为1的虚线，递归一层后变成长度为2/3的实线+总长度为1的虚线，即每递归一层总长度增加2/3，所以，长度为1的虚线递归到第500层后的总长度为1+2/3*495=331，如果是一半的话，则为166（包括中间长度为1的一段）。

3. 1000P ProductAndSum
求所有各位数字和为S，各位数字积为2^a*3^b*5^c*7^d的数的总和%500500573，其中S<=2500，a b c d<=100。

首先意识到数中各个数字的排列对题目是没有影响的，所以我们主要要求的就是每个数字出现的个数，以及知道每个数字的个数后求这些数字所有排列的和。其实求每个数字的个数我们可以用很暴力的枚举方式，首先5和7的个数是确定的，因为没有其他数字可以提供5和7这两个因子。之后我们可以枚举9 8 6 4的个数，这样1 2 3的个数也能唯一的确定下来了。整个枚举量最大只有50*33*100*50，实际上会远小于这个量。

现在我们知道每个数字出现的次数，求这些数字全排列形成的数的和。我们发现其实每一位的情况都是一样的，只是权重不同，所以我们只要求个位的和，乘以11…111（有多少位就乘多少个1）即可。这个求解就比较简单了，只要枚举这位放哪个数字，剩下位的放法可以用排列组合公式求得。

-----------------------------------------------------------------------------------------------------------------------
基本上去的都是零蛋收场吧

lost-star 该用户已被删除	20楼发表于 2011-9-28 23:06 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽
lost-star 该用户已被删除
	回复使用道具举报显身卡

帐号		自动登录	找回密码
密码			注册

8da编程无高手

2011年度八达十大水友

2013年夜饭