SDU暑期集训排位（4）
C. Pick Your Team
题意 有 (n) 个人，每个人有能力值，A 和 B 轮流选人，A 先选，B 选人按照一种给出的优先级，
A 可以随便选。A 想最大化己方能力值。
做法
- 划分方案合法的充要条件：任何前缀中，(被 B 选择的人 - 被 A 选择的人 > -1)
- 考虑 DP，(dp[i][j]) 表示考虑前 (i) 个人，(j) 个人被 B 选择了，A 和 B 最大分差。
- 考虑转移，枚举 (i+1) 个人归属即可。
D. Piece of Cake
题意 一个凸多边形上随机选k个顶点，求构成的凸多边形的面积的期望
做法
- 看成总面积减去一些由连续的几个点组成的多边形的面积
- 由x个点组成的多边形被减去的概率为(frac{C_{n-x}^{k-2}}{C_n^k})
- 这个概率要先约一约再算，而且要乘除交替计算，否则会爆精度
- 没注意复杂度T两发实属智障
E.Busy Board
题意 砸
做法
各种特判套在一起就行了，无法用语言描述
F. It's a Mod, Mod, Mod, Mod World
题意 求 (sum_{i=1}^{n}[pi\%q])
做法
- GCD 的经典应用。
- (sum_{i=1}^{n}[pi\%q] = sum_{i=1}^{n} (pi-[frac{pi}{q}]q)=(sum_{i=1}^{n}pi)-q(sum_{i=1}^{n}[frac{pi}{q}]))
- 只需求 (f(n,p,q)=sum_{i=1}^{n}[frac{pi}{q}])
- 若 (pgeq q) 可递归到 (f(n,p\%q,q))
- 若 (p<q) 可枚举 (x)，统计 ([frac{pi}{q}]geq x) 的 (i) 方案数，即可交换 (p,q)
- 更详细介绍见2009年论文 金斌《欧几里得算法的应用》
G.Monotony
题意 给定一个矩阵，问其有多少个子矩阵满足行列单调性
题解
- 枚举选哪些行
- 特判哪些列在选了这些行之后是合法的
- 考虑到，只选两列就能确定行的单调性，所以可以(DP)
- (DP[mask][j]) : 选了第(j)列，并且行的单调性为(mask)的方案数
- 然后枚举下一个(k),往后转移即可
I.Intersecting Rectangles
题意 给定n个矩形，问是否有交
做法
- 扫描线
- 从小到大枚举横坐标，如果是矩形左边界，查询上下边界内是否有点被标记，有的话直接输出yes，否则把上下边界打上标记，如果是右边界，消去边界
- 然后交换x,y坐标，再来一次
J. Cutting Strings
upsolved
题意 给一个字符串，可以截取下 (k) 段，使得字典序最大。
做法
- idea 比较简单，逐位考虑，我们先想让 'z' 字符的前缀尽可能长，以此为前提接下来想让之后的 'y' 尽可能长........
- 递归地求解 (solve(pos,k,ch))，在 (suffix(pos)) 中，我们想构造尽可能长的
ch前缀，至多可以切 (k) 刀。- 如果 s[pos] = ch，第一段连续的 ch 一定可以拿，我们可以递归到 (solve(nex,k,ch)),(nex) 为下一个不为 ch 的位置。
- 否则，考虑连续的 ch 的段，设这些段分别为 ([l_1,r_1],[l_2,r_2]....[l_m,r_m])
- 如果 (k geq m)，那么这些 (suffix(pos)) 中所有的 (ch) 都可以加入到答案中，递归到 (solve(r_m + 1, k-m, ch-1))
- 否则，我们可以在这 (m) 段中，枚举最后一个区间的位置，堆维护前 (k-1) 大值，再枚举最后一个区间的位置，在可能成为答案的后缀中挑选字典序最大的即可。
K. Subsequences in Substrings
做法 序列自动机，预处理位置 (x) 下一个字符 (ch) 在哪，枚举起点，然后往后跳。复杂度 (O(|S|*|T|))
M. XOR Sequences
upsolved
题意 给定(p_0,p_1,...,p_{2^m-1})求有多少长度为n的序列({x})满足(p_i=argmax i⊕x_j)
做法
- 考虑从顶向下建x的trie树
- 对于当前点，如果左树和右树的每个元素对应相等，那么只有左儿子或者只有右儿子，答案乘2，然后递归建左儿子或右儿子
- 不是对应相等的话说明既有左儿子又有右儿子，需要左树和右树的元素没有交集，然后递归建左儿子和右儿子
- 此题原榜过穿了，是个简单题，就是看起来很吓人
- 当时一看就没思路，其实算下样例也就会了