CF1490G Old Floppy Drive
首先判断是否可以在第一圈就符合题意，记录前缀和 \(sum\) 和 \(mx\) 数组，其中 \(mx_{i}\) 为 \(sum\) 从起点到 i 的最大值，即 \(mx_{i}=\max(mx_{i-1},sum_{i})\)。
显然如果在第一圈就满足条件，就有 \(mx_{n}\ge x\)，lower_bound 一下即可。
如果无解，就有 \(mx_{n}<x\) 且 \(sum_{n}\le 0\)。
接下来就是循环多次的情况，二分一下走的圈数，对于二分出来的 \(mid\)，判断是否符合题意，即是否满足 \(mx_{n}+sum_{n}\times mid\ge x\)。
对于一个符合条件的圈数 \(mid\)，再特判一下最后一圈是否走满，lower_bound 一下即可。
CF1494C 1D Sokoban
显然分开讨论正负箱子，首先考虑正数。
记录前缀和 \(sum\)，表示从 \(0\) 开始，能推 \(sum_{i}\) 个箱子过来。再记录数组 \(in\)，表示在推箱子之前从 \(0\) 到 \(i\) 有 \(in_{i}\) 已经在特殊位置了。
接下来枚举每一个位置 \(i\)，对于每一个位置 \(i\)，再找到一个位置 \(j\)，表示将从 \(0\) 到 \(i\) 的所有箱子推到位置 \(i\)，这些推在一起的箱子的终止位置为 \(j\)，注意这里推来的箱子不止 \(sum_{i}\)，而应该是 \(sum_{j}\)，因为 \(i\) 到 \(j\) 的箱子也会被推过来，所以对于一个合法的 \(j\)，有 \(b_{j}-b_{i}+1\le sum_{j}\)。
显然位置 \(j\) 是单调的，二分即可。在枚举的 \(i\) 时，当 \(i\) 单调时，\(j\) 也一定单调，因为积累的箱子会越来越多，因此双指针即可。
CF1495B Let's Go Hiking
显然两人选择坡长的山坡更优。
首先明确赢得比赛的两种方法：
其一是两人在不同的山坡移动，当 \(D\) 已经到达终点而无法移动时，\(Q\) 还未到达终点，那么 \(Q\) 胜利。
其二是两人在同一个山坡移动，\(Q\) 将 \(D\) 的路堵上了，那么 \(Q\) 胜利。
对于先手 \(Q\)，他首先选择了一个最长的坡，然后轮到 \(D\)。
第一种情况：如果剩下的坡长都小于 \(Q\) 选择的坡。
显然如果 \(D\) 选择与 \(Q\) 不同的坡，他会因为这条路短于 \(Q\) 的路而率先到达终点导致无法取胜。因此他会选择和 \(Q\) 选择同一条路去堵 \(Q\)。如果这条坡的长度为奇数，\(D\) 在坡底即可，如果是偶数，在坡底往上选一格即可。所以这种情况 \(Q\) 无法胜利。
接下来第二种情况：轮到 \(D\) 选择时，剩下的坡有与 \(Q\) 选择的坡长度相等的。
如果这两条坡没有连在一起，那么 \(D\) 显然会选择这条路，此时 \(D\) 会因为是后手而取得胜利。
显然如果有多条这样的坡，与上面同理，\(D\) 必胜。（同时也说明答案只会是 \(0\) 或 \(1\)）
如果这两条坡连在一起，\(Q\) 在这两条最长坡的坡顶，显然这时 \(Q\) 想取胜只能去堵 \(D\)，当坡长为偶数时，\(Q\) 可以获胜。否则若为奇数 \(Q\) 会反被 \(D\) 堵住。
最后我们发现 \(Q\) 胜利的条件只有一个：有且仅有两条最长的坡，并且这两条坡连在一起且长度为偶数。
CF1512F Education
我们发现如果升到第 \(i\) 级最早是第 \(j\) 天才能实现，那么，可以证明在 第\(j\) 天升到第 \(i\) 级是升到第 \(i\) 级后一直攒钱买电脑的最优解。
证明
假设要升到第 \(i\) 级最早要在第 \(j\) 天才能实现，而我们选择在第 \(k(k>j)\)天实现，由于升到第 \(i\) 级所需的钱相同，所以我们只需比较获得的钱即可。由于 \(j\) 天前和 \(k\) 天后两种情况一致，不考虑，只考虑 \(j\) 到 \(k\) 这 \(k-j\) 天的情况。在这段时间中，选择在第 \(j\) 天升级获得的钱数是 \((k-j)\times a_{i}\)，而选择在第 \(k\) 天升级获得的钱数是 \((k-j)\times a_{i-1}\)，由于 \(a\) 是一个不降的序列，所以 \((k-j)\times a_{i}\ge (k-j)\times a_{i-1}\)，因此选择在第 \(j\) 天升级是最优解。
我们可以使用两个数组 \(k_{i}\) 表示升到 \(i\) 级需要的最少天数，\(w_{i}\) 表示最快升到 \(i\) 级剩余的钱数。
得到公式：
\(k_{i}=k_{i-1}+\lceil \frac{b_{i-1}-w_{i-1}}{a_{i-1}} \rceil\)
\(w_{i}=w_{i-1}-b_{i-1}+\lceil \frac{b_{i-1}-w_{i-1}}{a_{i-1}} \rceil\times a_{i-1}\)
于是我们可以求出升到第 \(i\) 级后一直攒钱买电脑所需的天数，取最小值即可。
CF1468J Road Reform
先做一遍最小生成树，如果最小生成树上有大于 \(k\) 的边，设第 \(i\) 条边边权为 \(s_{i}\)，答案直接等于 \(\sum \max(0,w_{i}-k)\)。
如果最小生成树上所有的边都小于 \(k\)，这时我们只需要将其中任意一条边删去，再加上一条边权最接近 \(k\) 的边即可。因为在最小生成树上加一条边，一定会形成一个环，再在这个环上随便删除一条边即可。答案就等于这条最接近 \(k\) 的边与 \(k\) 的差。
CF1475D Cleaning the Phone
我们可以将体积为 \(1\) 和 体积为 \(2\) 的物品分成两堆，并分别将这两堆按照价值从大到小排序，考虑到答案的一定是由两个序列各选一个前缀构成。
枚举在第一堆选择的个数，再二分在第二堆满足条件的最小前缀。
最后取最小值即可。
CF1500A Going Home
这道题直接暴力枚举即可，因为 \(a_{i}\le 2.5\times 10^{6}\)，所以两两相加的和不会超过 \(5\times 10^{6}\)。暴力枚举的时间复杂度为 \(O(n^{2},C)\)，其中 \(C\) 是值域。
CF1509C The Sports Festival
显然我们应该将 \(s_{min}\) 或 \(s_{max}\) 放到最后。
那么容易想到改变后的 \(s\) 序列前 \(i\) 个数在有序的 \(s\) 中一定是连续的一段。
因此，先将 \(s\) 排序，设计出状态，\(dp_{i,j}\) 表示前 \(j-i+1\) 个数是 \(s_{i}\) 到 \(s_{j}\) 的数。
所以转移就是 \(dp_{i,j}=\min(dp_{i+1,j},dp_{i,j-1})+s_{j}-s_{i}\)。（区间 dp）
CF1517D Explorer Space
首先当 \(k\) 为奇数时，显然无法回到原点，直接输出 \(-1\)。
由于走出 \(k\) 步之后要回到原点，所以只能向外走 \(\frac{k}{2}\) 步。又因为要求最小值，所以走出去和走回来经过的路径的一样的。
于是问题转化成了：从原点向外走 \(\frac{k}{2}\) 步的最小取值。
设 \(dp_{i,j,d}\) 表示从 \((i,j)\) 出发，走 \(d\) 步的最小取值，转移即可。
CF1525D Armchairs
从源点向每一个人连一条流量为 \(1\)，费用为 \(0\) 的边，每一个椅子向汇点连一条流量为 \(1\)，费用为 \(0\) 的边。
对于每一个 \(i\)，向点 \(i-1\) 和 \(i+1\) 连一条流量为 inf，费用为 \(1\) 的边，跑一遍费用流即可。（也可以用 dp 做）
CF1535D Playoff Tournament
设 \(tree_{i}\) 表示第 \(i\) 局可能获胜的个数，因为晋级规则都是二选一，所以可以用线段树合并信息求解。
首先我们把题干中的标号重新排序，将原本的标号 \(x\) 改为 \(2^{k}-x\)，这样每一局的比赛信息 \(i\) 都与第 \(2\times i\) 局和第 \(2\times i+1\) 局有关，与线段树编号相同，方便操作。
当 \(s_{i}=0\) 时，\(tree_{i}=tree_{i<<1|1}\)。
当 \(s_{i}=1\) 时，\(tree_{i}=tree_{i<<1}\)。
当 \(s_{i}=?\) 时，\(tree_{i}=tree_{i<<1}+tree_{i<<1|1}\)。
最后 \(tree_{1}\) 即为答案。