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\) 个人归属即可。
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}]\)
- 若 \(p\geq q\) 可递归到 \(f(n,p\%q,q)\)
- 若 \(p<q\) 可枚举 \(x\)，统计 \([\frac{pi}{q}]\geq x\) 的 \(i\) 方案数，即可交换 \(p,q\)
- 更详细介绍见2009年论文 金斌《欧几里得算法的应用》
I.Intersecting Rectangles
题意 给定n个矩形，问是否有交
做法
- 扫描线
- 从小到大枚举横坐标，如果是矩形左边界，查询上下边界内是否有点被标记，有的话直接输出yes，否则把上下边界打上标记，如果是右边界，消去边界
- 然后交换x,y坐标，再来一次
K. Subsequences in Substrings
做法 序列自动机，预处理位置 \(x\) 下一个字符 \(ch\) 在哪，枚举起点，然后往后跳。复杂度 \(O(|S|*|T|)\)
SDU暑期集训排位（4）
原文：https://www.cnblogs.com/FST-stay-night/p/11299153.html
