題目
給定長為n(n<=1e4)的數(shù)組，第i個數(shù)為ai(0<=ai<2的60次方)
初始時，區(qū)間為[1,n]，也即l=1，r=n，
你可以在[l,r)中指定一個k，將區(qū)間分成左半邊[l,k]、右半邊[k+1,r]
1. 如果左半邊異或和與異或和的異或和相等，則可以二選一，要么保留左半邊，要么保留右半邊
2. 否則，只能保留異或和大的那半邊
當(dāng)l=r時，游戲結(jié)束
對于每個i，判斷是否能通過適當(dāng)操作，使得游戲結(jié)束時l=r=i
實際t(t<=1e4)組樣例，保證sumn不超過1e4
思路來源
力扣群 潼神
題解
這個st0[i]和ed0[i]實際只需要占一位，分開寫的話可讀性會好一點
此處由于值域限制，直接維護在了st[i]和ed[i]的第60位
n=1e4，說明只能是O(1)轉(zhuǎn)移的區(qū)間dp
異或和的兩種情況：
1. [l,r]異或和為0，那么[l,x](x<r)和[y,r](y>l)的區(qū)間都可以異或出
2. [l,r]異或和為s(s≠0)，記s的最高位為b，
那么，如果[l,x](x<r)的異或和包含b這一位，[l,x]的異或和就一定大于[x+1,r]的異或和
同理，如果[y,r](y>l)的異或和包含b這一位，[y,r]的異或和就一定大于[l,y-1]的異或和
判斷
①左端點/右端點第60位打過標(biāo)記，說明存在共左端點/右端點的更大的區(qū)間異或和為0
②[l,r]異或和為s，s和左端點/右端點的標(biāo)記有交，說明存在共左端點/右端點的更大的區(qū)間的異或和的最高位能被s取到，也就是s比區(qū)間另一半大
設(shè)位
①如果異或和為0，在第60位打標(biāo)記
②否則，在異或和最高位打標(biāo)記
心得
本題是長區(qū)間向短區(qū)間下放，沒怎么寫過，但本身區(qū)間dp也很靈活
由于下放時一定需要固定一個端點，所以可以將信息維護在端點處供后續(xù)使用
也就只需要開一維，不像傳統(tǒng)區(qū)間dp開兩位數(shù)組那樣了
__builtin_clzll(s)是獲取64位數(shù)二進制前導(dǎo)0個數(shù)
63-__builtin_clzll(s)是獲取64位數(shù)二進制最高位的1是第幾位
從右往左，從第0位開始數(shù)，也就是1<<b中的b，不存在時為-1文章來源：http://www.zghlxwxcb.cn/news/detail-698859.html
32位數(shù)時，可以對應(yīng)改成__builtin_clz(s)、31-__builtin_clz(s)文章來源地址http://www.zghlxwxcb.cn/news/detail-698859.html
代碼
#include<bits/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 pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#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 N=1e4+10,B=60;//xor=0代表的位
int t,n;
ll v,bl[N],br[N],sum[N];
char ans[N];
bool cal(int l,int r){
if(l==1 && r==n)return 1;
//之前的[l,R](R>r)的異或和有0
//之前的[L,r](L<l)的異或和有0
if(bl[l]>>B&1 || br[r]>>B&1)return 1;
ll s=sum[r]^sum[l-1];
return (s&bl[l]) || (s&br[r]);
//[l,r]的異或和有[l,R](R>r)的異或和的最高位
//[l,r]的異或和有[L,r](L<l)的異或和的最高位
}
void op(int l,int r){
ll s=sum[r]^sum[l-1];
int b;
if(!s)b=B; // 當(dāng)前[l,r]的異或和有0
else b=63-__builtin_clzll(s); // 當(dāng)前[l,r]的異或和的最高位
bl[l]|=1ll<<b;
br[r]|=1ll<<b;
}
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,n+1-sz){
int r=l+sz-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(l==r)ans[l]='1';
}
}
}
ans[n+1]='\0';
printf("%s\n",ans+1);
}
return 0;
}到了這里，關(guān)于Pinely Round 2 (Div. 1 + Div. 2) F. Divide, XOR, and Conquer(區(qū)間dp)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
