2022-team8-003
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
= 概览 =
通过数：6/10 Rank：4/11 dirt: 60%
== Rank和提交情况 ==
[[Image(1.png, 1000px)]]
[[Image(2.png, 1000px)]]
= 流水账 =
开局比较危险，三个人写的三道题都WA了，后来又陆续都过了。然后比较顺利，包括A、G和I。最后实在没有时间做B了，而且对概率论方便的技巧不是很熟悉，只觉得这题玄学。
= 总结 =
rtx:
复习了一手上学期刚学的概统。
好多题虽然过了，但其实不怎么会证明。
= 题解 =
* A：先预处理出每一个区间最少改几个数变成等差序列，之后即可n^2^dp。考虑怎么预处理，枚举等差数列的起始项，向后扫的过程中维护一个map表示每种公差最少需要改几位。比较重要的观察一个是等差数列确定两项之后公差就确定了，另一个是“最少改几位成为等差数列”即为“最长等差子序列”
* B：先估计s，将某一行的t加起来，由于\sum d几乎等于55，所以可以估计出s。再估计d，由于\sum 1/s几乎等于ln10/9，所以可以估计出来d，但是这样的d是错的，因为有一些作弊者。实际上这样估出的d是作弊者和正常人的d的平均值，作弊者的d可以认为是55，而作弊者和正常人几乎相等，所以可以估出正确的d。然后对一行根据估计的s和d计算一下方差，除以方差的期望，可以得到这个值不会大于1很多。经试验，取2.5为分界可以通过（取2会WA5，取3会WA1）。
* C：可以假定宽度无限，然后取左上角n的矩阵即可。先手玩前几行，发现按照2的幂分块，每一块后半部分为0，前半部分为上一块复制过来。最后打出来的表用vscode的缩略图看是一个很好看的分型。
* D：通用做法是线段树分治。但是我们在树上打标记求异或也过了，但是不大会严格证明。具体来说，对于非树边分配一个随机数作为边权，将其覆盖的树边边权都异或这个随机数，然后询问的时候如果有一个子集边权异或和为0，则不连通。证明的话我考虑了一下对于每个环这样搞相当于要求其要不不被割断，要么被割断两次。但是有一个问题在于对于一个跨过了两个非树边的环，他的所有边并非拥有同一个随机数。所以其实还是不大会证。
* E：
* F：
* G：f[S]表示考虑开头为S集合的子串，最短未出现的串的长度。转移时枚举子串的第一位是AGCT中的哪一个，例如填了A，则f[S]=max(f[S], f[(S&S_A)>>1]+1)。起始条件比较麻烦，需要注意一下。
* H：考虑如果用两端递增+1的排列拼起来，那么n需要满足2a<=n<=2b。又发现如果n可以拆成若干块n1, n2, ..., 每一块都满足2a<=ni<=2b，则可以分别使用前述方法最后拼起来。如果不能拆成这样的块就是-1（但是不会证明）。
* I：考虑底面的每一个点，在两个侧面分别做一条竖直线，与凸包必须相交形成一段合法的z的取值范围，显然两个侧面得到的该取值范围必须有交集。将三个面分别作为底面判一下即可。
* J：概览
通过数：6/10 Rank：4/11 dirt: 60%
Rank和提交情况
流水账
开局比较危险，三个人写的三道题都WA了，后来又陆续都过了。然后比较顺利，包括A、G和I。最后实在没有时间做B了，而且对概率论方便的技巧不是很熟悉，只觉得这题玄学。
总结
rtx:
复习了一手上学期刚学的概统。
好多题虽然过了，但其实不怎么会证明。
题解
- A：先预处理出每一个区间最少改几个数变成等差序列，之后即可n2dp。考虑怎么预处理，枚举等差数列的起始项，向后扫的过程中维护一个map表示每种公差最少需要改几位。比较重要的观察一个是等差数列确定两项之后公差就确定了，另一个是“最少改几位成为等差数列”即为“最长等差子序列”
- B：先估计s，将某一行的t加起来，由于\sum d几乎等于55，所以可以估计出s。再估计d，由于\sum 1/s几乎等于ln10/9，所以可以估计出来d，但是这样的d是错的，因为有一些作弊者。实际上这样估出的d是作弊者和正常人的d的平均值，作弊者的d可以认为是55，而作弊者和正常人几乎相等，所以可以估出正确的d。然后对一行根据估计的s和d计算一下方差，除以方差的期望，可以得到这个值不会大于1很多。经试验，取2.5为分界可以通过（取2会WA5，取3会WA1）。
- C：可以假定宽度无限，然后取左上角n的矩阵即可。先手玩前几行，发现按照2的幂分块，每一块后半部分为0，前半部分为上一块复制过来。最后打出来的表用vscode的缩略图看是一个很好看的分型。
- D：通用做法是线段树分治。但是我们在树上打标记求异或也过了，但是不大会严格证明。具体来说，对于非树边分配一个随机数作为边权，将其覆盖的树边边权都异或这个随机数，然后询问的时候如果有一个子集边权异或和为0，则不连通。证明的话我考虑了一下对于每个环这样搞相当于要求其要不不被割断，要么被割断两次。但是有一个问题在于对于一个跨过了两个非树边的环，他的所有边并非拥有同一个随机数。所以其实还是不大会证。
- E：
- F：
- G：f[S]表示考虑开头为S集合的子串，最短未出现的串的长度。转移时枚举子串的第一位是AGCT中的哪一个，例如填了A，则f[S]=max(f[S], f[(S&S_A)>>1]+1)。起始条件比较麻烦，需要注意一下。
- H：考虑如果用两端递增+1的排列拼起来，那么n需要满足2a<=n<=2b。又发现如果n可以拆成若干块n1, n2, ..., 每一块都满足2a<=ni<=2b，则可以分别使用前述方法最后拼起来。如果不能拆成这样的块就是-1（但是不会证明）。
- I：考虑底面的每一个点，在两个侧面分别做一条竖直线，与凸包必须相交形成一段合法的z的取值范围，显然两个侧面得到的该取值范围必须有交集。将三个面分别作为底面判一下即可。
- J：