A – Pay to Win
一个 DP。考虑反向构造：从 \(0\) 到 \(X\)。最后过程肯定是先加加减减然后再除、亦复如是。
继续阅读“AtCoder Grand Contest 044 – 解题报告”标签归档： DP
AtCoder Grand Contest 046 – 解题报告
A – Takahashikun, The Strider
SB 题，不解释。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
int x;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int main()
{
scanf("%d", &x), printf("%d\n", 360 / gcd(x, 360));
return 0;
}
继续阅读“AtCoder Grand Contest 046 – 解题报告” AtCoder Regular Contest 074E:RGB Sequence – 题解
主要思路
这个题看上去像是 \(\Theta(n^3)\) 的。一眼想到设置 \(dp[i][a][b][c]\) 进行转移，然而发现不仅空间开不下而且还需要额外的时间。
考虑设计 \(dp[a][b][c]\)，其中 \(a, b, c\) 为 \(R, G, B\) 出现的最晚时间，显然有 \(i = \max(a, b, c)\)。通过这个，我们可以遍历一下要求然后做转移。
继续阅读“AtCoder Regular Contest 074E:RGB Sequence – 题解”「Universal OJ」#311:「UNR #2」积劳成疾 – 题解
主要思路
这个处理方式很妙啊。根据 yyb 的博客介绍，这种处理方式被称作是「最大值分治」。
我们可以考虑设计状态 \(dp[i][j]\) 为长度为 \(i\)、最大值不超过 \(j\) 的方案数。那么，我们可以枚举一个 \(k\) 作为 \(j\) 的位置，然后强制这个 \(k\) 在这一段里面是最右边的 \(j\)，具体写出转移就是：
\[ dp[i][j] = dp[i][j – 1] + \sum_{k = 1}^i dp[k – 1][j] \times dp[i – k][j – 1] \times w^c \]
注意右侧的 \(dp[i – k][j – 1]\)，可以保证该位置为最右侧的 \(j\)，这样就不会算重复了。其中 \(c\) 是当前序列里包含这个数的区间个数，画个图，算最右和最左的区间左边缘之差即可。
继续阅读“「Universal OJ」#311:「UNR #2」积劳成疾 – 题解”「FZOI」 Round #41 (Div. 0) – 解题报告
P4517:「JSOI2018」防御网络 – 题解
主要思路
宏观很难看出什么东西，所以我们可以考虑每条边单独的贡献。
首先这个图是个仙人掌，所以我们需要分开考虑环边的贡献和树边的贡献。树边的贡献很好考虑，直接 \((2^{siz_u} – 1) \times (2^{siz_v} – 1)\) 即可。如果是环边就有点麻烦，我们需要枚举做贡献的最小弧长，然后再从某一个点作起点算两两出边大小乘积的答案。用前缀和优化可以省掉一维的转移复杂度。
继续阅读“P4517:「JSOI2018」防御网络 – 题解”