洛谷

题目大意 在 $0$ 到 $L$ 的位置间，有 $N$ 块岩石。若要使得岩石间距最小值最大，允许移除 $M$ 块，求此时间距最小值。 分析 定义函数 $f(x)$，输入为最小值，输出为被移除岩石的个数，实现如下 ll L, N, M, aa[100086]; ll f(ll x) { ll ans = 0; ll l = 0, r = 1; while (r <= N) { if (aa[r] - aa[l] >= x) l = r; else ans++; r++; } return ans; } 显然 $f(x)$ 是单调递减的函数，二分查找即可。 int main() { L = rr(), N = rr(), M = rr(); for (ll i = 1; i <= N; i++) aa[i] = rr(); aa[++N] = L; ll l = 1, r = L; while (l < r) { ll mid = (l + r + 1) >> 1; ll fm = f(mid); if (fm <= M) l = mid; else r = mid - 1; } printf("%lld\n", l); return 0; }

题目大意 环形队列上有 $n$ 堆石子，可以把相邻的两堆合成一堆，每次合并的得分是新一堆的石子数。 求最终分数的最小值和最大值。 分析 考虑 $dp(i,j)$ 是将区间 $[i,j]$ 的石子全部合并的最大值。于是状态转移方程为 $$ dp(i,j) = \max_{i \leqslant k \leqslant j}(dp(i,k) + dp(k+1,j) + s(i,j)) $$ 其中 $s(i,j)$ 是 $[i,j]$ 中所有石子数。 然而不能通过先 $i$ 再 $j$ 再 $k$ 的循环来递推，运算顺序值得注意。 细节：前缀和、循环开两倍。 int dmax[205][205], dmin[205][205]; int f[205], s[205]; int main() { int n = rr(); for (ll i = 1; i <= n; i++) f[i + n] = f[i] = rr(); for (ll i = 1; i <= n * 2; i++) s[i] = s[i - 1] + f[i]; for (ll len = 2; len <= n; len++) { for (ll i = 1; i <= 2 * n - len + 1; i++) { int j = i + len - 1; int tmax = 0, tmin = 0x3f3f3f3f; int ss = s[j] - s[i - 1]; for (ll k = i; k <= j - 1; k++) { tmax = max(tmax, dmax[i][k] + dmax[k + 1][j] + ss); tmin = min(tmin, dmin[i][k] + dmin[k + 1][j] + ss); } dmax[i][j] = tmax; dmin[i][j] = tmin; } } int mmin = 0x3f3f3f3f, mmax = 0; for (ll p = 0; p <= n - 1; p++) { mmin = min(mmin, dmin[p + 1][p + n]); mmax = max(mmax, dmax[p + 1][p + n]); } printf("%d\n%d\n", mmin, mmax); return 0; }

题目大意 混合背包。每棵树都有美学值 $C_i$，共有三种： 一种只能看一遍。 一种最多看 $A_i$ 遍。 一种可以看无数遍。 分析 对于混合背包，我们可以对物品拆分，得到多个物品。 ll dp[1086], tt[100086], cc[100086]; int main() { int tsh = rr(), tsm = rr(), teh = rr(), tem = rr(); int tsum = (teh - tsh) * 60 + tem - tsm; int n = rr(); int tp = 1; for (ll i = 1; i <= n; i++) { int t = rr(), c = rr(), p = rr(); if (p == 1) { tt[tp] = t, cc[tp] = c; tp++; } else { p = p !...

题目大意 初始有四种卡片，消耗后分别可以前进 $1$、$2$、$3$ 和 $4$ 格。棋盘上每个点都有个分数，求从第 $1$ 格到达第 $N$ 格途径分数的最大值。 分析 设状态 $F[i, j, k, w]$ 为使用 $i$ 张前进 $1$、……、$w$ 张前进 $4$ 之后的状态，容易得到转移方程 $$ F[i, j, k, w] = \max\left\{ \begin{matrix} dp[i - 1, j, k, w] \\ dp[i, j - 1, k, w] \\ dp[i, j, k - 1, w] \\ dp[i, j, k, w - 1] \end{matrix}\right\} + a[i + 2j + 3k + 4w] $$ 处理一下边界情况，滚动数组即可。 ll dp[50][50][50], aa[400], tt[10]; int main() { ll n = rr(), m = rr(); for (ll i = 1; i <= n; i++) { aa[i] = rr(); } for (ll i = 1; i <= m; i++) { tt[rr()]++; } for (ll i = 0; i <= tt[1]; i++) { for (ll j = 0; j <= tt[2]; j++) { for (ll k = 0; k <= tt[3]; k++) { for (ll w = 0; w <= tt[4]; w++) { dp[j][k][w] = aa[i * 1 + j * 2 + k * 3 + w * 4 + 1] + max4( j == 0 ?...

题目大意 在 $n \times n$ 的格上，在每行中各有一条线段 $(i, l_i) \to (i, r_i)$。 你从 $(1,1)$ 出发，只能沿着格子直走，最终走到 $(n,n)$。要求沿途经过所有的线段，且所走路程长度尽量的短。 分析 显然是一行一行的递推。维护两个数据，一个是走完该行后停留在左侧的，记作 ${\rm DP}_l$，相应的停留在右侧的记作 ${\rm DP}_r$。 若停在左侧，可能从上一行的右侧走来，也可能是由左侧走来，故转移方程有 $$ {\rm DP}_l[i] = r_i - l_i + \min\{{\rm DP}_l[i - 1] + |l_{i-1} - r_i|, {\rm DP}_r[i - 1] + |r_{i - 1} - r_i|\} $$ 右侧类似，故可以写出代码 int main() { int n = rr(); ll past_l = 1, past_r = 1, dpl = 0, dpr = 0; for (ll i = 1; i <= n; i++) { ll l = rr(), r = rr(); ll tl = min(dpl + abs(past_l - r), dpr + abs(past_r - r)) + r - l; ll tr = min(dpl + abs(past_l - l), dpr + abs(past_r - l)) + r - l; dpl = tl, dpr = tr; past_l = l, past_r = r; } printf("%lld\n", min(dpl + n - past_l, dpr + n - past_r) + n - 1); return 0; }

题目大意 要从 $n$ 种花中挑出 $m$ 盆展览，其中第 $i$ 种花不得多于 $a_i$ 种。求有几种选法。 分析 考虑动态规划，记状态 $dp[i,j]$ 为摆完前 $i$ 种花，共 $j$ 盆时的方案数。容易得到递推式 $$ dp[i,j] = \sum_{k = j - \min(a_i, j)}^j dp[i-1,k] $$ 边界条件是 $dp[0,0] = 1$。可以用滚动数组、前缀和优化。 const ll mod = 1e6 + 7; ll dp[110], aa[110], sum[110]; int main() { ll n = rr(), m = rr(); sum[0] = dp[0] = 1; for (ll i = 1; i <= n; i++) aa[i] = rr(); for (ll i = 1; i <= n; i++) { for (ll j = 1; j <= m; j++) sum[j] = (sum[j - 1] + dp[j]) % mod; for (ll j = m; j >= 0; j--) { int t = j - 1 - min(aa[i], j); if (t > 0) dp[j] = (dp[j] + sum[j - 1] - sum[t]) % mod; } } printf("%lld\n", (dp[m] + mod) % mod); return 0; }

题目大意 可以合并两堆果子成一堆新果子，消耗两堆果子数目之和的体力。给定 $n$ 堆果子的数目 $a_i$，求体力耗费最小的方案。 分析 很容易猜到贪心结论，不断选取两个最小的堆进行合并。 priority_queue<int, vector<int>, greater<int> > q; int main() { int n = rr(); for (ll i = 1; i <= n; i++) { int t = rr(); q.push(t); } int sum = 0; while (q.size() >= 2) { int x = q.top(); q.pop(); int y = q.top(); q.pop(); sum += x + y; q.push(x + y); } printf("%d\n", sum); return 0; } 本质上是证明 Huffman 树的构造的正确性，有点复杂。

题目大意 给定数列，求第 $k$ 小的数。 分析 模板题。考虑分治，随便选一个数 $x$，然后把比 $x$ 大的数移到右边，比 $x$ 小的数移到左边。因此得到了数 $x$ 的排位，若恰为第 $k$ 个则返回，否则根据大小在左右寻找。 该算法是不稳定的，期望复杂度 $O(n)$，最坏复杂度 $O(n^2)$。 实际上存在最坏复杂度为 $O(n)$ 的 BFPTR 算法，但因为其常数过大实现复杂而很少应用。 ll nn[5000010], k, n; ll quicksort(ll l, ll r) { ll i = l, j = r; ll x = nn[(l + r) / 2]; while (i <= j) { while (nn[j] > x) j--; while (nn[i] < x) i++; if (i <= j) { swap(nn[i], nn[j]); i++, j--; } } // l <= j <= i <=r if (k <= j) return quicksort(l, j); else if (k >= i) return quicksort(i, r); else return nn[k + 1]; } int main() { n = rr(), k = rr(); for (ll i = 1; i <= n; i++) scanf("%lld", &nn[i]); printf("%lld", quicksort(1, n)); return 0; }

题目大意 我们将重复的 $n$ 个字符串 S 压缩为 [nS]，且存在多重压缩。给定一个压缩结果，展开它。 分析 我考虑用类似状态机的方式解析字符串。 当读到正常字符时，把它添到 $s$ 末尾 读到左括号时，则递归 read()，重复 $n$ 遍添到 $s$ 末尾 右括号或文本结束则返回 $s$ 写成 BNF 更直观一点 <pwd> ::= <EMPTY> | {<ALPHA>} | <pwd> "[" <NUMBER> <pwd> "]" <pwd> string read() { string s = ""; char c; while (cin >> c) { if (c == '[') { int n; cin >> n; string ts = read(); while (n--) s += ts; } else if (c == ']') { return s; } else { s += c; } } return s; } int main() { cout << read(); return 0; }

题目大意 有 I 形和 L 形两种砖头，分别能覆盖 2 个单元和 3 个单元。求 $2 \times n$ 的墙有多少不重复的覆盖方式，结果对 $10^4$ 取模。 分析 其中 I 形砖块仅有横放和竖放两种。关键在于 L 形，两个 L 形之间可以用 I 形填充，这让情况变得复杂起来。 对于 $F_n$ 的递推，我们可以想到 在 $F_{n-1}$ 后放一个 I 形砖块。 在 $F_{n-2}$ 后放两个横着的 I 形砖块。 对于更前面的递推，较为复杂。 两个 L 形砖块对齐，上下翻转也可以，即 $2 F_{n-3}$。 两个 L 形砖块可以对顶放，空缺恰用一个 I 填充，即 $2 F_{n-4}$。 类似 $2F_{n-3}$，中间可以再插入两个 I 形，即 $2 F_{n-5}$。 …… 直到 I 形和 L 形砖块恰好铺满墙壁，即 $2F_{0}$。 容易得到我们的递推式...