Difference between revisions of "AtCoder Grand Contests"
Jump to navigation
Jump to search
| Line 260: | Line 260: | ||
* R: Read | * R: Read | ||
| − | + | = 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 === | |
跟多校的某个折线题（我记得有张图的）很像。搞清楚答案的形状之后，转移方程就是： | 跟多校的某个折线题（我记得有张图的）很像。搞清楚答案的形状之后，转移方程就是： | ||
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。