NOIP2023模擬13聯(lián)測34 總結(jié)

比賽過程

看了一下題，感覺就 $T2$ 有一點思路。

$T1$ 先打一個 $30$ 分暴力，感覺要分位考慮，想了大概 $1h$ 就跳了。

$T2$ 想到了先求出整個區(qū)間的長度乘上包含這個區(qū)間的總數(shù)再減去重復(fù)算的，想了很久，只會相鄰的，只好打個暴力，發(fā)現(xiàn)線段樹超時，加上離散化又掛了，于是調(diào)了好久都沒調(diào)出來。只好跳了

$T3$ 趕緊打個暴力

$T4$ 檢查了前 $3$ 題代碼后沒什么時間了，題也沒看懂

題目

A. origen

題目大意

給定 $n$ 個整數(shù) $a_1,a_2,a_3?a_n$ ，求
$$\sum _{i=1}^n\sum _{j=i}^n({\oplus }_{k=i}^j{a}_k{)}^2\mathrm{mod}998244353$$
$n\le 2?10^5,0\le a_i\le 2?10^5$

思路

設(shè) $s_i={\oplus }_{j=1}^i{a}_j$ ，則原式變?yōu)?#xff1a;
$$\sum _{i=0}^{n?1}\sum _{j=1}^n(s_i\oplus s_j{)}^2$$
按位考慮，一個數(shù)可以用二次冪的和來表示?？紤]怎么處理平方。

因為:
$$(\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$ 的每一位分開求貢獻(xiàn)，當(dāng)前處理到第 $j$ 位

設(shè)前 $i?1$ 個數(shù)這一位為 $0$ 的數(shù)有 $s0$ 個，為 $1$ 的數(shù)有 $s1$ 個

那么求這一位的貢獻(xiàn)

• 若當(dāng)前這一位為 $1$ ：$2^j?2?s0$
• 若當(dāng)前這一位為 $0$ ：$2^j?2?s1$

然后處理后面的那項

先枚舉兩位 $j1,j2$

當(dāng)前處理到第 $i$ 位

設(shè) $su{m}_{k,l}$ 為前面 $i?1$ 個數(shù)的第 $j1$ 位為 $k$ ，第 $j2$ 位為 $l$ 的個數(shù)

設(shè)第 $i$ 個數(shù)這兩位分別是 $x,y$

那么這里的貢獻(xiàn)為：$2?2^{j1}?2^{j2}?su{m}_{!x,!y}$

B.competition

題目大意

現(xiàn)在有 $n$ 個區(qū)間 $[l_i,r_i]$ ，現(xiàn)在問你選取若干的連續(xù)的區(qū)間的區(qū)間并的大小的和。

思路

設(shè) $pr{e}_{i,j}$ 表示前 $i?1$ 個區(qū)間內(nèi)，包含點 $j$ 的最靠右的數(shù)是多少。

可以發(fā)現(xiàn)答案就是
$$\sum _{i=1}^n(r_i?l_i+1)?i?(n?i+1)?pr{e}_{i,j}?(n?i+1)$$
也就是這個區(qū)間被記入答案的次數(shù)乘上區(qū)間的大小再減去重復(fù)的次數(shù)

可以用一棵線段樹維護(hù)加離散化來維護(hù)。

先統(tǒng)計答案，然后用線段樹更新 $pre$

要卡常

C. tour

題目大意

有 $n$ 個城市，每個城市有一個文化值 $va{l}_i$

接下來有兩種操作

• 0 x y

  表示城市 $x$ 和城市 $y$ 之間建立一條無向邊 （保證修建前 $x$ 和 $y$ 不連通）

• 1 x y

? 代表有一個人，初始時他的文化值為 $0$ ，他會從 $x$ 走到 $y$ （保證此時 $x$ 與 $y$ 連通），每走到一個城 市 $i$，他會與這個城市進(jìn)行文化交流，如果此時他的文化值大于等于 $va{l}_i$ ，那么這次文化交流是 成功的。無論文化交流結(jié)果如何，在此之后，他的文化值會加上 $va{l}_i$ 。求出成功的文化交流的次數(shù)。

D.abstract

題目大意

定義函數(shù) $f(i,j),g(i,j)$ ，分別表示 $i\to j$ 的權(quán)值和權(quán)值或，想要求出 ${\sum }_{i=1}^n{\sum }_{j=1}^{n}f(i,j{)}^{g(i,j)}$

把 $f(i , j) , g(i , j) $ 放到 $i\to j$ 的簡單路徑上的點權(quán)和點權(quán)或

輸出答案 $\mathrm{mod}111121$

定義：$0^0=0$