A \((\texttt{Easy} \ 2 / 0)\)
模拟即可。
B \((\texttt{Easy} \ 2 / 0)\)
若图不是二分图则无解，否则令每个点的标号为其到某个点的距离才可保证相邻点的标号差 \(= 1\)，所以答案即 \(\max d_{u, v}\)。
C \((\texttt{Easy} \ 3 / 1)\)
设 \(s^F\) 表示把 \(s\) 每一位翻转后得到的字符串。发现题目的操作等价于一个长度为 \(n\) 的滑动窗口在 \(ss^F\) 上不断向右移动。所以移动 \(k\) 次以后回到 \(s\) 等价于 \(ss^F\) 存在长度为 \(k\) 的循环节，所以 \(k \mid 2n\)。但是 \(k \nmid n\)，因为这样的话这个循环节 \(r\) 就要与 \(r^F\) 相等了，这是不可能的。
于是我们能发现 \(r\) 又可以被拆为 \(tt^F\)，只剩下 \(\le X\) 这一个限制条件了，而这是易于判断的。再加个容斥即可计算答案。
时间复杂度 \(\mathcal{O}(n \sigma_0(n))\)。
D \((\texttt{Medium} \ 4 / 0)\)
在这里，你甚至可以学习隔壁 MO 平几。
平几的东西忘光了 /ll/ll
可以通过一些转化和欧拉线证明如下结论：
- 对于 \(\triangle ABC\)，其内心坐标即三条边对应的劣弧中点坐标之和。
直接做就可以做到 \(\mathcal{O}(n^2)\)；使用和差化积可以优化至 \(\mathcal{O}(n)\)。
E \((\texttt{Medium} \ 5 / 0)\)
令 \(n = 2N\)，设 \(f_{l, r, k}\) 表示仅考虑 \([l, r]\) 内部的点，只有 \(k\) 与 \([l, r]\) 外的点连边的方案数，则 \([l, r]\) 中必有跨过 \(k\) 那条边的边，又因为其不相交，可以设其中左端点最小、右端点最大的一条为 \((x, y)\)，那么 \([x, k)\) 中肯定有一个前缀是首先和 \(x\) 连通的、剩下的后缀是首先与 \(k\) 连通的；\((k, y]\) 类似。我们设这两个分界点为 \(p, q\)，则有转移：
直接枚举 \(l, r, k, x, y, p, q\)，时间复杂度 \(\mathcal{O}(n^7)\)，因为极小的常数可以轻松通过。
考虑变换枚举顺序，改为首先枚举 \(p, q\) 再枚举 \(k\)，则可以使用另一个 dp 优化计算过程，时间复杂度 \(\mathcal{O}(n^5)\)。
F \((\texttt{Medium} \ 6 / 0)\)
感觉第一步比较难想到，但是好像没有 Au 的难度？
设 \(x_i = \min_j{a_{i, j}}, y_j = \min_i{a_{i, j}}\)，则 \(f(x, y) = \min\{x_i, y_j\}\)。假设我们已经确定了 \(x, y\)，考虑寻找一种快速计算权值的方式。
把 \(x, y\) 从小到大排序之后依次考虑每个数。假设在当前的数之前已经有了 \(u\) 个来自 \(x\) 的数和 \(v\) 个来自 \(y\) 的数，则
- 若当前的数 \(t\) 来自 \(x\)，则它可以限制 \(v\) 个数，答案乘以 \(t ^ {m – j}\)；
- 若当前的数 \(t\) 来自 \(y\)，则它可以限制 \(u\) 个数，答案乘以 \(t ^ {n – i}\)。
想到这里就基本上比较简单了。我们考虑容斥，即限制变为「第 \(i\) 行的最小值 \(\ge / > x_i\)」以及「第 \(j\) 列的最小值 \(\ge / > y_j\)」。从小到大添加 \(x, y\)，我们考虑设 \(f_{t, u, v}\) 表示考虑加入 \(\le t\) 的 \(x\) 和 \(y\)，其中 \(x\) 中有 \(u\) 个且 \(y\) 中有 \(v\) 个的所有方案数乘以系数之和，首先考虑加入 \(x\)，根据钦定 \(\ge\) 或 \(>\) 可以得到两种转移：
加入 \(y\) 的情况类似，注意转移的顺序。
时间复杂度 \(\mathcal{O}(nmk(n + m))\)。
原文地址：http://www.cnblogs.com/Scintilla/p/16861350.html
