NOIP2023模拟13联测34 总结

NOIP2023模拟13联测34 总结
- 比赛过程
- 题目

比赛过程

看了一下题，感觉就 $T2$ 有一点思路。

$T1$ 先打一个 $30$ 分暴力，感觉要分位考虑，想了大概 $1h$ 就跳了。

$T2$ 想到了先求出整个区间的长度乘上包含这个区间的总数再减去重复算的，想了很久，只会相邻的，只好打个暴力，发现线段树超时，加上离散化又挂了，于是调了好久都没调出来。只好跳了

$T3$ 赶紧打个暴力

$T4$ 检查了前 $3$ 题代码后没什么时间了，题也没看懂

题目

A. origen

题目大意

给定 $n$ 个整数 $a_1,a_2,a_3\cdots a_n$ ，求

\[\sum_{i = 1}^n\sum_{j = i}^n(\oplus_{k = i}^ja_k)^2 \mod 998244353 \]

$n\le 2 * 10^5 , 0\le a_i \le 2 * 10 ^5$

思路

设 $s_i = \oplus_{j = 1}^i a_j$ ，则原式变为：

\[\sum_{i = 0}^{n - 1} \sum_{j = 1}^n (s_i \oplus s_j)^2 \]

按位考虑，一个数可以用二次幂的和来表示。考虑怎么处理平方。

因为:

\[(\sum_{i = 1}^n a_i)^2 = \sum_{i = 1}^i a_i^2+ 2\sum_{i = 1}^{n - 1}\sum_{j = i +1}^n a_i*a_j \]

把两部分分开处理。

先处理前面的那项

把 $i$ 的每一位分开求贡献，当前处理到第 $j$ 位

设前 $i - 1$ 个数这一位为 $0$ 的数有 $s0$ 个，为 $1$ 的数有 $s1$ 个

那么求这一位的贡献

若当前这一位为 $1$ ：$2^j*2*s0$
若当前这一位为 $0$ ：$2^j*2*s1$

然后处理后面的那项

先枚举两位 $j1 , j2$

当前处理到第 $i$ 位

设 $sum_{k , l}$ 为前面 $i - 1$ 个数的第 $j1$ 位为 $k$ ，第 $j2$ 位为 $l$ 的个数

设第 $i$ 个数这两位分别是 $x , y$

那么这里的贡献为：$2 *2^{j1} * 2^{j2} *sum_{!x , !y}$

B.competition

题目大意

现在有 $n$ 个区间 $[l_i , r_i]$ ，现在问你选取若干的连续的区间的区间并的大小的和。

思路

设 $pre_{i , j}$ 表示前 $i - 1$ 个区间内，包含点 $j$ 的最靠右的数是多少。

可以发现答案就是

\[\sum_{i = 1}^n (r_i - l_i +1) * i * (n - i + 1) - pre_{i , j} * (n - i +1) \]

也就是这个区间被记入答案的次数乘上区间的大小再减去重复的次数

可以用一棵线段树维护加离散化来维护。

先统计答案，然后用线段树更新 $pre$

要卡常

C. tour

题目大意

有 $n$ 个城市，每个城市有一个文化值 $val_i$

接下来有两种操作

0 x y

表示城市 $x$ 和城市 $y$ 之间建立一条无向边（保证修建前 $x$ 和 $y$ 不连通）
1 x y

代表有一个人，初始时他的文化值为 $0$ ，他会从 $x$ 走到 $y$ （保证此时 $x$ 与 $y$ 连通），每走到一个城市 $i$，他会与这个城市进行文化交流，如果此时他的文化值大于等于 $val_i$ ，那么这次文化交流是成功的。无论文化交流结果如何，在此之后，他的文化值会加上 $val_i$ 。求出成功的文化交流的次数。