想做但是没有时间做的题-口胡题解&留坑待填

## CF567F Mausoleum 从小到大填数字，每个数字要么都填右边，要么都填左边，要么一边一个；同时我们还可以知道每个位置的大小关系了，直接暴力判断； $f[i][j][k]$用了前i个数字，左边填了j，右边填了k的方案数； ## HDU4333 Revolving Digits 原串复制两遍，然后跑exKMP或Hash二分求出匹配长度，判断不匹配那一位的大小关系； ## [HNOI2010]公交线路 看到如此小的k，p，肯定是状压；看到如此大的n，肯定是矩阵乘法； 这道题的核心是初始位置已经确定，我们不用关系具体的数字，只用关心填了/没填； 但是，如何实现每p个位置，出现所有k种数字呢？方法是：一个位置一个位置的考虑；$f[i][S]$表示考虑到1~i-1，$[i,i+p-1]$的状态（填了/没填）的状态，且S中含有恰好K个1； 转移的话，为了防止重复，每次只移动最高位的1； ## CF506E Mr. Kitayuta's Gift 这是一道神题，大致意思是设$f[i,j,k]$表示，从两边向中间同时填了k个数，还剩$[i,j]$没有匹配；然后神奇地把转移矩阵转化为图论，然后神奇的讨论，弃了弃了； ## CF894E Ralph and Mushrooms 都是正权，所以肯定越多越好；一个强联通分量的边都可以消完，其余的缩点后拓扑排序； ## CF528C 给定一张无向图，添加最少的边，给每一条边定向，使得每个点的入度和出度都是偶数； ## 构造题有一个比较常见的思路：找一个答案的下界，然后尝试通过构造达到这个下界。 首先每个点的度数一定是偶数，我们可以先把度数是奇数的点两两连起来。然后边的个数一定是偶数，如果此时边的个数是奇数，那么还要加上一条边。这显然是一个答案的下界。 然后跑一边欧拉回路，交错定向就可以了； ## APIO2017 商旅 01分数规划，对每个城市对(u, v)，求出从u市购买到v市卖出 能获得的最大收益w。建一个新图，u到v的距离dis为原来的最短路的长度，边权为w。那么我们要求一个环，边权与环长比值最大。 ## HAOI2017 新型城市化 图可以被分为至多两个团$\to$ 反图是二分图；