Day4
Gp
原题: Joi 2012 Kangaroo
(300) 个套娃, 容量 (Contain) 一定小于体积 (Size), 一个匹配是指不存在还有套娃能放在另一个套娃中的情况. 给出每个套娃的 (Size) 和 (Contain), 求合法的不同的匹配情况数量对 (10^9 + 7) 取模的结果.
考场思路: 把每个套娃拆成两个点, 一个是它的 (Size), 一个是它的 (Contain), 形成一个二分图, 每个 (Size) 点向能装下它的 (Contain) 点连边.
排序不亏: 分别排序 (Size) 和 (Contain), 由于排序后, (Size) 自增, 所以可以直接将 (Size) 小的点的边的后继连到相邻的 (Size) 比它大的点的 (Fst) 上, 这样实际连接的边数就是 (O(n)) 条, 就能完成 (O(n^2)) 种转移.
大暴搜: 枚举每个 (Size) 点, 在当前能选的转移边里选一个来匹配, 当然什么都不选也是一种情况, 每次到边界的时候, 判断是否有可用的边没连, 如果有, 则匹配情况不合法, 否则统计一次.
欣赏一下考场大暴搜:
unsigned n, m, Ans(0), The(0), Sq;
char flg(0), Ed[305];
struct WN {
unsigned Size, Contain;
const inline char operator<(const WN &x) const{
return this->Size > x.Size; }
}W[305];
struct Node {
Node *Fst, *Nxt; char Have;
}N[605];
char Judge () {
for (register unsigned i(n); i; --i)
if(!(N[i].Have)) {
register Node *now(N[i].Fst);
while (now) {
if(!(now->Have)) return 0;
now = now->Nxt; }
return 1; }
return 1;
}
unsigned long long BigDFS(Node *x) {
if(x > N + n) return Judge();
register unsigned long long CntCases(BigDFS(x + 1));
register Node *now(x->Fst);
x->Have = 1;
while(now) {
if(!(now->Have))
now->Have = 1, CntCases += BigDFS(x + 1), now->Have = 0;
now = now->Nxt; }
x->Have = 0;
return CntCases % MOD;
}
int main() {
n = RD();
for (register unsigned i(1); i <= n; ++i)
W[i].Size = RD(), W[i].Contain = RD();
sort(W + 1, W + n + 1);
for (register unsigned i(1); i <= n; ++i) {
N[i].Fst = N[i - 1].Fst;
for (register unsigned j(1); j <= n; ++j)
if(!Ed[j]) if(W[j].Contain > W[i].Size)
N[j + n].Nxt = N[i].Fst, N[i].Fst = N + j + n, Ed[j] = 1; }
printf("%llu
", BigDFS(N + 1));
return 0;
}
考试结束的时候发现, 由于连边单调性, 用数组代替边表, 左部点右部点分别存入不同的数组, 只存 (Size_i) 能连接的 (Contain) 最小的右部点.
unsigned n, m, Ans(0), The(0), Sq;
char flg(0);
struct NodeS;
struct Node {
NodeS *Fst; unsigned Size; char Have;
const inline char operator <(const Node &x) const {
return this->Size < x.Size;}
}N[305];
struct NodeS {
unsigned Contain; char Have;
const inline char operator <(const NodeS &x) const{
return this->Contain < x.Contain;}
}NS[305];
char Judge () {
for (register unsigned i(1); i <= n; ++i)
if(!(N[i].Have)) {
for (register NodeS *j(N[i].Fst); j <= NS + n; ++j)
if(!(j->Have)) return 0;
return 1; }
return 1;
}
unsigned long long BigDFS(Node *x) {
if(x == N) return Judge();
register unsigned long long CntCases(BigDFS(x - 1));
x->Have = 1;
for (register NodeS *i(x->Fst); i <= NS + n; ++i) if(!(i->Have))
i->Have = 1, CntCases += BigDFS(x - 1), i->Have = 0;
x->Have = 0;
return CntCases % MOD;
}
int main() {
n = RD();
for (register unsigned i(1); i <= n; ++i)
N[i].Size = RD(), NS[i].Contain = RD();
sort(N + 1, N + n + 1), sort(NS + 1, NS + n + 1);
N[n + 1].Fst = NS + n + 1, NS[n + 1].Contain = 0x3f3f3f3f;
for (register Node *i(N + n); i > N; --i) {
i->Fst = (i + 1)->Fst;
while((i->Fst - 1)->Contain > i->Size) --(i->Fst);
}
printf("%llu
", BigDFS(N + n));
return 0;
}
接下来是正解: DP
仍然是一个套娃拆成两个独立的点, (Size) 和 (Contain) 分别排序.
定义 (CntAfter_{i, j, k}) 指的是在 ([i, j]) 中可供 (Size_k) 选用匹配的 (Contain) 数量, 也就是满足 (Contain_x > Size_k, x in [i, j]) 的 (x) 数量.
定义 (CntBefore_{i, j, k}) 指的是在 ([i, j]) 中可以匹配 (Contain_{k}) 的 (Size) 数量, 也就是满足 (Contain_k > Size_x, x in [i, j]) 的 (x) 数量.
枚举一个分界点 (Mid), 作为从从左到右第一个没有匹配的 (Size), (Size_{Mid}) 没有任何匹配, 这时, (Contain_i > Size_{Mid}) 都应该有匹配, 否则如果有 (Contain_i > Size_{Mid}) 且没有匹配, 那么 (Size_{Mid}) 和 (Contain_i) 就可以匹配, 原方案不合法. 对于 (Size_x, x in [1, Mid - 1]), 都一定有匹配, 这是 (Mid) 的定义.
对于 (i, j in [1, Mid - 1]), (Size_i) 和 (Contain_j) 互相匹配后的方案数可以通过 (O(Mid^2)) 的 DP 求出, 设 (f_{i, j}) 表示对于 ([i, Mid - 1]) 的 (Size) 和 ([1, Mid]) 的 (Contain) 一共有 (j) 对匹配的方案数, 写出方程:
解释: (f_{i + 1, j}) 是第 (Size_i) 不进行匹配的贡献, (CntAfter_{1, Mid, i} - j + 1) 是可供选择的数量减去已经选择的数量, 也就是当前的选择数量, 乘法原理是因为不管是 (f_{i + 1, j - 1}) 包含的哪种情况, 都有这么多选择.
接下来, 设 (Left) 为满足 (Contain_{Left} > Size_{Mid}) 的最小下标. 接下来是 (g_{i, j}) 表示对于 ([Left, i]) 的 (Contain) 和 ([Mid + 1, n]) 的 (Size) 一共有 (j) 对匹配的方案数, 写出方程:
解释: 和 (f_{i, j}) 对称, 非常漂亮.
好了, 求得了 (f) 和 (g), 接下来对于枚举到的 (Mid) 对答案进行计算. 枚举一个 (i), 表示 (Size_x, x in [1, Mid - 1]) 匹配 (Contain_y, y in [Left, n]) 的对数. 这时的合法情况的数量应该是 (f_{1, Mid - i - 1} * g_{n, n - Left + 1 - i} * i!), 因为 ([1, Mid - 1]) 中, 有匹配的 (Size) 应该是 (Mid - 1) 也就是全部匹配, 所以需要和 (Contain_x, x in [Left, n]) 匹配, 而这根据单调性是可以随便连的, 而 (i) 的全排列恰好是 (i!), 所以加入 (Ans) 即可.
被改得面目全非的 AC 代码:
unsigned n, Size[305], Contain[305], CntAfter[305], CntBefore[305], f[305][305], g[305][305], Left, Factorial[305];
unsigned long long Ans(0);
char flg(0);
int main() {
n = RD(), Factorial[0] = 1;
for (register unsigned i(1); i <= n; ++i) Size[i] = RD(), Contain[i] = RD();
for (register unsigned i(1); i <= n; ++i) Factorial[i] = (unsigned long long)Factorial[i - 1] * i % MOD;
sort(Size + 1, Size + n + 1); sort(Contain + 1, Contain + n + 1);
f[n][0] = 1;
g[1][0] = 1;
Contain[n + 1] = 0x3f3f3f3f;
Left = 1;
for (register unsigned Mid(1); Mid <= n; ++Mid) {
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
CntAfter[Mid] = CntBefore[Left - 1] = 0;
for (; Contain[Left] <= Size[Mid]; ++Left) {}
for (register unsigned i(Mid - 1); i; --i) {
CntAfter[i] = CntAfter[i + 1];
while (Size[i] < Contain[Left - CntAfter[i] - 1]) ++CntAfter[i];
}
for (register unsigned i(Left); i <= n; ++i) {
CntBefore[i] = CntBefore[i - 1];
while(Size[Mid + 1 + CntBefore[i]] < Contain[i]) ++CntBefore[i];
}
f[Mid][0] = 1;
for (register unsigned i(Mid - 1); i; --i) {
f[i][0] = f[i + 1][0];
for (register unsigned j(1); j <= CntAfter[i]; ++j) {
f[i][j] = f[i + 1][j]; // 不拿
f[i][j] += (unsigned long long)f[i + 1][j - 1] * (CntAfter[i] - j + 1) % MOD; // 拿
if(f[i][j] >= MOD) f[i][j] -= MOD;
}
}
g[Left - 1][0] = 1;
for (register unsigned i(Left); i <= n; ++i) {
g[i][0] = g[i - 1][0];
for (register unsigned j(1); j <= CntBefore[i]; ++j) {
g[i][j] = g[i - 1][j];
g[i][j] += (unsigned long long)g[i - 1][j - 1] * (CntBefore[i] - j + 1) % MOD;
if(g[i][j] >= MOD) g[i][j] -= MOD;
}
}
for (register unsigned i(min(n - Left + 1, Mid - 1)); i < 0x3f3f3f3f; --i)
Ans += ((unsigned long long)f[1][Mid - 1 - i] * g[n][n - Left + 1 - i] % MOD) * Factorial[i] % MOD;
}
printf("%llu
", Ans % MOD);
return 0;
}
考后从 (19:00) 写到 (24:00), 第二天从 (5:30) 写到 (7:00), 中午又写了 (30min) 才过, 本来无脑 DP 竟然有这么多细节...
其实这个题能 (O(4n^2)) 做, 将拆点后的 (O(2n)) 个点放到一起排序. 然后在这上面跑序列 DP, (O(n^2)) 状态, (O(1)), 转移.
Of
在 (n*m) 网格上选择尽量多的格点 (必须包含 ((0,0)) 和 ((n, m))), 依次连接形成下凸包, 求点数.
考场上一眼看到这个题可以剪枝暴搜. 正解想推式子 (O(n^2)) 预处理, (O(1)) 回答询问. 答案的分布看起来像是反比例函数, 可是连 (Geogebra) 都找不到规律.
最后还是交的暴搜:
unsigned n, m, t;char flg(0);
unsigned DFS(unsigned x, unsigned y, unsigned Beforex, unsigned Beforey) {
if(x == 1 || y == 1) if((x * (Beforey - y)) > (y * (Beforex - x)))
return ((x * (Beforey - y)) > (y * (Beforex - x))) ? 2 : 0;
unsigned CntPnt(2);
for(register unsigned i(x - 1), Top(y - 1), Bot(y - 1); i; --i) {
while (((y - Top) * x) <= ((x - i) * y)) --Top;
while (Bot && (((x - i) * (Beforey - y)) > ((y - Bot) * (Beforex - x)))) --Bot;
++Bot;
if(((x - i) * (Beforey - y)) <= ((y - Bot) * (Beforex - x))) break;
for (register unsigned j(Bot), TmpD; j <= Top; ++j) {
TmpD = DFS(i, j, x, y) + 1;
if(TmpD > CntPnt) CntPnt = TmpD;
}
}
return CntPnt;
}
int main() {
t = RD();
for (register unsigned T(1); T <= t; ++T) {
n = RD(), m = RD();
if(((m * (m + 1)) >> 1) <= n) {printf("%u
", m + 1); continue;}
printf("%u
", DFS(n, m, n + 1, 6000));
}
return 0;
}
正解是枚举 (O(n^2)) 个横纵坐标互质的二维向量, 然后枚举选择哪些向量, 让它们的和等于 ((n, m)), 直接写是 (O(n^4)). 通过剪枝将向量数量压到 (O(n^{frac 23})) 这样复杂度就压到了 (O(n^{frac 73})).
Dls
一个序列, 两端是 (infin), 每个元素有对应的点, 每个元素 (i) 的点向它左边第一个值 (geq a_i) 的元素或右边第一个 (> a_i) 的元素连无向边.
支持单点修改, 每次修改求无向图上不同的六元环个数.
由于此题难度过于离谱, 以至于手玩都不会求静态六元环, 更别说带修计数了, 所以直接就没写.
Bitset Master
一棵集合构成的树, 一开始每个节点对应的集合之有一个元素, 也就是这个点, 支持:
查询包含点 (x) 的集合数
将树上的某条边两端的集合设为这两个集合的并
考虑一个集合 (x) 包含点 (y) 的条件. 必须存在一个操作序列, 依次合并 (y) 到 (x) 路径上每条边.
离线. 从上往下, 用 DP 求出每个点被根的集合包含的最早时间, 自己最早到根的时刻是到父亲之后, 父亲的最早的到根的操作序列的时刻.
将每个点按到根时间排序, 容易知道后代一定不会比祖先提前到达. 根不同的子树中的节点要想包含对方, 必须先到达根. 使用点分治 + 扫描线 + DFS 维护, 总复杂度 (O((n + m)log^2n))
Cyclic Distance
边带权的树, 求一个包含 (k) 个点的点集, 求一个点集中点的排序, 使相邻两点的距离和的最小值 (规定点 (1) 和点 (k) 相邻).
枚举点集的重心, 再构造出以这个点为重心的点集, 然后再求最小距离和.
考虑优化, 一个节点的子树大小超过这个点的子树的一半, 则要重心在这个子树中不会使答案更劣. 用数据结构可以优化到 (O(nlogn)).