Codeforces Round #187 DIV 1

题目链接

B题：事实证明是sb题，而且证明自己比题目还傻。。

C题：设dp[i]表示当前以数字i结尾的所有合法子序列乘积的总和（非递减），那么新插进来一个数K的时候，我们要更新dp[K],

dp[K] =( dp[0] + dp[1] + dp[2] +... + dp[K] ) * K  - dp[K]; 所以要用到个东东动态统计前缀和

比如1 2 3 3

插入最后一个3的时候，前面有这么写东西（1） （2）（3）（1 2）（1 3） （2 3），然后插入一个3相当于在每一项的后面增加一个

3，但是别忘了要减去原来以3结尾的，因为算重复掉了。

http://codeforces.com/contest/314/submission/3843964

D题：先膝跳反射想到二分， 但如果不将坐标系旋转，很难搞，，，以后这种题尽量把坐标旋转也当成非条件反射好了。。

我们可以将点的坐标逆时针旋转45度，，这样子题目中的那两条相互垂直的线就分别跟坐标轴平行了。。

然后

1 : 旋转45度(x,y) ->(x-y,x+y)（这个方法将坐标之间的距离也扩大了sqrt(2)）,坐标仍然为整数，比较好。。

2 : 最短的曼哈顿距离是最短距离的sqrt(2)倍，所以如果是将原图不变的旋转，算出的答案要乘sqrt(2)

3 : 验证的时候只需要维护两条距离为2*mid的竖线扫过去，然后如果在竖线外部的点的Y的最大值与最小值之差小于等于2*mid，当前位置就可以放两条线了，一条在两条竖线中间，另一条在外部的最高点与最低点中间。。

http://codeforces.com/contest/314/submission/3854573

Summary ： 比赛的时候思维还是不够独立，都只能想个大概，以后直接从B题开始看好了，，后面的做出一个再去看看A。。