leeco做两个.hjin也过了一个
先说一下基础的三个吧.
扇形面积:原来题目是:http://acm.jlu.edu.cn/joj/showproblem.php?pid=2437
原题:背景是圈地运动.告诉你你的马一天能走的距离.然后你早上出发走到晚上停止.那么你圈的地就是你的出发点到结束点这条直线和你跑出来的路线所围成的面积..
本来应该算的是一个弓形.结果那天弄了半天样例都没有过.结果才发祥题目出了问题.他算的是扇形面积.所以过了这个题目的可以把自己的程序改一下精度直接去那上面提交...
已知弦长和弧长可以列出这样的方程sin(k)-2*x*k/l=0(k是弧度所对应的半角度).如果是个优弧的话方程要变一下.
这个方程是没有公式的.但是只要你用笔话一下可以发现 y=sin(k),和y=2*x*k/l是只有一个交点的.所以就满足了二分的要求.当然你还可以发现y=sin(k)/(2*x*k/l)是单调的.所以你也可以用更快的牛顿切线或者迭代.
世界杯:http://acm.tju.edu.cn/toj/showp2865.html
大家看一下题目就发现那个输出太恶了.所以就把字符串给去掉了.这个题目大家过不去可能是忘记了高中数学里的概率的和积关系了.
比如第一个队伍得冠的应该是这么算的:当第1对进入决赛.那他面对的应该是8--16.那么:
P=p8*A[1,8]/100+p9*A[1,9]/100.0+....+; pi代表的是第i队进入决赛的概率..依次类推到进入前4强和前8强.
逆序数:(太失败了.提供的程序出了点问题..向大家道歉)
大家可以把程序直接到这里去提交: http://acm.pku.edu.cn/JudgeOnline/problem?id=2085
一定要发现一个重要的规律.其实在描述里就已经给了.那就是n个数字的全排列最大的逆序数是n*(n-1)/2
那么怎么样保证给你一个逆序数你输出最小的全排列呢? 很明显要全排列最小也就是第一个数字小.第一个数字小当然就是后面的逆序数大.
假设你排到第k个
当m>k*(k-1)/2 输出第m-k*(k-1)/2大的数.然后把没有输出的从大到小输出就可以了
当m<k*(k-1)/2 输出最小的就可以了.接下来继续试探第k+1个数字
当m=k*(k-1)/2 从大到小输出所有的
所以整体上应该是个O(n)
提高题目:
做的最好的毫无疑问的是ACking.第二个题目经过他的提示catlan数算是明白.第一个题目他是过了..我还是没过..
这两个题目就不说了...大家继续讨论..
[此贴子已经被作者于2007-9-16 13:27:29编辑过]