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，如需转载请自行联系原作者