CF908H New Year and Boolean Bridges
CodeforcesLuogu分析显然满足 $G_{i,j}=\mathsf{A}$ 的 $i,j$ 在同一个强连通分量内，所以先把这些点并起来。那么如果一个强连通分量内有 XOR 边就是不合法的。显然每个强连通分量内成环最优，那么答案等于 $n-1+$点数 $\geq 2$ 的强连通分量个数，则应最小化后面那个东西，即把一些强连通分量在满足条件的情况下合并成一个大环。因为点数 $\geq ...
标签 FWT 下的文章
- 首页
- FWT
洛谷5366 [SNOI2017]遗失的答案
LuoguLOJ分析首先特判掉 $G\nmid L$ 的情况。为了方便，将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数，必须选 $X$，选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。我们先不管那个必须选 $X$ 的条件，想一想怎么做。注意到值域只有 $10^8$，即最多只有 $8$ 个质因子...
JOI 2018 Final 简要题解
寒冬暖炉同 CF1110B Tape。先令每个客人来的时刻都开暖炉，其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。代码美术展览显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。设 $sum_i$ 表示 $\sum_{j=1}^iB_j$，那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。因此我们从后往前扫，维护 $sum_i-...
CF662C Binary Table
CodeforcesLuogu分析注意到 $n$ 很小，猜想复杂度肯定有个 $2^n$ 。设 $S_i$ 表示第 $i$ 列的状态，$F_i$ 表示 $i$ 状态翻转或不翻转最少能有多少个 $1$ 。首先考虑一个暴力：枚举翻转哪几行。那么答案就是 $\displaystyle\min_{X}\left\{\sum_{i=1}^mF_{S_i\oplus X}\right\}$ 。这样子是 $...
洛谷4221 [WC2018]州区划分
LuoguLOJ分析每个集合是否合法很容易判（并不，先把这个东西预处理出来，记为 $chk[S]$ 。设 $f[S]$ 表示集合 $S$ 的答案，那么有：发现后面是一个子集卷积的形式，然后就没了。代码// ================================= // author: M_sea // website: http://m-sea-blog.com/ // =...
洛谷3175 [HAOI2015]按位或
LuoguBZOJ分析我们把每个数看成一些二进制位的集合，每一位的值是加入的时间。那么我们要求的是全集的 $\max$ 值。根据 $\mathrm{min}$-$\mathrm{max}$ 容斥，有 $\large E(max(S))=\sum\limits_{T\subseteq S}(-1)^{|T|+1}E(min(T))$ 。考虑 $E(min(S))$ 怎么求。显然有 $\larg...
CF914G Sum the Fibonacci
CodeForcesLuogu分析设 $cnt[i]$ 表示 $i$ 的个数。那么原式可以视为 $cnt[s_a|s_b]\times f(s_a|s_b)$ 、$cnt[s_c]\times f(s_c)$ 、$cnt[s_d\hat\ s_e]\times f(s_d\hat\ s_e)$ 的与卷积。先不考虑 $f()$ ，那么第一个式子可以子集卷积做，第二个式子不用管，第三个式子可以异...