2023年多校联训NOIP层测试3
0x7f
·
·
个人记录
良心场。
T1 数列变换（trans）
诈骗题。
题意：维护多次高维前缀和与差分，最后输出序列的每个元素对 998244353 取模后的值。
思路：众所周知，差分可以当做是前缀和的逆运算，具体的，
令 b_i=\begin{cases}a_i-a_{i-1}&x\in[2,n]\\a_1&i=1\end{cases}，则有：
-
a_n=\sum\limits_{i=1}^nb_i
-
\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^n\sum\limits_{j=1}^ib_j=\sum\limits_{i}^n(n-i+1)b_i
所以抵消掉次数后直接跑即可，注意负数取模的处理。
Extend.
T2 超级质数（super）
板子题。
题意：n 组询问，求 [l,r] 内各位数字互不相同的质数的个数（n \le 10^5;l,r\le4\times10^7）。
赛时看到这题空间 64MB，一看数组开不下，以为正解是数位DP，果断选择分块打表。压缩了半天字符集，结果 TLE 20pts。赛后听 bdfs_then_csdn 讲题才意识到 int 数组只需要开到 \pi(n)，这下消愁了。
思路：预处理所有合法质数，二分回答每个询问即可。
T3 区间加和（sum）
题意：有一条从 1 到正无穷的数轴，初始每个整数均有一个为 0 的权值。
进行 n 次操作如下：
```cpp
while (n--) {
int op; ll k; cin >> op >> k;
if (op == 1) v.insert(lower_bound(all(v), k), k);
else {
if (!v.size()) {
cout << 0 << '\n'; continue;
}
ll ans = 0;
for (auto it = v.begin(); it != v.end() && *it < k; it++) {
ans += __lg(k - *it);
}
cout << ans << '\n';
}
}
```
## T4 距离序列（dseq）
题意：求满足以下所有条件的长度为 $n$ 的整数序列的个数，对 $998244353$ 取模。
- $1\le a_i\le m(1 \le i \le n)
-
\mid a_i-a_{i+1}\mid\ge k(1\le i\le n-1)
```cpp
void dfs(int now) {
if (now == n) {
bool f = true;
for(int i = 0; i < n - 1; i++) if (abs(res[i] - res[i + 1]) < k) { f = false; break; }
ans += f;
return;
}
for (int i = 1; i <= m; i++) {
if (now != 0 && abs(i - res[res.size() - 1]) < k) continue;
res.emplace_back(i);
dfs(now + 1);
res.pop_back();
}
}
```
总结：要清楚知道板子中每一句话的意义（刚重修完差分，xrlong正重修线性筛）。看清楚题再写。