仙桃住房和城乡建设部网站,seo主要是指优化,新品发布会新闻稿,wordpress 多站点 主题题目
给定长为n(n1e4)的数组#xff0c;第i个数为ai(0ai2的60次方)
初始时#xff0c;区间为[1,n]#xff0c;也即l1#xff0c;rn#xff0c;
你可以在[l,r)中指定一个k#xff0c;将区间分成左半边[l,k]、右半边[k1,r]
1. 如果左半边异或和与异或和的异…题目
给定长为n(n1e4)的数组第i个数为ai(0ai2的60次方)
初始时区间为[1,n]也即l1rn
你可以在[l,r)中指定一个k将区间分成左半边[l,k]、右半边[k1,r]
1. 如果左半边异或和与异或和的异或和相等则可以二选一要么保留左半边要么保留右半边
2. 否则只能保留异或和大的那半边
当lr时游戏结束
对于每个i判断是否能通过适当操作使得游戏结束时lri
实际t(t1e4)组样例保证sumn不超过1e4
思路来源
力扣群 潼神 题解
这个st[0]和ed[0]实际只需要占一位分开写的话可读性会好一点
此处由于值域限制直接维护在了st和ed的第60位
n1e4说明只能是O(1)转移的区间dp 异或和的两种情况
1. [l,r]异或和为0那么[l,x](xr)和[y,r](yl)的区间都可以异或出
2. [l,r]异或和为s(s≠0)记s的最高位为b
那么如果[l,x](xr)的异或和包含b这一位[l,x]的异或和就一定大于[x1,r]的异或和
同理如果[y,r](yl)的异或和包含b这一位[y,r]的异或和就一定大于[l,y-1]的异或和
判断
①左端点/右端点第60位打过标记说明存在共左端点/右端点的更大的区间异或和为0
②[l,r]异或和为ss和左端点/右端点的标记有交说明存在共左端点/右端点的更大的区间的异或和的最高位能被s取到也就是s比区间另一半大
设位
①如果异或和为0在第60位打标记
②否则在异或和最高位打标记
心得
本题是长区间向短区间下放没怎么写过但本身区间dp也很灵活
由于下放时一定需要固定一个端点所以可以将信息维护在端点处供后续使用
也就只需要开一维不像传统区间dp开两位数组那样了 __builtin_clzll(s)是获取64位数二进制前导0个数
63-__builtin_clzll(s)是获取64位数二进制最高位的1是第几位
从右往左从第0位开始数也就是1b中的b不存在时为-1
32位数时可以对应改成__builtin_clz(s)、31-__builtin_clz(s)
代码
#includebits/stdc.h
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef unsigned ui;
//typedef __uint128_t L;
typedef unsigned long long L;
typedef unsigned long long ull;
const int N1e410,B60;//xor0代表的位
int t,n;
ll v,bl[N],br[N],sum[N];
char ans[N];
bool cal(int l,int r){if(l1 rn)return 1;//之前的[l,R](Rr)的异或和有0//之前的[L,r](Ll)的异或和有0if(bl[l]B1 || br[r]B1)return 1;ll ssum[r]^sum[l-1];return (sbl[l]) || (sbr[r]);//[l,r]的异或和有[l,R](Rr)的异或和的最高位//[l,r]的异或和有[L,r](Ll)的异或和的最高位
}
void op(int l,int r){ll ssum[r]^sum[l-1];int b;if(!s)bB; // 当前[l,r]的异或和有0 else b63-__builtin_clzll(s); // 当前[l,r]的异或和的最高位bl[l]|1llb;br[r]|1llb;
}
int main(){sci(t);while(t--){sci(n);rep(i,1,n){scanf(%lld,v);sum[i]sum[i-1]^v;bl[i]br[i]0;ans[i]0;}per(sz,n,1){rep(l,1,n1-sz){int rlsz-1;//printf(l:%d r:%d ok:%1d s:%lld b:%d\n,l,r,cal(l,r),sum[r]^sum[l-1],63-__builtin_clzll(sum[r]^sum[l-1]));if(cal(l,r)){op(l,r);if(lr)ans[l]1;}}}ans[n1]\0;printf(%s\n,ans1);}return 0;
}
