博客食用更佳 https://www.cnblogs.com/czyty114/p/14691097.html

个人感觉atcoder上的题质量确实很高，比较偏向于竞赛的题型。

A

$\;$
$n$个人，$m$道题，每道题有两个选项。现在给出了这$n$个人的作答，用$n$个长度为$m$的01串来表示。
问：有多少个$(i,j)$，满足第$i$个人和第$j$个人做对的题目数量不可能相同。
$n\leq 10^5,m\leq 20$
$\;$
显然，如果两个人有奇数道题的答案不一样，他们做对的题目数量不可能相同。
把每个人的答案看成二进制数，问题转化为：异或后有奇数个1的数对有多少个
然后我们发现，如果两个数满足一个有偶数个1，另一个有奇数个1，则一定是满足条件的。
否则一定不行。
简单试试就看出来了。
$\;$

B

$\;$
给定$n \times n$的矩阵$C$
问：能否构造出两个数组$A,B$，满足：$C_{i,j}=A_i+B_j$
$n \leq 500$
$\;$
显然$A$是每一行的最小值，$B$就是这行每一列的数与这行最小值的差
$O(n^2)$简单判断一下是否是无解情况就行了
$\;$

C

$\;$
要求构造出长度为$n$的序列，使得对于任意$i|j$的情况，$a_i\neq a_j$
要求序列的最大值最小。
$n\leq 10^5$
$\;$
考虑一个位置的数，限制条件就是它的因数们。
考虑dp，那么一个位置应填的数，一定要比它所有因数下标中，填的数最大的那个+1
即:$dp_i=max \{dp_j \} +1$，这里$j$是$i$的因数
所以我们也可以直接枚举倍数去dp，复杂度为调和级数：$O(n log n)$
$\;$

D

$\;$
给定$n$个点，$m$条边的无向图（不保证联通）。
从$m$条边中选出一些边，与$n$个点所构成的图叫做生成子图
问：对于$k=0,1\cdots ,n$
有$k$个点的度数为奇数的生成子图有多少个。
$n\leq 5000$
$\;$
对于$k$为奇数的情况，答案就是0
然后考虑树的情况：
我们发现$ans_k=C_n^k$
为什么？
我们从这$n$个点中选出$k$个点，然后一定保证有且只有一种构造（选边）方案，使得这$k$个点度数都为奇数。
下面我们把那$k$个点称作关键点
证明：因为是$k$是偶数，所以我们进行两两配对。这样路径的两个端点奇偶性一定会发生变化，且路径中间的点奇偶性不会变。
而且我们必须从下往上逐渐进行配对，每次找到深度最深的点$x$，满足它至少有两个子树中都有1个关键点
然后两两配对。又发现，配对的过程，必须是选这些关键点与$x$之间的路径上的边。
感性理解一下就好。
$\;$
然后考虑非树（即图）的情况
我们一定可以从中找到一颗生成树，剩下$m-n+1$条边不是树上的边。
这$m-n+1$条边可以随便选。然后剩下的边又变成了树的情况
虽然选非树边会改变某些点的奇偶性，但是由于变成奇点的数量也一定是偶数个，而$k$也是偶数。
你会发现这两个玩意合并起来，只考虑树边使要变为奇点的（这里的奇点是只考虑树边贡献的度数）数量也一定是偶数。
这其实与$A$的思路有些类似。
因此，图的情况即是$C_n^k \times 2^{m-n+1}$
$\;$
若有多个连通图，那么只需进行一次简单的dp。
怎么dp就比较显然了。
看起来dp的复杂度是$O(n^3)$的（也有可能是我自己sb了），实际上是$O(n^2)$