$\text{+9 rating}$ 可还行.
A Takahashi Calendar
签到题,按题意暴力枚举一下.
B Kleene Inversion
贡献可以分成两部分,两个数在同一块中的贡献与两个数在不同块中的贡献,分开算一下.
C Cell Inversion
操作顺序对答案没有影响,将操作视作一个二元组 $(l,r)$ ,我们可以规定按 $l$ 从小到大的顺序操作,最后答案乘上 $n!$ .
将黑色看为 $1$ ,白色看为 $0$ ,显然只需要将偶数位置上的状态取反,然后答案就是前面的 $1$ 与后面的 $0$ 配对的方案数.
开始没判 $1$ 和 $0$ 个数不等的情况,卡了挺久的.
D Classified
题意读错了.意思是走回来时,走过的长度为偶数,不是每条边经过的次数都为偶数.
于是就要求同一种边权的边形成的图是二分图.
如果用到最大的边权为 $k$ ,那么最多只能构造出 $n=2^k$ 的情况.
首先证最大边权为 $k$ 时, $n=2^k+1$ 不可行.
考虑使用数学归纳法,当 $k=1,n=2^1+1=3$ 时,显然不可行.否则,假定 $k=x-1,n=2^{x-1}+1$ 时不可行.
那么当 $k=x,n=2^x+1$ 时,二分图中黑色的节点至少有 $2^{x-1}+1$ 个,否则白色的节点至少有 $2^{x-1}+1$ 个.
假设黑色节点至少有 $2^{x-1}+1$ 个,对于黑色节点内部,因为用前 $x-1$ 种边权无合法解,所以一定会有权值为 $x$ 的边.
这与二分图的定义相矛盾了,所以结论成立,即最大边权为 $k$ 时, $n=2^k+1$ 不可行.
再来证 $n\le2^k$ 时一定存在最大边权不超过 $k$ 的合法解,尝试直接构造方案.
对于节点 $i,j$ ,若它们的二进制位从低到高第 $x$ 位不同,就将它们之间的边权设为 $x$ .
这样对于任意一个 $0\le x<k$ ,边权为 $k$ 的边一定只存在于第 $x$ 位为 $0$ 与第 $x$ 位为 $1$ 的点之间,形成了二分图.
E Card Collector
考虑像网络流那样,每一行每一列都建出一个点,读入的每个点向所在行列连边,权值都是 $A_i$ .
于是需要选出一些边使得它们的权值最大,并且任意两条边不能有公共点.
分析性质后,发现就是在求解加权拟阵的最大权值独立子集,贪心求解即可.
即将所有边按权值从大到小排序后,依次遍历,若当前的边能加入,就加入.
F Candy Retribution
留坑.