题解：P10690 Fotile 模拟赛 L

不懂为啥都可持久化 Trie，甚至有的人还用区间 dp 过了。

这里讲一种比区间 dp 更好写，且跑的更快的做法，时间复杂度也为

O(n^2)

。

代码压一压 596B。

Solution

先求前缀异或和是自然的。

考虑对于每个

i

预处理出

f_{i, j}(j < i)

表示

pre_i \oplus pre_k(j \le k < i)

的最大值。这个直接扫一遍就做完了。时间复杂度

O(n^2)

，当然还有个

\frac{1}{2}

的常数。空间复杂度也是这个，开一维数组就不会爆。

然后查询的时候就是

\max_{l \le i \le r}\{f_{i, l-1}\}

。时间复杂度

O(nq)

。

比区间 dp 快了 300ms。

AC Code

CPP

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 12005;
int f[N * N / 2];
int n, m, a[N];
int pre[N];
int get(int x, int y) {
	if (x == y) return 0;
	return x * (x - 1) / 2 + y + 1;
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> m;
	For(i ,1, n) cin >> a[i];
	For(i, 1,n) pre[i] = pre[i - 1] ^ a[i];
	For(i ,1, n) Dec(j, i - 1, 0) f[get(i, j)] = max(f[get(i, j + 1)], pre[i] ^ pre[j]);
	int lastans = 0;
	while (m--) {
		int x, y;
		cin >> x >> y;
		x = (1ll * x + lastans) % n + 1;
		y = (1ll * y + lastans) % n + 1;
		if (x > y) swap(x, y);
		lastans = 0;
		For(i, x, y) lastans = max(lastans, f[get(i, x - 1)]);
		cout << lastans << '\n';
	}
	return 0; 
}

这里再给个压行的。

AC Code

CPP

#include <iostream>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);Ti++)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);Ti--)
const int N=12005;
int n,m,a[N],f[N*N/2],pre[N],x,y,lastans;
int get(int x,int y){return x*(x-1)/2+y+1;}
int main(){
	cin>>n>>m;
	For(i,1,n)cin>>a[i];
	For(i,1,n)pre[i]=pre[i-1]^a[i];
	For(i,1,n)Dec(j,i-1,0)f[get(i,j)]=max(f[get(i,j+1)],pre[i]^pre[j]);
	while(m--){
		cin>>x>>y;
		x=(1ll*x+lastans)%n+1,y=(1ll*y+lastans)%n+1;
		if(x>y)swap(x,y);
		lastans=0;
		For(i,x,y)lastans=max(lastans,f[get(i,x-1)]);
		cout<<lastans<<'\n';
	}
	return 0; 
}

题解：P10690 Fotile 模拟赛 L

文章操作

Solution

相关推荐

评论

题解：P10690 Fotile 模拟赛 L