给定一个非负整数数组 a a a,定义操作:
问对于 ∀ i ∈ [ 1 , n ] \forall i \in [1,n] ∀i∈[1,n],能否从一开始的数组到只留下 a i a_i ai,即 l = r = i l = r = i l=r=i
这里比较明显的是区间的转移,可以考虑用区间 D P DP DP 来解决。对于当前的区间 [ l , r ] [l,r] [l,r],我们定义左边部分的异或和为 s 1 s_1 s1,右边部分的异或和为 s 2 s_2 s2,显然要能够实现 [ l , k ] [l,k] [l,k],必须有 s 1 ≥ s 2 s_1 \geq s_2 s1≥s2。
如果我们直接采用传统区间 D P DP DP 的方法,枚举每一个长度的区间的分界点,时间复杂度会到达 O ( n 3 ) O(n^3) O(n3),记录状态的空间复杂度也过高。
进一步观察发现:
我们如果按照区间长度从大到小枚举区间,对于当前枚举的区间
[
l
,
r
]
[l,r]
[l,r],如果它可达的话,
可以对于区间端点维护四种信息:
对于当前区间 [ l , r ] [l,r] [l,r] 的最高位 b i t bit bit ,如果它可达,
最终时间复杂度: O ( n 2 ) O(n^2) O(n2)
#include<bits/stdc++.h>
#define fore(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;
const int INF=0x3f3f3f3f;
const long long INFLL=1e18;
typedef long long ll;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int t;
std::cin >> t;
while(t--){
int n;
std::cin >> n;
std::vector<ll> a(n + 1);
std::vector<ll> st(n + 1, 0), ed(n + 1, 0);
std::vector<bool> st0(n + 1, false), ed0(n + 1, false);
std::vector<ll> sum(n + 1, 0);
fore(i, 1, n + 1){
std::cin >> a[i];
sum[i] = sum[i - 1] ^ a[i];
}
std::vector<int> ans(n + 1, 0);
for(int len = n; len >= 1; --len)
fore(L, 1, n - len + 2){
int R = L + len - 1;
ll s = sum[R] ^ sum[L - 1];
ll bit = 1ll << std::__lg(s);
if(len == n || st0[L] || ed0[R] || (s & st[L]) || (s & ed[R])){
if(len == 1) ans[L] = 1;
if(!s) st0[L] = ed0[R] = true;
else{
st[L] |= bit;
ed[R] |= bit;
}
}
}
fore(i, 1, n + 1) std::cout << ans[i];
std::cout << endl;
}
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- bangwoyixia.com 版权所有 湘ICP备2023022004号-2
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务