A,B略
C - Fair Elevator
如果出现重复的\(A,B\)或者\(A>B\)则显然不合法.
根据题意知道可以将整个序列分成若干长度为偶数的段\([i,i+2L)\),每一段中每个人都是从\(j\)出发到\(j+L(j\in[i,i+L))\).
区间DP,每个区间如果可以分成两个合法的子区间则该区间合法.
某个长度为\(2L\)的区间能单独作为一段存在当且仅当:
1.左半区间不出现\(B\),右半区间不出现\(A\);
2.如果其中的\(A,B\)是成对给出的,则它们必须相差\(L\);
3.如果其中的\(A,B\)相差\(L\),则它们必须是成对给出的.
复杂度为\(O(N^3)\).
D - Multiset Mean
考虑对每个\(x\)计算答案.
将除\(x\)以外的数都减去\(x\),答案就是这些数的多重集(可以为空)和为\(0\)的方案数乘上\((K+1)\)再减\(1\).
DP,\(dp[i][j]\)表示考虑完第\(i\)个数和为\(j\)的方案数,最后答案就是\(dp[N-1][0]\cdots(K+1)-1\).
需要使用前缀和将每个状态转移复杂度变成\(O(1)\),总的复杂度为\(O(N^4K)\),常数比较小.
E - Random LIS
枚举所有可能的顺序.如果两个数相等则认为排在前面的数比较大.
DP,\(dp[i][j]\)表示考虑第\(i\)大的数为\(j\)时的方案数,直接DP复杂度为\(O(NA_\max)\).
可以发现dp关于\(j\)是分段多项式函数,最多\(N\)段,每段次数最多为\(N\).
使用许多技巧可以完成计算,复杂度为\(O(N!N^4)\).
F - Visibility Sequence
不会.
总结:被C卡了一个多小时,E只剩20分钟写不出来.
原文：https://www.cnblogs.com/Heltion/p/13765687.html