UOJ

我还是太不懂 FWT 了！ 首先发现，两个人的集合异或和相等，那么这两个人的集合的并的异或和等于 $0$，而相对应地，每一个大小为 $k$ 的异或和为 $0$ 的集合都有 $2^k$ 种方案。那么我们实际上就是要找所有异或和等于 $0$ 的方案数。 考虑集合幂级数刻画，那么我们要求的就是 $n$ 个 ......

mt19937_64 rnd(time(0)); signed main() { freopen("data.in","w",stdout); int n=1e5,m=1e5,k=1e5; cout<<15<<"\n"<<n<<" "<<m<<" "<<k<<endl; For(i,2,n)cout ......

题面传送门 很好的题目。 首先我们假设 $a$ 没有初始值，这貌似是平凡的。因为这样的话如果两个位置 $x<y$ 那么 $a_x\leq a_y$ 对于任意时刻都成立。取 $\min$ 的过程只需要线段树上二分加上区间覆盖即可。 但是有初始值怎么办呢？这个问题开始变得棘手起来。但是我们发现上面那个性 ......

题面传送门 有点精妙的题目。 首先我们发现这个题目问的方式非常奇怪，它只要求最小的集合大小。这说明如果无脑把所有点的集合都求出来应该是做不了的。因此我们需要对于最小值的问题挖掘一点性质。 观察：如果 $x$ 可以走到 $y$ ，那么$p_x\geq p_y$。特别的，如果 $y$ 可以走到 $x$， ......

print("Same") 嗯。期望得分 100。 首先考虑到题目要求所有字符串的出现次数相同，这意味着两个图能表示出来的字符串的多重集相等。 先考虑有向无环图的情况，发现这时候这个多重集一定是一个有限集，且字符串的长度不超过 $\min(n_1, n_2)$。判定两个集合是否相等，考虑哈希。我们可 ......

好像并不是很难的题？~~虽然从上午想到现在才开始写，还因为不知道 __builtin_popcount(x) 传入的是 int 调了一个多小时~~ 题目就是要求一个全源最短路。直接求显然不太现实，考虑分析标签的性质。发现，同一标签内的所有点到某个点 $u$ 的最短路的差值一定不超过 $1$，因为同一 ......

图论好难啊。 首先明确题目要求的其实就是从 $1$ 到 $u$ 是否能够经过一个负环。首先容易得到如果存在负环，那么一定存在一个简单负环，所以只需要考虑简单环。 考虑如何判断负环：Floyd 和 Bellman-Fold。 为什么不用 SPFA ______，___。 Bellman-Fold 这么 ......

有趣构造题，和今年省选 D2T2 类似的思路？ 首先看到字符串长度为 1 或 2，可以想到建图来转换题目。但是建出图后题目的要求还是不好抽象。 我们可以将回文串的两半拆开（先假设答案恰好划分成了两半），然后对齐在一起。此时我们就发现，只有两种情况，一种是有两个相同的直接拼接在一起，一种是先有一个长为 ......

记直径为$(x,y)$，则有以下做法： 利用直径的经典做法，可以$3n$次询问得到$x,y$和其余点到$x,y$的距离 设直径上距离$i$最近的点为$k$，已知$x,y,i$两两距离，即可解出$k$到$x,y,i$的距离 注意到$r(k)=\max{dis(k,x),dis(k,y)}$，即中心城市 ......

考虑原先求的是 SCC 为 1 的方案数，这很困难！因为并没有能够转移到子问题的路径。 不妨考虑容斥，即 SCC 为 1 的方案数=所有方案数-SCC 不为 1 的方案数。 不妨先集合划分出 SCC，然后就变成了，内部的 SCC 子问题（此时因为钦定的 SCC 个数 >1，因此规模一定变小）以及外层 ......