2016.8.12纪中比赛总结

    xiaoxiao2024-07-25  13

    今天考得很不错,题目简单,可以算是超常发挥了(呵呵)

    心情不错,给大家多写点

    估分:100+20+100+100=320

    实际:100+20+100+100=320(现已AK

    排名:并列第3

    第一题[游荡的奶牛]

    本次题目中最难的题目(我都怀疑出题者把第一题和第四题交换了),刚开始很没底气地想要用暴力深搜。花了30分钟打了个迷宫问题,竟然还错了。于是想到用动态规划,想啊想啊,终于勉强求出状态转移方程(动态中的水题),又经过调试后,在比赛后约两小时终于做出正解。

    正解:如上,状态转移方程:f[i,j,k]表示在第ij列的位置上走到第k个时刻。

     F[i,j,k]:=f[i-1,j,k-1]+f[i+1,j,k-1]+f[i,j+1,k-1]+f[i,j-1,k-1] 

    第二题[渡河问题]

    我做完第一题后先去做稍简单的第34题(莫名其妙),最后只剩10来分钟,干脆把所有n头牛的时间全加起来,得到20分。

    正解:还是动态规划,f[i]表示运i头牛的最优解,

    状态转移方程:f[i]:=min(f[i],f[j]+f[i-j]+m),初始化时要先将f[i]定义为1i的前缀和。

    第三题[土地购买]

    刚开始真的没想到正解,于是把所有数的最大长和最大宽加起来(大家不要学),到比赛结束后一看竟然有50分(极度惊喜)。不过比赛结束前30分钟左右思路如泉涌,于是我决定背水一战,没想到很快便做了出来,交上去就carry

    正解:如上。哦,不好意思,我还没说呢。用一个双重循环贪心,x指长,y指宽。则判断max(x[i],x[j])*max(x[j],y[j])是否小于x[i]*y[i]+x[j]*y[j],如果小了的话就将x[i]赋值为max(x[i],x[j])y[i]赋值为max(x[j],y[j]),然后再将x[j]y[j]归零,便处理完毕。

    第四题[珍珠分对]   Special Judge

    史上最水第四题,我的方法是先将数据处理成一个一个的(比如2(编号为1)则处理为1 1),然后再来一个优质的快排,最后将头尾的配对即可,数据比较水(听说某些大逆不道的家伙直接输出“1  0AC了)。

    正解:如上。

    列点总结:(JY不要介意)

    1这次考得比较好,分数排名都很靠前,这是我也没有想到的,以后要尽量保持。

    2要合理利用时间,要不是34题简单,我就完全被第1题给弄惨了。

    3以后要努力想正解,才能取得好成绩

    4不要骄傲,再接再厉!

    转载请注明原文地址: https://ju.6miu.com/read-1291038.html
    最新回复(0)