Difference between revisions of "AtCoder Grand Contests"

From EOJ Wiki
Jump to navigation Jump to search
Line 260: Line 260:
 
* R: Read
 
* R: Read
  
# 7C
+
= Solutions =
 +
 
 +
=== 7C ===
  
 
猜他拿完一个以后期望仍然是等差数列就赢了。(反正我是看了题解)
 
猜他拿完一个以后期望仍然是等差数列就赢了。(反正我是看了题解)
Line 270: Line 272:
 
* $\frac{2n-i-1}{2n} (d + (i-1)x)$
 
* $\frac{2n-i-1}{2n} (d + (i-1)x)$
  
# 7D
+
=== 7D ===
  
 
跟多校的某个折线题(我记得有张图的)很像。搞清楚答案的形状之后,转移方程就是:
 
跟多校的某个折线题(我记得有张图的)很像。搞清楚答案的形状之后,转移方程就是:

Revision as of 10:41, 21 January 2019

大坑。

有意思的题会写题解。

Status

# A B C D E F
AtCoder Grand Contest 001 · · · · · ·
AtCoder Grand Contest 002 · · · · · ·
AtCoder Grand Contest 003 · · · · · ·
AtCoder Grand Contest 004 · · · · · ·
AtCoder Grand Contest 005 · · · · · ·
AtCoder Grand Contest 006 · · · · · ·
AtCoder Grand Contest 007 A A A A · ·
AtCoder Grand Contest 008 · · · · · ·
AtCoder Grand Contest 009 · · · · · ·
AtCoder Grand Contest 010 · · · · · ·
AtCoder Grand Contest 011 · · · · · ·
AtCoder Grand Contest 012 · · · · · ·
AtCoder Grand Contest 013 · · · · · ·
AtCoder Grand Contest 014 · · · · · ·
AtCoder Grand Contest 015 · · · · · ·
AtCoder Grand Contest 016 · · · · · ·
AtCoder Grand Contest 017 · · · · · ·
AtCoder Grand Contest 018 · · · · · ·
AtCoder Grand Contest 019 · · · · · ·
AtCoder Grand Contest 020 · · · · · ·
AtCoder Grand Contest 021 · · · · · ·
AtCoder Grand Contest 022 · · · · · ·
AtCoder Grand Contest 023 · · · · · ·
AtCoder Grand Contest 024 · · · · · ·
AtCoder Grand Contest 025 · · · · · ·
AtCoder Grand Contest 026 · · · · · ·
AtCoder Grand Contest 027 A T · · · ·
AtCoder Grand Contest 028 A A · · · ·
AtCoder Grand Contest 029 A A A · · ·
AtCoder Grand Contest 030 · · · · · ·
  • A: Accepted
  • T: Tried
  • R: Read

Solutions

7C

猜他拿完一个以后期望仍然是等差数列就赢了。(反正我是看了题解)

第 $i$ 段,分三种情况讨论,贡献分别如下(这一部分题解省略了):

  • $\frac{i}{2n} (d + (i + 1)x)$
  • $\frac{1}{2n} (3d + 3 i x)$
  • $\frac{2n-i-1}{2n} (d + (i-1)x)$

7D

跟多校的某个折线题(我记得有张图的)很像。搞清楚答案的形状之后,转移方程就是:

$f_i = min_{1 \le j \le i} \{ f(j - 1) + \max(2(x_i-x_j), T) + (x_i - x_{j-1})\}$。

max 的那部分可以用单调队列处理,中间的那部分维护一个单调增队列,弹出来以后更新一个全局最小值。最后答案就是两部分的 min。