ABC370 DEF 题解
赛时过了 ABCD，补题的时候发现 EF 其实也是简单题，为什么就做不出来呢？E 这样简单的 dp 都做不出来，dp 必须得多练啊！
D - Cross Explosion
对于每一行、列，我们要用一个数据结构来维护未被删除的点，并且要快速找到某一行/列中是否存在某个数，以及查询某个数的前驱/后继。自然想到使用 set。
或许只看第一个要求：维护未被删除的点，会想到用链表。但链表的随机访问是线性复杂度的，不能快速查询某个数的位置。
然后直接按题意模拟即可。这一步主要考察对 set 的使用，刚好我这几天一直在加强学习 STL，感觉已经逐渐熟能生巧了，代码还是比较好看的（
代码实现上的一些细节：
-
可以用
set.lower_bound(x)来查询x是否存在。设返回的迭代器为it，如果存在，那么*it == x。如果不存在，那it就指向x的后继，prev(it)指向x的前驱。（这里说前驱后继指的是假设x存在，x的前驱后继。）用
set.find(x)也可以查询x是否存在，但是如果它不存在，用find()不好查找前驱后继。以及，不要用
algorithm库中的lower_bound()，要用set自带的lower_bound()，否则无法保证单次查找的时间复杂度是对数。 -
每次删除一个点，要同时在维护行和列的
set中删除。（一开始没注意到这个调了好久）
int n, m, q, cnt;
vector<set<int>> row, col;
void del(int x, int y)
{
cnt--;
auto it_row = row[x].find(y);
assert(it_row != row[x].end());
row[x].erase(it_row);
auto it_col = col[y].find(x);
assert(it_col != col[y].end());
col[y].erase(it_col);
}
int main()
{
cin >> n >> m >> q;
row.resize(n + 1), col.resize(m + 1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) row[i].insert(j);
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++) col[i].insert(j);
cnt = n * m;
for(int i = 1, x, y; i <= q; i++)
{
cin >> x >> y;
auto it_row = row[x].lower_bound(y);
if(*it_row == y) del(x, y);
else
{
if(it_row != row[x].begin()) del(x, *(prev(it_row)));
if(it_row!= row[x].end()) del(x, *it_row);
auto it_col = col[y].lower_bound(x);
if(it_col != col[y].begin()) del(*(prev(it_col)), y);
if(it_col != col[y].end()) del(*it_col, y);
}
}
cout << cnt << endl;
return 0;
}
E - Avoid K Partition
首先要想到用 dp，但是我连这一步都没想到，哈哈哈。
dp 还是得多做啊。
设 \(f(i)\) 表示 \(A_1 \sim A_i\) 的合法划分方案数。易得转移方程：
\[f(i) = \sum_{j=0}^{i-1} [\operatorname{sum}(j+1 \dots i) \not= K] \times f(j) \]这里注意一下初始化的问题：我们应初始化 \(f(0) = 1\)。为什么呢？可以从转移的角度考虑：\(j = 0\) 时，我们考虑 \(1\dots i\) 这一段的和。如果和不为 \(K\)，我们就加上 \(f(0)\)，这就相当于已知把 \(1 \dots i\) 当成一整段时，问 \(1 \dots i\) 划分的方案数——显然就是 \(1\)。
用上面这个转移方程转移是 \(O(N^2)\) 的。考虑优化。
求 \(f(i)\) 时，我们相当于是在 \(0 \le j < i\) 中寻找那些使得 \(\operatorname{sum}(j+1 \dots i) \not= K\) 的 \(j\)。用 \(\operatorname{sum}\) 表示前缀和，就相当于寻找那些使得 \(\operatorname{sum}(j) \not= \operatorname{sum}(i) - K\) 的 \(j\)，然后求这些 \(f(j)\) 的和。
于是可以设 \(M(x)\) 表示当前（枚举到 \(i\) 时）所有使得 \(\operatorname{sum}(j) = x\) 的 \(f(j)\) 的和，那么转移方程可以改写成：
\[f(i) = \left(\sum_{j = 0}^{i-1} f(j) \right) - M(\operatorname{sum}(i) - K) \]同时再维护一下 \(M\) 即可：\(M(\operatorname{sum}(i)) \gets M(\operatorname{sum}(i)) + f(i)\)。初始化 \(\forall x, M(x) = 0\)。\(M\) 可以用 map 维护。（用 map 的话，实际上可以不用初始化，因为 map 保证第一次访问 \(M(x)\) 时它的值为 \(0\)。）总时间复杂度 \(O(N \log N)\)。
f[0] = 1;
ll all = 1;
map<ll, ll> mp;
mp[0] = 1;
for(int i = 1; i <= n; i++)
{
f[i] = ((all - mp[sum[i] - K]) % MOD + MOD) % MOD;
all = (all + f[i]) % MOD;
mp[sum[i]] = (mp[sum[i]] + f[i]) % MOD;
}
细节：作为 map 下标的数（这里是 sum[i] - K）是不能取模的，原因一是它不会爆 long long，二是不同的数取模的结果可能相同，可能导致冲突（我就因为这个爆了）。
F - Cake Division
题目大意：有一个环状序列，要把它分成 \(K\) 段。设每段的权值为该段中所有数的和，你需要最大化最小的权值。可能有多种划分方案使得最小权值最大，你还需要求出在这些划分方案中，有哪些地方从未被划开过。
因为一些细节调了很久（恼）
先考虑如何求出最大的最小权值。
题目是个环，有点麻烦。先考虑序列是个链时怎么做。这时显然有一个简单的二分：设 \(x\) 表示最小值，然后可以 \(O(N)\) 地判定在每一段的和都大于 \(x\) 的情况下，能否把序列分为至少 \(K\) 段。
到了环上，一个经典的 trick 是断环成链：把原序列复制接在它自己的后面。然后，我们还是想到二分，但不能用上面的方法判定了。
设 \(f(i)\) 表示在 \(i + 1 \sim 2\times N + 1\) 范围内，第一个使得 \(\operatorname{sum}(i\dots f(i)-1) \ge x\) 的数。换句话说，如果 \(i\) 是某一段的开头，这一段至少要到 \(f(i) - 1\) 结束才能满足该段的权值不小于 \(x\)，\(f(i)\) 就是这一段的下一个位置。（这里定义的 \(f(i)\) 往后挪了一位，主要是为了方便后续操作。当然不挪这一位也是可以的。）如果不存在这样的数，则 \(f(i) = +\infty\)。运用双指针的技巧，\(f(i)\) 可以在 \(O(N)\) 的时间内求出。
\(f(i)\) 的妙处在于它是可以自身复合的：\(f(f(i))\) 表示从 \(i\) 开始找两段以后的下一个位置，同理 \(f^{K}(i)\) 就表示从 \(i\) 开始找 \(K\) 段以后的下一个位置。于是，只要存在 \(1 \le i \le N\) 使得 \(f^{K}(i) \le N + i\)，此时的 \(x\) 就是可行的。而 \(f^{K}(i)\) 可以通过倍增在 \(O(N \log K)\) 的时间内求出。
这里要注意一下 \(+\infty\) 的问题：实现时，\(+\infty\) 应该是一个比所有的 \(f(i)\) 都大的数，而 \(f(i) \le 2 \times N + 1\)，所以 \(+\infty\) 可以设为 \(2 \times N + 2\)。另外，我们得保证 \(f(1 \dots 2\times N + 2)\) 中所有的数都有值，所以初始化 \(f(2\times N+1) = f(2 \times N + 2) = 2 \times N + 2\)。
接下来考虑第二个问题。
直接考虑并不容易。我们可以先求出：有多少个地方，断开之后能满足条件？这是容易的，沿用上文中的方法：只要 \(f^{K}(i) \le N + i\)，那么 \(i\) 和 \(i-1\) 之间就可以断开，同时满足最小权值不小于 \(x\)。又因为我们总共有 \(N\) 个地方可以断开，所以用 \(N\) 减去这个数就是答案。
int n, K;
cin >> n >> K;
vector<int> a(n + 1), sum(2 * n + 1);
for(int i = 1; i <= n; i++)
{
cin >> a[i];
sum[i] = sum[i-1] + a[i];
}
for(int i = n + 1; i <= 2 * n; i++)
sum[i] = sum[i-1] + a[i-n];
vector<vector<int>> f(2 * n + 3);
for(auto &vec: f) vec.resize(__lg(K) + 1);
auto check = [&](int x) -> int // 返回需要切开的切线的数量
{
for(int i = 1, j = 1; i <= 2 * n; i++)
{
while(j < 2 * n && sum[j] - sum[i - 1] < x) j++;
if(sum[j] - sum[i-1] >= x) f[i][0] = j + 1;
else f[i][0] = 2 * n + 2; // 相当于INF
}
f[2 * n + 1][0] = 2 * n + 2;
f[2 * n + 2][0] = 2 * n + 2;
int t = __lg(K);
for(int k = 1; k <= t; k++)
for(int i = 1; i <= 2 * n + 2; i++)
f[i][k] = f[f[i][k-1]][k-1];
int cnt = 0; // 能作为起点的点数
for(int i = 1; i <= n; i++) // 枚举每个点，判断其是否能成为起点
{
int en = i;
for(int j = 0; (1 << j) <= K; j++)
if(K & (1 << j)) en = f[en][j];
if(en <= n + i) cnt++;
}
return cnt;
};
i64 l = 0, r = sum[n], ans = -1;
int cnt = -1;
while(l <= r)
{
i64 mid = (l + r) >> 1;
int res = check(mid);
if(res != 0) // 可行（至少有一个解）
{
l = mid + 1;
ans = mid, cnt = n - res;
}
else r = mid - 1;
}
cout << ans << ' ' << cnt << endl;