Codeforces Round #242 (Div. 2) <A-D>

<a target="_blank" href="http://codeforces.com/problemset/problem/424/A">CF424 A. Squats</a>

題目意思：

有n（n為偶數）個x和X，求最少的變換次數，使得X的個數為n/2，輸出變換後的序列。

解題思路：

統計X的個數ans,和n/2比較，少了的話，須要把n/2-ans個x變成X，多了的話須要把ans-n/2個X變成x.（從前往後掃一遍即可了）。

代碼：

<a target="_blank" href="http://codeforces.com/problemset/problem/424/B">CF 424B. Megacity</a>

給一個中心城市的坐标(0,0)和人口s，n個周圍城市。告訴n個城市的人口及位置坐标，求以中心城市為圓心的最小的半徑，使得人口總數超過1000000-s.

先求出每一個城市距離中心城市的距離，然後對距離從小到大排序，然後依次掃描，假設達到要求，就退出輸出最小的半徑。

<a target="_blank" href="http://codeforces.com/problemset/problem/424/C">CF 424C. Magic Formulas</a>

給定pi,求Q。

抑或運算滿足交換律和結合律。

原式能夠等價于先對pi所有抑或。然後對每一個i（1=&lt;i&lt;=n),求出1~n對i求模再抑或，能夠發現一直是1~i-1 1~i-1..... 是以假設n/i是偶數抑或值為0。假設是奇數抑或值為1^2^3^4...^i-1 最後餘數是1~n%i .

預處理出dp[i]=1^2^3..^i

<a target="_blank" href="http://codeforces.com/problemset/problem/424/D">CF 424D. Biathlon Track</a>

給一個2維矩陣。給三個參數tp（相等）,tu（大于）,td（小于）,t（總時間），每一個格子有個權值，求一個矩陣（長&gt;=3&amp;&amp;寬&gt;=3),使得邊緣走完的總時間T，與t盡可能靠近。輸出矩陣的左上角坐标和右下角坐标。

dp+預處理

o(n^3*lgn)  枚舉兩列i,j 把最後一行的 形如 |_| 值丢進set裡，從第n-2行開始枚舉，求出形如 |_|  的值v，二分查找t-v 找到最接近的，更新。

使用set&lt;pair&lt;int,int&gt; &gt;裡的lower_bound函數。

此題的關鍵在于僅僅用枚舉三維。兩列和一行 構造 |_| 形狀。直接用lower_bound得出最接近的矩形的值。

l[i][j]表示從位置（i,j）水準走到左邊界的時間值

r[i][j]表示從最左邊向右水準走到位置（i,j）所需時間值

u[i][j]表示從位置（i,j）豎直向上走到上邊界的時間值 

d[i][j]表示從上邊界豎直向下走到位置（i,j）所需時間值

本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/5196565.html，如需轉載請自行聯系原作者