### [CF2139D](https://codeforces.com/problemset/problem/2139/D) 好题 比较想到区间内存在长度 的单调递减子串即可 （**对于询问提前预处理每个右端点可以到达的最远左端点**） **我是用单调栈+树状数组维护，但题解用两个单调栈维护更妙也更好写** [CODE](https://codeforces.com/problemset/submission/2139/337972321) ### [CF2139E1](https://codeforces.com/problemset/problem/2139/E1) & [CF2139E2](https://codeforces.com/problemset/problem/2139/E2) 好题 没有想到结论，答案只能最小深度或最小深度-1 然后判断是否可行就很简单，E1直接背包 [CODE](https://codeforces.com/problemset/submission/2139/338022938) E2 bitset 优化背包就可以过** **[CODE](https://codeforces.com/problemset/submission/2139/338023595) 看题解学会了一个**优化背包的方法** 所有物品体积和固定时 体积 的最多 个 小于的最多 种不同体积，每种二进制拆分，最多 个物品 [CODE2](https://codeforces.com/problemset/submission/2139/338024962) ### [CF2134D](https://codeforces.com/problemset/problem/2139/D) 好题 开始想到把所有的移动到直径上，很容易举出反例 然后容易发现把直径移动使直径变长一定可行且最优 [CODE](https://codeforces.com/problemset/submission/2134/338352913) ### [CF2134E](https://codeforces.com/problemset/problem/2139/E) 好题 交互题 2n 步的想到之后就发现很多是多余的，刚好可以满足 [CODE](https://codeforces.com/problemset/submission/2134/338357859) ### [CF2128D](https://codeforces.com/problemset/problem/2128/D) 好题 画图画了好久 满足条件的排列都是两个（或者全递减）递减的序列合并到一起 单独算每个的贡献 感觉比前面2个D题难想诶 [CODE](https://codeforces.com/problemset/submission/2128/338546811) ### [CF2124E](https://codeforces.com/problemset/problem/2124/E) 好题 构造题没想到/kk 最多 次这个数字好奇怪没想到最多 次就可以 看了题解才做出了/kk 不过确实是好题目 从 推到任意情况（**特殊到一般**） 就可以构造出来，后面 3 步变成 2 步也很重要 [CODE](https://codeforces.com/problemset/submission/2124/338549353) ### [CF2112F](https://codeforces.com/problemset/problem/2112/F) Div 2 的 F 题都好难，前面有几道做不出来就换了 这题没想到转换 就是把**数组数值关系转换成图上路径** 然后条件转换成是否所有最短路径都是单条边到达的 然后就超好做了！！ [CODE](https://codeforces.com/problemset/submission/2112/338610497) ### [CF2113F](https://codeforces.com/problemset/problem/2113/F) 好 结论很好猜 构造感觉也挺好想到的直接二分图匹配就好了 题解的另一种做法没想到但是也特别聪明！！ （以下内容翻译自题解） > 基于数组中的值构建图：对于每个下标 ，在顶点 和 之间添加一条无向边。现在，我们需要为图中的边定向，使得每个度数至少为 的顶点至少有一条出边，并且每个度数至少为 的顶点至少有一条入边。如果第 条边被定向为从 指向 ，则令 。 > > 在每个连通分量中，以任意顶点为根构建 DFS 树。将所有树边从上向下定向，并将回边从下向上定向。容易看出，在这种构造下，除根节点外所有顶点都满足条件。对于根节点，仅当其度数至少为 且没有回边指向它时，条件不满足。此时，根节点至少有两个子树，只需选择其中一棵子树并将其中的所有边反向即可。 > > 这种构造方法可以达到上界，且可以在 时间内完成。 [CODE](https://codeforces.com/problemset/submission/2113/338620876) Loading... ### [CF2139D](https://codeforces.com/problemset/problem/2139/D) 好题 比较想到区间内存在长度 的单调递减子串即可 （**对于询问提前预处理每个右端点可以到达的最远左端点**） **我是用单调栈+树状数组维护，但题解用两个单调栈维护更妙也更好写** [CODE](https://codeforces.com/problemset/submission/2139/337972321) ### [CF2139E1](https://codeforces.com/problemset/problem/2139/E1) & [CF2139E2](https://codeforces.com/problemset/problem/2139/E2) 好题 没有想到结论，答案只能最小深度或最小深度-1 然后判断是否可行就很简单，E1直接背包 [CODE](https://codeforces.com/problemset/submission/2139/338022938) E2 bitset 优化背包就可以过** **[CODE](https://codeforces.com/problemset/submission/2139/338023595) 看题解学会了一个**优化背包的方法** 所有物品体积和固定时 体积 的最多 个 小于的最多 种不同体积，每种二进制拆分，最多 个物品 [CODE2](https://codeforces.com/problemset/submission/2139/338024962) ### [CF2134D](https://codeforces.com/problemset/problem/2139/D) 好题 开始想到把所有的移动到直径上，很容易举出反例 然后容易发现把直径移动使直径变长一定可行且最优 [CODE](https://codeforces.com/problemset/submission/2134/338352913) ### [CF2134E](https://codeforces.com/problemset/problem/2139/E) 好题 交互题 2n 步的想到之后就发现很多是多余的，刚好可以满足 [CODE](https://codeforces.com/problemset/submission/2134/338357859) ### [CF2128D](https://codeforces.com/problemset/problem/2128/D) 好题 画图画了好久 满足条件的排列都是两个（或者全递减）递减的序列合并到一起 单独算每个的贡献 感觉比前面2个D题难想诶 [CODE](https://codeforces.com/problemset/submission/2128/338546811) ### [CF2124E](https://codeforces.com/problemset/problem/2124/E) 好题 构造题没想到/kk 最多 次这个数字好奇怪没想到最多 次就可以 看了题解才做出了/kk 不过确实是好题目 从 推到任意情况（**特殊到一般**） 就可以构造出来，后面 3 步变成 2 步也很重要 [CODE](https://codeforces.com/problemset/submission/2124/338549353) ### [CF2112F](https://codeforces.com/problemset/problem/2112/F) Div 2 的 F 题都好难，前面有几道做不出来就换了 这题没想到转换 就是把**数组数值关系转换成图上路径** 然后条件转换成是否所有最短路径都是单条边到达的 然后就超好做了！！ [CODE](https://codeforces.com/problemset/submission/2112/338610497) ### [CF2113F](https://codeforces.com/problemset/problem/2113/F) 好 结论很好猜 构造感觉也挺好想到的直接二分图匹配就好了 题解的另一种做法没想到但是也特别聪明！！ （以下内容翻译自题解） > 基于数组中的值构建图：对于每个下标 ，在顶点 和 之间添加一条无向边。现在，我们需要为图中的边定向，使得每个度数至少为 的顶点至少有一条出边，并且每个度数至少为 的顶点至少有一条入边。如果第 条边被定向为从 指向 ，则令 。 > > 在每个连通分量中，以任意顶点为根构建 DFS 树。将所有树边从上向下定向，并将回边从下向上定向。容易看出，在这种构造下，除根节点外所有顶点都满足条件。对于根节点，仅当其度数至少为 且没有回边指向它时，条件不满足。此时，根节点至少有两个子树，只需选择其中一棵子树并将其中的所有边反向即可。 > > 这种构造方法可以达到上界，且可以在 时间内完成。 [CODE](https://codeforces.com/problemset/submission/2113/338620876) 最后修改：2025 年 10 月 19 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏