CodeforcesLuogu分析显然满足 $G_{i,j}=\mathsf{A}$ 的 $i,j$ 在同一个强连通分量内,所以先把这些点并起来。那么如果一个强连通分量内有 XOR 边就是不合法的。显然每个强连通分量内成环最优,那么答案等于 $n-1+$点数 $\geq 2$ 的强连通分量个数,则应最小化后面那个东西,即把一些强连通分量在满足条件的情况下合并成一个大环。因为点数 $\geq ...
LuoguLOJ分析首先特判掉 $G\nmid L$ 的情况。为了方便,将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数,必须选 $X$,选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。我们先不管那个必须选 $X$ 的条件,想一想怎么做。注意到值域只有 $10^8$,即最多只有 $8$ 个质因子...
998244353?998244353!
寒冬暖炉同 CF1110B Tape。先令每个客人来的时刻都开暖炉,其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。代码美术展览显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。设 $sum_i$ 表示 $\sum_{j=1}^iB_j$,那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。因此我们从后往前扫,维护 $sum_i-...
CodeforcesLuogu分析注意到 $n$ 很小,猜想复杂度肯定有个 $2^n$ 。设 $S_i$ 表示第 $i$ 列的状态,$F_i$ 表示 $i$ 状态翻转或不翻转最少能有多少个 $1$ 。首先考虑一个暴力:枚举翻转哪几行。那么答案就是 $\displaystyle\min_{X}\left\{\sum_{i=1}^mF_{S_i\oplus X}\right\}$ 。这样子是 $...
LuoguLOJ分析每个集合是否合法很容易判(并不,先把这个东西预处理出来,记为 $chk[S]$ 。设 $f[S]$ 表示集合 $S$ 的答案,那么有:发现后面是一个子集卷积的形式,然后就没了。代码// ================================= // author: M_sea // website: http://m-sea-blog.com/ // =...
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...
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()$ ,那么第一个式子可以子集卷积做,第二个式子不用管,第三个式子可以异...