2024.10.9训练记录

下午 提高组模拟

省流：又被lyy吊打了

晚上 订正

A

神秘猜结论题，场上少猜了一点挂了 \(18\) 分，遗憾。
结论：\(ans \in [0, 3]\)
\(0/1\) 可以直接判。\(1\) 的情况就是存在一个前缀 \(a_{1, i}\) 满足出现的数是 \(1\) 到 \(i\)。
\(3\) 的情况仅当 \(a_1 = n\) 且 \(a_n = 1\)。场上就是少判了 \(a_1\) ，其实倒过来是一个道理。
剩下就是 \(2\)。

C

简单题。设一个颜色的点坐标是 \((X_i, Y_i)\)。
这个颜色的正方形的边长为 \(max(max X_i - min X_i, max Y_i - min Y_i)\)。

B 序列(sequence)

没场切/kk

题面变量有点反人性，设值域为 \(m\)，数列长度为 \(n\)。
考虑容斥。对于一个 \(t\) 的方案数是所有 满足 \(B\) 字典序小于等于 \(A\) 的方案数 减去 不出现 \(t\) 且 \(B\) 字典序小于等于 \(A\) 的方案数。

先想字典序小怎么做，设 \(pre_i\) 是前 \(i\) 个数的答案，即 \(B_{1, i}\) 的字典序小于等于 \(A_{1, i}\)。
则当前 \(i-1\) 个数满足字典序小于时，第 \(i\) 个数可以任意放没填过的数，已经填完了 \([1, i - 1]\) 所以没填过的数有 \(m-(i-1)\) 种。
即 \(pre[i] += (pre[i - 1] - 1) * (m - (i - 1))\)。
前 \(i-1\) 个数刚好和 \(A\) 中相等时，第 \(i\) 个数需要小于等于 \(A_i\)。而此时已经填过的不能再填，可以用树状数组维护当前还能填几个数。
具体：树状数组中一开始将 \([1, m]\) 全赋为 \(1\)，代表这些数还每填，做完 \(i\) 就 \(add(a[i], -1)\)。
当前小于等于 \(A_i\) 的未填过的数的数量就是 \(query(a[i])\)。
综上：\(pre[i] = (pre[i - 1] - 1) * (m - (i - 1)) + query(a[i])\)。
容易发现 \(pre\) 数组可以压成一个数。

然后暴力时枚举 \(t\)，统计不出现 \(t\) 的方案数。大体和上面相等。
首先树状数组中一开始要把 \(t\) 排掉。
然后考虑，当 \(A_{1, i - 1}\) 中出现过 \(t\)，此时的 \(pre[i - 1]\) 就代表了字典序小于 \(A\) 的方案数，而不是小于等于。
因为等于 \(A\) 会出现 \(t\)，不满足钦定条件。
所以出现过 \(t\) 时，\(pre[i] = pre[i - 1] * (m - (i - 1) - 1)\)，这里多减一个 \(1\) 是把 \(t\) 减掉。
未出现过 \(t\) 时与之前相同，也要多减一个 \(1\)。
这个暴力的复杂度是 \(O(nm \log m)\)。
考虑这个暴力怎么优化。
把每个 \(pre\) 弄成一个数，放进线段树中。
对于未在 \(A\) 中出现过的每个 \(t\)，只需要的操作是 \(pre = (pre - 1) * (m - (i - 1)) + query(a[i])\)。
加号前面是全体减和全体乘。
注意到：\(query(a[i])\) 的值最多只有两种。
对于每一个 \(t\)，\(query(a[i])\) 的变化只是因为树状数组中一开始将 \(t\) 除去了。
如果不除去的话：
对于\(\forall t \leq A_i\)，它加上的是原本的 \(query(a[i]) - 1\)。
对于\(\forall t > A_i\)，它加上的是原本的 \(query(a[i])\)。
于是将每次树状数组中删去 \(t\) 的操作变成：
线段树中区间 \([1, a[i]]\) 加 \(query(a[i]) - 1\)，区间 \([a[i] + 1, m]\) 加 \(query(a[i])\)。

这样就成功用线段树优化掉了一个 \(n\)，复杂度变成 \(O(n \log m)\)，通过此题。

区间乘其实有点难写，考场只剩半个小时自认为是写不完，去打暴力了。
实际订正的时候写错了好几次，有几个地方比较模糊，被回旋镖了。
对于思维不佳的选手，线段树的基础操作应当非常熟练，需要反省。

D

dp，结论比较抽象，不太懂正确性先按下不表/kel。