【BZOJ5092】【Lydsy1711月赛】分割序列

超集和变换即可。

s_i=\bigoplus_{j=1}^ia_j ,容易看出原题相当于对于每个 i ,求 s_j+s_j \oplus s_i(1 \leq j \leq i) 的最大值。

考虑分离出 s_i ,注意到异或可以被看成不退位减法:

a\oplus b=a-b+2\times ((\lnot a) \land b)

于是 s_j+s_j \oplus s_i=s_i+2\times ((\lnot s_i) \land s_j) ,我们只需求出 (\lnot s_i) \land s_j 的最大值即可。

注意到一个数的超集不会比他本身更劣,可以想到使用超集和变换求出每个数的超集的最小出现时间。

然后直接按位贪心就好了。

时间复杂度 O((n+a_i) \log a_i)

Code

  1. //x+(sum^x)=sum+2*(x&(~sum))
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. const int MAXSIZE=10000020;
  6. int bufpos;
  7. char buf[MAXSIZE];
  8. #define NEG 0
  9. void init(){
  10. #ifdef LOCAL
  11. freopen("5092.txt","r",stdin);
  12. #endif
  13. buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  14. bufpos=0;
  15. }
  16. #if NEG
  17. int readint(){
  18. bool isneg;
  19. int val=0;
  20. for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  21. bufpos+=(isneg=buf[bufpos]=='-');
  22. for(;isdigit(buf[bufpos]);bufpos++)
  23. val=val*10+buf[bufpos]-'0';
  24. return isneg?-val:val;
  25. }
  26. #else
  27. int readint(){
  28. int val=0;
  29. for(;!isdigit(buf[bufpos]);bufpos++);
  30. for(;isdigit(buf[bufpos]);bufpos++)
  31. val=val*10+buf[bufpos]-'0';
  32. return val;
  33. }
  34. #endif
  35. char readchar(){
  36. for(;isspace(buf[bufpos]);bufpos++);
  37. return buf[bufpos++];
  38. }
  39. int readstr(char* s){
  40. int cur=0;
  41. for(;isspace(buf[bufpos]);bufpos++);
  42. for(;!isspace(buf[bufpos]);bufpos++)
  43. s[cur++]=buf[bufpos];
  44. s[cur]='\0';
  45. return cur;
  46. }
  47. int a[300002],f[1<<20];
  48. int query(int x,int t){ //f[]<=t
  49. int ans=0;
  50. for(int i=19;i>=0;i--)
  51. if (x>>i&1){
  52. int qwq=ans|(1<<i);
  53. if (f[qwq]<=t)
  54. ans=qwq;
  55. }
  56. return ans;
  57. }
  58. int main(){
  59. init();
  60. int n=readint();
  61. memset(f,0x3f,sizeof(f));
  62. f[0]=0;
  63. for(int i=1;i<=n;i++){
  64. a[i]=readint()^a[i-1];
  65. f[a[i]]=min(f[a[i]],i);
  66. }
  67. for(int i=0;i<20;i++)
  68. for(int j=0;j<(1<<20);j++)
  69. if (!(j>>i&1))
  70. f[j]=min(f[j],f[j^(1<<i)]);
  71. for(int i=1;i<=n;i++)
  72. printf("%d\n",a[i]+2*query(~a[i],i));
  73. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

本文链接:https://www.q234rty.top/2018/03/25/bzoj5092/

隐藏