点击打开题目列表

• A. 直接输出
• B. 2018 = 2 * 1009，分开考虑 2 和 2019. 考虑 2 时，矩阵只有 2 和 1 两种元素，它们的分界线是一条从 (0, 0) 到 (n, m) 的最短路径（不能经过 (n, 0)），最终方案数是 ((n+m)!/n!/m!−1)².
• C. 一定需要预留 h-1 的额外燃料，所以答案是 max(h, c + 1).
• D. 前两种和后两种互不影响，分开处理。以前两种举例，冲突的情况一定是形如

^ ^ ^ ^
 v v v ...如果链长度是 x，那么对答案的贡献就是 x/3.

• E. 如果有 h 条不同的横线，v 条不同的竖线，答案就是 n * m − (m−1) * h − (n−1) * v + (h−1) * (v−1). 只需要用线段树（或者其他类似结构）维护不同的竖线、横线的数量即可。
• F. 先模拟一遍，把置换搞出来，然后注意到不同置换的长度是 O(sqrt{n}) 的，每种长度置换把贡献算一下就行。
• G. 考虑把数字从小往大填，用 dp(mask) 表示还有 mask 这些位置没填，那么填进去的时候只要看一下它周围有多少个填过/没填的，就能知道跟它有关的绝对值有拆开有多少个取正有多少个取负，直接把贡献加上就行。
• H. 对于 r − l = 0, 1, 2 分别维护一个树状数组即可。
• I. 首先当 k 比较小时，可以用经典的 O(3^k+2^km) 的斯坦纳树 DP。当 k 比较大时，可以 2^n − k 剩下的点要不要，直接跑最小生成树。两个算法拼一下就行。
• J. 先考虑序列上怎么不算重，方法是相同的元素取靠后的那个，也就是对于每种元素最后出现的位置，数一下它之前出现的不同元素数量。dfs 的时候维护一下这个即可。
• K. 答案是 ∑_{L <  = i + j <  = R}a[i] * b[j]. 枚举 i，就变成求 j 的区间和。