2024.10.12总结

标签：总结 连边 2024.10 12 frac sum leq hash 复杂度

本文于 github 博客同步更新

你他妈管这个叫 noip 模拟赛？

A：

对于上述整除式的一组解 \((c, s)\) ，在 \(c \leq a \leq A\) 且 \(s \leq b \leq B\) 时，会被统计入答案，因此它对答案的贡献为 \((A-c-1)(B-s-1)\) 。

在 \(s>x\) 时，注意到 \(\frac{s}{s+x}>\frac{1}{2}\) ， \(\frac{c}{c+x}<1\)，因此 \(k=\frac{\frac{c}{c+x}}{\frac{s}{s+x}}<\frac{1}{\frac{1}{2}}=2\) ，所以 \(k=1\) 。此时可得 \(c=s\) 。

记 \(p=\min (n, m)\)：

\[\begin{aligned} ans&={c} \sum_{i=x+1}^{p}(n+1-i)(m+1-i) \\ &=\sum_{i=x+1}^{p}(n+1)(m+1)-(n+m-2) \sum_{i=x+1}^{p} i+\sum_{i=x+1}^{p} i^{2} \\ &=(n+1)(m+1)(p-x)-\frac{1}{2}(n+m+2)(p-x)(p+x+1)+\frac{1}{6} p(p+1)(2 p+1)-\frac{1}{6} x(x+1)(2 x+1)\\ \end{aligned} \]

在 \(s \leq x\) 时，注意到 \(k=\frac{\frac{c}{c+x}}{\frac{s}{s+x}}<\frac{1}{\frac{s}{s+x}}=\frac{s+x}{s}=1+\frac{x}{s}\)。

暴力枚举 \(s, k\)，复杂度为 \(\sum_{i=1}^{x} \frac{x}{i}\) 为调和级数，此时暴力枚举每组解，累加贡献即可，时间复杂度为 \(\mathcal x\log x\)。

B：

我们发现两个点 \(u,v\) 在同一个点集的充分条件是：对于所有不是 \(u,v\) 的点 \(x\)，要么 \(u,v\) 与 \(x\) 之间均有直接连边，要么 \(u,v\) 与 \(x\) 之间均无直接连边。

容易想到哈希，每个点维护该点与别的点是否有直接连边。

而我们仅需讨论一下 \(u,v\) 是否存在边即可，我们如果直接维护这两个点是否有边也是可以做的，或者我们可以考虑同时维护 \(hash_u=hash_v\) 和 \(hash_u \operatorname{xor} val_v=hash_v \operatorname{xor} val_u\)，如果这两个点不在同一连通块，则这两个等式均不成立，否则一定只会成立其中一个。

时间复杂度 \(\mathcal O(n)\)。

C：

牛魔酬宾

D：

牛魔酬宾

原题

标签：总结,连边,2024.10,12,frac,sum,leq,hash,复杂度
From： https://www.cnblogs.com/Mitishirube0717/p/18461163