A
结论题。
容易做差去考虑，设 \(c_i=a_i-b_i\)，每次操作就是在 \(c\) 序列上选择 \(k\) 个位置，奇数位 \(+1\)，偶数位 \(-1\)。这并不会改变区间和，所以有解的必要条件是区间和为 \(0\)。
这还不够，转化到前缀和上考虑，我们发现操作只会让前缀和变大，所以另一个条件就是任意位置的前缀和小于等于 \(0\)。
考虑最少的操作次数，再分析操作，每一次操作可以让前缀和上若干区间 \(+1\)，并且由于有解，区间最后一个位置前缀和 \(c_i\) 一定为 \(0\)，可以构造一组方案，使得答案为区间前缀和最小值的相反数。
维护区间最大/小值复杂度 \(O(n\log n)\)。
B
写过了。简单状压。
C
区间 dp。
写过了。可行性问题的主要优化方式就是把状态内存的 \(0/1\) 换为最优位置等更好的信息，分段维护信息，减小复杂度。
D
写过了。简单状压。
E
图论题。
首先根据内向基环树的充要条件：
具有 \(n\) 个点 \(n\) 条边的联通块，任意节点有且只有一条出边
所以从内向基环树上考虑，最终的答案一定是一个环，也就是每个点有且仅有一条入边。
将树断成若干链，要使答案最优，考虑贪心，每个节点独立，所以保留代价最大不删即可。
然后发现在环上的点有时是错的：如果环上所有边都保留，那么就不是链了。
所以环上至少断一条边，这条边一定是改变后答案增加最小的边。
复杂度 \(O(n)\)。
F
简单状压。
G
状压 dp。
实数范围内的随机显然一点思路都没有，考虑转化条件。
人类智慧：设 \(y_i=x_i-0.5\)，那么限制就变成：
- \(y_i+y_j\le0\)
- \(y_i+y_j\ge0\)
这两个式子的判断实际上只与绝对值大的数有关。具体的说：不妨设 \(|y_i|\le|y_j|\)，那么 \(y_i+y_j\le0\) 的充要条件就是 \(|y_j|\le 0\)。这样每个位置就只关心正负性了，脱离实数就好做了。
这启发我们按绝对值从小到大考虑 \(y_i\)，这样每条限制就只和前面的数相关了。考虑状压，设 \(f_s\) 表示考虑了当前集合 \(s\) 中的位置的满足限制（只考虑集合中相互的限制）的方案数。转移枚举集合中的最大值满足限制下是取正还是取负。
考虑这样的方案数实际上是啥。实际上是长度为 \(n\) 的 \(01\) 串从小到大考虑后满足限制的方案数。每个 \(1\) 数量相同的 \(01\) 串有 \(n!\) 种排列，而满足大小关系的排列只有 \(1\) 种，所以总共的情况为 \(2^nn!\) 种，答案需要除以 \(2^nn!\)。
标签：0725,前缀,--,复杂度,状压,盖世,区间,考虑 From： https://www.cnblogs.com/FireRaku/p/18332291