NOI Online 2020 #1

序列

一个长度为 $n$ 的整数序列 $a_{1 \dots n}$，判断能否通过若干次操作把它变成序列 $b_i$。

有 $m$ 种可选的操作，第 $i$ 种操作可使用三元组 $(t_i,u_i,v_i)$ 描述：

• 若 $t_i=1$，则她可以使 $a_{u_i}$ 与 $a_{v_i}$ 都加一或都减一；
• 若 $t_i=2$，则她可以使 $a_{u_i}$ 减一、$a_{v_i}$ 加一，或是 $a_{u_i}$ 加一、$a_{v_i}$ 减一，因此当 $u_i=v_i$ 时，这种操作相当于没有操作。

每种操作可以无限次进行

对于测试点 $1 \sim 5$：$n=2$，$m=1$，$a_i,b_i \le 99$，$u_1 \ne v_1$，$t_1=1$。
对于测试点 $6 \sim 10$：$n=2$，$m=1$，$a_i,b_i \le 99$，$u_1 \ne v_1$，$t_1=2$。
对于测试点 $11 \sim 12$：$n=2$，$a_i,b_i \le 99$，$u_i \ne v_i$。
对于测试点 $13 \sim 16$：$t_i=2$。
对于测试点 $17$：$n,m \le 20$。
对于测试点 $18$：$n,m \le 10^3$。
对于所有测试点：$1 \le T \le 10$，$1 \le n,m \le 10^5$，$1 \le a_i,b_i \le 10^9$，$t_i \in \{1,2\}$，$1\le u_i,v_i \le n$。

从部分分入手先看只有操作 $2$，操作 $2$ 的特点就是一加一减，那么我们考虑把所有能联通的点缩点成为一个连通块，那么我们就发现对于同 $1$ 个连通块，联通块内的每个点都可以任意变化，但前提是总和不变，因此对此类操作仅仅只需判断 $a,b$ 相对应的连通块内，点集之和是否相等。

再看只有操作一，操作一是同加同减，很显然还是同一个连通块内的奇偶性不变，并且每个元素还能任意变化，还有集合中若划分为两集合，是集合对应操作，那么差值是不变的，因此只需判断奇偶是否相同即可，可是这个是有前提的，我们必须要划分出两个集合去判断。

直接推广到两操作混合。

序列通过操作已经分成若干集合，那么我们其实可以考虑二分图，连通块之间是否相等我们直接考虑对应元素做差，最主要的还是操作 $2$，因为二分图是最好能判断差值是否相等，若形不成那么就判断奇偶性是否相等。

1操作考虑并查集维护连通性，二操作考虑连边判断

$O(T(n+m)\alpha(n))$

$\alpha(n) \approx 4$

冒泡排序

给定一个 $1 ∼ n$ 的排列 $p_i$，接下来有 $m$ 次操作，操作共两种：

1. 交换操作：给定 $x$，将当前排列中的第 $x$ 个数与第 $x+1$ 个数交换位置。
2. 询问操作：给定 $k$，请你求出当前排列经过 $k$ 轮冒泡排序后的逆序对个数。
   对一个长度为 $n$ 的排列 $p_i$ 进行一轮冒泡排序的伪代码如下：

1
2
3

for i = 1 to n-1:
  if p[i] > p[i + 1]:
    swap(p[i], p[i + 1])

$2 \leq n,m \leq 2 \times 10^5$，$t_i \in \{1,2\}$，$1 \leq x < n$，$0 \leq k < 2^{31}$。

众所周知冒泡排序是 $O(n^2)$，其本质就是单次交换逆序对减少 $1$，那么我们就发现对于一次操作所有元素 $i$，在 $<i$ 与其匹配的逆序对个数减小 $1$，因此查询操作是很简单的，就是对于逆序对相同的位置，他们肯定是在逆序对轮下他们是不动的，然后剩下的都 $-1$，若记录 $<i$ 与其匹配的逆序对个数为 $x$，那么总的减少的就是 $n-x$。

直接使用树状数组维护即可，好疑惑他为何要求一个前缀和？

考虑交换，交换根据实际意义逆序对的增减，放在树状数组上就好了。

最小环

打表找规律发现，无论 $k$ 为即，当原序列从小到大排序玩 $i$ 向 $i+2$ 连边是最优的，在发现，对于一个 $k$ 距离长度，本质不同的环只有 $gcd(n,k)$，那么环长应该是 $\frac{n}{gcd(n,k)}$。

我们直接枚举环上每个新环的点，答案此时必然是最优的。

NOI Online 2020 #3

水壶

贪心求解即可。

问题转化为连续 $k+1$ 个数的和的最大值。

记前缀和 $S_i=\sum_{j=1}^ia_j$，则 $ans=\max\{S_i-S_{i-k-1}|k+1 \le i \le n \}$

复杂度 $O(n)$

魔法值

给定 $n$ 节点无向图 $G(V,E)$，初始点权为 $f_i$，每回合第 $i$ 个点的点权为上一回合所有相邻节点的点权的异或值。

给定 $q$ 此询问，问第 $x$ 回合 $1$ 号点的点权。

形式操作：

$$f_{x,j}=f_{v_1,j-1}\oplus f_{v_2,j-1}\oplus \cdots\oplus f_{v_k,j-1}$$

其中 $j\ge 1$，$v_1,v_2,\cdots,v_k$ 是所有与 $x$ 号城市直接相连的城市，$\oplus$ 为异或运算。

• 对于 $20\%$ 的数据，满足 $a_i \leq 100$。

$O(qm)$ 暴力

• 对于 $40\%$ 的数据，满足 $n \leq 20$。
  $O(n^3 q \log n)$

• 另有 $30\%$ 的数据，满足 $m=\frac{n(n-1)}{2}$。

不会。

• 对于 $100\%$ 的数据，满足 $1 \leq n,q \leq 100$，$1 \leq m \leq \frac{n(n-1)}{2}$，$1\leq a_i < 2^{32}$，$0\leq f_i < 2^{32}$。

考虑二进制拆分，提前预处理。

$O(n^3 q \log n) \rightarrow O(n^2 q \log n)$

优秀子序列

给定长度为 $n$ 的非负整数序列 $A$，求满组一下要求的子序列的贡献之和（子序列）不要求连续。

• 对于任意 $i ,j \in [1,m]$，$i \not ={j}$，满足 $B_i \And B_j=0$。
• 贡献是 $\phi(1+\sum_{i=1}^mB_i$。

$n\le 10^6，a_i \le 2\times 10^5$

分析

先考虑子序列中任意两个不同的数按位与等于0，说明相加不可能产生进位。

即 $1+\sum_{i=1}^mB_i\le2^{18}$

设 $d=\lfloor\log_2max\{A_i\}\rfloor$

那么预处理 $2^{18}$ 的欧拉函数。

$\dots$

__END__