今天考得很不错,题目简单,可以算是超常发挥了(呵呵)
心情不错,给大家多写点
估分:100+20+100+100=320
实际:100+20+100+100=320(现已AK)
排名:并列第3
第一题[游荡的奶牛]
本次题目中最难的题目(我都怀疑出题者把第一题和第四题交换了),刚开始很没底气地想要用暴力深搜。花了30分钟打了个迷宫问题,竟然还错了。于是想到用动态规划,想啊想啊,终于勉强求出状态转移方程(动态中的水题),又经过调试后,在比赛后约两小时终于做出正解。
正解:如上,状态转移方程:f[i,j,k]表示在第i行j列的位置上走到第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]
第二题[渡河问题]
我做完第一题后先去做稍简单的第3、4题(莫名其妙),最后只剩10来分钟,干脆把所有n头牛的时间全加起来,得到20分。
正解:还是动态规划,f[i]表示运i头牛的最优解,
状态转移方程:f[i]:=min(f[i],f[j]+f[i-j]+m),初始化时要先将f[i]定义为1至i的前缀和。
第三题[土地购买]
刚开始真的没想到正解,于是把所有数的最大长和最大宽加起来(大家不要学),到比赛结束后一看竟然有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 0”AC了)。
正解:如上。
列点总结:(JY不要介意)
1这次考得比较好,分数排名都很靠前,这是我也没有想到的,以后要尽量保持。
2要合理利用时间,要不是3、4题简单,我就完全被第1题给弄惨了。
3以后要努力想正解,才能取得好成绩
4不要骄傲,再接再厉!