比赛名称

排名	当场过题数	至今过题数	总题数
8/?	10	10	12

A

upsolved by

题意

题解

B

solved by JLK

题意

\(n\)​​​个数，有\(m\)​​​个限制条件，形如\(a_u \oplus a_v=w\)​​​，求满足条件的可能的最小总和。

\(1 \le n \le 10^5,0 \le m \le 2\times 10^5,0 \le w \lt 2^{30}\)

题解

异或关系显然是可以传递的，用带权并查集维护限制条件，如果某个限制条件加进来成环并且导致这个环的异或和不为0，那么无解。

在有解的情况下，可以每个连通块分开考虑，再对每个位分开考虑，每一位一定贪心地取，选择这一位是0或1的个数较少的那个异或成1即可。

\(O(n\alpha(n))\)

C

solved by TYB

题意

题解

D

upsolved by

题意

题解

E

solved by JLK

题意

签到，略

题解

F

solved by TYB

题意

签到。

题解

略。

G

solved by YZW

题意

题解

H

solved by JLK

题意

给定一个无向图，求线图的最大权匹配。

\(3 \le n \le 10^5,n-1 \le m\le \min(\frac{n(n-1)}2,2\times 10^5)\)

题解

相当于就是每次选两个相交的边，得到两个边权之和的权值。要让这个总和最大。

一个结论是，如果一个连通块有偶数条边，那么一定存在一种方法能取完。

也就是偶数条边的连通块的边一定能全部取完。

那么就考虑奇数条边的连通块。在连通块里删一条边，如果删的不是割边，那么剩下的连通块一定是偶数条边，可以全部取完。如果删的是割边，就要考虑剩下两边连通块的边数的奇偶性。

这种情况肯定会切成两个偶数条边的连通块。因为如果是奇数，那么两边还要继续删，这样一定是不优的。

因此做一遍Tarjan，然后对每个连通块的奇偶性，每条边是否是割边讨论一下即可。

\(O(n+m)\)

I

solved by YZW

题意

题解

J

solved by YZW

题意

题解

K

upsolved by

题意

题解

L

solved by TYB

题意

一个\(2n\)个点的完全图，删掉其中\(2n-1\)条边，这\(2n-1\)条边构成一棵树，求删边后的图完备匹配个数。

\(n\le2000\)

题解

考虑容斥，则要计算出至少用了\(i\)条树边的方案数。可以先树形DP求出选了\(i\)条树边匹配的方案数，然后乘上删掉这\(2i\)个点，剩下的点之间任意匹配的方案数，后者容易计算的。注意这种树形DP复杂度是\(\mathcal{O}(n^2)\)的。

M

solved by YZW

题意

题解

记录

JLK写E，RE一次后AC(0:03)。

TYB过F(0:18)。

YZW过J(0:30)。

JLK过B(0:40)。

TYB过L(1:02)。

JLK TLE一次后过H(1:36)。

TYB和YZW讨论M，JLK看其他题。

YZW过M(2:05)。

一起看GI，YZW想出了两题的解法，先写I。

JLK和TYB讨论C。

YZW WA一次后AC(3:31)。

TYB写C，写了一半发现问题，换YZW写G。

YZW过G(4:16)。

TYB和JLK在大量分类讨论修改后过了C(4:42)。

总结

Dirt

E(-1)

H(-1)

I(-1)