JZOJ | NOIP2018模拟10.27 百鸽笼

把序列倒过来建主席树

没了。

 

[JZOJ1026模拟] 苹果

考虑每个节点对区间的贡献

考虑要是一个节点的左儿子产生贡献,那么贡献区间的 L 是这个左儿子的左端点,假如我们设这个区间长度是 2^w ,贡献区间所有可能的右端点是 [L+2^w-1,L+2^{w+1}-1)

那么一层来看的话,所有的右端点总长是 2^{n-1} 的。

那么这块的总贡献是

\sum_{i=1}^{n-1} { i \cdot 2^{n-1} } = 2^{n-2} \cdot (n+1) \cdot n

现在考虑右儿子,类似地,我们单点可用的区间右端点是:

2^n - (L+2^w) +1

那么一层的话就是 2^{n+i-2} - 2^{n-1} + 2^{i-1}

那么这块的总贡献是

\sum_{i=1}^{n} { i \cdot ( 2^{n+i-2} - 2^{n-1} + 2^{i-1} ) }

那么把这个式子改写一下 ( 设 \lambda = 2^0+2^{n-1}

\sum_{i=1}^n { i \cdot \lambda \cdot 2^{i-1} } - \sum_{i=1}^n { i \cdot 2^{n-1} }

化简,求总答案:

A=2^{n-2}\cdot \left( n+1 \right) \cdot n

B=\lambda \cdot \left( n\cdot 2^n-2^n \right) +1-2^{n-2}\cdot \left( n+1 \right) \cdot n

\text{ans}=2\cdot \left( A+B \right)

=\left[ \left( n-1 \right) \cdot 2^{n+1}+2 \right] \cdot \lambda \cdot \ \left( \frac{\left( 2^n+1 \right) \cdot 2^n}{2} \right) ^{-1}

还有两个周该搞的东西

  1.  数论复习( exgcd Lucas CRT 合并同余方程 异或方程组 各种其他脑洞题 )
  2. 博弈
  3. 概期(以及 DP )
  4. 单调队列维护 DP(包括复习一遍斜率优化 DP )
  5. 把坑填完
  6. NOIP2017 做完
  7. 数据结构打熟练 不学 Treap 了
  8. 差分约束
  9. 树剖多做题 网络流也要写
  10. 贪心

 

先到这里

 

 

[CYYZOJ 1020] 校验码加强版

首先每一位独立。

对于每一位,统计不合法答案,即有至少一行/列全 0

先枚举有几列必定全为0 ,然后拿出可能非 0 的列。

然后让这些列上的所有行都满足条件。即每一行至少填一个 1

然后乘容斥系数。

 

[Codeforces R489D2C] Nastya and a Wardrobe

手模一下发现除掉最后一轮会形成一个区间

那么

L=\left( \left( \left( x\times 2 \right) -1 \right) \times 2-1 \right) \times 2-1\cdots =x\cdot 2^k-2^{k-1}-2^{k-2}\cdots -1 L=x\cdot 2^k-2^k+\text{1 } R=x\cdot 2^k \text{ans}=\frac{S\left( L,R \right) \times 2}{2^k} =\frac{\frac{\left( R-L+1 \right) \left( R+L \right)}{2}\times 2}{2^k} =\frac{2^k\cdot \left( x\cdot 2^{k+1}-2^k+1 \right)}{2^k} =x\cdot 2^{k+1}-2^k+1

然后暴算这个东西。