24pht春1

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/136814064

A

1询问除2外所有点，2询问所有除1外所有点，然后直接取 $\min(f_{1,x}+f_{x,2})$ 即可。

剩下只有最后一种情况，1和2有直接连边。那应该满足所有 $\forall x\in [3,n],|f_{1,x}-f_{2,x}|=1$

感觉和我的做法差不多，只是判1，2连边那一步不一样，不知道有没有问题。

题解就是把1、2附近所有点找出来。

自己思考了一下，1，2中有1个点用我自己的方法判了，只有2个点的情况会被hack。考虑此时必然存在两个点 $A,B$ ，满足 $dis(A,1)+dis(A,2)=dis(B,1)+dis(B,2)$ 。

B

感觉直接做挺对的。把所有相邻的逆序对丢到奇、偶set里，然后直接做。

每次直接把最后满足奇偶性位置的拿出来做交换。

毕竟理论上一个排列至多交换 $\frac{n(n-1)}{2}$ ，乘2后就是 $n(n-1)$ 。这么看次数是没问题的。

题好像看错了。

每次操作必须进行。 ~~现在只需要证明在不满足的条件在~~

好像突然间不会了。

直接做，不行询问1或2，感觉是没问题的

题解：每次把 $p_n$ 换到 $n$ 。如果不行就动1或2。

嗯，和我的一模一样。

C

要求在 $j$ 最小的情况下 $i$ 最大。

考虑从小到大枚举 $j$ ，对于每个位置暴力把所有相同的令 $cnt(j,i)++$ 。 $cnt$ 的上界是 $k$ 。

这样子已经可以保证 $j$ 最下且复杂度正确了，但不能保证 $i$ 最大。如果 $cnt$ 超过5，我们就钦定不再统计，直接拿个bitset维护即可。

$O(\frac{n^2m}{\omega})$ ，在5s情况下应该能过。

好像和我的有一点不一样。

先扫一遍找出 $j$ 。然后再做一遍暴力找出最大的 $i$ ，那样子复杂度是 $O(n^2k+nmk)$ 。

D

枚举因子，然后扫一遍数组显然是必要的。

也就是在 $k$ 确定的情况下 $O(n)$ 确定最小值，而这个 $O(n)$ 只能丢到枚举位置里。

处理出前后缀模 $k$ 位置的和是容易的，这样子就有个 $O(n\log^2 n)$ 的做法。

显然移动位置变化时那个长为 $k$ 的变化时 $O(1)$ 的。所以现在是一个数组，单点修改，求max/min。这也是必须带 $\log$ 的。但是个 $\log$ 是 $k$ 而不是 $n$ 的，在5s的情况下应该能卡？

但这样子按照题解是TLE的。

后面的 $O(n\log k)$ 是个经典问题，是优化不了的了，只能去搞外层 $k$ 了。

里面 $\log$ pht说能减。因为每次修改有单调性，可以维护前后缀min/max。

但外层 $k$ 也是能优化的。设 $k=a\times b$ ，现在是 $S_{max},S_{min}$ 。我们变成 $b$ ，显然有 $S'_{max}\le a\times S_{max},S'_{min}\ge a\times S_{min}$ 。这样子比例就必然会变小。

那样子我们就只用枚举 $n$ 的所有素因子即可。

E

操作2就是个单点修改。

对下标建trie树。然后按位往下来，再加个 $[0,1]_2$ 表示是否达到上下界，每到一个地方判断一下能不能继续走即可。如何当前为 $[0][0]$ 直接返回子树异或和即可。

正确性感觉没太大问题，尝试证一下复杂度。

感觉只要在某个节点能分叉走，则必然会导致往其中一个方向走时某个状态由 $1$ 变成 $0$ ，证毕。复杂度上界是 $O(n\log^2n)$

有更巧妙的做法。先补齐至 $2^k$ 。

每次询问相当于Xor-shift，然后询问 $[l,r]$ 。

考虑上面的过程变成dfs。考虑 $dfs(L,2^k,l,r,V)$ ，分别表示当前实际区间、询问区间， $V$ 是要shft的值。主函数调用 $dfs(0,2^{20},l,r,x)$ 。

考虑当前所在位置是否交换，只有三种情况

递归右区间
递归左区间
递归左 + 右区间

但把必须考虑偏移量。

和线段树一样返回区间。

可以直接树状数组维护，当然线段树也行。只需要实行dfs。

我最后打的是树状数组写法。大致就是维护两个区间 $[l,r],[L,R]$ 代表现在的区间和 $\oplus x$ 后的区间。

F

不清楚直接fhq能不能支持区间交换，个人感觉没啥大问题。

如果直接维护所有长为 $2^k$ 的区间的和显然行不通。

和E一样。

操作2相当于Xor-shift $2^k$ 。

操作3就是Xor-shift $2^k-1$ 。

（为什么感觉反了？）

然后就行了。

确实反了。可以理解成给每个层打个标记，更可以直接理解成直接多维护一个数

G

把序列看成线段树，每次相当于把线段树某一层所有相邻节点两两交换。首先这个转化是显然等价的。

如果直接拿普通线段树求最大子段和的方法似乎不好做。

XorSegmentTree。

同上，有 $i\to i\oplus 2^k$ 。

正常线段树求最大子段和要维护三个东西 $(L,V,R)$ 。而我们现在有一个异或值，因此有 $(L,V,R)_i$ 。

每个东西可以从下一层merge过来。

每个节点会存当前对应叶子节点个数的值（即 $i$ 的规模），所以总共有 $n\log n$ 个。

询问是 $O(1)$ 的，因为只需要把所有历史异或值全部异或起来，然后在根节点询问即可。

好像有神秘格雷码做法。

打了第一种做法，就是合并就行

H

根据题意和显然的性质，每个 $x$ 对应的序列都是两两不同的。因此 $x$ 和 $2^n$ 的序列直接形成双射。现在问题转化为这类序列满足什么性质。

打了个 $n=4$ 的表：

 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 
 2  1  4  3  6  5  8  7 10  9 12 11 14 13 16 15 
 3  4  1  2  7  8  5  6 11 12  9 10 15 16 13 14 
 4  3  2  1  8  7  6  5 12 11 10  9 16 15 14 13 
 5  6  7  8  1  2  3  4 13 14 15 16  9 10 11 12 
 6  5  8  7  2  1  4  3 14 13 16 15 10  9 12 11 
 7  8  5  6  3  4  1  2 15 16 13 14 11 12  9 10 
 8  7  6  5  4  3  2  1 16 15 14 13 12 11 10  9 
 9 10 11 12 13 14 15 16  1  2  3  4  5  6  7  8 
10  9 12 11 14 13 16 15  2  1  4  3  6  5  8  7 
11 12  9 10 15 16 13 14  3  4  1  2  7  8  5  6 
12 11 10  9 16 15 14 13  4  3  2  1  8  7  6  5 
13 14 15 16  9 10 11 12  5  6  7  8  1  2  3  4 
14 13 16 15 10  9 12 11  6  5  8  7  2  1  4  3 
15 16 13 14 11 12  9 10  7  8  5  6  3  4  1  2 
16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

感觉很像FFT的那个过程。也很像上一题，有些层可以转，有些层不用转。

~~那样子就可以像线段树那样，对于~~ 不对，每层要么都转，要么都不转。

还是Xor-Segment Tree。

怎么比较两个串哪个更小。考虑存哈希。

$h(i)$ 表示当前用 $i$ 后的哈希值。比较左右串谁更小。

Eg： $A_2=B_2+C_2,A_3=C_3+B_3$

哈希值相等，说明一样大
哈希值不同
1. $B_2=C_3$ ，递归至 $C_2,B_3$
2. 否则递归到 $B_2,C_3$

另一种做法，倍增 + 类似后缀数组的东西

我打的是倍增 + 类后缀数组的做法。

考虑一个倍增构造串，必然有 $f(x,2^k)=f(x,2^{k-1})+f(x\oplus 2^{k-1},2^{k-1})$ 。

因此我们枚举 $k$ ，然后写一个排序函数即可。

I

只剩下一堆时必胜。

剩下两堆， 1 1 必败。（假设左边先手）。否则 x 1 是必胜的。

在 x y 的情况下可以和上面一起归纳，谁先把自己的拿完，谁就输。 $x>y$ 是先手的必胜态。

现在如果有 $x\ge y$ ，对于 z x y 显然先手必胜。否则如果 $z=1$ 或者 $x\ge z-1$ 则先手必败。

剩下大致是 $z-1>x<y$ 的情况。 ~~此时直接比较 $z,y$ 的大小就行了。因为谁拿剩2堆时对手就赢了。~~ 不对，会拿到小于 $x$ 的情况。等一下，如果拿到小于 $x$ 也输了，所以好像还是对的。

还有就是每次要么拿一堆，要么拿一个，这个结论感觉没什么大问题。

考虑区间DP。 $L(i,j,k),R(i,j,k)$ ， $k\in[1,a_{i或j}]$ 。要么取 $1$ ，要么全取。

正常DP要存结果和状态。考虑把状态和存的东西交换。

把 $k$ 取出来，显然满足存在一个 $k$ ，只要大于等于这个 $k$ 先手就必胜。

现在就变成了 $L(i,j)$ 和 $R(i,j)$ 了。

考虑转移。什么时候全取，什么时候取一个。

全取前提： $a_j<R(i+1,j)$ ，这是必要的（好像也是充分的）。否则取 $1$ 个。

取 $1$ 个能不能胜？若 $a_i-1<L(i,j-1)$ ，则必败的。所以至少要有 $L(i,j-1)+1+c$ 。

此时大家都只能一个一个取了。

出现变化时 $a_j\to R(i+1,j)-1$ ，此时后手必败。这里的步数就是先手必须有的步数，也就是 $c$ 。

因此：

一步胜，为1！
不行，一步败，为0
僵持状态，看谁先死。

J

有点神秘，没有任何思路，明天再想。

转化为这样一个模型：

考虑一个长度为 $30n$ 的01二进制（超级大的数），以及 $\binom n 2$ 组二进制数（任意一个 $i,j$ ），会在某60位（各30）有1。每次/可以选这其中一个二进制数异或这个值。

问线性基有多少个元素。

显然现在有一个高斯消元的做法，复杂度大概是 $O((30n)^2\binom n 2)$ 。

考虑消元的过程。现在 $X$ ，和每个基去检查。如果有那个基的1，则去异或。

也就是要去找自己的合适位置，而这不用取找 $30n$ 个位置，其实只需要去检查 $60$ 个位置，可以优化掉很多了。

伪代码大致如下：

for i to n
	for j in [i + 1, n]
		// 把60位拆成两个30位
		if Bas[i].insert(a[i] xor a[j]) or Bas[j].insert(a[j] xor a[j])
		//是否存在一个位置可以插入
			cnt++; // cnt为最终基的个数

令 $a'_i=a_i|(2^{30})$ ，在异或时是没影响的。晕掉了