【学习笔记】ARC146/AGC020/

ARC146

Even XOR

我是sb我是sb我是sb

考虑从大小为$i$的集合$S$中添加一个数，使其仍然满足条件。

设添加的数为$X$，则合法的充要条件是$S$中不存在异或和为$X$的大小为奇数的子集。

显然方案数$2^n-2^{i-1}$

那么$d{p}_i=d{p}_{i-1}(2^n-2^{i-2})$

AC Code

>=<

似乎不难。。。除了第一步？？？

首先转化限制。初始状态下$A=(1,\cdots ,1)$

然后考虑调整。形式化的说，限制是如：

$1.1$.如果$A_{P_i}\le X_i-1$，那么$A_{Q_i}\le Y_i-1$
$1.2$.如果$A_{P_i}\le X_i$，那么$A_{Q_i}\le Y_i$

跑$spfa$即可。复杂度$O(n+K)$ 。

AGC020

Min Max Repetition

答案是$\lceil \frac{\max (a,b)}{\min (a,b)+1}\rceil$。

我会构造！！乱搞万岁

考虑先二分前缀$\underset{k}{\underbrace{A_{\cdots }A}}B$的最大段数，再二分后缀$\underset{k}{\underbrace{A{B}_{\cdots }B}}$的最大段数，中间就是连续$A$和$B$。

证明略。AC Code

Median Sum

思维题。。

显然子集和其补集之和为定值，问题转化为求$\ge \lceil \frac{sum}{2}\rceil$的最小的数。

bitset复杂度离谱

Arcs on a Circle

首先以最长的弧的左端点为原点，把环断开成链。

我们只关注小数部分的相对大小关系。考虑枚举其排列，并且显然每种排列是等概率的。

相当于数轴上有$0\sim nC$的整数点，其中$i$的小数部分大小为$i\mathrm{mod}n$。并且每个区间的小数部分都不同。

现在问题转化为区间覆盖问题。设$dp[i][j][S]$表示考虑了左端点$\le i$的区间，最远覆盖到$j$，所选区间集合为$S$的方案数。转移是$O(1)$的。

复杂度$O((n-1)!2^{n-1}(nC{)}^2)$。