31 2024.8.3
1 得分
| 题目 | T1 | T2 | T3 | T4 | 总分 |
|---|---|---|---|---|---|
| 得分 | \(0\) | \(20\) | \(60\) | \(0\) | \(80\) |
排名：rank \(12\)。
2 题解
T1
考虑最小的数，显然它要放到最左边或者最右边，那么它要交换的次数就是它左边比它大的数的个数或者右边比他大的数的个数，两者取 \(\min\) 即可。
显然将最小的数删去后对于整个序列答案不会发生影响，因此用树状数组扫一遍即可，复杂度 \(O(n\log n)\)。
T2
比较狗屎的一道题。
首先考虑设 \(dp(i,j)\) 表示第 \(i\) 次美食节后在坐标 \(j\) 的花费最小值。实际上，这个 dp 转移可以分为两部分：
- 用 \(dp(i-1,j)\) 更新 \(dp(i,j)\)，\(j<l_i\) 就加上 \(l_i-j\)，\(j>r_i\) 就加上 \(j-r_i\)。
- 用 \(dp(i,j)+1\) 更新 \(dp(i,j-1),dp(i,j+1)\)。
实际上，通过这两步操作，最后得到的 \(dp\) 数组一定满足一个性质：对于固定的 \(i\)，\(dp(i,j)\) 的差分只可能是 \(-1,0,1\)，且连续出现。显然差分为 \(0\) 的一段必为最小值，那我们就维护这一段差分为 \(0\) 的区间即可。
\(O(n)\) 扫一遍所有区间即可，注意分类讨论。
T3
设当前要查询 \(k\)，令 \(b_i=\text{sgn}(a_i-k)\)，那么我们肯定使用 \(0\) 去更新中间的 \(1,-1\)。考虑以 \(0\) 为界限分开每一个区间，这样我们实际上就是求区间两端为 \(0\)、中间为 \(1,-1\) 的答案。
不难发现，每一个位置都要进行一次操作，但是可能会产生额外的操作。具体的，对于一段连续的 \(1,-1\) 交替出现的区间 \([l,r]\)，那么其需要的额外操作次数是 \(\lfloor\dfrac{r-l+1}2\rfloor\)。我们用线段树维护出连续的 \(1,-1\) 区间即可。
T4
直接粘波波题解了。
（实际上 \(dp_i\) 表示的是以点 \(i\) 为开头的最小代价）
32 2024.8.5
1 得分
| 题目 | T1 | T2 | T3 | T4 | 总分 |
|---|---|---|---|---|---|
| 得分 | \(10\) | \(30\) | \(20\) | \(0\) | \(60\) |
排名：rank \(24\)。
考的最好的一集。
2 题解
T1
显然一次反转可以减少 \(1\) 或 \(2\) 个逆序对，那么我们只需要统计出整个序列的逆序对个数 \(n\)。接下来由基础的博弈论知识可知：
- 当 \(n\) 为 \(3\) 倍数时，后手必胜。
- 当 \(n\) 不是 \(3\) 倍数时，先手必胜。
T2
由于对 \(a_x\) 操作后 \(a_{x-1},a_{x+1}\) 永远不会大于 \(a_x\)，因此操作总数一定是某些位置上的数的总和，并且之间仅相邻 \(1\) 或 \(2\) 个数。
这样我们就可以考虑线段树了，我们考虑在合并时会出现的情况：
[..._X_X_]+[_X__X...][..._X_X]+[_X_X_...][..._X__]+[X_X_...][..._X_X]+[X_X_...]
容易发现上面三种情况都很简单，直接合并即可。但是最后一种情况比较难，我们必须要舍弃掉左右区间的端点，具体的应该根据原数组大小确定。那么在舍弃掉一个区间的端点后，我们的答案会发生变化，因此实际上我们需要维护的信息有：考虑左右端点的答案，不考虑左端点的答案，不考虑右端点的答案，两个端点都不考虑的答案。
同时为了判断中间是否会出现第四种情况，我们还需要维护上面四个情况下每一种情况的答案状态是否选了左端点或右端点。这样我们就能直接在线段树上求出答案了。
T3
首先考虑怎样组合零件最大，实际上是每次取两端。
然后发现贪心是具有正确性的，因此我们每一次要尽可能扩展右端点直到不能再扩展。
那么朴素做是 \(O(n^2)\) 的，考虑优化。我们采用倍增的方式可以轻松优化到 \(O(n\log ^2 n)\)。
但是这样做其实是比较卡的，我们考虑另一种倍增的方式。容易发现上面每一次尝试扩展都要重新整个排一边序，复杂度有点高。如果我们已经扩展的序列是排好的了，那就只需要对新增加的序列进行排序然后归并即可。基于这种思路我们可以设计出这样的倍增：
- 设当前左端点为 \(l\)，已扩展的右端点是 \(r\)，上一次扩展的长度是 \(p\)。此时我们尝试扩展 \(2\times p\)，如果可以的话直接就将 \(r\) 赋成 \(r+2\times p\)，更新 \(p\)；否则就将 \(p/2\)，然后再次尝试。
每一次只有扩展的时候才会排序，并且归并的复杂度是 \(O(n)\) 的，总复杂度 \(O(n\log n)\)，十分优秀。
T4
首先连边跑出最短路，接下来不难发现我们的操作一定是在最短路图上进行的。那么我们就可以将所有铁路再拆成几段，每一段再最短路图上联通且原先位于同一条铁路上。此时考虑设 \(f_i\) 表示走到 \(i\) 的最大平方和，那么对于在新的同一段铁路上的点 \(j\)，会有转移：
\[f_i=f_j+(dis_i-dis_j)^2 \]显然可以直接斜率优化。那么我们对于每一段铁路开一个单调栈维护凸包即可。
最后我们还需要考虑一下枚举顺序，实际上由于该图没有负权边，\(dis\) 更小的拓扑序一定更小，因此按 \(dis\) 排序然后 dp 即可。
33 2024.8.6
1 得分
| 题目 | T1 | T2 | T3 | T4 | 总分 |
|---|---|---|---|---|---|
| 得分 | \(30\) | \(-\) | \(0\) | \(30\) | \(60\) |
排名：rank \(19\)。
第一次连代码都没交的题！
2 题解
T1
运用注意力加上一点点直觉可知，答案就是 \(\max\{a_i\}\) 和 \(\lfloor\dfrac{\sum a_i}{m}\rfloor\) 取最大值。
T2
直接拆式子即可，这里就不讲了。
T3
首先发现打比赛的涨分过程实际上可以分为几段，每一段都是当前较小的超过当前较大的。
那么我们就可以设 \(f(i,j)\) 表示当前号分数为 \(i\)，第一次超过自己到达了 \(i+j\) 的答案。注意这里的答案是要同时维护概率和期望的。这一部分实际上可以由之前的部分推出，不难想到可以枚举第一次跳的步数 \(k\)，然后通过 \(f(i+k,*)\) 转移即可。但是此时会有两个问题：
- \(k=0\) 时两边都有 \(f(i,j)\)。
- 只枚举第一次跳的步数有些局限。即我们无法单纯通过 \(f(i+k,*)\) 转移。
第一个问题很简单，我们只需要解方程就行。对于第二个问题，我们可以这样解决：考虑再设一个 \(t(j)\) 表示从 \(i\) 走到 \(i+j\) 的答案，我们利用 \(f\) 数组进行 dp 求出 \(t(j)\)。然后再利用 \(t(j)\) 求出 \(dp(i,j)\) 即可。
最后我们再设 \(g(i,j)\) 表示大号分数为 \(i\)，小号分数为 \(j\) 的答案，这一部分直接利用 \(f\) 数组计算即可。
T4
显然只有 \(\gcd\) 相同的区间才能选，那么不妨考虑枚举当前的 \(\gcd\)。同时设 \(f(i)\) 表示此时在前 \(i\) 个数中选择区间的方案数。显然如果这样做的话我们必须要知道对于每个 \(i\)，可以分割出多少 \(\gcd\) 相同的左端点区间。这个直接使用 ST 表 + 二分就可以求出。
现在我们就得出了很多形如 \((l,r,p,d)\) 的东西，表示 \(\forall j\in [l,r],\gcd(j,i)=d\)。那么若 \(d\) 等于当前枚举的 \(\gcd\)，则会有转移方程：
\[f(i)(i\in [r,n])\ +\!\!=\sum_{j=l}^r f(j-1) \]同时我们考虑设 \(g(i)\) 表示后 \(i\) 个数中选区间的方案数。与 \(f(i)\) 的处理是一致的。
不难发现两个数组只需要执行区间求和、区间加操作，考虑用线段树维护。
现在考虑求出 \(i\) 的答案，考虑容斥。所有区间任选的方案是 \(f_n\)，而没有 \(i\) 的方案数是 \(f_{i-1}g_{i+1}\)。但是如果每一次都暴力增加答案的复杂度会炸。考虑到如果一个 \(i\) 没有作为 \(r\) 出现，那么一定有 \(f(i)=f(i-1)\)。因此两个端点 \(r_1,r_2\) 之间增加的贡献是相等的，考虑差分维护即可。复杂度是 \(O(n\log w)\) 的。
34 2024.8.7
1 得分
| 题目 | T1 | T2 | T3 | T4 | 总分 |
|---|---|---|---|---|---|
| 得分 | \(100\) | \(100\) | \(20\) | \(13\) | \(233\) |
排名：rank \(2\)。
2 题解
T1
可以得到如下模型：
- 首先显然 \(n\) 是答案。
- 考虑将 \(i\) 之前的字符串翻转，然后考虑两端的字符串是否相等，同时计算延伸到的右端点 \(r\)。如果两端字符串相等且 \(r\) 也是合法答案，那么 \(i\) 就是合法答案。
判字符串相等直接用哈希即可，不过你用 Manacher 我也没意见。
T2
大分类讨论题。首先发现答案只可能是 \(0,1,2,3\)。
-
若整个序列已经有序，答案为 \(1\)。
-
若 \(1\) 右边有数字。
- 如果存在一个位置 \(i\)，使得 \(p_i=i\)，且 \(p_1,p_2,\cdots p_{i-1}\) 出现了所有 \(1,2,\cdots,i-1\) 的数，答案为 \(1\)。
- 否则，答案为 \(2\)。
-
若 \(1\) 右边没有数字（即 \(p_n=1\)）。
- 若 \(a_1=n\)，那么必须要 \(3\) 次才能将两者全部返回原位，答案为 \(3\)。
- 否则，答案为 \(2\)。