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。。