paulzrm 的小窝

比较内存连续访问和随机访问。

link

萌萌莫队模板题。

我们考虑没有询问的时候怎么做。

赛时看到“误差修复”就一直往随机化方面想了

假设对于时刻 $j$， 第 $i$ 个人的位置为 $a_{i,j}$。 本文统一用 $i$ 表示人，用$j$ 表示时刻

那么我们令 $sum_j = \sum_{i=1}^{n}a_{i,j}$，$squsum_j=\sum_{i=1}^{n}a_{i,j}^2$

再令$deltasum_{j}=sum_{j+1}-sum_j$，$deltasqusum_j=squsum_{j+1}-squsum_{j}$

赛后写题解补教训

场上数组开小本机AC但开了O2就会RE=爆零

洛谷上测由于数组开小导致访问不到死递归MLE我还以为还是开大了

小心，小心，再小心

我们尝试建立一棵线段树。

考虑到最多只会有一个 $b_i \ge \sqrt{k}$。

• 没有任何一个 $b_i \geq \sqrt{k}$。

那么我们可以考虑类似 meet-in-the-middle 的做法。

题目大意：

给你一个长度为 $n$ 的字符串 $s$。

每一次操作，可以选择一个位置（不为最后一位），然后删除它和它后面一位，在原来的位置上填上他们的或。每次操作会使 $n-1$。

问你执行最多 $n-1$ 次操作后能得到多少不同的串。

题目大意：

一款游戏中有 $k$ 种装备，你一开始每种装备各有 $1$ 个，且每种装备的初始等级均为 $1$。游戏中可以靠打怪来获取新装备，总共有 $n$ 只怪兽，每打赢 $1$ 只怪兽后会随机获得一种装备 $a \in [1,k]$。假设原有的 $a$ 装备的等级为 $t$，那么新获得的装备的等级为 $[1,t+1]$，且你会将新获得的装备和原来的装备中等级较高的装备留下，等级较低的装备卖出，卖出可获得的金币为该装备的等级。 问打完这 $n$ 只怪兽后，获得的金币的期望。

$1 \le n \le 10^5, 1 \le k \le 100$

题目大意：

有一个 $4\times n$ 的 $01$ 矩阵。你每次可以选择一个 $k \times k (1 \le k \le 4)$ 大小的子矩阵，将其中的值都赋为 $0$，代价为 $a_k$。问你最小的代价使得整个矩阵的值都为 $0$。

题解：

萌萌题。

我只是去摸鱼的。

总的来说机试要比去年难的多，大概CSP2019Day1的难度。

事实上这篇游记的目的大概就是介绍流程。

Warning：可能比官方题解复杂的多，思维难度估计要上紫，但推出来了能有很好的训练效果

然后你们知道为啥 div2 rank1 的 YuezhengLing 最后才过D了吧