二模 (1) day1

第一题:

题目大意:给出N(N<=50)个小于1000的正整数Ai,和一个正整数max,和一个整数cur,从前往后依次对每个Ai,可以让cur+Ai 或者 cur-Ai,但是结果不能大于max,也不能小于0.求最终的cur的最大值。

解题过程:

1.一开始直接写了个爆搜+剪枝(ans=max或者ans+sum[i]<=ans),除了N=50的一些恶心数据都能过。

2.然后想到一个更强力的剪枝,就是当状态 (step,cur)之前已经搜索到过了,就跳过。然后就AC了。

3.其实第2条中的实质就是动态规划,有点像记忆化搜索。直接递推也很好做。


第二题:

题目大意:给出一个N*M(小于1000)的矩阵,由空地和障碍组成,每行每列最多只有一个障碍。且2个障碍不会在对角相邻。

也就是不会有下面这种情况。(‘X’表示障碍,‘.’表示空地)

.X

X.

求出两两空地的距离之和。

解题过程:

1.先考虑没有障碍的情况:

笨方法:

用O(NM)的时间处理出所有以(1,1)为左上角顶点的A类矩形内的空地的横纵坐标之和,保存在sqr1,sqr2中,所有以(1,M)为右上角顶点的B类矩形内的空地的横纵坐标之和,保存在sqr3,sqr4中,还要保存相应矩形内空地的个数,cnt1,cnt2,cnt3,cnt4,对于每一个坐标为(i,j)的X,只要统计 以(i,j-1)为右下角顶点的A类矩形,即sqr1[i][j-1]和sqr2[i][j-1]。这些矩形里的空地的横纵坐标都比当前点小,所以加上sqr1[i][j-1]-cnt1[i][j-1]*i以及sqr2[i][j-1]-cnt2[i][j-1]*i; 同理根据横纵坐标的大小处理B类矩形,最后答案*2.

标准方法:

以处理横坐标的和为例。用F[i]保存横坐标为i的X有多少个,那么答案就是 sum(F[i]*F[j]*abs(i-j));纵坐标同理。

2.再看有障碍的情况,画图可以发现,两个点的距离要么是欧几里得距离,要么是欧几里得距离+2.那么只要统计出要+2的点对数。

对于一个X1,如果它右边一列有一个X2,那么X1上方的点到X2下方的点的距离都要+2.如果X2右边一列还有一个X3,且X3在X2的下方,那么X1上方的点到X3下方的点的距离也要+2。因此只要是在X1右边,纵坐标连续且横坐标递增(往下是增)的X,都是这种情况。  同理可以计算在X1上方的X,以及横着的情况(X2在X1右边,且刚好在正下(上)方一列,X1左边的点到X2右边的点也要+2)。

非常不错又恶心的一道题。。。


第三题:

题目大意:给出一个N个元素的队伍(N<=2*10^5),以及每个元素的权值和种类,每次要求相邻的两个不同种类且权值差最小的两个元素出队,求出队顺序。

解题过程:

1.对于出队的情况,直接数组模拟双向链表来优化时间。可以拿50分。

2.考虑到每次取最小,就建一个小根堆,每次取出堆顶元素知道堆顶元素表示的编号为x,y的人都还没有出队。让其出队,然后把他们左右两个人组成一个元素加入堆。

上一篇:AFNetworking之多图片-文件上传


下一篇:js中的break ,continue, return (转)