[toc]

## 1001 A题

题意简述：

形式化题面：

思路：

备注：

## 1002 B题

题意简述：

形式化题面：

思路：

备注：

## 1003 C题

题意简述：

形式化题面：

思路：

枚举 $1\le i < j \le n$ ，

* 若存在 $i\leftrightarrow j+n$ ，考虑 $k\in[1,i-1]$ 中是否存在 $i\leftrightarrow k+n$ 且 $\cdots\leftrightarrow k \leftrightarrow i \leftrightarrow j+n$ 的交错路
* 若存在 $j\leftrightarrow i+n$ ，考虑 $k\in[1,i-1]$ 中是否存在 $k\leftrightarrow i+n$ 且 $\cdots\leftrightarrow k \leftrightarrow i+n \leftrightarrow j$ 的交错路

将上述信息 $O(1)$ 地存放在左侧 $n$ 个点的空间中，并在循环过程中维护。

备注：

## 1004 D题

题意简述：

形式化题面：

思路：

备注：

## 1005 E题

题意简述：

形式化题面：

思路：

备注：n=8 [1,4,0] [5,8,0] [1,8,1]

1 2 3 5 4 6 7 8

9 6
1 2 0
1 3 0
1 4 0
1 5 1
6 9 1
7 9 0

## 1006 F题

题意简述：

形式化题面：

思路：

备注：

## 1007 G题

题意简述：

形式化题面：

思路：

备注：

## 1008 H题

题意简述：

形式化题面：

思路：

备注：

$dp_{i,j}$ 表示 第 $i$ 次操作，解决了区间 $1 \sim j$ 的最优答案

$dp_{i,j} = \max\{dp_{i-1,k} + w[k+1][j][sz[i]]\}$

## 1009 I题

题意简述：

形式化题面：

思路：

先考虑两段异或和相乘，再考虑三段，因为两段的解决了三段肯定也很简单。

设 $pre[i],suf[i]$ 为异或前缀和、后缀和，

$$XOR(i,j)=pre[i-1] \oplus pre[j]$$

$$F(x,y)=\sum_{i=x}^y XOR(i,y)$$

$$G(x,y)=\sum_{i=x}^y XOR(x,i)$$

$$
\begin{aligned}
H(m)
& = \sum_{i=1}^{m-1}F(1,i) \times F(i+1,m)
\end{aligned}
$$

$$
\begin{aligned}
T(n)
& = \sum_{j=2}^{n-1} (H(j) \times \sum_{k=j+1}^n F(j+1,k))
\end{aligned}
$$

$F(1,i)$ 可以预处理，时间空间都是 $O(n)$

$\displaystyle \sum_{k=j+1}^n F(j+1,k)$ 也可以预处理

-------------------

$$XOR(i,j)=pre[i] \oplus pre[j]$$

$$F(x,y)=\sum_{x\le l\le r\le y}XOR(l,r)$$

$$
\begin{aligned}
G(m)
& = \sum_{1\le l_1 \le r_1 < l_2 \le r_2 \le m} XOR(l_1,r_1)\times XOR(l_2,r_2) \\
& = \sum_{k=1}^{m-1} F(1,k)\times F(k+1,m)
\end{aligned}
$$

$$
\begin{aligned}
H(n)
& = \sum_{1\le l_1 \le r_1 < l_2 \le r_2 < l_3 \le r_3 \le n} XOR(l_1,r_1) \times XOR(l_2,r_2) \times XOR(l_3,r_3)\\
& = \sum_{m=1}^{n-1}G(m)\times F(m+1,n) \\
& = \sum_{m=1}^{n-1} \sum_{k=1}^{n-2} F(1,k)\times F(k+1,m)\times F(m+1,n)
\end{aligned}
$$

截止目前已经将 $O(n^6)$ 压到了 $O(n^2)$ 。

备注：

## 1010 J题

题意简述：

形式化题面：n 个数的序列，m 次操作
每次操作给定 x，要求翻转 $a_1,a_2,...,a_x$
并求有多少个 k 使得存在 $1\le i \le x < j \le n$ 且 $a_i=a_j=k$

思路：

备注：$1\le a_i,x\le n$
不存在四个及以上相同的元素
$1\le n,m \le 3\times10^5$

## 1011 K题

题意简述：

形式化题面：

思路：

备注：

## 1012 L题

题意简述：

形式化题面：

思路：

备注：