flash Little Wheel
Little Wheel
一个很赞的flash小游戏…
画面很简单…却能表现出奇妙的效果…难以语言形容…
作为游戏来说难度很低…与其说是游戏…不如说是看故事一样…
轮子机器人国度的故事
pe vol14 66~70
Project Euler
Problem 66 : C++,Python
Problem 67 : C++
Problem 68 : pencil & paper
Problem 69 : C++
Problem 70 : C++
下面是详细内容:
pku 3028 Shoot-out
3028 Shoot-out
一群牛仔,依次射击,每人有固定命中率
轮到某人射击时他会选一个人去射,要使如果命中的话,自己有最大的胜利几率,如果有多个满足条件的,就随机选择
每个人都知道别人的命中率以及策略,并且不能故意不打中
求每人的胜利几率(最后活下来的)
人数<=13
一个状态压缩dp,优化再优化
一开始我以为只要选择命中率最高的人去射就行了,找到了数据后才发现我原来想错了…
其实是每人准备射击时,会先计算一下如果命中某个人,自己的存活概率是多少,选择最大的那个作为目标,当然如果有相同的就在此之中随机选择
这样一来,寻找目标时还要计算一次存活率…这样复杂度就上去了…
看了标程的方法后,自己写了一个…
dp[state][shooter][i]=在活下来的人为state时,轮到shooter射击,第i人存活可能性
先计算shooter的目标,就是找到使得 { dp[state^j][(shooter+1)%n][shooter] , j在state中 } 最大的i
然后计算在一圈内的存活概率:
sum{ dp[state^j][(shooter_now+1)%n][i] / target_count * accuracy[shooter_now] * multiply{ 1-accuracy[k] , k在shooter_now之前的人 } , j是shooter_now的目标 , shooter_now从shooter到一圈结束 }
至于会有环,则是在这个一圈的基础上除以(1-所有人都没有命中的概率),这个结果就是dp[state][shooter][i]
直接这样做的话还是会超时
于是在计算dp[state][shooter][i]的时候顺便把其他shooter的情况一起填了
这样才终于过了
下面是代码:
16860K,2000MS,1865B
contest dhu The 34th ACM/ICPC Asia Regional Shanghai online contest
今天的上海赛区网络赛…
网络赛也差不多都比过了…还剩个武汉的…
今天的排名约是昨天的十倍… rank 69 …
一共出了5题,总数10题…
果然不行了呢…
话说东华的题目很奇妙呢…之前的邀请赛也是…这次的网络赛也是…每道题都有种想让人去做做看的冲动…
可是似乎很容易想出错误的或者不太好的算法去做…然后就会吃掉很多时间…
是错觉么…
简述:(?)
A: 修门?没看题
B: 烧饼,计算几何,用昨天的模板就很容易搞定了,多边形旋转换成锅子绕多边形转比较容易处理
C: card captor sakura …汗…比赛时似乎用什么最小树形图弄的…后来才知道其实只要拓扑排序然后拆环就行了…
D: 流水线…在指定费用下的最大收益,规模奇妙,没想出来
E: 日食,三维计算几何,转化到二维后可以做,我当时居然去判断点是否在各圆锥体内…后来发现似乎计算点到太阳和月球的切线之间的位置关系就行,可惜时间不够了
F: 2^n第一位数字的统计,我们用log来做的…有人直接高精度就过了…
G: 黑白,操作增边删边改颜色和查询路径上黑白个数,没想出来
H: 药物互相作用,微妙的dp,一开始想了个dp[state]=value[state]+dp[state^first1]+dp[state^second1]-dp[state^first1^second1],可是后来才发现不对…还用暴力做过TLE,最后在上述基础上再加了个sum{value[i],i是state的子集且包括first1和second1}就过了
I: 没看题
J: 交通拥堵,简单模拟
微妙啊…似乎做的都是很多人过的…很多人过的有没做出来的…
于是没有详述了…
似乎有人需要B题的代码,所以下面是B题的详述和代码:
contest dhu The 34th ACM/ICPC Asia Regional Shanghai warmup
今天的上海赛区的热身赛
不过…东华似乎没有普通的oj?
只有去下载客户端,然后比赛时才能用…
排名在这里
一共8题…简单题比较多…
我们队全出了…很神奇…最终排名 rank 7
今天中午过去的时候…似乎没有比赛的样子…感觉被耍了
可是…大约12:20的时候…得知原来是有热身赛的…然后赶快登陆…
下载题目非常的卡…题目密码居然是…[上帝说:要有光,于是便有了光]…
然后终于开始看题…
先找了题短的看…G题…很简单的模拟伪随机数生成函数并统计数量…敲了,然后过了
接着A题很多人过…answeror说了下题意,然后说,因为每场的奖金是2^n,所以概率只要看最后一场就行了
原来如此…恩…然后敲了过了
接着又说B题大水…输入n个变量和值,判断一个不等式或等式是否成立,左边是变量的加法,右边是数字
题意很明了,感觉也的确很水…但是写起来才发现…字符串处理还是有点烦的…用了map节省了很多代码…
然后CE了一次…本地里面有strcmp的说…于是加了个的头文件,然后过了
接着又说D题大水…一个kruskal求最小生成树的题…写了然后过了…
然后似乎没有大水题了…剩下的题目看起来…
answeror说H题可以做…10000个点,100个旅馆,开车不能连续开10小时的路程,问最少去旅馆睡几次到达目的地
先对原图的每个旅馆和起点来一次dijkstra+heap求10小时内能到哪些旅馆或目的地
然后建一张旅馆间旅馆间能否到达的新图,边权都是1,这个就只有100点了,再来一次起点到目的地的dijkstra,然后就可以了
一开始answeror说还要弄什么网络流…果然交流是很重要的…
这个让answeror来写了…wa了两次…
然后我看F题也许可以乱搞…于是开写…
题目是说一群人吃饭,要定饭碗大小,每个人都有饭量值,吃不完的就浪费掉了,吃不饱的话就要再盛饭
每次盛饭必须盛满,盛饭次数不超过3次,评价指标是a*浪费饭的总量+b*总盛饭次数,要求使得这个指标最小
饭碗可以是分数容量
于是猜测分母是不是只可能是1,2,3,然后照这个思路枚举了下所有情况取最小值,然后就过了
这时answeror的H题也找到问题所在了,改了下,然后过了
E题过的人也不少,题意是一种编码方式,把数字写成二进制数,长度是k,加密后就是k-1个0加上一个1加上这个二进制数自身
这个加密后的东西前半段就是表示后半段有多少长度的意思
然后有两种优化,一个是如果长度为k的数不存在的话,就可以用它表示后半段有k+1的长度,如果长度k+1的也没有,继续往后延
另一个是可以给一些数字添加前置0,使得这些数长度增加,于是某个长度的数就会没有,就可以应用第一个优化来减少总长度
给定各种位数的数有多少个,问最少总长度是多少
过的人不少,感觉不是难题,想到dp,然后做了,用dp[i]表示长度从i到n这些数最少总长度,然后就能做了…然后过了…
最后还剩C题…认为是大自然题…但是有人过了…
题意是给定一个三角形和一个圆,求相交面积最大值
既然还有点时间…我就开写了…先贴上了三角形和圆的交的模板…
似乎我这个模板只用过1~2次…而各种函数我又是分开放的…
所以当我重复了N次{贴模板,编译,报告某函数不存在}的操作之后,才终于贴完这个模板…满满2屏…真的是密密麻麻的满满的…
然后就开始正文了…先根据三角形三边,随便定个坐标,一个在原点,一个在x轴,另一个计算一下
先判断圆半径小于内切圆半径就返回圆面积,大于外接圆半径就返回三角形面积
然后把圆放在原点,每次往上下左右四个方向都偏移微小量dt,如果哪个方向值更高就移过去,找极值…
数学老师打过一个比方:盲人爬山,每次只能知道四周是否有高的地方,有的话就往那边走,这样总能达到一个山峰(极值),但不一定是最高的那座
可是这题似乎找到的那个就是最高的那个…居然很顺利的AC了…
至此所有题目都解决了
今天不会用掉了明天的rp吧…
简述:
A: 彩票,最大公约数
B: 判不等式,map
C: 三角形和圆最大相交面积,计算几何,找极值
D: kruskal最小生成树
E: 加密,dp
F: 盛饭,枚举
G: 伪随机数,模拟
H: 开车,dijkstra+heap建图,然后再dijkstra一次
下面是CEF的代码,详述见上文:
pe Problem 66
Project Euler 第66题
Investigate the Diophantine equation x2 − Dy2 = 1.
给定D,求最小x满足 二次Diophantine 方程x^2-D*y^2=1
其中x,y,D都是正整数
问D<=1000中最小x最大的那个D
下面是我的解题过程:
RSS订阅