UOJ Logo Sky_miner的博客

博客

求助各位dalao

2017-01-07 19:11:58 By Sky_miner

遇到了一个问题,向各位dalao求助.

给定一个长为n的序列(数字大小两两不同),老师想把这个序列排序。
他会掷一枚均匀硬币.如果正面朝上,他就会选择一对满足左边的数比右边大的相邻元素进行交换,否则选中一对满足左边的数比右边小的相邻元素进行交换.
如果无法进行交换,他就再扔一次硬币.如果序列按递增顺序排好序,那么操作结束.问期望的操作次数
(n <= 3000)

这道题我写出了一个算法,但是发现算出来的所有的答案都是整数。 是不是这个题的性质就决定了答案一定是整数?

本苣表示不理解,希望各位dalao能够解答一下。 感激不尽。。。

新博客

2017-01-04 07:26:42 By Sky_miner

我不知道谁给我发的博客。。。

反正我们全机房共用一个IP..

NOIP2016 游记

2016-12-11 16:36:49 By Sky_miner

Day 0:

联赛前一天,收拾行装准备出发了!
大家都激动了,那个早上闹的可欢了,拿着胶带扔来扔去。
   一堆一堆没吃完的苹果和蜂蜜都分了下来,都装不下了。。
但是闹的这么欢的时候居然还有人躲了起来,一副(你们这群愚蠢的人类)的样子
藏到了南楼梯口上,不过还是被我发现了(你们火星人也聪明不到哪去)
临走的时候叫上了(ZS),然后我们抱着(衡水老白干?)出发了!

大巴车,高铁上,一切都很浪。
还见到了高一的学弟(学妹?)我们的学妹呢?

晚上分到了鱼蛋蛋,味道还不错啊。

大晚上的没睡觉看饥饿游戏看到了12点多。

Day 1:

早上吃了早饭(黄焖鸡米饭)就早早地在考场前面等着了。
一边希望着这次的题不要太简单也不要太难,恰好我都会就行了。
进考场,拉键盘,开编译器,然后... ...
WTF,不能动电脑!?
被你们打败了,,,干坐了半个小时~!@#¥%……&×()——+,
一开包:
    T1:
        哎呀,水题。
       T2:
        。。。 。。。
        没有什么思路,一会想一想应该能想出来吧
       T3:
        WOC,概率期望,,,你们这是要翻天了啊!
   花了10mins左右打完了第一题,开始看第二题,结果怎么想也没有思路,怎么想也没有思路,再怎么想也没有思路。
看来还是拿部分分吧,这道题貌似有很高的部分分,不过就是程序难写一点,先放放,去想想第三题。
第三题完全有思路,状态秒出,转移也秒出。20mins敲完,调了半小时还没调出来。

时间过去一个多小时了,不行,先把暴力程序都打上!
于是先把第三题的暴力打上了,过去了40mins左右搞出来了,还加了几个小剪枝。
返回去敲第二题的暴力,我敲了1h多,敲出来了80分的,放下了。
发现时间不够了!
赶紧检查文件名,检查各种的低级错误and数组大小。
最后给T3加了一种情况。交了上去。
从考场出来,感觉要废!

虽然感觉自己要废了吧,,但该浪还是得浪!
浪了一下午!
MC + 饥饿游戏 + 黑乐谱 + bilibili
非常感动、感激、感谢爸妈,在这个时候赶了过来。
让我这要废的心灵受到了抚慰

Day 2:

早上依旧去吃早饭,不过这次去吃饭和Day 1不同了。
这次是带上了一个活宝(ZS)去吃饭。
终于可以找一个人和我一起浪了。

开考:
    T1:
        水题啊!
    T2:
        直接骗分60啊
    T3:
        状压Dp骗分70啊
       0 mins
    开始码T1,码完了,样例都不过,发现自己的方法错了,,,
    想了一会才想出可以直接推过去。。。
    30mins
    T2直接上堆,去骗分,骗完了就没有管他。
    1h 10mins
    T3推二元一次不等式推了半天,,
    其实主要是一直以为是自己推错了,过不了自己手算的数据,最后才发现是自己手算的数据算错了
    然后开始状压,为什么我想到的是枚举两个集合啊,,,这是O(4^n)的啊,直接枚举子集的子集就可以做到O(3^n)啊,,,
    O(3^n)就80了!这样我只打到了60分。
    2h 30 mins
    然后打了打对拍,把三个程序都拍了一遍。

    出考场,直接被爸妈带到了海边去。
    好冷啊!

After Ended

我们坐车连夜回到了衡水。
在NOIP倒计时上挂上了-1,终于结束了啊。
Sky_miner Avatar