八达网

标题: 8da编程无高手 [打印本页]

作者: lvan 时间: 2011-9-28 19:17
标题: 8da编程无高手
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）即可。这个求解就比较简单了，只要枚举这位放哪个数字，剩下位的放法可以用排列组合公式求得。

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

作者: Serioc 时间: 2011-9-28 19:17
屁眼在哪里？

作者: 灰灰 时间: 2011-9-28 19:20
插哪里？

作者: lvan 时间: 2011-9-28 19:24

作者: [CUGL].eyeS` 时间: 2011-9-28 19:28
楼主难道是o老师的马甲？

作者: 斯文败类 时间: 2011-9-28 19:32
提示: 作者被禁止或删除内容自动屏蔽

作者: liuchangnet 时间: 2011-9-28 19:33

lvan 发表于 2011-9-28 19:24

ivan是黑手党，ivan是黑手党史上唯一能一边做爱一边脸贴屁股的人
ivan的JJ是分形的，分形图像画出来就是ivan的JJ

作者: bglps 时间: 2011-9-28 19:55

作者: 小包猫小包猫bm 时间: 2011-9-28 19:56

作者: 风剑 时间: 2011-9-28 20:04
O老师发帖忘记换ID了

作者: T_forever_T 时间: 2011-9-28 20:06
O老师发帖忘记换ID了

作者: podmilk1104 时间: 2011-9-28 20:09

O老师发帖忘记换ID了

作者: suiyue 时间: 2011-9-28 21:01
O老师发帖忘记换ID了

作者: 格老子的 时间: 2011-9-28 21:06
O老师发帖忘记换ID了

作者: 田田蓝心 时间: 2011-9-28 21:11
O老师发帖忘记换ID了

作者: baiyayeya 时间: 2011-9-28 21:20
O老师发帖忘记换ID了

作者: jjy 时间: 2011-9-28 22:58
O老师发帖忘记换ID了

作者: 迦摩天 时间: 2011-9-28 23:04
O老师发帖忘记换ID了

作者: ugg 时间: 2011-9-28 23:05
O老师发帖忘记换ID了

作者: lost-star 时间: 2011-9-28 23:06
提示: 作者被禁止或删除内容自动屏蔽

作者: 迦摩天 时间: 2011-9-28 23:09
O老师发帖忘记换ID了

作者: CHEN___G 时间: 2011-9-28 23:13
这还是我的兄弟一万马？？

作者: LOY 时间: 2011-9-28 23:16
楼主，这个是你？
http://community.topcoder.com/tc ... ofile&cr=273450

作者: 猎鹰赌场 时间: 2011-9-28 23:18
O老师发帖忘记换ID了

作者: Damocles 时间: 2011-9-29 02:58
O老师发帖忘记换ID了

作者: hpPlayer 时间: 2011-9-29 03:11
屁眼在哪里？

作者: stonyfield 时间: 2011-9-29 08:39
本帖最后由 stonyfield 于 2011-9-29 08:39 编辑

作者: 菊菊思密达 时间: 2011-9-29 08:41
O老师发帖忘记换ID了

作者: ghostfirst 时间: 2011-9-29 08:56
O老师发帖忘记换ID了

作者: PalmCivet 时间: 2011-9-29 09:10
O老师发帖忘记换ID了

作者: anomaly 时间: 2011-9-29 09:12
只有家里蹲的编程高手才闲的蛋疼在网上做题

作者: MosaiC 时间: 2011-9-29 09:18
O老师发帖忘记换ID了

作者: W_M_W 时间: 2011-9-29 09:21
O老师发帖忘记换ID了

作者: atom 时间: 2011-9-29 09:59

O老师发帖忘记换ID了

作者: funeral112 时间: 2014-12-10 10:07

作者: 我不是大米 时间: 2014-12-10 10:14
原来伊万竟是O老师

欢迎光临八达网 (https://www.8-da.com/)