## [CF2147D](https://codeforces.com/contest/2147/problem/D) [CODE](https://codeforces.com/contest/2147/submission/341869591) ## [CF2147E](https://codeforces.com/contest/2147/problem/E) 错了几发是因为刚开始的贪心有点想当然了，没有严谨证明，看了题解才发现差了一个小地方 [CODE](https://codeforces.com/contest/2147/submission/341881059) ## [CF2147F](https://codeforces.com/contest/2147/problem/F) 第一次见到竞赛图（tournament）诶，整理了网上看到的几点性质（这题主要用到第一点）： 1. 缩点之后是一条链，每个 scc 连向所有出度小的 scc 2. 所有强连通分量都存在一条哈密顿回路 3. 存在一条哈密顿路径 4. 一个大小为 $n$ 的 scc，存在且仅存在大小为 $[3,n]$ 的环 5. 令 $s_i$ 为第 $i$ 个点的出度，对 $s$ 排好序后，若满足 $\sum_{i=1}^k s_i \geq \binom{k}{2}$ 且 $\sum_{i=1}^n s_i = \binom{n}{2}$ 定能构造出一种竞赛图，反之不能。 6. 图中出度最大的点最多经过 $2$ 条边可以到达任意点 很妙的一个地方就在于将图的连通性转化到区间覆盖上（当然我没想到）！！ [CODE](https://codeforces.com/contest/2147/submission/342010056) ## [CF2140D](https://codeforces.com/contest/2140/problem/D) [CODE](https://codeforces.com/contest/2140/submission/342019586) ## [CF2140E](https://codeforces.com/contest/2140/problem/E2) 忘记了有一个比较常见的转化 要求所有可行的值的和 可以求出 $\ge1$，$\ge2$ …… $\ge x$ 的分别的数量的和 [CODE](https://codeforces.com/contest/2140/submission/342028653) ## [CF2103D](https://codeforces.com/contest/2103/problem/D) 简单题 忘记考虑端点错了一次 [CODE](https://codeforces.com/contest/2103/submission/341631378) ## [CF2103E](https://codeforces.com/contest/2103/problem/E) 也比较简单 感觉这类题目经常是存在一个可行位置就可以构造出答案 或者说很多构造题一定存在合法解（除去明显错误的情况） [CODE](https://codeforces.com/contest/2103/submission/341736874) ## [CF2107F](https://codeforces.com/contest/2107/problem/F1) 单 F1 的话是一个简单的 DP F2 的话需要给 DP 优化 一直往 F1 的 DP 想就很难找到优化（F1 是倒着DP的） 需要找到性质后重新找到新的转移 然后就可以用斜率优化 斜率优化感觉超久没写了（好像有超多东西可以实现） Loading... ## [CF2147D](https://codeforces.com/contest/2147/problem/D) [CODE](https://codeforces.com/contest/2147/submission/341869591) ## [CF2147E](https://codeforces.com/contest/2147/problem/E) 错了几发是因为刚开始的贪心有点想当然了，没有严谨证明，看了题解才发现差了一个小地方 [CODE](https://codeforces.com/contest/2147/submission/341881059) ## [CF2147F](https://codeforces.com/contest/2147/problem/F) 第一次见到竞赛图（tournament）诶，整理了网上看到的几点性质（这题主要用到第一点）： 1. 缩点之后是一条链，每个 scc 连向所有出度小的 scc 2. 所有强连通分量都存在一条哈密顿回路 3. 存在一条哈密顿路径 4. 一个大小为 $n$ 的 scc，存在且仅存在大小为 $[3,n]$ 的环 5. 令 $s_i$ 为第 $i$ 个点的出度，对 $s$ 排好序后，若满足 $\sum_{i=1}^k s_i \geq \binom{k}{2}$ 且 $\sum_{i=1}^n s_i = \binom{n}{2}$ 定能构造出一种竞赛图，反之不能。 6. 图中出度最大的点最多经过 $2$ 条边可以到达任意点 很妙的一个地方就在于将图的连通性转化到区间覆盖上（当然我没想到）！！ [CODE](https://codeforces.com/contest/2147/submission/342010056) ## [CF2140D](https://codeforces.com/contest/2140/problem/D) [CODE](https://codeforces.com/contest/2140/submission/342019586) ## [CF2140E](https://codeforces.com/contest/2140/problem/E2) 忘记了有一个比较常见的转化 要求所有可行的值的和 可以求出 $\ge1$，$\ge2$ …… $\ge x$ 的分别的数量的和 [CODE](https://codeforces.com/contest/2140/submission/342028653) ## [CF2103D](https://codeforces.com/contest/2103/problem/D) 简单题 忘记考虑端点错了一次 [CODE](https://codeforces.com/contest/2103/submission/341631378) ## [CF2103E](https://codeforces.com/contest/2103/problem/E) 也比较简单 感觉这类题目经常是存在一个可行位置就可以构造出答案 或者说很多构造题一定存在合法解（除去明显错误的情况） [CODE](https://codeforces.com/contest/2103/submission/341736874) ## [CF2107F](https://codeforces.com/contest/2107/problem/F1) 单 F1 的话是一个简单的 DP F2 的话需要给 DP 优化 一直往 F1 的 DP 想就很难找到优化（F1 是倒着DP的） 需要找到性质后重新找到新的转移 然后就可以用斜率优化 斜率优化感觉超久没写了（好像有超多东西可以实现） 最后修改：2025 年 10 月 19 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏