模拟DAY4

模拟DAY4

题目:冲刺Noip2016模拟赛4
密码:monisai4

T1题解:
纯粹数学题!
首先,我们会发现,对于每个点,都有作为式子中减数和被减数的机会。
但是,对于终点来说,它只能作为被减数,不能作为减数,而其他点均可。
那么我们知道总次数是n!,而一个点作为终点的概率是1/n,也就是说他作为被减数的次数是(n-1)!,那么不是终点的概率就是n!-(n-1)!
然后我们再对式子进行一定的展开:
对于|a-b|,显然有两种展开,a-b和b-a,然后对这里的这个式子进行分类讨论。
对于一个排好序的序列中的一个点,他到所有他前面的点的距离绝对值展开,它是不用变号的,同理对于他后面的点是要变号的,也就是说对于第i个点,他的dis有i个是正的,n-i个是负的。
然后再将得到的这个规律放到刚刚的式子中,即为:
减数:(n!-(n-1)!)(ia[i]+(n-i)(-a[i]))
被减数:(n-1)!
(i(-a[i])+(n-i)a[i])
所以加起来合并后得到式子:
ans=sigma(i=1,i<=n)(a[i](4i-2*n-1))/n
所以计算出sigma后,求与n的gcd然后输出即可
//完全考验数学啊!!吐槽!!

AC代码:

T2题解:
听说正常人的想法都是:
由3个类比两个,对于每一个元素枚举第三个后去找他之前是否有两个元素的和满足这个条件。
也就是说,维护一个数据结构,里面存有到目前为止,我之前有的两个元素的和有哪些。
所以,出题人想到了hash表,并且是链表的hash表。
为什么呢?
因为hash表查找判断的复杂度很低,而且通过每一个hash值下面连一个链表会使值都是精确的,不会出现误差,所以其实这是一个很好的数据结构(不,他不是一个数据结构)
//顺便说一下这个模数……按照标称来看,我们能用的模数只有三个,不然不是TLE就是MLE,真滴坑……

AC代码:

T3题解:
当我们无尽的把问题想的简单化的时候,问题就真的简单了……?
对于这道题来说,乍一看,分类讨论 n和m的位置有很多种,那么怎么办啊!
事实上,如果全面的来看,所有的情况下,我们的棋盘都可以被分为三个部分
<图待补>
那么我们就可以在每一部分内分别处理前i行放了j个城堡的方案数,也就是一个很简单的dp
再通过将这三块的合并:
dp[h][i][j][k]表示到第h行,第1块i个城堡,第2块j个城堡,第3块k个城堡
然后再压缩掉一维空间即可……

说着容易?
明明代码实现很简单的题,怎么可能这么出给你?!
所以啊,记得看数据范围,要写高进度啊!!!
要写好多好多高精度啊!
慢慢写,加油哈!

AC代码:

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注