Codeforces Round #280（Div. 2）

A. Vanya and Cubes

題目大意：

       給你n(n <= 1e4)個立方體，問你能建的最高的金字塔的高度是多少。金字塔頂層需要1個立方體，往下第i層需要個立方體。

題解：

       模拟。由于n <= 1e4，層數也不會超過1e4。是以就一層一層加到不能加位置。

B. Vanya and Lanterns

題目大意：

       坐标範圍為[0,l]的線段上有n個點，每個點可以覆寫坐标差的絕對值不大于d的位置，求确定最小的d使得這n個點可以覆寫整條線段。

題解：

       貪心。将點按坐标排序，最左邊的點覆寫0，最右邊的點覆寫l。相鄰兩點間的部分由這兩個點各覆寫一半。将這些覆寫範圍取max即為答案。

C. Vanya and Exams

題目大意：

       有n門考試，每門考試最高分不超過r，現在知道第i門考試得到了ai分，要提高這門考試1分需要寫bi篇文章，問最少寫多少篇文章才能使總平均分大于等于avg。

題解：

       貪心。将考試按提高分數需要寫的文章數從小到大排序。按照這個順序提升分數直到分數夠了或者這門考試已經達到r分為止。

D. Vanya and Computer Game

題目大意：

       有n(n <= 1e5)隻怪物，第i隻怪物需要被攻擊ai(ai <= 1e9)下才能被消滅。Vanya每秒鐘攻擊x(x <= 1e6)下，Vova每秒鐘攻擊y(y <= 1e6)下。問每隻怪物被誰攻擊的最後一下。如果同時攻擊輸出Both。

題解：

       模拟。直接模拟每隻怪物每次是誰攻擊的肯定不行。觀察到x <= 1e6, y <=1e6。每秒鐘兩個人一起造成的傷害是固定的x + y。是以可以先将ai mod (x + y)再模拟每次攻擊。由于有n隻怪物。是以可以将血量為0~x + y – 1的結果都先預處理出來，最後輸出答案即可。

E. Vanya and Field

題目大意：

       n*n(n <= 1e6)的網格中有m(m <= 1e5)棵蘋果樹，Vanya從一個格子出發(x0, y0)，每次移動的向量均為(dx, dy)，即如果Vanya現在在(x, y)，移動後的格子為((x + dx) % n, (y + dy) % n)。問從哪個格子出發可以預見最多的蘋果樹。其中gcd(n, dx) = gcd(n, dy) = 1

題解：

       數學題，由gcd(n, dx) =gcd(n, dy) = 1，我們知i周遊0 ~ n – 1時，i * dx mod n也周遊0 ~ n – 1。是以從(0, 0), (0, 1)…(0, n - 1)出發将得到n條兩兩不相交的路線。并且每條路線的長度為n。即将網格分成了n個”等價類”。對于每棵蘋果樹，我們給它屬于的路線答案加1，最後找到答案最大的路線即可。

       我們用d[x] = y來記錄從(0, 0)出發的過程中橫坐标到x的時候縱坐标為y。則第i棵蘋果樹屬于第(yi – d[xi] + n) % n條路線。