1122总结
1122总结
T1
有趣的题。
场上瞎撞结论显然是错误的。
考虑 \(01\) 矩阵乘法的组合意义，就是统计一张图从 \(S\) 到 \(T\) 某个长度的路径总条数。
所以如果不存在长度为 \(k\) 的路径，考虑将点按照最长路径长度分类，每一类需要尽可能均分。
然后每一类内部不连边，和向外部路长度更短的所有点连单向边。
考虑证明这样的边数最多，问题本质是有 \(k\) 个变量 \(a_1,a_2\cdots a_k\) 满足 \(\sum\limits_{i\in[1,k]}a_i=n\)，求 \(\sum\limits_{i\in[1,k]} \binom{a_i}{2}\) 的最小值，列式计算： \[ \begin{align} \sum\limits_{i\in[1,k]} \binom{a_i}{2}=&\dfrac{a_i\times(a_i-1)}{2}\\ =&-\dfrac{n+\sum\limits_{i\in[1,k]}a_i^2}{2} \end{align} \] 考虑证明分布在 \(v=\lfloor\frac{n}{k}\rfloor\) 和 \(\lfloor\frac{n}{k}\rfloor+1\) 之间的 \(a_i\) 是最优的，假设不为这两个值，那么找到两个值 \(x<v\) 和\(y>v+1\)，将 \(x\) 调整为 \(x+1\)，\(y\) 调整为 \(y-1\)，那么从 \(x^2+y^2\) 变成了 \(x^2+2x+1+y^2-2y+1\)，由于 \(y> x+1\)，所以一定会变优，如果只能找到 \(x\) 或者 \(y\)，就对应的选择 \(v+1\) 和 \(v\)，同样会变优，调整到最后就分布在 \(v,v+1\)。
不直观的计数问题，考察其组合意义，变成直观的计数问题。
T2
很容易想到二分，直接二分的复杂度是 \(O(nq\log^2 n)\) 的。发现 \(check\) 的代价和二分值有关，考虑调整二分策略，尝试以 \(O(ans\log ans\log n)\) 的代价找出一次清空，发现倍增后二分即可。
T3
朴素的动态规划是 \(O(n^5)\) 的，配合性质的暴力可以有 \(50\)。
观察，发现答案不会很大，考虑改变动态规划状态，设 \(dp[x][y][i][ans]\) 表示左端点为 \((x,y)\)，横向延伸到 \(i(i\ge x)\)，纵向延申的最远位置，不难发现该状态有单调性，即 \(dp[x+1][y][i][ans]\ge dp[x][y][i][ans]\)，因此纵向转移是简单的，可以做到 \(O(1)\)，转移完之后其实就已经单调了，不用前缀 \(\max\)。
考虑横向的转移，不难发现最优的转移点单调，且答案递减，维护这个最优转移点即可。
T4
朴素做法
考虑设 \(dp[i][j][k]\) 表示考虑到第 \(i\) 个数，抹掉了 \(k\) 位后再加上了若干位，最终的 \(\log_2\) 值为 \(j\) 的最小方案。
视实现有 \(40-75\)，转移是一个前缀 \(\min\) 加上一个带判断的转移。
不太需要动脑子的办法
转移可以通过类似双指针的方法做到均摊 \(O(1)\)，考虑优化状态数。
有一个显然的可行解需要 \(\sum\log_2{a_i}=sum\) 步。
考虑每一个位置 \(k\) 的上界，设 \(T=\log m \approx18\)，那么如果一个位置 \(i\) 的 \(j\) 的状态如果满足了 \((j-T)\times(n-i) \ge sum\)，那么这个 \(j\) 是没有意义的，这样限制下来 \(j\) 这一维是 \(Tn\ln n\) 大小的。
已经可以比较险的通过了，其实还有一个限制，就是 \(lim_i\le lim_{i-1}+1\)，原因是显然的，加上这个限制之后又会变松很多。
最后记一个 \(mn\) 表示当前状态的最小可能值，条件变为 \((j-T)\times(n-i)+mn \ge sum\)，就很容易通过了。
场上前缀最小值只取了上一个位置的，挂了。
比较聪明的办法
考虑如果 \(a_i'\) 变到了 \(\log_2\ge 17\) 之后会发生什么，它之后的位置的 \(\log_2\) 值，都必须要大于 \(17\)，不妨先在这些数后面添 \(0\) 补到 \(17\)，进行代价的预付，到一个位置的时候，我们已知它和上一个位置的 \(\log2\) 已经相同了，只需要改变高位的一些值，这样的改变方式只有 \(\log n\) 种，代价也是好算的，暴力枚举就是 \(O(n\log^2n )\) 的，如果会导致后面的位置的 \(\log_2\) 变大，就在这里预付代价。
本质上，这种方法通过分析 \(j\ge 17\) 后最优解 \(\log_2\) 值的变化，得到了一种新的代价计算方式，这种方式不依赖 \(j\)，减少了状态数量
同一个最优化问题，可以采取不同的代价计算方式，得到不同的动态规划状态。预付代价是一种常用的方式。
典型例题是《任务安排》。