bzoj 5092 分割序列 —— 高维前缀和
題目：https://www.lydsy.com/JudgeOnline/problem.php?id=5092
首先，處理出異或前綴和 s[i]，i 位置的答案就是 s[j] + s[j]^s[i]，j <= i
異或的套路是按位考慮，但是這里有加法...怎么考慮進(jìn)位？
所以就不能考慮答案的這一位是什么，而應(yīng)該考慮在這一位上的貢獻(xiàn)，那么即使進(jìn)位了，還是各位算各位的貢獻(xiàn)，互相獨(dú)立；
然后發(fā)現(xiàn)，如果 s[i] 在第 k 位上是1，那么 s[j] 的第 k 位無論是0還是1，總體的貢獻(xiàn)都是 1<< k；
而如果 s[i] 在第 k 位上是0，那么如果有一個 s[j] 的第 k 位是1，總體貢獻(xiàn)就是 2 * (1<<k)，否則貢獻(xiàn)是0；
于是現(xiàn)在問題變成在 j <= i 中找到第 k 位是1的 s[j]，并且還要根據(jù)情況，對前面的位有限制；
這個不太好做，不妨變成在第 k 位是1(并且滿足前面位的限制)的所有位置中，找到最靠前的位置 l，看是否 l <= i；
由于只限制某些位是1，其它位隨便，符合了超集的概念，所以用高維前綴和維護(hù)滿足每種限制的位置集合中最靠前的位置即可！
真是巧妙的思路，經(jīng)典的應(yīng)用！
(為什么處理最高位+1的 l 就秒WA，而直接做到20就A了？l 好像也沒有處理錯啊...)
代碼如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const xn=(<<);
int n,l,s[xn],f[xn],bin[];
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
return f?ret:-ret;
}
void init()
{
int t=n; while(t)l++,t>>=;
bin[]=; l++;
for(int i=;i<=l;i++)bin[i]=bin[i-]+bin[i-];
for(int i=;i<(<<l);i++)f[i]=n+;
}
int main()
{
n=rd();
//init();
l=; memset(f,0x3f,sizeof f);
bin[]=;
for(int i=;i<=;i++)bin[i]=bin[i-]+bin[i-];
for(int i=;i<=n;i++)
{
s[i]=rd(); s[i]^=s[i-];
f[s[i]]=min(f[s[i]],i);
}
for(int i=;i<l;i++)
for(int j=;j<(<<l);j++)
if(!(j&bin[i]))f[j]=min(f[j],f[j|bin[i]]);
for(int i=;i<=n;i++)
{
int ans=,t=;
for(int j=l-;j>=;j--)
{
if(s[i]&bin[j]){ans+=bin[j]; continue;}
if(f[t|bin[j]]<=i)ans+=bin[j+],t|=bin[j];
}
printf("%d\n",ans);
}
return ;
}
總結(jié)
以上是生活随笔為你收集整理的bzoj 5092 分割序列 —— 高维前缀和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 转载Spring Introspecto
- 下一篇： ORACLE Physical Stan