2019牛客暑期多校训练营（第七场)
A. String
做法 比赛时预处理哪些子串是最小表示，然后 BFS 最短路。复杂度不是很合理，本地测试了下 300 组长度为 200 的 010101.... 串，严重 TLE，题目中数据范围的描述可能存在不严谨之处。
B. Irreducible Polynomial
题意 判断一个多项式能否分解成若干个实系多项式。
做法 实系数多项式因式分解定理。多项式的非是根一定是共轭负数。
- 比赛时想了半天，发现这个东西不会做啊。
- RDC: 我们先求出所有根，再把这些根划分成很多个集合。
- F0_0H: 大胆猜结论，虽然猜的没一个对的。
C. Governing sand
做法 按高度分类，从小到大枚举最大高度，比当前枚举的高度 h 要高的，一定删，比它小的，如果删前 ? 小的。
E.Find the median
solved by F0_0H 194min -1
题意 每次插入([l[i], r[i]]),询问中位数
做法
- 很奇怪，数据为什么要这么搞，很容易让人想歪或者认为这是个强制在线题
- 离散化后权值线段树上二分即可，比赛时因为没考虑好边界条件，智障了很久...
F.Energy stones
upsolved
题意 吃能量
做法 比赛中对着一个假做法自闭了很久，一直坚信其优美性和正确性
正解：
- 查询离线，依次计算每个石头对答案的贡献
- (set)维护包含当前石头的区间的(ti)
- 每次插入删除至多修改三个区间差，用树状数组维护即可
- 这种套路上次是在维护树上联通块大小上
I. Chessboard
很精彩的一道题！
做法
- 设 (A_i) 为第 (i) 行全为 1，其它位置全为 0 的方阵。
- 设 (B_j) 为第 (j) 列全为 1，其它位置全为 0 的方阵。
- 一个 (k) 行 (k) 列，任取 (k) 个元素，每个元素不同行不同列的方阵，一定可以由 ({A_1,A_2,....,B_1,B_2.....}) 的生成的线性空间中。也就是 (sum_{i=1}^{k}a_iA_i+sum_{j=1}^{k}b_jB_k)
- 于是有 (sum_{i=1}^{k}a_i+sum_{j=1}^{k}b_j leq n)
- 但很可惜，如上线性空间的基中只有 (2k-1) 个向量，因此表出方式不唯一。
- 对于不同的表出方式，令 (d=min_{i=1}^{k} a_i) 做变换 (a_i:=a_i-d), (b_i:=b_i+d)，于是我们识破了本质相同的矩阵的不同表出方式。
- 对于一个确定的 (k)，答案为 (sum_{i=1}^{k}a_i+sum_{j=1}^{k}b_j leq n(存在 a_i=0))
- 枚举 (k)，用 (sum_{i=1}^{k}a_i + sum_{j=1}^{k}b_jleq n, (a_i,b_jgeq0)) 的解数，减去 (sum_{i=1}^{k}a_i + sum_{j=1}^{k}b_jleq n, (b_jgeq0, a_igeq1)) 的解数。即可，复杂度 (O(n))
复盘
- 比赛时第一眼的想法：任选 (k) 个元素，之和相等，等价于任意子矩阵对角之和相等。建立线性方程组，第一行第一列的是主元，其它是自由元。
- 然后就没有然后了。
- 把矩阵中的元素当成变量，不失为一种合理的想法，但只有这个想法，就是视野狭窄了。
- 题解中的做法，把行和列当成了变量。
- 从行和列的角度考虑一个矩阵，这是常见的思路。